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

Forpersonaluseonlyinstudyandresearch;mercialuse芀实验一分治与递归算法的应用芁薆一、(分-治-合)、技巧和效率分析方法。(基准与递归方程)。。羇二、问题描述螅金块问题肂老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。蒁3、问题分析莈一般思路:假设袋中有n个金块。可以用函数Max,通过n-1次比较找到最重的金块。找到最重的金块后,可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样,比较的总次数为2n-3。芃分治法:袁如果集合中只有1个元素,则它既是最大值也是最小值;薀如果有2个元素,则一次maxnum(i,j)一次minnum(i,j)就可以得到最大值和最小值;衿如果把集合分成两个子集合,递归的应用这个算法分别求出两个子集合的最大值和最小值,最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值;让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。羅程序设计袄对金块问题的程序设计如下:蚀核心算法分析羆doubleSearch_Max(doubleg[],intleft,intright)与doubleSearch_Min(doubleg[],intleft,intright)函数分别是求最大重量与最小重量金块的被调用函数,函数体中蚇当left==right时,只有一个重量,最小和最大重量相等,分别直接返回返回g[left],g[right]。蚃当right-left==1时,有两个重量,分别调用一次min(g1,g2)和max(g1,g2)函数就可得出最小与最大重量,分别返回。螀当right-left>1时,mid=(left+right)/2取中点,将数据群分为两半,分别递归调用,最后将得到的两个数据群的最值运用min()或max()函数得到最小最大重量。莇函数调用及主函数设计膅Intmain()中,首先输入要输入的数据个数n,运用for循环将数据输入到gold[0~n]数组中,然后分别调用Search_Max(gold,0,n-1)和Search_Min(gold,0,n-1)函数输出最小最大重量;莂doubleSearch_Max(doubleg[],intleft,intright)与doubleSearch_Min(doubleg[],intleft,intright)函数中,分别调用min(g1,g2)和max(g1,g2)函数实现查找最小最大值功能。袀主要算法流程图螈袇输入n膁袀For循环输入g[0~n]腿芄膃羀芅Main()函数分别调用用羆羂肀Search_Min(gold,0,n-1)蚆Search_Max(gold,0,n-1)蒄螁膀调用肇调用膆螄doublemin(g1,g2)艿蒈doublemax(g1,g2),知道了分治法的思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。对它的运用模型更加熟悉,相信以后会更加熟练的运用它。节附录源程序:葿#include<iostream>肆#include<>螄#include<algorithm>肁usingnamespacestd;葿doublemax(doubleg1,doubleg2)//比较找大值蒇{薅 return(g1>g2?g1:g2);肄}蕿doublemin(doubleg1,doubleg2)//比较找小值袈{羃 return(g1<g2?g1:g2);袂}虿doubleSearch_Max(doubleg[],intleft,intright)//用二分法递归找最大值芈{蚅 if(left==right) //当只有一个数时,直接返回该值蚁 {蝿 doublemax;虿 max=g[right];膃 returnmax;蚄 }衿 if(right-left==1)螆 {袅doubleLM,RM;蒃 LM=g[left];羈RM=g[right];***return(max(LM,RM));薇 }节 if(right-left>1)肈 {薈doubleLM,RM;肅 intmid=(left+right)/2;//取中点羁 LM=Search_Max(g,left,mid);肈 RM=Search_Max(g,mid,right);//左半部分,右半部分的最大