《計算機算法基礎》第三版-課后習題答案

1、上機實驗 書上121頁 5。2 5。3 書上151 6。1 6。3 6。6他說搞懂這幾題和實驗就沒問題了 4.2在下列情況下求解遞歸關(guān)系式 T(n)= 當n=2k g(n)= O(1)和f(n)= O(n)； n=2k g(n)= O(1)和f(n)= O(1)。解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) = =2kT(1)+2k-1f(2)+2k-2f(22)+20f(2k) =2kg(n)+ 2

2、k-1f(2)+2k-2f(22)+20f(2k) 當g(n)= O(1)和f(n)= O(n)時，不妨設g(n)=a，f(n)=bn，a，b為正常數(shù)。則 T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+20*2kb =2ka+kb2k =an+bnlog2n= O(nlog2n) 當g(n)= O(1)和f(n)= O(1)時，不妨設g(n)=c，f(n)=d，c，d為正常數(shù)。則 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+20d=c2k+d(2k-1)=(c+d)n-d= O(n)4.3根據(jù)教材中所給出的二分檢索策略，寫一個二分檢索的遞歸過程。Procedu

3、re BINSRCH(A, low, high, x, j)integer midif lowhigh then mid if x=A(mid) then jmid; endifif x>A(mid) then BINSRCH(A, mid+1, high, x, j); endifif x<A(mid) then BINSRCH(A, low, mid-1, x, j); endifelse j0; endifend BINSRCH4.5作一個“三分”檢索算法。它首先檢查n/3處的元素是否等于某個x的值，然后檢查2n/3處的元素；這樣，或者找到x，或者把集合縮小到原來的1/3。分

