算法分析与设计实验报告

项目序号1项目名称分治法实验成绩小标题找最大值和最小值方法思想 分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得

项目序号 项目名称 1 分治法实验 成 绩 小标题 找最大值和最小值 1、 方法思想 分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题， 递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。 分治法在每一层递归上由三个步骤组成：  (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式 相同的子问题。  (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3) 合并(combine)： 将各子问题的解合并为原问题的解。 2、问题描述 我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分 中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问 题的分治算法。 3、算法描述 ijfmaxfmin REC-MAXMIN(，，，) ij 1if = 2then fmax ←fmin ←A［i］ ij 3if =(-1) AiAj 4then if［］>［］ fmax Ai 5then ←［］  fminAj 6← ［］ fmax Aj else ←［］