实验一 分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块（共n 块，n 是2 的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三. 问题分析: 一般思路：假设袋中有n 个金块。可以用函数 M a x（程序1 - 3 1）通过 n-1 次比 较找到最 重的金块。找到最重的金块后，可以从余下的n-1 个金块中用类似法通过 n-2 次比较找出最轻的金块。这样，比较的总次数为 2n-3。 分治法：当n 很小时，比如说， n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋 A 和 B。第二步，分别找出在 A 和 B 中最重和最轻的金块。设 A 中最重和最轻的金块分别为 HA 与 LA，以此类推，B 中最重和最轻的金块分别为 HB 和 LB。第三步，通过比较HA 和 HB，可以找到所有金块中最重的；通过比较 LA 和 LB，可以找到所有金块中最轻的。在第二步中，若 n＞2，则递归地应 用分而治之方法 程序设计 据上述步骤，可以得出程序 1 4 - 1 的非递归代码。该程序用于寻找到数组 w [ 0 : n - 1 ]中的最小数和最大数，若 n < 1，则程序返回 f a l s e，否则返回 t r u e。 当n≥1 时，程序 1 4 - 1 给 M i n 和 M a x置初值以使 w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理 n≤1 的情况。若 n>1 且为奇数，第一个重量 w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值 w [ 1 : n - 1 ]参与f o r 循环。当n 是偶数时，首先将两个重量值放在 for 循环外进行比较，较小和较大的重量值分别置为 Min 和 Max，因此也有偶数个重量值 w[2:n-1]参与 for 循环。 在 for 循环中，外层 if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的 2) 相对应，而内层的 i f 负责找出较小重量值和较大重量值中的最小值和最大值，这个工作对应于3 )。for 循环将每一对重量值...
