算法設(shè)計與分析C語言描述(陳慧南版)課后答案

1、第一章P51-3.最大公約數(shù)為1?？?414倍。主要考慮循環(huán)次數(shù)， 程序1-2的while循環(huán)體做了 10次，程序1-3的while循環(huán)體做了 14141次 循環(huán)）若考慮其他語句，則沒有這么多，可能就601倍。第二章(14142-2P322-8. （ 1 ）畫線語句的執(zhí)行次數(shù)為log n。門（log n）。劃線語句的執(zhí)行次數(shù)應(yīng)該理解為一格整體。(2)畫線語句的執(zhí)行次數(shù)為1二n（n 四 2）。匚（門3）。i 4 j 4 k4(3)畫線語句的執(zhí)行次數(shù)為I -/n o 0G.n）。(4)當(dāng)n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為(n 1)(n 3)當(dāng)n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為(n 2)2。20(n )。2

2、-10.2 2(1 ) 當(dāng) n_1時，5n -8 n，2空5 n ,所以，可選 c = 5 , n0=1。對于n n。，f(n)=5n2 -8n 2 - 5n2，所以,5n2 -8n 2 -)(n2)。(2)2 2 2 2當(dāng) n _8 時，5n -8n 2 _ 5n -n 2 - 4n ,所以，可選 c = 4， n0 = 8。對于n - n。,f(n)O229=5n -8n 2 _ 4n，所以，5n -8n 2 =i (n )。(3)由（1 ）、（ 2）可知，取 q=4， q=5，讓=8，當(dāng) nn0 時，有 jn2 蘭5 n2 -8 n + 2 蘭qn2，所以 5n2 -8n 2 - 0(n

3、2)。332-11. (1)當(dāng) n 啟3時，logn cn 2n?？?1選 c=，n =3。對于 n -n， f （n） eg （n），即 f （n） -）（g（ n）。注意：是 f（n）和 g（n）的關(guān)系。(2)當(dāng) n 一4 時，logn ： n ： log n，所以 f (n) = n /log n ： n , g(n)二 nlog n _ n?？蛇x c = 1,2no =4。對于 nn， f(n) : n 乞 cg(n)，即 f (n) r)(g(n)。(3)因?yàn)?f(n)=(logn)logn = nlog(logn) , g(n)二 n/logn = nlogn2。當(dāng) n-4 時，f

4、(n)二 nlog(logn) _ n ,g(n)= nlogn2 ： n。所以，可選 c =1 ,=4，對于 n _ ,f(n) _ cg(n)，即 f(n)u(g(n)。第二章2-17.證明：設(shè) n =2，貝y i =log n。T n j=2T+ 2n log n = 2 |2T 2LL2 JJ|+2 nlog n2 9-22T2n log n -Iog2 2nlog n= 22T2 2nlogn-2n+ 2匯 *xlog1 + 2x2 nlogn2n-23T2nlogn-Iog4 2 2nlog n-2n= 23T 丨再 +3漢2nlogn-2n-4nIL23丿= 2kT I l+2k

5、nlogn-2n-4n-1|-2n(k-1)i L2 i 丿=2 T 2y 2 i _ 1 n log n - 2n - 4n -111 - 2 n i - 2 = 2i4 4 2n log n log n -1 i i - 2 i T n22=2n 2n log n -2n log n - log n - 3log n 2 n=nl og2 n nlog n當(dāng) n 丄2 時，Tn 豈 2n log2 n。所以，T n =0 nlog2 n 。第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right )&lef

6、tright)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) return BSearch(x,m+1,right); else return m;return -1;第五章9.42 61357log n，至多為 |log n 1。在證明：因?yàn)樵撍惴ㄔ诔晒λ阉鞯那闆r下，關(guān)鍵字之間的比較次數(shù)至

7、少為不成功搜索的情況下，關(guān)鍵字之間的比較次數(shù)至少為log n 1，至多為logn j2。所以，算法的最好、最壞情況的時間復(fù)雜度為心log n。1假定查找表中任何一個元素的概率是相等的，為一，那么，n不成功搜索的平均時間復(fù)雜度為Au n = log n ,n十1I + n E 2 n + n E成功搜索的平均時間復(fù)雜度為A.n1 - D log n。nnn其中，I是二叉判定樹的內(nèi)路徑長度，E是外路徑長度，并且 E = I 2n。11.步數(shù)012345初始時11111111111OO211111OO311111OO411111OO排序結(jié)果11111OO步數(shù)01234567初始時5583432OO1

