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

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中最重和最轻的金块分别为

3、HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n2，则递归地应用分而治之方法算法实现：截图：输入5块金块的重量后：得出的结果为源代码：#include <iostream>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

4、=aj;else if(i=j-1)if(ai<aj)max=aj; min=ai;else max=ai; min=aj;elsemid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmax>rmax)max=lmax;elsemax=rmax;if(lmin>rmin)min=rmin;elsemin=lmin;void main()/给数组赋值int *p=a;cout<<"*"<<endl;cout<<"*算法分析与设计-分治

5、法 *"<<endl;cout<<"* -金块问题 *"<<endl;cout<<"*组员: 胡昌腾 刘全成 *"<<endl;cout<<"* 马起 卢东平 马悦 *"<<endl; cout<<"* 班级：09级2班 *"<<endl; cout<<"*"<<endl;cout<<endl;cout<<endl;cout<

6、<endl;cout<<" 请输入5块金块的重量："<<endl;for(int n=0;n<5;n+)cout<<"请输入第"<<n+1<<"块金块的重量:"<<endl;cin>>*(p+n);for(int m=0;m<5;m+)cout<<"第"<<m+1<<"块金块的重量:"<<am<<endl;int max,min;max

7、min(0,4,max,min);cout<<"重量最大为"<<max<<endl;cout<<"重量最小为"<<min<<endl;复杂性分析注意到当n为偶数时，在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 )次比较，比较的总次数为3 n / 2 - 2。当n 为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数，当n>0时，比较的总次数为3n/2ù-2次。  关键步

8、骤：程序14-1 找出最小值和最大值的非递归程序  template<class T> bool MinMax(T w, int n, T& Min, T& Max) / 寻找w 0 : n - 1 中的最小和最大值 / 如果少于一个元素，则返回f a l s e / 特殊情形： n <= 1 if (n < 1) return false; if (n = 1) Min = Max = 0; return true; / /对Min 和M a x进行初始化 int s; / 循环起点 if (n % 2) / n 为奇数 Min = Max = 0; s = 1; else / n为偶数，比较第一对 if (w0 > w1) Min = 1; Max = 0; else Min = 0; Max = 1; s = 2; / 比较余下的数对 for (int i = s; i < n; i += 2) / 寻找wi 和w i + 1 中的较大者 / 然后将较大者与w M a x 进行比较 / 将较小者与w M i n 进行比较 if (wi > wi+1) if (wi &