《算法实验报告分治法》由会员分享，可在线阅读，更多相关《算法实验报告分治法（6页珍藏版）》请在金锄头文库上搜索。
1、组员：胡昌腾、刘全成、马起.卢东平、马悦问題描述：有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名 第一的雇员将得到袋中最重的金块，排名笫二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的 金块加入袋中，否则第一名屣员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性 的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比 较次数找出最轻和最重的金块算法思想：分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1）把它分成两 个或多个更小的问题；2）分别解决毎个小问题：3）把各小
2、问题的解答组合起来，即可得到原问题的解 笹。小问厲通常与原问題相似，可以递归地使用分而治之策略来解决。问題分析：一般思路:假设袋中有n个金块。可以用函数M a x （程序1-31）通过n-l次比较找到最重的金 块。找到最重的金块后，可以从余下的1个金块中用类似的方法通过n-2次比较找出最轻的金块。这的 比较的总次数为23。分治法:当n很小时，比如说，nW2,识别出最重和最轻的金块，一次比较就足够了。当n校大时 （n2）,第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。 设A中最重和最轻的金块分别为HA与LA,以此类推，B中最重和最轻的金块分别为IIB和LB。
3、第三步， 通过比较HA和HB,可以找到所有金块中最重的：通过比较LA和LB,可以找到所有金块中最轻的。在笫 二步中，若n2,则递归地应用分而治之方法算法实现：截图：M-M-MM-M-M输入5块金块的重量后: 得出的结果为M-M-MM-X-M块金块的重量: 弟輸入氣块金块的重量： 黄输入第2块金块的重量： 賞输入第3块金块的重量： 常输入第4块金块的重量： 备输入第5块金块的重量：量量曰里曰里星 ghE-二fa二二 m -le ipnXVT块块块块块寫8112 3 4 5continue源代码：itinclude using namespace std；int a5 = 10J2,5,9,7；v
4、oid maxmin(int i, int j. int &max, int &min ) int mid；int lmax, lmin,rniax, rmin；if(i=j)max=ai；min=aj；else if(i=j-l)if (airmax) maxlmax；elsemaxrmax；if (lm in nnin)min=rmin；elsemin=lmin；void main()/给数组賦值int *p=a；cout” * end1:cout，T*算法分析与设计一分治法*endl；-一金块问题COUtJ杯组员：胡昌腾刘全成马起卢东平马悦cout,T*班级：09级2班cou t * ,
5、Tend 1 ；coutendl；coutendl；coutendl；cout请输入5块金块的重量：endl；for(int n=0；n：rendl； cin*(p+n)；for(int m=0；m0时，比较的总次数为3n/2ti-2次。关键步骤：程序14-1找出最小值和最大值的非递归程序templatebool MinMax(T w. int n, T& Mint T& Max)/寻找w 0 ： n - 1 中的最小和最大值/如果少于一个元素，则返回false/特殊情形：n = 1if (n wl) Min = 1:Max = 0；else (Min = 0；Max = 1；s = 2；/比较余下的数对for (int i = s； i wi+l) i f (wi wMax) Max = i:if (wi+l wMax) Max = i + 1；if (wi wMin) Min = i；returntrue；
