算法复习2.doc

主要程序分治法1、分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试计算的所有不同排列。（13分）解：解答如下： Templatevoid Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; .（4分） coutendl;else for(int i=k;i=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi); .（8分） ; 其中ok用于判别重复元素。 Template int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1;.（13分）动态规划1求解矩阵链乘问题的动态规划算法矩阵链乘问题：给出n个矩阵M1, M2, , Mn , Mi 为riri+1阶矩阵，i=1, 2, , n，求计算M1M2Mn所需的最少数量乘法次数。解：记 Mi, j=MiMi+1Mj , i=j。设Ci, j, 1=i=j=n, 表示计算Mi, j的所需的最少数量乘法次数，则 算法 MATCHAIN输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。for i=1 to n Ci, i= 0 for d=1 to n-1 for i=1 to n-d j= i+d Ci, j= for k=i+1 to j x= Cik-1+Ckj+ri*rk*rj+1 ; if xCi, j then Cij =x end if end for end for end for return C1n end MATCHAIN2.最长公共子序列问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 解：由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：在程序中，bij记录Cij的值是由哪一个子问题的解得到的。（1） 请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将bij的取值与（1）中您填写的取值对应，否则视为错误）。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);3.动态规划算法实现0-1闭包问题。（15分）解： Templatevoid Knapsack(Type v,int w,int c,int n,Type *m) Int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=mi+1j; for(int j=wi;j=w1) m1c=max(m1c,m2c-w1+v1); .（10分）TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in) output(x); else for (int i=t;i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; 3、回溯法求解马的周游问题的算法解：马的周游问题：给出一个nxn棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0, y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）算法 HORSETRAVEL 输入：正整数n，马的起点位置(x0, y0)，1=x0, y0=1 and not flag while ki8 and not flag ki= ki+1 x1= x+dxki; y1= y+dyki if (x1,y1)无越界and tagx1, y1=0) or (x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tagx, y= 1 if i=m then flag=true elsei= i+1 ki=0 end if end if end whilei=i-1 x=x-dxki; y=y-dyki end while if flag then outputroute(k) /输出路径 else output “no solution”end HORSETRAVEL4、n后问题回溯算法解：用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0。分别用一维数组MN、L2*N-1、R2*N-1表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;jmaxdep) break; init();.（6分）if(found) output(); else cout”No Solution!”k) return false; for(int i=0;i2;i+) int n1=f(n,i);tdep=i; .（12分） if(n1= =m|search(dep+1,n1) Found=true; Out(); return true; return false; .（18分）6、回溯法解0/1背包问题，计算结点的上界的函数如下所示，请在空格中填入合适的内容：Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) （b += pi/wi * cleft）; return b;7、写出图着色问题的回溯算法的判断Xk是否合理的过程。解：i0while ik do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true?回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn）。Bool Color:OK(int k)/ for(int j=1;jdu+w(u,v)then dv=du+wu,v; pv=u dijkstra(G,w,s)1. Init-single-source(G,s) 2. S= 3. Q=VG4.while Q do u=min(Q) S=Su for each vertex vadju do Relax(u,v,w) 2、试用贪心算法求解下列