实验一分治与递归算法.doc

计科111 201100814127 王天柱 第  PAGE 8 页 共  NUMPAGES 8 页 分金块问题的解决思想和算法设计 1 问题概述 老板有n个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？ 2 理解金块问题：以9以内的实例理解问题 金块示例 问题：1.最重的是那块？用max标记 2.最轻的是那块？用max标记 3 求解金块问题的常用算法一蛮力法 蛮力法的设计思想：蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。即从第一块开始查找，查找哪块最重，哪块最轻。 a[0] a[1] a[2] a[3] max min ? max 4算法设计： Maxmin(float a[],int n) {max=a[1];min=a[1]; for(i=2;i=n;i=i+1) {if(maxa[i]) max=a[i] else if(mina[i]) min=a[i] } Return(max, min) } Step1 将所有金块重量存于数组 Step2 将第一个金块同时标记为最重和最轻的金块 Step3 将第一个与后一个进行重量的比较，将更重的标记为max，同时如果现阶段最轻的比后者轻，那么将后者标记为min。 Step4 依次进行比较，最重得到最重的和最轻的max min. 5算法分析：(1)时间复杂性和空间复杂性。 分析该算法可以看出，比较操作 maxa[i]和mixa[i]是执行频次最高的关键语句。因此以这两个语句执行的总次数作为该算法执行所需要的时间。最好情况下，金块由轻到重排列，不需要进行mina[i]比较，而 maxa[i]比较共需进行n-1次,即可得到max和min; 最坏情况下，金块由重到轻排列，还需要进行n-1次mina[i]比较，才能得到最终的min，因此共进行2(n-1)次比较。在平均情况下(概率平均)，a[i]将有一半的时间比max大，因此平均比较次数是3(n-1)/2。所以算法时间复杂度为O(n). 算法共用了n个存贮空间(a[i]占用的空间），所以空间复杂度为S(n). 6算法的正确性分析 算法的正确性分析包含两方面的含义：1）算法是可终止的。2）算法是有效的。 在上述算法中，由于n是有限数，所以算法在有限次执行之后必然终止，这是显然的。 算法的有效性是指当算法正常终止时，最重、最轻的金块能够被找到(没有遗漏现象)。由于算法是从第一个金块开始逐一寻找，直到和第n个金块比较之后才结束，所以最后得到的必然是最重(max)、最轻(min)的金块.综合1）和2），算法是正确的。 7实验结果： 算法思想二 用分治法解决金块问题 1典型二分法思想：一种简单的分治法。即当每次将比较大的一个问题一分为二，形成两个较小的问题，再把每个较小问题一分为二，变为更小的两个问题，……,直到得到容易解决的小问题为止，再解决所有小问题，然后把小问题的解逐层合并，得到原来大问题的解。 原问题 子问题二 子问题一 子问题三 子问题四 子问题五 子问题六 典型二分法用二叉树表示： 2 用二分法如何解决金块问题？ 从两个简单实例谈起： 假设只有一个金块，重10克，则不需要比较轻重,最重者和最轻者是同一个金块。即比较0次。 (2) 假设有2个金块，一个重10克，另一个重16克，则 需要比较1次，可以把最重者和最轻者确定下来。 (3) 当有多个金块时（假设6块），则用二分法对其分 解，直到分解为（1）或（2）的情形时，问题很 容易解决。 假设6个金块重量如下(以找最轻金块为例)： 2 6 4 3 8 1 一分为二（两组）： [2 6 4] [3 8 1] 一分为二（四组）： [2 6] [4] [3 8][1] 解较小子问题： [2] [4] [ 3] [1] 合并子问题解： [2] [1] lmin rmin ? 3用二分