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

1、v1.0可編輯可修改第一章P51-3.最大公約數(shù)為1?？?414倍。主要考慮循環(huán)次數(shù)，程序1-2的while循環(huán)體做了10次，程序1-3的while循環(huán)體做了14141次(14142-2循環(huán))若考慮其他語句，則沒有這么多，可能就601倍。第二章P32152-8.(1)畫線語句的執(zhí)行次數(shù)為logn(logn)。劃線語句的執(zhí)行次數(shù)應(yīng)該理解為一格整體。(2)畫線語句的執(zhí)行次數(shù)為n(n1)(n2)o(n3)。(3)畫線語句的執(zhí)行次數(shù)為Jn。(無)。(4)當(dāng)n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為(n1)(n3)2-10.f(n)(2)f(n)(3)當(dāng)n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為(n2)2(n2)。2.1時，5

2、n8n5n2,所以，可選5n25n28n8n時,以5n2_2一._25n,所以，5n8n(n2)。_2_225n8n25nn4n2,所以,25n28n22一.,4n,所以，可選8。對于nO，(n2)。由(1)、(2)可知，取c1-一28n2(n)。2-11.(1)當(dāng)n3時，logn可選21,n03。對于n2(2)n4時，lognn4,C25,n°n0時,.22有c1n5n8n3logn,所以f(n)20nn,f(n)cg(n),即f(n)log2n,所以f(n)n2/lognlogn21n,g(n).3logn2n。(g(n)。注意：是f(n)和g(n)的關(guān)系。222n,g(n)nl

3、ognn?？蛇xc1,n04。對于n2n0,f(n)ncg(n),即f(n)(g(n)。(3)因為f(n)lognlogQogQ(10gn)n?g(n)n/lognnlogn2。當(dāng)n4時，f(n)10g(logn)nn,g(n)nlogn2no所以，可選c1,n0對于no，f(n)cg(n),即f(n)(g(n)。第二章2-17.證明：設(shè)n2ilogno2T2nlogn22Tn2225log-n2nlogn22Tn222nlognlog22nlogn22T22nlogn2n222Tn23cnn22log2222222nlogn2n23Tn232nlognlog422nlogn2n23Tn2332

4、nlogn2n4n2kTn2k2knlogn2n4nL2nk2i1Ti1nlogn2n4nL2ni2i142nlognlogn122n2nlogn2nlogn2logn3logn2,2,nlognnlogn當(dāng)n2時，Tn2nlog2n。所以,-i_2一nlogn。第五章5-4.SolutionTypeDandC1(intleft,intright)while(!Small(left,right)&&left<right)intm=Divide(left,right);if(x<P(m)right=m-1;elseif(x>Pm)left=m+1;elseret

5、urnS(P)5-7.template<classT>intSortableList<T>:BSearch(constT&x,intleft,intright)constif(left<=right)intm=(right+left)/3;if(x<lm)returnBSearch(x,left,m-1);elseif(x>lm)returnBSearch(x,m+1,right);elsereturnm;return-1;第五章9.26/X/x.1357；、K_>II01234115I-67證明：因為該算法在成功搜索的情況下，關(guān)鍵字之間

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

7、83432OO14233585OO23234585OO33234585OO42334585OO52334558OO排序結(jié)果2334558OO12.(1)證明：當(dāng)n0或n1或n2時，程序顯然正確。當(dāng)n=right-left+1>2時，程序執(zhí)行下面的語句：intk=(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,right)

8、;時，使序列的后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ā)生在序列按遞減次序排列。2n010,21,n31。3、幾c3logn1設(shè)n2，則i。2log31/411 9 n 3 1 L L9c24n3n133n39Qi2-Qi1Qi23n333233i11 32 2logn13 n010g31124 22log3lo

9、g315 ng10g3冒泡排序最壞時間復(fù)雜度為niog31n2,隊排序最壞時間復(fù)雜度為nlogn，快速排序最壞時間復(fù)雜度為nlogn。所以，該算法不如冒泡排序，堆排序，快速排序。13.template<classT>select(T&x,intk)if(m>n)swap(m,n);if(m+n<k|k<=0)cout<<"OutOfBounds"returnfalse;int*p=newtempk;intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;i<m;i+)while

10、(k>0)domid=(left+right)/2;if(amid<bi)left=mid;elseif(amid>bi)right=mid;elsecnt=mid;break;while(left<right-1)if(aleft<bi)cnt=left;elsecnt=left-1;if(k>cnt)if(cnt>0)for(j=0;j<cnt；j+)tempj=ar;r+;left=cnt;k-=cnt;elsetempj=bi;left=0;k-;elsefor(j=0;j<k;j+)tempj=ar;r+;left=cnt;k-=

11、cnt;returntempk-1;第六章1由題可得.包包包心口正丑1051576183，,c，c，f-，r，/，/，/w0w1w2w3W4w5W623571412,所以，取優(yōu)解為Xo,Xi,X2,X3,X4,X5,X6,1-,1,0,1,1,1,321最大收益為10515618355,338.6-9.普里姆算法。因為圖G是一個無向連通圖。所以n-1<=m<=n(n-1)/2;O(n)<=m<=O(n2)；接近完全圖,克魯斯卡爾對邊數(shù)較少的帶權(quán)圖有較高的效率，而mn1.99n2，此圖邊數(shù)較多，故選用普里姆算法。6-10.T仍是新圖的最小代價生成樹。)<cost(T

12、)。這與題設(shè)中證明：假設(shè)T不是新圖的最小彳t價生成樹，是新圖的最小代價生成樹，那么cost(T'有cost(T')-c(n-1)<cost-c(n-1),即在原圖中存在一顆生成樹，其代價小于T的代價,T是原圖的最小代價生成樹矛盾。所以假設(shè)不成立。證畢。第七章1.Bcost(1,0)=0;Bcost(2,1)=c(1,1)+Bcost=5Bcost(2,2)=c(1,2)+Bcost(1,0)=2Bcost(3,3)=minc(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)=min6+2,3+5=8Bcost(3,4)=c(2,4)+Bcost(2,2)

13、=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+8=9Bcost(5,8)=minc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=122

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

15、2所以，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. charA8='0','x','z','y','z','z','y','x'B8='0','z','x','y','y',

16、9;z','x','z'0000000111011110112201122011220112301223(a) cij所以，最長公共字串為第七章0000011102222012220233301334013340234402(x,y,z,z)。000000133313222131211222222131222121211222122212(b) s皿11. voidLCS:CLCS(inti,intj)if(i=0|j=0)return;if(cij=ci-1j-1+1)CLCS(i-1,j-1);Cout<<ai;elseif(ci-1j&

17、gt;=cij-1)CLCS(i-1,j);elseCLCS(i,j-1);12. intLCS:LCSLength()for(inti=1;i<=m;i+)ci0=0;for(i=1;i<=n;i+)c0i=0;for(i=1;i<=m;i+)for(intj=1;j<=n;j+)if(xi=yj)cij=ci-1j-1+1;elseif(ci-1j>=cij-1)c皿尸ci-1jelsecij=cij-1;returncmn;15. S1(0,0),S0(10,2),_01S(0,0),(10,2),Si(15,5),(25,7),S1(0,0),(10,2)

18、,(15,5),(25,7),Si2(6,8),(16,10),(21,13),(31,15),S2(0,0),(6,8),(16,10),(21,13),(31,15)S3(9,1),(15,9),(25,11),(30,14),(40,16),3S(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)稱為一個問題狀態(tài)解狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則該狀態(tài)為解狀態(tài)答案狀態(tài)：如果從根到樹中某個狀態(tài)的路徑代表一個作為可行解的元組，則該狀態(tài)為解狀態(tài)?；罱Y(jié)點(diǎn)：回溯法從開始結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)。未檢測的結(jié)點(diǎn)稱為活結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)：算法從x出發(fā)，訪問x的摸個后繼結(jié)點(diǎn)y,則x被稱為擴(kuò)展結(jié)點(diǎn)約束函數(shù)：一個約束函數(shù)是關(guān)于部分向量的函數(shù)Bk(x0,x1.xk),它被定義為：如果可以判定Y的子樹上不含任何答案狀態(tài)，則Bk(x0,x1.xk)為false,否則為true.剪枝函數(shù)：約束函數(shù)和限界函數(shù)的目的相同，都是為了剪去不必要搜索的子樹，減少問題求解所需實(shí)際生成的狀態(tài)節(jié)點(diǎn)