实验一分治与递归算法的应用
一、实验目的1．掌握分治算法的基本思想（分治合）、技巧和效率分析方法。2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3．学会利用分治算法解决实际问题。
二实验容金块问题老板有一袋金块（共
块，
是2的幂（
≥2））最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。
三问题分析一般思路：假设袋中有
个金块。可以用函数Max（程序
131）通过
1次比较找到最重的金块。找到最重的金块后，可以从余下的
1个金块中用类似法通过
2次比较找出最轻的金块。这样，比较的总次数为2
3。


c
f


分治法：当
很小时，比如说，
≤2，识别出最重和最轻的金块，一次比较就足够了。当
较大时（
＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若
＞2，则递归地应用分而治之方法程序设计据上述步骤，可以得出程序141的非递归代码。该程序用于寻找到数组w0
1中的最小数和最大数，若
1，则程序返回false，否则返回true。当
≥1时，程序141给Mi
和Max置初值以使wMi
是最小的重量，wMax为最大的重量。首先处理
≤1的情况。若
1且为奇数，第一个重量w0将成为最小值和最大值的候选值，因此将有偶数个重量值w1
1参与for循环。当
是偶数时，首先将两个重量值放在for循环外进行比较，较小和较大的重量值分别置为Mi
和Max，因此也有偶数个重量值w2
1参与for循环。在for循环中，外层if通过比较确定wiwi1中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2相对应，而层的if负责找出较小重量值和较大重量值中的最小值和最大值，这


c
f


个工作对应于3。for循环将每一对重量值中较小值和较大值分别与当前的最小值wMi
和最大值wMax进行比较，根据比较结果来修改Mi
和Max（如果必要）。
源程序i
cludeiostreami
cludestri
ghi
cludealgorithmusi
g
amespacestd0
floatmaxfloatg1floatg2比较找大值

retur
g1g2g1g2
r