搜索
金砖问题研究探讨组员：胡昌腾、刘全成、马起、卢东平、马悦问题描述：有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块算法思想：分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。问题分析:一般思路：假设袋中有n个金块。可以用函数Max（程序1-31）通过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，则递归地应用分而治之方法算法实现：截图：输入5块金块的重量后：得出的结果为源代码：#includeiostreamusingnamespacestd;inta[5]={10,12,5,9,7};voidmaxmin(inti,intj,int&max,int&min){intmid;intlmax,lmin,rmax,rmin;if(i==j){max=a[i];min=a[j];}elseif(i==j-1)if(a[i]a[j]){max=a[j];min=a[i];}else{max=a[i];min=a[j];}else{mid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmaxrmax)max=lmax;elsemax=rmax;if(lminrmin)min=rmin;elsemin=lmin;}}voidmain(){//给数组赋值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(intn=0;n5;n++){cout请输入第n+1块金块的重量:endl;cin*(p+n);}for(intm=0;m5;m++){cout第m+1块金块的重量:a[m]endl;}intmax,min;maxmin(0,4,max,min);cout重量最大为maxendl;cout重量最小为minendl;}复杂性分析注意到当n为偶数时，在for循环外部将执行一次比较而在for循环内部执行3(n/2-1)次比较，比较的总次数为3n/2-2。当n为奇数时，for循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n为奇数或偶数，当n0时，比较的总次数为「3n/2ù-2次。关键步骤：程序14-1找出最小值和最大值的非递归程序templateclassTboolMinMax(Tw[],intn,T&Min,T&Max){//寻找w[0:n-1]中的最小和最大值//如果少于一个元素，则返回false//特殊情形：n=1if(n1)returnfalse;if(n==1){Min=Max=0;returntrue;}//对Min和Max进行初始化ints;//循环起点if(n%2){//n为奇数Min=Max=0;s=1;}else{//n为偶数，比较第一对if(w[0]w[1]){Min=1;Max=0;}else{Min=0;Max=1;}s=2;}//比较余下的数对for(inti=s;in;i+=2){//寻找w[i]和w[i+1]中的较大者//然后将较大者与w[Max]进行比较//将较小者与w[Min]进行比较if(w[i]w[i+1]){if(w[i]w[Max])Max=i;if(w[i+1]w[Min])Min=i+1;}else{if(w[i+1]w[Max])Max=i+1;if(w[i]w[Min])Min=i;}}returntrue;}