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

《算法分析与设计(李清勇)课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、....5-1凸多边形最优三角剖分问题//3d5凸多边形最优三角剖分#include"stdafx.h"#includeusingnamespacestd;constintN=7;//凸多边形边数+1intweight[][N]={{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}};//凸多边形的权intMinWeightTriangulation(intn,int**t,int**s);voidTraceback(inti,intj,int**s);

2、//构造最优解intWeight(inta,intb,intc);//权函数intmain(){int**s=newint*[N];int**t=newint*[N];for(inti=0;i

3、nWeightTriangulation(intn,int**t,int**s){for(inti=1;i<=n;i++){t[i][i]=0;}for(intr=2;r<=n;r++)//r为当前计算的链长（子问题规模）{for(inti=1;i<=n-r+1;i++)//n-r+1为最后一个r链的前边界{intj=i+r-1;//计算前边界为r，链长为r的链的后边界t[i][j]=t[i+1][j]+Weight(i-1,i,j);//将链ij划分为A(i)*(A[i+1:j])这里实际上就是k=is[i][j]=i;for(intk=i+1;k

4、[i:k])*(A[k+1:j])intu=t[i][k]+t[k+1][j]+Weight(i-1,k,j);.下载可编辑.....if(u

5、eturnweight[a][b]+weight[b][c]+weight[a][c];}5-4数字三角形最短路径#include#include#include"string.h"#defineMax101usingnamespacestd;intD[Max][Max];intnum;.下载可编辑.....intMaxSum(intnum){inti,j;for(i=num-1;i>=1;i--)for(j=1;j<=i;j++){D[i][j]=max(D[i+1][j],D[i+1][j+1])+D[i][j];}returnD[1][1]

6、;}intmain(intargc,charconst*argv[]){inti,j;cin>>num;for(i=1;i<=num;i++)for(j=1;j<=i;j++)cin>>D[i][j];cout<usingnamespacestd;#defineN210intcost[N][N];intm[N];.下载可编辑.....intmain(){intn,i,j;while(cin>>n){for(i=1;i>c

7、ost[i][j];m[1]=0;intmin;for(i=2;i<=n;i++){min=cost[1][i];for(j=1;j<=i-1;j++){if(cost[j][i]!=0&&m[j]+cost[j][i]  1.us