4、析此算法在各種情況下的計算復雜度。 Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhigh do p1 ; p2 case :x=A(p1): jp1; return :x=A(p2): jp2; return :x<A(p1): highp1-1 :x>A(p2): lowp2+1:else: lowp1+1; highp2-1 end caserepeatj0end ThriSearchT(n)= g(n)= O(1) f(n)= O(1)成功:O(1),O(log3(n

5、),O(log3(n)最好，平均， 最壞失敗: O(log3(n),O(log3(n),O(log3(n)最好，平均， 最壞4.6對于含有n個內(nèi)部結(jié)點的二元樹，證明E=I+2n，其中，E，I分別為外部和內(nèi)部路徑長度。證明：數(shù)學歸納法當n=1時，易知E=2，I=0，所以E=I+2n成立；假設nk(k>0)時，E=I+2n成立；則當n=k+1時，不妨假定找到某個內(nèi)結(jié)點x為葉結(jié)點（根據(jù)二元擴展樹的定義，一定存在這樣的結(jié)點x，且設該結(jié)點的層數(shù)為h），將結(jié)點x及其左右子結(jié)點（外結(jié)點）從原樹中摘除，生成新二元擴展樹。此時新二元擴展樹內(nèi)部結(jié)點為k個，則滿足Ek=Ik+2k，考察原樹的外部路徑長度為Ek

6、+1= Ek-（h-1）+2h，內(nèi)部路徑長度為Ik+1=Ik+（h-1），所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1)，綜合知命題成立。4.10過程MERGESORT的最壞情況時間是O(nlogn)，它的最好情況時間是什么？能說歸并分類的時間是(nlogn)嗎？最好情況：是對有序文件進行排序。分析：在此情況下歸并的次數(shù)不會發(fā)生變化-log(n)次歸并中比較的次數(shù)會發(fā)生變化（兩個長n/2序列歸并）最壞情況兩個序列交錯大小，需要比較n-1次最好情況一個序列完全大于/小于另一個序列，比較n/2次差異都是線性的，不改變復雜性的階因此最好情況也是nlogn, 平均復

7、雜度nlogn?？梢哉f歸并分類的時間是(nlogn)5.2 求以下情況背包問題的最優(yōu)解，n=7，m=15，=(10,5,15,7,6,18,3)和=(2,3,5,7,1,4,1)。 將以上數(shù)據(jù)情況的背包問題記為I。設FG(I)是物品按的非增次序輸入時由GREEDY-KNAPSACK所生成的解，F(xiàn)O(I)是一個最優(yōu)解。問FO(I)/ FG(I)是多少? 當物品按的非降次序輸入時，重復的討論。解： 按照/的非增序可得(/，/，/，/，/，/，/)= (6,5,9/2,3,3,5/3,1) W的次序為(1,2,4,5,1,3,7),解為(1,1,1,1,1,2/3,0) 所以最優(yōu)解為：（1,2/3,

8、1,0,1,1,1）FO(I)=166/3 按照Pi的非增次序輸入時得到(,)= (18,15,10,7,6,5,3)，對應的(,)= (4,5,2,7,1,3,1)解為(1,1,1,4/7,0,0,0)所以FG(I)的解為（1,0,1,4/7,0,1,0）FG(I)=47，所以FO(I)/ FG(I)=166/141. 按照的非降次序輸入時得到(,)=(1,1,2,3,4,5,7)相應的(,)=(6,3,10,5,18,15,7) 解為(1,1,1,1,1,4/5,0)則FW(I)的解為（1,1,4/5,0,1,1,1）FW(I)=54，所以FO(I)/ FW(I)=83/81.5.3（0/

9、1背包問題）如果將5.3節(jié)討論的背包問題修改成 極大化 約束條件 xi=0或1 1in這種背包問題稱為0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按/的非增次序考慮這些物品，只要正被考慮的物品能裝進的就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。證明：當按照/的非增次序考慮物品存放背包時，如果所裝入的物品恰能裝滿背包時，易證為最優(yōu)解，否則未必是最優(yōu)解?？膳e例如下：設n=3，M=6，（, , ）=(3,4,8)，（, , ）=(1,2,5)，按照/的非增序得到（/, /, /）=(3,2,1.6)，則其解為（1,1,0），而事實上最優(yōu)解是(1,0,1)

10、，問題得證。5.11 證明如果一棵樹的所有內(nèi)部節(jié)點的度都為k，則外部節(jié)點數(shù)n滿足n mod (k-1)=1. 證明對于滿足 n mod (k-1)=1的正整數(shù)n，存在一棵具有n個外部節(jié)點的k元樹T(在一棵k元樹中，每個節(jié)點的度至多為k)。進而證明T中所有內(nèi)部節(jié)點的度為k.證明： 設某棵樹內(nèi)部節(jié)點的個數(shù)是m，外部結(jié)點的個數(shù)是n，邊的條數(shù)是e，則有 e=m+n-1和 e=mkmk=m+n-1 Þ (k-1)m=n-1 Þ n mod (k-1)=1 利用數(shù)學歸納法。當n=1時，存在外部結(jié)點數(shù)目為1的k元樹T，并且T中內(nèi)部結(jié)點的度為k；假設當 nm，且滿足n mod (k-1)=

11、1時，存在一棵具有n個外部結(jié)點的k元樹T，且所有內(nèi)部結(jié)點的度為k；我們將外部結(jié)點數(shù)為n(n為滿足nm，且n mod (k-1)=1的最大值)的符合上述性質(zhì)的樹T中某個外部結(jié)點用內(nèi)部結(jié)點a替代，且結(jié)點a生出k個外部結(jié)點，易知新生成的樹T中外部結(jié)點的數(shù)目為n+(k-1)，顯然n為滿足n mod (k-1)=1，且比m大的最小整數(shù)，而樹T每個內(nèi)結(jié)點的度為k，即存在符合性質(zhì)的樹。綜合上述結(jié)果可知,命題成立。6.2修改過程ALL_PATHS，使其輸出每對結(jié)點（i,j）間的最短路徑，這個新算法的時間和空間復雜度是多少？ Procedure ShortestPath(COST, n, A, Max)inte

12、ger i , j, kreal COST(n, n), A(n, n), Path(n, n), Maxfor i1 to n do for j1 to n do A(i ,j)COST(i ,j) if ij and A(i, j)Max then Path(i, j )j else Path(i, j)0 endif repeatrepeatfor k1 to n do for i1 to n do for j1 to n do if A(i,j)>A(i,k)+A(k,j)then A(i,j)A(i,k)+A(k,j) Path(i,j)Path(i,k)endif repea

13、t repeatrepeatfor i1 to n do for j1 to n do print(“the path of i to j is ” i ) kpath(i, j) while k0 do print( ,k) kpath(k, j) repeat repeatrepeat end ShortestPath時間復雜度O(n3)，空間復雜度O(n2) 6.4證明算法OBST的計算時間是O(n2)。 在已知根R(i, j)，0i < j4的情況下寫一個構(gòu)造最優(yōu)二分檢索樹T的算法。證明這樣的樹能在O(n)時間內(nèi)構(gòu)造出來。解： 將C中元素的加法看做基本運算，則算法OBST的時間復

14、雜性為： O(n2) Procedure BuildTree(m, n, R, Root)integer R(n,n), kTreeNode Root, LR, RRkR(m,n)if k0 then data(Root)k, BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR) left(Root)LR, right(Root)RRelse data(Root)m, left(Root)null, right(Root)null, endif end BuildTree時間復雜性分析：T(n)=c+T(k)+T(n-k-1)，此遞推式保證算法的時間復雜性為O(n)，也可從遞歸的角度出發(fā)，遞歸的