分治与递归上机

《分治与递归上机》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告实验1分治与递归上机[实验目的]1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法；2．熟练掌握利用递归设计分治算法的基本步骤；3．学会利用分治算法解决实际问题。[实验要求]按以下实验内容完成题目，并把编译、运行过程中出现的问题以及解决方法填入实验报告中，按时上交。[实验学时]2学时。[实验内容]一、实验内容金块问题。老板有一袋金块（共n块，n是2的幂（n≥2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。请对自己实现的程序进行复杂性分析。二、算法描述（1

2、）划分：将数组分割成两半（2）治理：在每一半中找到最大值和最小值。（3）合并：返回两个最大值中的最大值和两个最小值中的最小值。Minmax(intlow,inthigh){iflow==highreturn(A[low],A[high])//只有一个元素elseifhigh-low=1then//如果只有两个元素直接解决ifA[low]

3、=minmax(low,mid);//求左半区间的最大最小值(x2,y2)=minmax(mid+1,high);//右半区间的最大最小值x=min{x1,x2};y=max(y1,y2);//求整体最大最小值return(x,y);endif}三、源程序#include#defineMaxsize1000voidMinmax(intA[],intlow,inthigh,int*min,int*max);voidmain(){intn;intmin,max;intGold[Maxsize];printf("pleaseinputn:");scanf("%d",

4、&n);printf("pleaseinputweightofgold:");for(inti=1;i<=n;i++){scanf("%d",&Gold[i]);}Minmax(Gold,1,n,&min,&max);《算法设计与分析》实验报告printf("Min:%d",min);printf("Max:%d",max);}voidMinmax(intA[],intlow,inthigh,int*min,int*max){intmid,x1,x2,y1,y2;if(low==high){*min=*max=A[low];}if(high-low==1){if(A

5、[low]x2)*min=x2;else*min=x1;if(y1>y2)*max=y1;else*max=y2;}}四、程序的复杂度分析T(n)=1(n=2)T(n)=2T(n/2)+2(n>=2)得T

6、(n)=n/2+n-2O(n)=n