《算法分析与设计实验报告》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、1项目序号 1 项目名称 分治法实验小标题 找最大值和最小值成绩1、 方法思想分治法是把规模大的问题，分割成 n 个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。分治法在每一层递归上由三个步骤组成： (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3) 合并(combine)： 将各子问题的解合并为原问题的解。 2、问题描述我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出
2、最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。3、算法描述REC-MAXMIN( i， j， fmax， fmin)1 if i=j2 then fmax fmin Ai3 if i=(j-1)4 then if A i A j5 then fmax A i 6 fmin A jelse fmax A j8 fmin A i9 else mid ( i+j)/210 REC-MAXMIN(i， mid， gmax， gmin)11 REC-MAXMIN(mid+1， j， hmax， hmin)12 fmax max gmax， hmax13 fmin min
3、 gmin， hmin 4、程序清单#includevoid FZFa(int i,int j,int &max,int &min,int a)2if(i= =j)max=ai;min=aj;else if(i= =(j-1)if(aiaj)max=ai;min=aj;elsemax=aj;min=ai;elseint midd=(i+j)/2;int max1=0,min1=0,max2=0,min2=0;FZFa(i,midd,max1,min1,a);FZFa(midd+1,j,max2,min2,a);if(max1max2)max=max1;elsemax=max2;if(min1i
4、nt lcsleng(char x,char y,int a1010,int n,int m)int c1010;int i,j;for(i=1;i=cij-1)cij=ci-1j;aij=2;else5cij=cij-1;aij=3;return cnm;void lcs(int i,int j,char x,int a1010)if(i=0|j=0)return;if(aij=1)lcs(i-1,j-1,x,a);coutint recuractivityselect(int s,int f,int i,int j)int m=i+1,k=0;while(m=fi)kt=m;t+;w+;i
5、=m;return w;int main()int a=0,1,2,3,4,5,6,7,8,9,10,11;int p=0,1,2,0,5,3,5,6,8,8,2,12;int q=0,4,5,6,7,8,9,10,11,12,13,14;int t12=0;int i,f;cout0 do 4 x k x k+1 9/到下一列5 while x k n & not PLACE(k) do6 x k x k+17 if xk n /找到一个位置8 then if k=n /测试是否为问题的解9 then output( X) /输出解10 else k k+1 /转下一行，即给下一个皇后找位置
6、11 x k 0 /初始化当前皇后列取值12 else k k-1 /回溯13 return PLACE(k)1 i 12 while i#includebool place(int k,int x)int j;for(j=1;j0)xk+=1;while(xk=n)&(!place(k,x)xk+=1;if(xk=n)if(k=n)for(int i=1;i=n;i+)for(int j=1;j=n;j+)if(j=xi)cout;elsecout;coutendl;coutendl;sum+;elsek+;xk=0;else k-;int main()int n=4,m,i,sum=0;int x5;for(i=0;i=n;i+)xi=0;backtrack(x,sum,n);coutsumendl;return 0;5、实验结果11
