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

实验一分治与递归算法.doc:..分金块问题的解决思想和算法设计1问题概述老板有IV个金块,希望最优秀的雇员得到其中最重要的一块,最差的雇员得到其中最轻的一块。假设冇一台比较重量的仪器,如何用最少的比较次数找出最重和最轻的金块?2理解金块问题:以9以内的实例理解问题金块示例问题:??用max标记3求解金块问题的常用算法一蛮力法蛮力法的设计思想:蛮力法,也称穷举法,是一种简单而直接地解决问题的方法,常常直接基于问题的描述,因此,也是最容易应用的方法。但是,用蛮力法设计的算法其时间性能往往是最低的,典型的指数时间算法一般都是通过蛮力搜索而得到的。即从第一块开始査找,査找哪块最重,哪块最轻。a[0]a[l] a[2] a[3]makmin?<max4算法设计:Maxmin(floata[],intn){max=a[l];min=a[l];for(i=2;i<=n;i=i+l){if(max<a[i])max=afilelseif(min>a[i])min=a[i]}Return(max,min)}Stepl将所有金块重量存于数组Step2将第一个金块同时标记为最重和最轻的金块Step3将第一个与后一个进行重量的比较,将更重的标记为max,同时如果现阶段最轻的比后者轻,那么将后者标记为min。Step4依次进行比较,:(1)时间复杂性和空间复杂性。分析该算法可以看出,比较操作max<a[i]和mix<a[i]是执行频次最高的关键语句。因此以这两个语句执行的总次数作为该算法执行所需要的时间。最好情况下,金块由轻到重排列,不需要进行min<a[i]比较,而max<a[i]比较共需进行n-1次,即口H尋到max和min;最坏情况卜,金块由重到轻排列,还需要进行n-1次min<a[i]比较,才能得到最终的min,因此共进行2(n-l)次比较。在平均情况下(概率平均),a[i]将有一半的时间比max大,因此平均比较次数是3(n-l)/2。所以算法时间复杂度为0(h).算法共用了n个存贮空间(a[il占用的空间),所以空间复杂度为S(n).6算法的正确性分析算法的正确性分析包含两方面的含义:1)算法是可终止的。2)算法是有效的。在上述算法中,由于是有限数,所以算法在有限次执行之后必然终止,这是显然的。算法的有效性是指当算法正常终止时,最重、最轻的金块能够被找到(没有遗漏现象)。由于算法是从第一个金块开始逐一寻找,直到和第n个金块比较之后才结束,所以最后得到的必然是最重(max)、最轻(min)☆1)和2),算法是正确的。7实验结果:输入金块的重畳,||234578902456最大的金±夬是:::一种简单的分治法。即当每次将比较大的一个问题一分为二,形成两个较小的问题,再把每个较小问题一分为二,变为更小的两个问题,……,直到得到容易解决的小问题为止,再解决所冇小问题,然后把小问题的解逐层合并,得到原来大问题的解。原问题子问题二子问题五 子问题六典型二分法用二叉树表示:) I )2