算法分析与设计(李清勇)课后习题答案

1、5-1凸多边形 最优三角剖分问题/3d5 凸多边形最优三角剖分#include stdafx.h#include using namespace std; const int N = 7;/凸多边形边数+1int weightN = 0,2,2,3,1,4,2,0,1,5,2,3,2,1,0,2,1,4,3,5,2,0,6,2,1,2,1,6,0,1,4,3,4,2,1,0;/凸多边形的权int MinWeightTriangulation(int n,int *t,int *s);void Traceback(int i,int j,int *s);/构造最优解int Weight(int

2、a,int b,int c);/权函数int main()int *s = new int *N; int *t = new int *N; for(int i=0;iN;i+) si = new intN; ti = new intN; cout此多边形的最优三角剖分值为：MinWeightTriangulation(N-1,t,s)endl; cout最优三角剖分结构为：endl; Traceback(1,5,s); /sij记录了Vi-1和Vj构成三角形的第3个顶点的位置return 0;int MinWeightTriangulation(int n,int *t,int *s)for

3、(int i=1; i=n; i+)tii = 0;for(int r=2; r=n; r+) /r为当前计算的链长（子问题规模） for(int i=1; i=n-r+1; i+)/n-r+1为最后一个r链的前边界 int j = i+r-1;/计算前边界为r，链长为r的链的后边界 tij = ti+1j + Weight(i-1,i,j);/将链ij划分为A(i) * ( Ai+1:j )这里实际上就是k=isij = i;for(int k=i+1; kj; k+)/将链ij划分为( Ai:k )* (Ak+1:j) int u = tik + tk+1j + Weight(i-1,k,

4、j);if(utij)tij = u;sij = k;return t1N-2;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout三角剖分顶点：Vi-1,Vj,Vsijendl;int Weight(int a,int b,int c) return weightab + weightbc + weightac;5-4 数字三角形最短路径#include #include #include string.h#define Max 101using namesp

