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

1、第一章P151-3.最大公约数为1。快1414倍。主要考虑循环次数， 程序1-2的while循环体做了 10次，程序1-3的while循环体做了 14141次(14142-2 循环)若考虑其他语句，则没有这么多，可能就601倍。第二章1322-8.( 1 )画线语句的执行次数为log n。 (log n)。划线语句的执行次数应该理解为一格整体。(2)画线语句的执行次数为n(n 1)(n 2)6(n3)。f(n)5n28n25n2,所以,5n2 8n 2(2)当n8时,5n2 8n2 22 5n n 2f(n)5n28n224n，所以,5n2 8n 2(3)由(1 )、( 2 )可知，取Q4,

2、C25 , n(n2)。24n，所以，可选 c 4， n8。对于n n，(n2)。8，当 n n0 时，有 &n2 5n2 8n 2 c2n2，所(3)画线语句的执行次数为.n 。 G，n)。(4)当n为奇数时画线语句的执行次数为(n1)(n3)4当n为偶数时画线语句的执行次数为(n2)2c(n2)。42-10.2(1)当 n 1 时，5n 8n25n2 ,所以，可选 c 5 ,n01。对于nn0 ,以5n2 8n2(n2)。2-11.(1)当n3 时，log nn log3n，所以 f(n)20nlogn 21n , g(n)n log3 n 2n。可选c212，n3。对于nn , f(n)

3、 cg(n)，即f(n)(g(n)。注意：是f(n)和g(n)的关系。(2)当n4时，log n n2log n ,所以 f (n)n2 /logn n2, g(n) nlog2 2n n 。可选 c1 ,n4。对于 n n， f(n)2n cg(n)，即 f(n)(g(n)。(3)因为 f(n) (log n)lognnlog(log n)，g(n) n / log n nlogn2。当 n4 时，f(n) nlog(logn)g(n) n 也2n。所以，可选 c 1, no 4，对于n n, f(n)cg(n)，即 f (n)(g(n)。第二章2-17.证明：设n 2i，则i log n。

4、T n2T -22nlogn22T2222log n2nlog n22T2n log n Iog2 2nlogn22T2 2n log n 2n22 2T. nlog22 2n log n 2n23T2n log n Iog42 2n log n 2n3 n2 T 33 2nlog n 2n 4nL L2kT 芈2knlog n 2n 4n L 2n k 12k2i 1T 22 i 1 nlog n 2n 4n L 2n i 2 2i 1 4 2n log n log n 1 i 2 i 1 n22n 2nlog n 2nlog n2log n 3log n 2 n2n log n n log

5、 nn log2 n 。当 n 2 时，Tn 2nl og2 n。所以，T n第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right )&leftright)int m=Divide(left,right); if(xPm) left=m+1;else return S(P)5-7. template int SortableList:BSearch(const T&x,int left,int right) const if (left=right)int m=(right+left)/3;if (xlm)

6、 return BSearch(x,m+1,right); else return m;return -1;第五章9.4log n，至多为 log n证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为不成功搜索的情况下，关键字之间的比较次数至少为log n 1，至多为log n2。所以，算法的最好、最坏情况的时间复杂度为log n1假定查找表中任何一个元素的概率是相等的，为-，那么,n不成功搜索的平均时间复杂度为Aulogn，成功搜索的平均时间复杂度为 人n其中，I是二叉判定树的内路径长度，I n E 2n n E , 1 nnnE是外路径长度，并且 E Ilog n。2n 。11

7、.步数012345初始时11111111111OO2:11111OO311111OO411111OO排序结果11111OO步数01234567初始时5583432OO14233585OO23234585OO3J卩234585OO42334585OO52334558OO排序结果2334558OO12.( 1)证明：当n 0或n 1或n2时，程序显然正确。当n=right-left+12时，程序执行下面的语句：int k=(right-left+1)/3;StoogeSort(left,right-k); StoogeSort(left+k,right);StoogeSort(left,right

8、-k); 首次递归 StoogeSort(left,right-k);时，序列的前 2/3的子序列有序。 当递归执行 StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。 再次执行StoogeSort(left,right-k);使序列的前2/3有序。经过二次递归，最终使序列有序。所以，这一排序算法是正确的。(2)最坏情况发生在序列按递减次序排列。010,21 , n 3 2n 1。3i设 n 2 3 ，则 i

9、logn 12Iog3 1n 32n 1 3 34n391194 n 3 1 L L93ii2 n3i 1 3i 2 L 3 133i23i 13ilog n 13 n Iog3 112 22 2Iog3Iog3 1nIog3Iog3 1n冒泡排序最坏时间复杂度为n2，队排序最坏时间复杂度为nIog n，快速排序最坏时间复杂度为nlogn。所以，该算法不如冒泡排序，堆排序，快速排序。13. template select (T&x,int k)if(mn) swap( m,n);if(m+nk|k=0) coutOut Of Bounds; return false; int *p=new t

10、empk;int mid,Ieft=0,right =n-1,c nt=0,j=0,r=0;for(int i=0;i0)domid=(Ieft+right)/2;if(amidbi) right=mid; else cn t=mid; break; while(leftright-1) if(aleftc nt) if(cn t0)for(j=0;jc nt;j+) tempj=ar; r+;left=c nt;k-=cnt;elsetempj=bi;left=0;k-;else for(j=0;jk;j+) tempj=ar; r+;left=c nt;k-=cnt;return temp

11、k_1;第八早1由题可得:直 P_P2_P3_P4_P5_P6 10 5 15 7 6 18 3 w0则w2 w3 w4 w5 w62 3 5 7 V 412所以，最优解为X,Xi,X2,X3,X4,X5,X6,1-,1,0,1,1,1，321最大收益为10 515 6 18 3 55丄。336-9.普里姆算法。因为图G是一个无向连通图。所以 n-1=m=n (n-1)/2;O(n)=m=0(n 2);克鲁斯卡尔对边数较少的带权图有较高的效率,1.99n2n ，此图边数较多，接近完全图,故选用普里姆算法。6-10.T仍是新图的最小代价生成树。证明：假设 T不是新图的最小代价生成树，T是新图的最

12、小代价生成树，那么cost(T )cost。有cost(T -c)-1)cost(t)-c(n-1)，即在原图中存在一颗生成树，其代价小于T的代价，这与题设中 T是原图的最小代价生成树矛盾。所以假设不成立。证毕。第七章1. Bcost(1,0)=0;Bcost(2,1)=c(1,1)+Bcost(1.0)=5Bcost(2,2)=c(1,2)+Bcost(1,0)=2Bcost(3,3)=mi nc(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)=mi n6+2,3+5=8Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7Bcost(3,5)=mi nc(

13、1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)=mi n3+5,8+2=8Bcost(4,6)=mi nc(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)=mi n1+8,6+7,6+8=9Bcost(4,7)=mi nc(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=mi n4+8,2+7,6+8=9Bcost(5,8)=mi nc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=mi n7+9,3+9=122.向后递推的计算过程如上题所示

14、向前递推过程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3,3)=mi n1+cost(4,6),4+cost(4,7)=7,cost(3,4)=mi n6+cost(4,6),2+cost(4,7)=5cost(3,5)=mi n6+cost(4,6),2+cost(4,7)=5cost(2,1)=mi n3+cost(3,3),3+cost(3,5)=8cost(2,2)=mi n6+cost(3,3),8+cost(3,5),5+cost(3,4)=10cost(1,0)=mi n5+cost(2,1),2+cost(2,2)=12所以，d(4,6

15、)=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. chair A8=cO,x5z ,y,z5z,y , x B8=c05z ,xy5y ,z5x , z 0000000000000000001111110213331301111222012221310112222202211222011223330122213101122334012221210112333402211222

