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

1、第一章1- 3.最大公約數(shù)為1?？?414倍。主要考慮循環(huán)次數(shù)，程序1-2的while循環(huán)體做了 10次，程序1-3的while循環(huán)體做了 14141 次(14142-2 循環(huán))若考慮其他語句，則沒有這么多，可能就 601倍。第二章2- 8.( 1 )畫線語句的執(zhí)行次數(shù)為log n。O(log n)。劃線語句的執(zhí)行次數(shù)應(yīng)該理解為一格整體。(2) 畫線語句的執(zhí)行次數(shù)為二1 = n(n 1)(門2) 0 0(n3)。iA kA6(3) 畫線語句的執(zhí)行次數(shù)為n。0(、.n)。(4) 當(dāng)n為奇數(shù)時(shí)畫線語句的執(zhí)行次數(shù)為(n 1)(n 3),4當(dāng)n為偶數(shù)時(shí)畫線語句的執(zhí)行次數(shù)為3 空。0(n2)。42-10

2、. (1) 當(dāng) n-1 時(shí)，5n2 -8n 2 乞 5n2，所以，可選 c = 5 , n。=1。對(duì)于 n 一 n。,f (n)=5n2 -8n 2 _5n2，所以,5n2 _8n 2 -)(n2)。(2) 當(dāng) n-8 時(shí)，5n2-8 n，2_5n2-n2 2 一 4n2，所以，可選 c = 4 ,n。=8。對(duì)于 n 一 n。，f (n)=5n2 -8n 2 _4n2，所以，5n2 -8n 2 =門(n2)。(3) 由( 1 )、(2)可知，取° =4 , C2 =5 , n。= 8 ,當(dāng) nn。時(shí)，有&n2 蘭 5n2 8n + 2 蘭 C2， 所以 5n2 -8n 2 -

3、 0(n2)。2-11. 當(dāng) n 一3 時(shí)，log n : n : log3 n，所以 f (n)=2On log n ： 21n ,g(n)二 n log3 n 2n?？蛇x21cp，n0二3。對(duì)于n丄n0,f (n)< cg(n),即詢=(：gn11.注意：是f(n)和 g(n)的關(guān)系。(2) 當(dāng) n 4 日寸,log n ： n ： log2 n , 所以 f (n)二 n2 / log n ： n2, g(n)二 nlog2 n _ n2。o可選 c=1, n° =4。對(duì)于 n_n°, f(n)：n < cg( n)，即 f(n )=O(g( n)。(3)

4、因?yàn)?f(n) =(log n)logn = nlog(logn), g(n)=n /log n=n logn 2。當(dāng) n_4 時(shí)，f (n) =nlog(logn) _ n , g(n) =nl ogn 2 ： n。所以，可選 c = 1 , n o =4，對(duì)于 n _ n° , f( n) _ cg(n),即 f (n) f：(g( n)。第二章2-17.證明：設(shè) n =2i，貝U i = log n。當(dāng) n-2 時(shí)，Tn 乞 2 nlog2 n。所以，T n -n log2 n 。第五早5-4. SolutionType DandC1(int left,int right)wh

5、ile(!Small(left,right )&&leftvright)int m=Divide(left,right);if(x<P(m) right=m-1;else if(x>Pm) left=m+1;else return S(P)5-7. template vclass T> int SortableList<T>:BSearch(c onst T&x,i nt left,i nt right) constif (left<=right)int m=(right+left)/3;if (x<lm) return BSe

6、arch(x,left,m-1);else if (x>lm) return BSearch(x,m+1,right);else return m;return -1;第五章9.證明：因?yàn)樵撍惴ㄔ诔晒λ阉鞯那闆r下，關(guān)鍵字之間的比較次數(shù)至少為lllog n，至多為|logn 10在不成功搜索的情況下，關(guān)鍵字之間的比較次數(shù)至少為 |_logn 1，至多 為logn 2。所以，算法的最好、最壞情況的時(shí)間復(fù)雜度為 。log n 。1假定查找表中任何一個(gè)元素的概率是相等的，為丄，那么，n不成功搜索的平均時(shí)間復(fù)雜度為代n二上 log n ,n +1I +n F-2n +n E,成功搜索的平均時(shí)間復(fù)雜

7、度為 As n二-二二一-1-心logn onnn其中，I是二叉判定樹的內(nèi)路徑長度，E是外路徑長度，并且I 2n o步數(shù)012345初始時(shí)11111111111OO211111OO311111OO411111OO排序結(jié)果11111OO步數(shù)01234567初始時(shí)5583432OO14233585OO23234585OO33234585OO42334585OO52334558OO排序結(jié)果2334558OO12. (1)證明：當(dāng)n =0或n =1或n =2時(shí)，程序顯然正確當(dāng)n=right-left+1>2時(shí)，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort

8、(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);首次遞歸StoogeSort(left,right-k);時(shí)，序列的前2/3的子序列有序設(shè) n =2 12丿log3 -1 當(dāng)遞歸執(zhí)行StoogeSort(left+k,right); 時(shí)，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后1/3的位置上是整個(gè)序列中較大的數(shù)，即序列后1/3的位置上數(shù)均大于前2/3的數(shù)，但此時(shí)，前2/3的序列并不一定是有序的。 再次執(zhí)行StoogeSort(left,right-k);使序列的前2/3有序。經(jīng)過三次遞歸，最

9、終使序列有序。所以，這一排序算法是正確的。(2)最壞情況發(fā)生在序列按遞減次序排列。-0 = - 1 =0 , - 2 =1，一 n =3一冒泡排序最壞時(shí)間復(fù)雜度為O n2，隊(duì)排序最壞時(shí)間復(fù)雜度為O nlog n，快速排序最 壞時(shí)間復(fù)雜度為nlogn。所以，該算法不如冒泡排序，堆排序，快速排序。13. template vclass T>select (T&x,int k)if(m>n) swap(m,n);if(m+n<k|k<=0) cout«"Out Of Bounds" return false;int *p=new temp

10、k;int mid,left=0,right=n-1,c nt=0,j=0,r=0;for(int i=0;i<m;i+)while(k>0)domid=(left+right)/2;if(amid<bi) left=mid;else if(amid>bi) right=mid;else cnt=mid; break;while(left<right-1)if(aleft<bi) cnt=left;else cnt=left-1;if(k>cnt)if(cnt>0)for(j=0;j<cnt;j+)tempj=ar;r+;left=cnt;

11、k-=cnt;elsetempj=bi;left=0;k-;elsefor(j=0;j<k;j+)tempj=ar;r+;left=cnt;k-=cnt;return tempk-1;第八早1.由題可得:Po Pl P2 P3 P4 P5 P6門0 5 15 7 6 18T 3,7,7173,i,o,i1i1i最大收益為10 5 15 6 18 3 = 551338.第八早6-9 .普里姆算法。因?yàn)閳DG是一個(gè)無向連通圖。所以 n-1<=m<=n (n-1)/2;O(n )<=m<=0( n2);克魯斯卡爾對(duì)邊數(shù)較少的帶權(quán)圖有較高的效率，而m=O n1.9O n2，

12、此圖邊數(shù)較多，接近完全圖，故選用普里姆算法。6-10 .T仍是新圖的最小代價(jià)生成樹。證明：假設(shè)T不是新圖的最小代價(jià)生成樹，T'是新圖的最小代價(jià)生成樹，那么cost(T ' )<cost(T)cos有T'-c)n-1)<cost(t)-c(n-1)，即在原圖中存在一顆生成樹，其代價(jià)小于T的代價(jià)，這與題設(shè)中T是原圖的最小代價(jià)生成樹矛盾。所以假設(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)=minc(2,3)+Bco

