算法设计与分析C++语言描述（陈慧南版）课后答案

}

}

}

}

}

left=0; k--;

else { }

for(j=0;j

return temp[k-1];

temp[j]=a[r]; r++;

第六章 1.由题可得：??p0p1p2p3p4p5p6??1051576183?,,,,,,???,,,,,,?， w?0w1w2w3w4w5w6??2357141??2?3??所以，最优解为?x0,x1,x2,x3,x4,x5,x6,???1,,1,0,1,1,1?，

最大收益为10?5? 8.

21?15?6?18?3?55。 33172564076181820915162325283第六章 6-9.

78 普里姆算法。

因为图G是一个无向连通图。 所以n-1<=m<=n (n-1)/2; O(n)<=m<=O(n2);

克鲁斯卡尔对边数较少的带权图有较高的效率，而故选用普里姆算法。 6-10.

T仍是新图的最小代价生成树。

证明：假设T不是新图的最小代价生成树，T’是新图的最小代价生成树，那么cost(T’)

m???n1.99????n2?，此图边数较多，接近完全图，

是原图的最小代价生成树矛盾。所以假设不成立。证毕。 第七章

1. Bcost(1,0)=0;

Bcost(2,1)=c(1,1)+Bcost(1.0)=5 Bcost(2,2)=c(1,2)+Bcost(1,0)=2

Bcost(3,3)=min{c(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)}=min{6+2,3+5}=8 Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7

Bcost(3,5)=min{c(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)}=min{3+5,8+2}=8

Bcost(4,6)=min{c(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)}=min{1+8,6+7,6+8}=9 Bcost(4,7)=min{c(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)}=min{4+8,2+7,6+8}=9 Bcost(5,8)=min{c(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)}=min{7+9,3+9}=12

2.向后递推的计算过程如上题所示 向前递推过程如下： cost(5,8)=0

cost(4,6)=7,cost(4,7)=3

cost(3,3)=min{1+cost(4,6),4+cost(4,7)}=7, cost(3,4)=min{6+cost(4,6),2+cost(4,7)}=5 cost(3,5)=min{6+cost(4,6),2+cost(4,7)}=5 cost(2,1)=min{3+cost(3,3),3+cost(3,5)}=8

cost(2,2)=min{6+cost(3,3),8+cost(3,5),5+cost(3,4)}=10

cost(1,0)=min{5+cost(2,1),2+cost(2,2)}=12

所以，d(4,6)=d(4,7)=8, d(3,3)=d(3,4)=d(3,5)=7, d(2,1)=5, d(2,2)=4, d(1,0)=2 从s到t的最短路径为 (0, d(1,0)=2, d(2,2)=4, d(3,4)=7, d(4,7)=8),路径长为12。 第七章

9. char A[8]={‘0’,’x’,’z’,’y’,’z’,’z’,’y’,’x’ } B[8]={‘0’,’z’,’x’,’y’,’y’,’z’,’x’,’z’}

?0?0??0?0 ??0??0?0???00011111101111112011222220112223301223333012233340?1??2??2? ?3?4?4??4???0?0??0??0?0??0?0???00212112201222221032122120321221203121122013232210?3??1??2? ?1?1?2??2?? (a) c[i][j] （b）s[i][j] 所以，最长公共字串为 (x,y,z,z)。 第七章

11. void LCS::CLCS ( int i , int j ) {

if ( i = = 0 || j = = 0) return; if (c[i][j] = = c[i-1][j-1]+1) {

CLCS ( i-1,j-1); Cout<