实验一分治与递归算法

《实验一分治与递归算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分金块问题的解决思想和算法设计1问题概述老板有IV个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。假设冇一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？2理解金块问题：以9以内的实例理解问题金块示例问题：1.最重的是那块？用max标记2.最轻的是那块？用max标记3求解金块问题的常用算法一蛮力法蛮力法的设计思想：蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法

2、一般都是通过蛮力搜索而得到的。即从第一块开始査找，査找哪块最重，哪块最轻。a[0]a[l]a[2]a[3]makmin?a[i])min=a[i]}Return（max，min）}Stepl将所有金块重量存于数组Step2将第一个金块同时标记为最重和最轻的金块Step3将第一个与后一个进行重量的比较，将更重的标记为max，同

3、时如果现阶段最轻的比后者轻，那么将后者标记为min。Step4依次进行比较，最重得到最重的和最轻的maxmin.5算法分析：（1）时间复杂性和空间复杂性。分析该算法可以看出，比较操作max

4、2（n-l）次比较。在平均情况下（概率平均），a[i]将有一半的时间比max大，因此平均比较次数是3（n-l）/2。所以算法时间复杂度为0（h）.算法共用了n个存贮空间（a[il占用的空间），所以空间复杂度为S（n）.6算法的正确性分析算法的正确性分析包含两方面的含义：1）算法是可终止的。2）算法是有效的。在上述算法中，由于是有限数，所以算法在有限次执行之后必然终止，这是显然的。算法的有效性是指当算法正常终止时，最重、最轻的金块能够被找到（没有遗漏现象）。由于算法是从第一个金块开始逐一寻找，直到和第n个金块比较之后才结束，

5、所以最后得到的必然是最重（max）、最轻（min）的金块.综☆1）和2），算法是正确的。7实验结果：输入金块的重畳，

6、

7、234578902456最大的金±夬是：9.000000最小的金快是：0.000000Pvessanvkevtocontinue算法思想二用分治法解决金块问题1典型二分法思想：一种简单的分治法。即当每次将比较大的一个问题一分为二,形成两个较小的问题，再把每个较小问题一分为二，变为更小的两个问题，……，直到得到容易解决的小问题为止，再解决所冇小问题，然后把小问题的解逐层合并，得到原来大问题的解。原问题子问题

8、二子问题五子问题六典型二分法用二叉树表示:)I)2用二分法如何解决金块问题？从两个简单实例谈起：（1）假设只有一个金块，重10克，则不需要比较轻重，最重者和最轻者是同一个金块。即比较0次。（2）假设有2个金块，一个重10克，另一个重16克，则需要比较1次，可以把最重者和最轻者确定丁来。（3）当有多个金块时（假设6块），则用二分法对其分解，直到分解为（1）或（2）的情形时，问题很容易解决。假设6个金块重量如下（以找最轻金块为例）：264381一分为二(两组)：[264][381]一分为二(四组)：[26][4][38][1]

9、解较小子问题：[2][4][3][1]合并子问题解：[21rnlminrmin3用二分法解决金块问题算法设计：问题抽象、简化为：在n个元素的集合中寻找最大和最小值元素。(iMf集合一分为二，变为两个集合，目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合，直到每个集合屮的元素个数<2,然后找出小集合的最大、最小元素。(3)合并(回溯)：自低向上把子问题的解合并，大元素中取最大者，小元素中取最小者，最后得到元问题的解。4用二分法解决金块问题算法描述：voidMaxAndMin(inti，intj，float

10、array口，float&max,float&min){intmid;//取得金块中间值，便于下次分组float16代013乂，16矜111111，1^111013?<,1^1^111111;//存储分组后的最值if(i==j){max=an*ay[il;min=array[i];}elseif(