8、4233585OO23234585OO33234585OO42334585OO52334558OO排序結(jié)果2334558OO12.( 1)證明：當(dāng)n = 0或n =1或n = 2時，程序顯然正確。當(dāng)n=right-left+12時，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right); StoogeSort(left,right-k); 首次遞歸 StoogeSort(left,right-k);時，序列的前 2/3的子序列有序。 當(dāng)遞歸執(zhí)行 StoogeSort(left+k,ri

9、ght);時，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后1/3的位置上是整個序列中較大的數(shù)，即序列后1/3的位置上數(shù)均大于前2/3的數(shù)，但此時，前2/3的序列并不一定是有序的。 再次執(zhí)行StoogeSort(left,right-k);使序列的前2/3有序。經(jīng)過二次遞歸，最終使序列有序。所以，這一排序算法是正確的。(2)最壞情況發(fā)生在序列按遞減次序排列。f2n 一 0 = _ 1 =0，一 2 =1，一 n i=3 一 一 1。I 3丿則ogn。 log3 -1 if(amidbi) left=mid;一 n =3一 2n 1 =3 _13丿 19丿帆樹計+1=叫列+3+1

10、=出川.3 2 .3212=23 _2log n3 n 2log32 2log33 n時log3=0 n時冒泡排序最壞時間復(fù)雜度為門n2，隊(duì)排序最壞時間復(fù)雜度為門nlog n ,快速排序最壞時間復(fù)雜度為On log n。所以，該算法不如冒泡排序，堆排序，快速排序。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 tempk;int mid,left=0,right =n-1,c nt=0,j=0,r=0;for(int i=0;i0)

11、domid=(left+right)/2;else 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-;elsefor(j=0;jk;j+)tempj=ar; r+;left=c nt;k-=cnt;return tempk_1;10 5 15 7 6 18 37,3，I，7，i，7，i1由題可得:PlP3 P4 5 _P6lW0 則w2

12、 w3 w4 w5 w6 ；所以,f 2最優(yōu)解為X,Xi,X2,X3,X4,X5,X6 ，3,1,0,1,1,1，最大收益為10 5 - 15 6 18 55-。3 36-9.普里姆算法。因?yàn)閳DG是一個無向連通圖。所以 n-1=m=n (n-1)/2;2O(n)=m=0(n );1 992克魯斯卡爾對邊數(shù)較少的帶權(quán)圖有較高的效率,而 m -n.”0 n ，此圖邊數(shù)較多，接近完全圖, 故選用普里姆算法。6-10.T仍是新圖的最小代價生成樹。證明：假設(shè) T不是新圖的最小代價生成樹，T是新圖的最小代價生成樹，那么cost(Tcost(T)。有cost(T )-c(n-1)cost(t)-c(n-1)

13、，即在原圖中存在一顆生成樹，其代價小于T的代價，這與題設(shè)中 T是原圖的最小代價生成樹矛盾。所以假設(shè)不成立。證畢。第七章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(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)=mi n3+5,8+2=8Bco

14、st(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=12 2.向后遞推的計算過程如上題所示向前遞推過程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3

15、,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)=d(4,7)=8, d(3,3)=d(3,4)=d(3,5)=7, d(2,1)=5, d(2

16、,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 A8=0 , x ,z ,y , z,z,y ,x B8=0 , z ,x ,y , y,z,x ,z -0000 000010000000010011 1111021333130111 1222012221310112 2222022112220112 2333012221310112 2334012221210112 333402211222-0122 33441 102122212 一(a) cij(b)s

17、ij所以，曰 最長公共字串為(x,y,z,z)o第七章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 (int j =1; j=cij-1)cij

18、=ci-1j;else cij=cij-1;return cm n;15. S=(0,0),S=(10,2),0 1S 二(0,0),(10,2), s 二(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),53 二(0,0),(6,8),(15,9),(16,10),(21,13),(30,14),(31,15)8-1.狀態(tài)空間：描述問題的各種可能的情況，一種情況對呀狀態(tài)空間的一個狀態(tài)。顯示約束：用于規(guī)定每個 xi取值的約束條件稱為顯示約束隱式約束：用于判定一個候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個節(jié)點(diǎn)稱為