算法分析与设计实验报告.doc

项目序号1项目名称分治法实验成绩小标题找最大值和最小值1、 方法思想 分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。分治法在每一层递归上由三个步骤组成： (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3) 合并(combine)： 将各子问题的解合并为原问题的解。 2、问题描述 我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。 3、算法描述REC-MAXMIN(i，j，fmax，fmin)1 if i=j2 then fmax fmin Ai3 if i=(j-1)4 then if AiAj5 then fmax Ai 6 fmin Aj else fmax Aj8 fmin Ai9 else mid (i+j)/210 REC-MAXMIN(i，mid，gmax，gmin)11 REC-MAXMIN(mid+1， j， hmax，hmin)12 fmax maxgmax，hmax13 fmin mingmin，hmin 4、程序清单 #includevoid FZFa(int i,int j,int &max,int &min,int a)if(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(min1min2)min=min1;elsemin=min2;int main()int t=2,4;int max,min;FZFa(0,1,max,min,t);cout最大值：maxendl; cout最小值：minendl;return 0;5、实验结果（可用文字描述和贴图等方式表现实验结果）项目序号2项目名称动态规划法实验成绩小标题最长公共子序列1、方法思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而再需要时再找出已求的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不过孩子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。2、问题描述 最长公共子序列为题：给定两个序列X=x1,x2,x3xm和Y=y1,y2,y3yn,找出X和Y的最长公共子序列。3、算法描述LCSLENGTH(X, Y)1 m lengthX2 n lengthY3 for i 1 to m4 do li, 0 05 for j 1 to n6 do l0, j 07 for i 1 to m8 do for j 1 to n9 do if xi=yj10 then li, j li-1, j-1+1 bi, j112 else if li-1, j li, j-113 then li, j li-1, j14 bi, j2 15 else li, j li, j-116 bi, j317 return l andb 4、程序清单#includeint lcsleng(char x,char y,int a1010,int n,int m)int c1010;int i,j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i;for(i=1;i=n;i+)for(j=1;j=cij-1)cij=ci-1j;aij=2;elsecij=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); coutxiendl;else if(aij=2)lcs(i-1,j,x,a);elselcs(i,j-1,x,a);int main()char a= kagajsj;char b= asjofgo;int t1010; int c=lcsleng(a,b,t,7,7);coutcendl; lcs(7,7,a,t);return 0;5、实验结果项目序号3项目名称贪心法成绩小标题活动选择问题1、方法思想 贪心算法总是做出再当前看来最好的选择，也就是说贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上看的局部最优选择。2、问题描述活动选择问题(activity-selection problem)即若干个具有竞争性的活动要求互斥使用某一公共资源，目标是选择最大的相容活动集合。 假定集合S=a1, a2, , an中含有n个希望使用某一资源的活动，这样的资源有教室、某一设备等，它们一次只能由一个活动使用。每个活动ai有开始时间(start time)si和完成时间(finish time)fi，其中，0sifi。如果某个活动ai被选中使用资源，则该活动在半开区间(si，fi这段时间占据资源。如果活动ai和aj在时间区间(si，fi 和(sj，fj上不重叠，则称它们是相容的(compatible)，即如果si fj或者sj fj ，活动ai和aj是相容的。 活动选择问题是选择最大的相容活动集合。 3、算法描述 RECUR-ACTIVITY-SELECT(s, f, i, j)1 m i+12 while mj and smfi /找Sij中第一个活动3 do m m+14 if mj /找到满足条件的活动m5 then return amRECUR-ACTIVITY-SELECT(s,f, m, j)/将m加入集合6 else return 4、程序清单#includeint recuractivityselect(int s,int f,int i,int j)int m=i+1,k=0;while(mj&smfi)m=m+1;if(mj)coutm ;k=1+recuractivityselect(s,f,m,j);return k;int budigui(int s,int f,int k,int n)k1=1;int i=1,m,t=2,w=1;for(m=2;m=fi)kt=m;t+;w+; i=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;cout 活动名称 ;for(i=0;i11;i+)coutai ;coutendl;cout 活动开始时间; for(i=0;i11;i+)coutpi ;coutendl; cout 活动结束时间;for(i=0;i11;i+)coutqi ;coutendl;cout最大相容活动序列是: ; f=recuractivityselect(p,q,0,12);coutendl;cout安排活动个数:fendl;coutendl; f=budigui(p,q,t,12);coutfendl;/*for(i=0;i12;i+)coutti0 do 4 xk xk+1 /到下一列5 while xk n & not PLACE(k) do6 xk xk+17 if xk n /找到一个位置8 then if k=n /测试是否为问题的解9 then output(X) /输出解10 else k k+1 /转下一行，即给下一个皇后找位置11 xk 0 /初始化当前皇后列取值12 else k k-1 /回溯13 return PLACE(k)1 i 12 while ik do 3 if (xi=xk or abs (xi-xk)=abs (i-k) /同一列或同一对角线有两个皇后4 then return (false)5 i i+16 return (true) 4、程序清单#include#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