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

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

2、執(zhí)行次數(shù)為( n2) 2。(n2 ) 。42-10. （ 1 ）當(dāng)n1 時(shí) ， 5n28n25n2 ， 所 以 ， 可 選 c5 ， n0 1 。 對 于 nn0 ，f (n)5n28n25n2 ，所以， 5n28n2(n2 ) 。（ 2）當(dāng) n8時(shí)， 5n28n25n2n224n2，所以，可選c 4 ， n08 。對于 nn0 ，f (n)5n28n24n2 ，所以， 5n28n2(n2 ) 。（ 3）由（ 1）、（ 2）可知，取 c14， c25 ， n08，當(dāng) n n0 時(shí)，有 c1n25n28n 2 c2n2 ，所以 5n2 8n 2(n2 ) 。2-11.(1) 當(dāng) n3 時(shí)， lo

3、g nn log3 n ，所以 f (n)20 nlog n21n ， g(n)nlog3 n2n 。可選 c21， n03 。對于 nn0 ， f (n)cg( n) ，即 f (n)(g (n) 。注意：是 f(n)和 g(n)的關(guān)系。2（ 2）當(dāng) n4時(shí)，22222lognf (n) n/ log nn g (n)nlognnlog n n，所以?？蛇xc 1，n04 。對于n n0 ， f (n)n2cg( n) ，即f (n)(g (n) 。（ 3）因?yàn)閘og nlog(log n)log(log n )f (n)(log n)ng(n)n / log nnlog n 2。當(dāng)n4 時(shí)，

4、f (n) nn，g(n)n logn 2n 。所以，可選c1 ， n04 ，對于 n n0 ， f ( n)cg (n) ，即 f (n)( g(n) 。第二章2-17.證明：設(shè)n 2i，則ilog n 。T n2Tn2n log n2 2Tnnlogn22222nlog n2222Tn2n log nlog22nlog n2222Tn22n log n2n2222Tn2nn22n log n 2n232log222223Tn2n log nlog422n log n2n2323Tn32n log n2n4n232k Tn2knlog n2n4n2n k12k2i1 T 22 i1 nlog

5、 n 2n4n2n i22i142n log n log n1i 2i 1 n2n2n log 2 n2n log nlog 2 n3log n 2 nn log 2 nn log n當(dāng) n2 時(shí)，Tn2n log 2 n 。所以， Tnn log 2 n。第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right)&&left<right)int m=Divide(left,right);if(x<P(m)right=m-1;else if(x>Pm)left=m+1;else

6、 return S(P)5-7. template <class T>int SortableList<T>:BSearch(const T&x,int left,int right) constif (left<=right)int m=(right+left)/3;if (x<lm) return BSearch(x,left,m-1);else if (x>lm) return BSearch(x,m+1,right);else return m;return -1;第五章9426135701234567-10證明：因?yàn)樵撍惴ㄔ诔晒λ阉鞯?/p>

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

8、34321423358523234585332345854233458552334558排序結(jié)果233455812.（ 1）證明：當(dāng) n0 或 n1 或 n2時(shí)，程序顯然正確。當(dāng) n=right-left+1>2 時(shí)，程序執(zhí)行下面的語句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);首次遞歸StoogeSort(left,right-k); 時(shí)，序列的前2/3 的子序列有序。當(dāng)遞歸執(zhí)行StoogeSort(left+k,right); 時(shí)，

9、使序列的后2/3 的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后 1/3 的位置上是整個序列中較大的數(shù)， 即序列后 1/3 的位置上數(shù)均大于前 2/3 的數(shù)，但此時(shí)， 前的序列并不一定是有序的。2/3再次執(zhí)行StoogeSort(left,right-k); 使序列的前2/3 有序。經(jīng)過三次遞歸，最終使序列有序。所以，這一排序算法是正確的。（ 2）最壞情況發(fā)生在序列按遞減次序排列。01 0 ，2 1，2n1。n 332 3ilog n1 。設(shè) n，則 i2log31n 32 n 1 3 34 n 1 1 94 n 3 13992i3in 3i 13i 23 13i23i1323 3i122lo

10、g n13n2 log311222log33 n log3 1log3n log3 1冒泡排序最壞時(shí)間復(fù)雜度為n2 ，隊(duì)排序最壞時(shí)間復(fù)雜度為n log n ，快速排序最壞時(shí)間復(fù)雜度為n log n 。所以，該算法不如冒泡排序，堆排序，快速排序。13. template <class 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 tempk;int mid,left=0,ri

11、ght=n-1,cnt=0,j=0,r=0;for(int i=0;i<m;i+)while(k>0)domid=(left+right)/2;第六章1.由題可得：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;k-=cnt;els

12、etempj=bi;left=0;k-;elsefor(j=0;j<k;j+)tempj=ar;r+;left=cnt;k-=cnt;return tempk-1;p0 , p1 , p2 , p3 , p4 , p5 , p6w0 w1 w2 w3 w4 w5 w610,5,15,7,6,18,3 ，23571412所以，最優(yōu)解為x0, x1 , x2 , x3 , x4 , x5 , x6,1,1,0,1,1,1 ，3最大收益為 105215618355 1。338.17256407618182091516232528378第六章6-9.普里姆算法。因?yàn)閳D G 是一個無向連通圖。所以

13、 n-1<=m<=n (n-1)/2;O(n)<=m<=O(n 2);克魯斯卡爾對邊數(shù)較少的帶權(quán)圖有較高的效率，而mn1.99n2，此圖邊數(shù)較多， 接近完全圖，故選用普里姆算法。6-10.T 仍是新圖的最小代價(jià)生成樹。證明：假設(shè)T 不是新圖的最小代價(jià)生成樹，T是新圖的最小代價(jià)生成樹，那么cost(T )<cost(T) 。有cost(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(

14、1,1)+Bcost(1.0)=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)=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)=

15、minc(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=min4+8,2+7,6+8=9 Bcost(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+

16、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)=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

17、,y,z,z,y,xB8= 0,z,x,y,y,z,x,z00000000000000000011111102133313011112220122213101122222022112220112233301222131011223340122212101123334022112220122334402122212(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);Co

18、ut<<ai;else if ( ci-1j>=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<=n; j+)if (xi= =yj)cij=ci-1j-1+1;else if (ci-1j>=cij-1)cij=ci-1j;elsecij=cij-1;return cmn;15. S1(

19、0,0) , S10( 10,2) ,S0( 0,0), (10,2),S11( 15,5), (25,7) ,S1( 0,0), (10,2), (15,5), (25,7),S12( 6,8), (16,10), ( 21,13), (31,15) ,S2( 0,0), (6,8), (16,10), (21,13), (31,15)S13( 9,1), (15,9), (25,11), (30,14), (40,16) ,S3( 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)稱為一個問