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

计科 111 201100814127 王天柱分金块问题的解决思想和算法设计 1问题概述老板有 n个金块,希望最优秀的雇员得到其中最重要的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,如何用最少的比较次数找出最重和最轻的金块? 2理解金块问题:以 9以内的实例理解问题金块示例问题: ?用 max 标记 ?用 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(max<a[i]) max=a[i] else if(min>a[i]) min=a[i] 计科 111 201100814127 王天柱} Return(max, min) }S tep1 将所有金块重量存于数组 S tep2 将第一个金块同时标记为最重和最轻的金块 S tep3 将第一个与后一个进行重量的比较,将更重的标记为 max ,同时如果现阶段最轻的比后者轻,那么将后者标记为 min 。 S tep4 依次进行比较,最重得到最重的和最轻的 max min. 5算法分析: (1) 时间复杂性和空间复杂性。分析该算法可以看出,比较操作 max<a[i] 和 mix<a[i] 是执行频次最高的关键语句。因此以这两个语句执行的总次数作为该算法执行所需要的时间。最好情况下, 金块由轻到重排列, 不需要进行 min<a[i] 比较,而 max<a[i] 比较共需进行 n-1 次, 即可得到 ma x和 min; 最坏情况下,金块由重到轻排列,还需要进行 n-1次 min<a[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典型二分法思想:一种简单的分治法。即当每次将比较大的一个问题一分为二, 形成两个较小的问题,再把每个较小问题一分为二,变为更小的两个问题,……, 直到得到容易解决的小问题为止,再解决所有小问题,然后把小问题的解逐层合并,得到