16、0122334402122212 cij( b)sij所以，最长公共字串为(x,y,z,z)。第七章11. void LCS:CLCS ( int i , i nt j )if ( i = = 0 | j = = 0) return;if (cij = = ci-1j-1+1)CLCS ( i-1,j-1);Cout=cij-1) CLCS (i-1,j);else CLCS (i,j-1); 12. int LCS:LCSLength()for ( int i =1; i=m; i+)ci0=0;for (i =1; i=n; i+)c0i=0;for (i =1; i=m; i+)for

17、(int j =1; j=cij-1)cij=ci-1j;else cij=cij-1;return cm n;1 015. S (0,0),S1(10,2),0 1S (0,0),(10,2), S1(15,5), (25,7),51 (0,0),(10,2),(15,5),(25,7),S；(6,8),(16,10),(21,13),(31,15),52 ( 0,0), (6,8), (16,10), (21,13), (31,15) S；(9,1), (15,9),(25,11), (30,14), (40,16)3S ( 0,0),(6,8), (15,9),(16,10),(21,1

18、3),(30,14),(31,15)8-1.状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个 xi取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态 答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。 活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。 未检测的结点称为活结点扩展结点：算法从 x出发，访问x的摸个后继结点y,则x被称为扩展结点Y的子树约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1xk),它被定义为：如果可以判定上不含任何答案状态，则Bk(x0,x1.xk)为false,否则为true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际 生成的状态节点数，他们统称为剪枝函数8-2bool place(