算法設計與分析報告C++語言描述課后問題詳解

1、第一章R51-3.最大公約數(shù)為1?？?414倍。主要考慮循環(huán)次數(shù)，程序1-2的while循環(huán)體做了 10次，程序1-3的while循環(huán)體做了 14141次（14142-2循環(huán)）若考慮其他語句，則沒有這么多，可能就601倍。1322-8. （ 1）畫線語句的執(zhí)行次數(shù)為log n。 （log n）。劃線語句的執(zhí)行次數(shù)應該理解為一格整體。（2 ）畫線語句的執(zhí)行次數(shù)為n(n 1)(n 2)6(n3)。（3）畫線語句的執(zhí)行次數(shù)為A。 G，n）。（4 ）當n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為(n 1)(n 3)42-10.(1)當1時，5n2 8n2 5n2，所以，可選c 5 ，no1。對于nno，f (n)5

2、n28n25n2，所以，5n28n 2(n2)。（2）當n8時,5n：2 8n2 5n2n2224n，所以人可選c 4，no 8。對于n no,f (n)5n28n24n2，所以，5n28n 2(n2)。（3）由（1）、（2）可知，取Ci4，C25， no8，當nno時,有&n25n2 8n 22C2n，所2以5n8n2(n2)。2-11. (1）當n3時,logn nlog3n，所以f （n) 20nlogn21n , g(n)n logn2n?？蛇xc21no3。對于nno，f(n)cg(n)，即 f(n)(g( n）。注意:是f(n)和 g(n)的關系。當n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為(n

3、 2)24(n2)。2 2 2 2 2(2 )當 n 4 時，log n n log n,所以 f( n) n /log n n , g( n) n log n n?？蛇x c 1,2no 4。對于 n no, f(n) n cg(n)，即 f(n) (g(n)。22Tn222n log n Iog2 2nlogn22T2 2nlogn 2n(3)因為 f(n)(log n)lognnlog(logn) , g(n)n / log nn log.2。當n4 時，f(n) nlog(logn) n，g(n) n log.2n。所以，可選 c 1，n4，對于n no，f(n)cg(n)，即 f (n

4、)(g(n)。第二章2-17.證明：設n 2i，則 i log n。T n2T n2n log n 22T 2 -.nlog -2n log n22222 nn , n2 2T 322 log?22 2n log n 2n3 n2 T32n log n Iog4 2 2nlogn 2n3n2 T33 2nlog n 2n 4nL Lk n2 T 2?2kn log n 2n 4n L 2n k 12i 1T 22 i 1 nlog n 2n 4n L 2n i 2i 124 2nlogn logn 1 i 2 i 1 n2 22n 2nlog n 2n log n log n 3log n 2

5、 n n log2 n n log nn log2 n 。2當 n 2 時，Tn 2n log 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+

6、left)/3;if (xlm) return BSearch(x,m+1,right);else return m;return -1;第五章9.4廠-2 61357證明：因為該算法在成功搜索的情況下，關鍵字之間的比較次數(shù)至少為log n，至多為log n 1。在不成功搜索的情況下，關鍵字之間的比較次數(shù)至少為log n 1，至多為log n2。所以，算法的最好、最壞情況的時間復雜度為log n。假定查找表中任何一個元素的概率是相等的，為丄，那么,n不成功搜索的平均時間復雜度為Aulog n ，成功搜索的平均時間復雜度為A； nIn E 2n n E其中，I是二叉判定樹的內路徑長度,E是外路徑

7、長度，并且 E Ilog n。2n 。11.步數(shù)012345初始時11111111111OO211111OO311111OO411111OO排序結果11111OO步數(shù)01234567初始時5583432OO14233585OO23234585OO33234585OO42334585OO52334558OO排序結果2334558OO12. (1 )證明：當n 0或n 1或n2時，程序顯然正確。當n=right-left+12時，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);St

8、oogeSort(left,right-k); 首次遞歸 StoogeSort(left,right-k); 當遞歸執(zhí)行 StoogeSort(left+k,right);原序列的后1/3的位置上是整個序列中較大的數(shù)， 前2/3的序列并不一定是有序的。 再次執(zhí)行StoogeSort(left,right-k); 使序列的前經(jīng)過二次遞歸，最終使序列有序。時，序列的前2/3的子序列有序。時，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使即序列后1/3的位置上數(shù)均大于前2/3的數(shù)，但此時,2/3有序。(2)最壞情況發(fā)生在序列按遞減次序排列。2n01 0,2 1,n33i3log n1設n2，則

9、i。2log31c24,n3n 13 3n 11939ici2i 1i 23n3i 13i 2 L313所以，這一排序算法是正確的。1。4n 3 1 L L93i23i 123ilog n 13n 2og31222log3log3 1log3log3 1n2冒泡排序最壞時間復雜度為n ，隊排序最壞時間復雜度為n log n，快速排序最壞時間復雜度為nlog n。所以，該算法不如冒泡排序，堆排序，快速排序。13. template select (T&x,int k)if(mn) swap( m,n);if(m+nk|k=0) coutOut Of Bounds; return false;in

10、t *p=new tempk;int mid,left=0,right =n-1,c nt=O,j=O,r=O;for(int i=0;i0)domid=(left+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=O;k-； elsefor( j=O;jk;j+)tempj=ar; r+;left=c nt;k-=cnt;retur

11、n tempk-1;第八早1.由題可得:Po P1 P2 P3 P4 _P5 _Rl w0 W! w2 w3 w4 w5 Wj10 5 15 7 62，3, 5，7,118 3，4，1所以，最優(yōu)解為 Xo,X1,X2,X3,X4,X5,X6,553。2最大收益為10 515 6 18 338.第八早6-9 .普里姆算法。因為圖G是一個無向連通圖。所以 n-1=m=n (n-1)/2;0(n )=m=0( n2);n2，此圖邊數(shù)較多，接近完全圖,克魯斯卡爾對邊數(shù)較少的帶權圖有較高的效率，而 m n1.99故選用普里姆算法。6-10 .T仍是新圖的最小代價生成樹。證明：假設T不是新圖的最小代價生成

12、樹，T是新圖的最小代價生成樹，那么cost(T )cost(T)。有cost(T )-c(n-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=7Bco

13、st(3,5)=mi nc(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(

15、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. chair A8=c0 5x ,z,y5z,z5y5xB8= 0/ z5x,y,y5z5x 5z 0000000000000000001111110213331301111222012221310112222202211222011223330122213101122334012221210112

16、3334022112220122334402122212cij(b)sij所以，最長公共字串為(x,y,z,z)。第七章11. void LCS:CLCS ( int i , i nt j )if ( i = = 0 | j = = 0)return;if (ci j = = 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

17、; i+)for (int j =1; j=cij-1)cij=ci-1j;else ci j=cij-1;return cm n;15. S 1(0,0),S0(10,2),S0(0,0),(10,2),S；(15,5),(25,7),1 2S (0,0),(10,2),(15,5),(25,7), S1(6,8),(16,10),(21,13),(31,15),23S ( 0,0), (6,8), (16,10), (21,13), (31,15) S1( 9,1), (15,9), (25,11), (30,14), (40,16),S3( 0,0),(6,8), (15,9),(16,

18、10),(21,13),(30,14),(31,15)8-1 .狀態(tài)空間：描述問題的各種可能的情況，一種情況對呀狀態(tài)空間的一個狀態(tài)。顯示約束：用于規(guī)定每個 Xi取值的約束條件稱為顯示約束隱式約束：用于判定一個候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個節(jié)點稱為一個問題狀態(tài)解狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則該狀態(tài)為解狀態(tài)答案狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為可行解的元組，則該狀態(tài)為解狀態(tài)?；罱Y點：回溯法從開始結點出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結點就成為一個活結點。未檢測的結點稱為活結點擴展結點：算法從 X出發(fā)，訪問X的摸個后繼結點y,則X被稱為擴展結點約束函數(shù)：一個約束函數(shù)是關于部分向量的函數(shù)Bk(xO,x1xk),它被定義為：如果可以判定 Y的子樹上不含任何答案狀態(tài)，則Bk(x0,x1.xk)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的相同，都是為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態(tài)節(jié)點數(shù)，他們統(tǒng)稱為剪枝函數(shù)8-2bool pla