分治与递归上机.doc

实验1分治与递归上机 [实验目的] 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法； 2．熟练掌握利用递归设计分治算法的基本步骤； 3．学会利用分治算法解决实际问题。 [实验要求] 按以下实验内容完成题目，并把编译、运行过程中出现的问题以及解决方法填入实验报告中，按时上交。 [实验学时] 2学时。 [实验内容] 一、实验内容 金块问题。老板有一袋金块（共n块，n是2的幂（n≥2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。请对自己实现的程序进行复杂性分析。 二、算法描述 （1）划分：将数组分割成两半 （2）治理：在每一半中找到最大值和最小值。 （3）合并：返回两个最大值中的最大值和两个最小值中的最小值。 Minmax(int low,int high) { if low==high return(A[low],A[high]) //只有一个元素 else if high-low=1 then //如果只有两个元素直接解决 if A[low]A[high] then return(A[low],A[high]) else return(A[high],A[low]) end if else //否则递归解决 mid=(low+high)/2 ; //将区间一分为二 (x1,y1)=minmax(low,mid); //求左半区间的最大最小值 (x2,y2)=minmax(mid+1,high); //右半区间的最大最小值 x=min{x1,x2}; y=max(y1,y2); //求整体最大最小值 return(x,y); endif } 三、源程序 #includestdio.h #define Maxsize 1000 void Minmax(int A[],int low,int high,int *min,int *max); void main() { int n; int min,max; int Gold[Maxsize]; printf(please input n: ); scanf(%d,n); printf(please input weight of gold: ); for(int i=1;i=n;i++) { scanf(%d,Gold[i]); } Minmax(Gold,1,n,min,max); printf(\nMin: %d,min); printf(\nMax: %d\n,max); } void Minmax(int A[],int low,int high,int *min,int *max) { int mid,x1,x2,y1,y2; if (low==high) { *min=*max=A[low]; } if (high-low==1) { if (A[low]A[high]) { *min=A[low]; *max=A[high]; } else { *min=A[high]; *max=A[low]; } } if (low!=high((high-low)!=1)) { mid=(low+high)/2; Minmax(A,low,mid,x1,y1); Minmax(A,mid+1,high,x2,y2); if (x1x2) *min=x2; else *min=x1; if (y1y2) *max=y1; else *max=y2; } } 四、程序的复杂度分析 T(n)=1 (n=2) T(n)=2T(n/2)+2 (n=2) 得 T(n)=n/2+n-2 O(n)=n 《算法设计与分析》实验报告