算法实验报告----分治法

1、金砖问题研究探讨组员：胡昌腾、刘全成、马起、卢东平、马悦问题描述：有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块算法思想：分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问

2、题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。问题分析:一般思路：假设袋中有n 个金块。可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这的比较的总次数为2n-3。分治法：当n很小时，比如说， n2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻

3、的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n2，则递归地应用分而治之方法算法实现：截图：输入5块金块的重量后：得出的结果为源代码：#include using namespace std;int a5=10,12,5,9,7;void maxmin(int i,int j, int &max,int &min )int mid;int lmax,lmin,rmax,rmin;if(i=j)max=ai;min=aj;else if(i=j-1)if(airmax)max=lmax;elsema

4、x=rmax;if(lminrmin)min=rmin;elsemin=lmin;void main()/给数组赋值int *p=a;cout*endl;cout*算法分析与设计-分治法 *endl;cout* -金块问题 *endl;cout*组员: 胡昌腾 刘全成 *endl;cout* 马起 卢东平 马悦 *endl; cout* 班级：09级2班 *endl; cout*endl;coutendl;coutendl;coutendl;cout 请输入5块金块的重量：endl;for(int n=0;n5;n+)cout请输入第n+1块金块的重量:*(p+n);for(int m=0;m

5、5;m+)cout第m+1块金块的重量:amendl;int max,min;maxmin(0,4,max,min);cout重量最大为maxendl;cout重量最小为min0时，比较的总次数为3n/2-2次。 关键步骤：程序14-1 找出最小值和最大值的非递归程序 template bool MinMax(T w, int n, T& Min, T& Max) / 寻找w 0 : n - 1 中的最小和最大值 / 如果少于一个元素，则返回f a l s e / 特殊情形： n = 1 if (n w1) Min = 1; Max = 0; else Min = 0; Max = 1; s = 2; / 比较余下的数对 for (int i = s; i wi+1) if (