13、st(2,2),c(1,3)+Bcost(2,1)=min6+2,3+5=8Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7Bcost(3,5)=minc(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)=min3+5,8+2=8Bcost(4,6)=minc(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)=min1+8 ,6+7,6+8=9Bcost(4,7)=minc(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=min4+8 ,2+7,6

14、+8=9Bcost(5,8)=minc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=122.向后遞推的計(jì)算過程如上題所示向前遞推過程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3,3)=min1+cost(4,6),4+cost(4,7)=7,cost(3,4)=min6+cost(4,6),2+cost(4,7)=5cost(3,5)=min6+cost(4,6),2+cost(4,7)=5cost(2,1)=min3+cost(3,3),3+cost(3,5)=8 cost(2,2)=min6+cost(

15、3,3),8+cost(3,5),5+cost(3,4)=10 cost(1,0)=min5+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 A8= 0' , ' x' , ' z' ,''z y'', ,''

16、y z'', ,' x' B8= 0' , ' z' , ' x' , ' y' , ' y' , ' z' , ' x' , ' z'(a) cij(b )sij所以，最長公共字串為 (x,y,z,z)。第七章11. void LCS:CLCS ( int i , int j )if ( i = = 0 | j = = 0) return;if (cij = = ci-1j-1+1)CLCS ( i-1,j-1);Cout<<ai

17、;else if ( ci-1j>=cij-1)CLCS (i-1,j);else CLCS (i,j-1);12. int LCS:LCSLength()for (i =1; i<=n; i+)c0i=0；for (i =1; i<=m; i+)for (i nt j =1; j<=n; j+)if (xi= =yj)cij=ci-1j-1+1;else if (ci-1j>=cij-1)cij=ci-1j;else cij=cij-1;return cm n;1 015. S二(0,0),S1 二(10,2),50 =( 0,0),(10,2), S；二(15

18、,5),(25,7),51 二(0,0),(10,2),(15,5),(25,7), S 二( 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),8-1 .狀態(tài)空間：描述問題的各種可能的情況，一種情況對(duì)呀狀態(tài)空間的一個(gè)狀態(tài)。顯示約束：用于規(guī)定每個(gè)xi取值的約束條件稱為顯示約束隱式約束：用于判定一個(gè)候選解是否為可行解的條件問題狀態(tài)：在狀態(tài)空間樹中的每個(gè)節(jié)點(diǎn)稱為一個(gè)問題狀態(tài)解狀態(tài)：如果從根到樹中某個(gè)狀態(tài)的路徑代表一個(gè)作為候選解的元