5、ace std;int DMaxMax;int num;int MaxSum(int num) int i, j; for(i = num - 1; i = 1; i -) for(j = 1; j num; for(i = 1; i = num; i +) for(j = 1; j Dij; cout MaxSum(num) endl; return 0;5-2 游艇租赁问题#include using namespace std;#define N 210int costNN;int mN; int main() int n,i,j; while(cinn) for(i=1;in;i+)

6、for(j=i+1;jcostij; m1=0; int min; for(i=2;i=n;i+) min=cost1i; for(j=1;j=i-1;j+) if(costji!=0 & mj+costjimin) min=mj+costji; mi=min; coutmnendl; return 0;5-6 合唱队形问题#include1. usingnamespacestd;2. 3. /用于保存子问题最优解的备忘录4. typedefstruct5. 6. intmaxlen;/当前子问题最优解7. intprev;/构造该子问题所用到的下一级子问题序号(用于跟踪输出最优队列)8. M

7、emo;9. 10. /用于递归输出MemoB中的解11. voidDisplay(int*A,Memo*M,inti)12. 13. if(Mi.prev=-1)14. 15. coutAi;16. return;17. 18. Display(A,M,Mi.prev);19. coutAi;20. 21. 22. /算法主要部分23. voidGetBestQuence(int*A,intn)24. 25. /定义备忘录并作必要的初始化26. Memo*B=newMemon;/Bi代表从A0到Ai满足升序剔除部分元素后能得到的最多元素个数27. Memo*C=newMemon;/Ci代表从

8、Ai到An-1满足降序剔除部分元素后能得到的最多元素个数28. B0.maxlen=1;/由于Bi由前向后构造初始化最前面的子问题(元素本身就是一个满足升序降序的序列)29. Cn-1.maxlen=1;/同样Ci由后向前构造30. for(inti=0;in;i+)/为前一个最优子问题序号给定一个特殊标识-131. /用于在跟踪路径时终止递归或迭代(因为我们并不知道最终队列从哪里开始)32. 33. Bi.prev=-1;34. Ci.prev=-1;35. 36. 37. for(i=1;i=0;j-)/查看前面的子问题找出满足条件的最优解并且记录41. 42. if(Ajmax)43.

9、44. max=Bj.maxlen+1;/跟踪当前最优解45. Bi.prev=j;/跟踪构造路径46. 47. 48. Bi.maxlen=max;/构造最优解49. 50. 51. for(i=n-1;i0;i-)52. 53. intmax=1;54. for(intj=i;jn;j+)/从后往前构造这是为了后面在统筹最终解时可以直接用Bi+Ci-155. /否则我们得到的最优解始终为Bn-1+Cn-156. 57. if(Ajmax)/比当前长度更长记录并构造58. 59. max=Cj.maxlen+1;60. Ci.prev=j;61. 62. 63. Ci.maxlen=max;

10、64. 65. 66. /遍历i得到最大的Bi+Ci-1(-1是因为我们在Bi和Ci中均加上了Ai这个数因此需要减去重复的)67. intmaxQuence=0;/记录当前最优解68. intMostTall;/记录i用于跟踪构造路径69. for(i=0;imaxQuence)72. 73. maxQuence=Bi.maxlen+Ci.maxlen-1;74. MostTall=i;75. 76. 77. 78. cout最大合唱队形长度:maxQuenceendl;79. 80. /B由前向后构造因此prev指向前面的元素需要递归输出81. Display(A,B,MostTall);8

11、2. /C的prev指向后面元素直接迭代输出83. while(CMostTall.prev!=-1)84. 85. MostTall=CMostTall.prev;86. coutAMostTall;87. 88. coutendl;89. 90. deleteB;91. deleteC;92. 93. intmain()94. 95. /测试96. int*A;97. intn;98. cout请输入合唱队员个数:n;100. 101. A=newintn;102. cout输入队员身高:endl;103. for(inti=0;iAi;106. 107. GetBestQuence(A,

12、n);108. deleteA;109. return0;110. 5-7买票问题状态转移方程是 fi := min(fi - 1 + ti, fi - 2 + ri - 1); i = 2 n初值 f0 := 0; f1 := t1;const maxn = 1000; var i, j, n : longint; f, t, r : array0.maxn of longint; function min(a, b : longint) : longint; begin if a fi-1+Ti then 7 fi fi-1+Ti8 return f5-8最大子段和问题 #include

13、#include int max_sum(int n,int *a,int *besti,int *bestj) int *b = (int *)malloc(n * sizeof(int); int sum = 0;int i = -1;int temp = 0; for (i=0;i 0) temp += ai; else temp = ai; bi = temp; sum = b0; for (i=1;i=n-1;i+) if (sum = 0;i-) if (bi = ai) *besti = i; break; free(b); return sum; int main(void)

14、int a = -2,1,-4,13,-5,-2,-10,20,100; int length = sizeof(a)/sizeof(int); int sum = -1; int besti = -1; int bestj = -1; sum = max_sum(length,a,&besti,&bestj); printf(besti = %d,bestj = %d,max_sum=%dn,besti,bestj,sum); return 0;5-9 装箱问题发现就是0-1背包问题 每个物品的体积就是花费同时也是价值， 也就是说这题可以转化为在总体积为w下，可以得到最大的价值 最后用总体积

15、减去最大的价值就是剩下最少的空间 状态转移方程dj = max(dj, dj - ai + ai);第二行为一个整数，表示有n个物品；接下来n行，每行一个整数表示这n个物品的各自体积。 输出格式 一个整数，表示箱子剩余空间。#include #include using namespace std;int n;int d20005;int a35;int main()int w;scanf(%d%d, &w, &n);int i, j;for (i = 0; i n; i+)scanf(%d, &ai);memset(d, 0, sizeof(d);for (i = 0; i = ai; j-

16、)dj = max(dj, dj - ai + ai);printf(%dn, w - dw);return 0;6-10 表格乘法#include stdio.h#define num 50void chengji_1(int (*a)num3,int n,char b);int _tmain( )int anumnum3;char bnum;int i,j,k,n;char c;printf(intput the num of array:);scanf(%d,&n);getchar();for(i=0;in;i+)for(j=0;jn;j+)for(k=0;k3;k+)aijk=0;i=

17、0;while(c=getchar()!=/n)bi=c; i+;chengji_1(a,n,b);printf(reslut is:%d,a0n-10);getchar();void chengji_1(int (*a)num3,int n,char b)int i,j,k,t;for(i=0;in;i+)*(*(*(a+i)+i)+(bi-a)=1;for(k=1;kn;k+)for(i=0;in;i+)j=i+k;for(t=i;tj;t+)*(*(*(a+i)+j)+0)+=(*(*(*(a+i)+t)+0)*(*(*(*(a+t+1)+j)+2)+(*(*(*(a+i)+t)+1)*

18、(*(*(*(a+t+1)+j)+2)+(*(*(*(a+i)+t)+2)*(*(*(*(a+t+1)+j)+0);*(*(*(a+i)+j)+1)+=(*(*(*(a+i)+t)+0)*(*(*(*(a+t+1)+j)+0)+(*(*(*(a+i)+t)+0)*(*(*(*(a+t+1)+j)+1)+(*(*(*(a+i)+t)+1)*(*(*(*(a+t+1)+j)+1);*(*(*(a+i)+j)+2)+=(*(*(*(a+i)+t)+1)*(*(*(*(a+t+1)+j)+0)+(*(*(*(a+i)+t)+2)*(*(*(*(a+t+1)+j)+1)+(*(*(*(a+i)+t)+2

19、)*(*(*(*(a+t+1)+j)+2);11 最长滑雪道问题#include using namespace std;int data102102,longetr102102;int m,n;int cal(int i,int j)int max = 0;if (longetrij 0)/如果该点已经计算过直接返回路径长度，保存已有的计算结果这是动态规划优越之处return longetrij;if(j-1 = 0 & dataij dataij-1 & max cal(i,j-1)max = cal(i,j-1);/向左走if(j+1 dataij+1 & max = 0 & datai

20、j datai-1j & max cal(i-1,j)max = cal(i-1,j);/向上走if(i+1 datai+1j & max mn;int maxway = 0;for ( i=0;im;i+)for( j=0;jdataij;longetrij = 0;for ( i=0;im;i+)for( j=0;jn;j+)longetrij = cal(i,j);for ( i=0;im;i+)for( j=0;jn;j+)if(maxway longetrij)maxway = longetrij;coutmaxwayendl;return 0;方法2#includeiostream

21、#include#include#include#includeusingnamespacestd;structdot/创建一个结构体存储每个点的信息intx;inty;inth;dotline20000;/将每个点存入该结构体数组intheight120120;/用于存储inputintlen120120;/dp数组，存储每个点的最优解intcmp(constvoid*a,constvoid*b)/快速排序的参考函数if(*(dot*)a).h(*(dot*)b).h)return1;elsereturn-1;intmain()intm,n;cinmn;inti,j;intflag=-1;i

22、ntmax=0;for(i=1;i=m;i+)for(j=1;j=n;j+)flag+;scanf(%d,&heightij);lineflag.x=i;lineflag.y=j;lineflag.h=heightij;/这个双层循环用来完成数据收集的工作qsort(line,m*n,sizeof(line0),cmp);/对结构体的h参数进行排序for(i=0;im*n;i+)if(heightlinei.xlinei.y=lenlinei.xlinei.y+1)lenlinei.xlinei.y+1=lenlinei.xlinei.y+1;if(heightlinei.xlinei.y=l

23、enlinei.x+1linei.y)lenlinei.x+1linei.y=lenlinei.xlinei.y+1;if(heightlinei.xlinei.y=lenlinei.xlinei.y-1)lenlinei.xlinei.y-1=lenlinei.xlinei.y+1;if(heightlinei.xlinei.y=lenlinei.x-1linei.y)lenlinei.x-1linei.y=lenlinei.xlinei.y+1;/动态规划过程for(i=1;i=m;i+)for(j=1;jmax)max=lenij;/遍历len数组，求出最大值coutmax+1endl;/因为初始值是0,所以最后要加一return0;最大矩形和bj=maxbj-1+aj,aj, 1 #include 2 using namespace std; 3 4 int * a; 5 int *sum; 6 int max_array(int *a,int n) 7 8 int *c = new int n; 9 int i =0; 10 c0 = a0; 11 for(i=1;in;i+) 12 13 if(ci-10) 14 ci = ai; 15 else 16 ci = ci-1+ai; 17 18 int max_sum = -65536; 19 for(i=0;i