《計算機算法基礎(chǔ)》課后答案_第1頁
《計算機算法基礎(chǔ)》課后答案_第2頁
《計算機算法基礎(chǔ)》課后答案_第3頁
《計算機算法基礎(chǔ)》課后答案_第4頁
《計算機算法基礎(chǔ)》課后答案_第5頁
已閱讀5頁,還剩34頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、計算機算法分析 習(xí)題課第四章: 2 、3、5、6、10、 11 、23 P99-2在下列情況下求解 4.1節(jié)的遞歸關(guān)系式 T(n)= ()2(/2) () gnnTnfn? 足夠小 + 否則當 g(n)=0(1)和f(n)=O(n):g(n)=0(1)和f(n)=0(1)。P99-2遞推表達式設(shè)n=2k則:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k)=22T(2k-2)+21f(2k-1)+ f(2k)=2kT(1)+2k-1f(2)+2k-2f(22)+ +20f(2k)=2kg( n)+ 2k-1f(2)+2k-2f(22)+ +

2、20f(2k)g(n)=0(1)和 f(n)=O(n)當 g(n )=0(1)和 f(n)二 0( n)時不妨設(shè)g(n)二a, f(n)二bn,貝U:T(n)=T(2k)=2ka+ 2k-1*2b+2k-2*22b+ +20*2kb=2ka+kb2k=an+bnlog2n=0(nlog2n) g(n)=0(1)和 f(n)=0(1) 當 g( n)=0(1)和 f(n )=0(1)時,不妨設(shè) g(n)=c, f(n)=d,貝T(n)=T(2k)二c2k+2k-1d+2k-2d+ +20d=c2k+d(2k-1)=(c+d) n-d=0(n)P99-3根據(jù)2.2節(jié)開始所給出的二分檢索策略,寫一個

3、二分檢索的遞歸過程Procedure BINSRCH(A, low, high, x, j)integer midif low whighthenmid J?low+high)/2?if x=A(mid) thenjJmid;endifif x>A(mid) thenBINSRCH(A, mid+1, high, x, j);endifif x<A(mid) thenBINSRCH(A, low, mid-1, x, j);endif else endifend BINSRCHP99-5作一個 三分”僉索算法,它首先檢查n/3處的元素是否等于某個x的 值,然后檢查2n/3處的元素。

4、這樣,或者找到x,或者把集合縮小到 原來的 1/3。分析此算法在各種情況下的計算復(fù)雜度。Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low J1; high J nwhile low whighdop1 J?(high+2low)/3?p2 J?(2high+low)/3?case:x=A(p1): j Jp1; return:x=A(p2): j Jp2; return:x<A(p1): high Jp1-1:x>A(p2): lowJp2+1:else: low Jp1+1; high Jp2-1end ca

5、serepeatjJ0en dThriSearch實例運行 1 , 2,3,4,5,6,7,8,9 36112 3 4567891 234567891 2 345678912345 6 789123 4 567891234 5 6789成功:O(1),O(log3( n),O(log3( n)最好,平均,最壞失?。篛(log3( n), O(log3( n), O(log3( n)最好,平均,最壞P99-6對于含有n個內(nèi)部結(jié)點的二元樹,證明E=l+2 n其中,E,I分別為外部和內(nèi)部路徑長度。證明:數(shù)學(xué)歸納法當n=1時,易知E=2 ,1=0,所以E=I+2n成立;假設(shè) n < k(k>

6、;0)時,E=l+2n 成立;則當n=k+W, ' 妨認定某個內(nèi)結(jié)點 Xt而且它為葉結(jié)點(根據(jù)二元擴展樹 的定義,一定存在 這樣的結(jié)點X,且設(shè) 該結(jié)點的層數(shù)為 h),將結(jié)點x及其 左右子結(jié)點(外結(jié) 點)從原樹中摘除(X替換為外結(jié)點)此時新樹內(nèi)部結(jié)點為k個,貝y滿足:Ek=lk+2k (1)考察原樹的外部路徑長度和內(nèi)部路徑長度:Ek+1= Ek-h+2(h+1)( 2)lk+ 仁lk+h ( 3)綜合(1)( 2)( 3)式:Ek+1= Ik+2k+h+2=Ik+1-h+2k+h+2=lk+1+2(k+1)故命題成立。P99-10過程MERGESORT的最壞情況時間是O(nlogn),它

7、的最好情況時間是什么?能說歸并分類的時間是 © (nlogn)嗎?最好情況:對有序文件進行排序分析歸并的次數(shù)不會發(fā)生變化 log(n) 次歸并中比較的次數(shù)會發(fā)生變化(兩個長 n/2 序列歸并) 最壞情況兩個序列交錯大小需要比較 n-1 次最好情況一個序列完全大于 /小于另一個序列比較n/2次差異都是線性的,不改變復(fù)雜性的階 最好情況也是 nlog(n), 平均復(fù)雜度 nlog(n) 。P99-11寫一個 “由底向上 ”的歸并分類算法,從而取消對棧空間的利用 見數(shù)據(jù)結(jié)構(gòu) -第九章 P238算法 MPass(R,n,1engthX)MP1 初始化i1 .MP2 合并相鄰的兩個長度為len

8、gth的子文件WHILE i < n -2*length + 1 DO(Merge (R, i, i + length-l, i + 2*lengthT. X) i i + 2*length ).MP3 處理余留的長度小于2*length的子文件IF i+length - < n THENMerge (R, i, i+length-1, n. X)ELSEFOR j = i TO n DO Xj Rj |P99-23通過手算證明(4.9)和(4.10)式確實能得到C11,C12,C21和C22的正 確值。C11=P+S-T+V=(A11+A22)(B11+B22) +A22(B21

9、-B11) -(A11+A12)B22 +(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22 +A22B21-A22B11 -A11B22-A12B22 +A12B21+ A12B22-A22B21-A22B22=A11B11 +A12B21P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11 U=(A21-A11)(B11+B12)R=A11(B12-B22)V =(A12-A22)(B21+B22)S=A22(B21-B11)P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21

10、+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)C12=R+T= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S= A21B11+A22B11 +A22B21-A22B11= A21B11 +A22B21C22=P+R-Q+U=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11+(A21-A11)(B11+B12)A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A

11、21B11-A22B11 +A21B11 +A21B12-A11B11-A11B12=A22B22+A21B12P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V =(A12-A22)(B21+B22)S=A22(B21-B11) 計算機算法分析 習(xí)題課 第五章: 2、3 、6、8 、9 、10 、11 、12 P121-2求以下情況背包問題的最優(yōu)解,n=7, m=15, ( pl,,p7=(10,5,15,7,6,18,3)和(w1,w7)=(2,3,5,7,1,4,1)將以上

12、數(shù)據(jù)情況的背包問題記為I。設(shè)FG(I)是物品按pi的非增次序 輸入時由 GREEDY-KNAPSACK 所生成的解, FO(I) 是一個最優(yōu)解。問FO(I)/ FG(I)是多少?當物品按wi的非降次序輸入時,重復(fù)的討論。 按照 pi/mi 的非增序可得(p5/w5, p1/w1,p6/w6, p3/w3, p7/w7,p2/w2, p4/w4)=(6,5,9/2,3,3,5/3,1) 所以最優(yōu)解為:( 1,2/3,1,0,1,1,1),并且 FO(I)=166/3 按照pi的非增次序輸入時,得到(p6, p3, p1, p4, p5, p2, p7)=(18,15,10,7,6,5,3),對應(yīng)

13、的(w6, w3, w1, w4, w5, w2, w7)= (4,5,2,7,1,3,1) 則 FG(I)的解為(1,0,1,4/7,0,1,0,并且 FG(I)=47,所以 FO(I)/ FG(I)=166/141. 按照wi的非降次序輸入時,得( w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7,) 相應(yīng)的( p5, p7, p1, p2, p6,p3, p4) =(6,3,10,5,18,15,7),貝卩 FW(I)的解為(1,1,4/5,0,1,1,1),并且 FW(I)=54,所以 FO(I)/ FW(I)=83/81 P122-33( 0/1背包問題)如果

14、將 5.3節(jié)討論的背包問題修改成極大化約束條件 xi=0或1 1< i< n這種背包問題稱為0/1背包問題。它要 求物品或者整件裝入背包或者整件不裝入。 求解此問題的一種貪心策 略是:按pi/wi的非增次序考慮這些物品,只要正被考慮的物品能裝的 進就將其裝入背包。證明這種策略 不一定能得到最優(yōu)解。Iniipx藝 1niiwxM證明:當按照pi/wi的非增次序考慮物品存放背包時,如果所裝入的物品恰 能裝滿背包時,顯然為最優(yōu)解,否貝未必是最優(yōu)解 可舉例如下:設(shè)n=3, M=6 ,(p1,p2,p3) =(3,4,8),( w1,w2,w3) =(1,2,5)按照pi/wi的非增序得到(

15、p1/w1,p2/w2,p3/w3) =(3,2,16),貝其解為( 1,1,0),而事實上最優(yōu)解是 (1,0,1) 。問題得證。ERT=fi1li1+fi2(li1+li2)+fik(li1+li2+ +lik)+ +fin(li1+li2+P122-6.假定要將長為11,12,山的n個程序存入一盤磁帶,程序i被檢索的頻 率是fi。如果程序按i 1,i2,in的次序存放,則期望檢索時間(ERT) 是:J工(厶以)/pj k=l 證明按li的非降次序存放程序不一定得到最小的 ERT。 證明按fi的非增次序存放程序不一定得到最小的 ERT。 證明按fi/li的非增次序來存放程序時ERT取最小值。

16、 l:(4,1,2) f:(0.8,0.1,0.1)按li的非降序存放程序ERT=0.1*1+0.1*3+0.8*7=6而最優(yōu)解為 0.8*4+0.1*5+0.1*7=4.4 l:(16,1,2) f:(0.8,0.1,0.1)按fi的非增序存放程序ERT=0.8*16+0.1*17+0.1*19=16.4而最優(yōu)解為 0.1*1+0.8*17+0.1*19=15.6證明結(jié)論是正確的,證明如下:假設(shè)li1,li2, 按照fi/li的非增次序存放,即 fi1/li1 >fi2/li2>->fin/lin,則得到)/假設(shè)該問題的一個最優(yōu)解是按照j1,j2,,的順序存放,并且其期 望

17、檢索式是ERT,我們只需證明ERT < ERT,即可證明按照fi/li的 非增次序存放得到的是最優(yōu)解。易知if藝ERT =fj1lj1+fj2(lj1+lj2)+fjk(lj1+lj2+ljk)+ +fjn(lj1+lj2+ljn)/ ,從前向后考察最優(yōu)解中的程序,不妨設(shè)程序jk是第一個與其 相鄰的程序jk+1存在關(guān)系,則交換程序jk和程序jk+1,得到的期望檢 索時間記為ERT ',容易證明ERT '< ERT,顯然ERT '也是最優(yōu)解, 將原來的最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置, 得到的解 不比原來的最優(yōu)解差, 所以最終變換后得到的解也是最優(yōu)解

18、, 而最終 的解恰是程序按fi/li的非增次序來存放得到的順序。命題得證。P123-8 當 n=7 ,( p1,p7) =(3,5,20,18,1,6,30) 和(di,d7)=(1,3,4,3,2,1,2)時,算法5.5所生成的解是什么? 證明即使作業(yè)有不同的處理時間定理 5.3亦真。這里,假定作業(yè) i 的效益pi>0,要用的處理時間ti>0,限期di >ti.解:根據(jù)pi的非增排序得到(p7, p3, p4, p6, p2, pi, p5 ) =(30,20,18,6,5,3,1) ,對應(yīng)的期限為 (2,4,3,1,3,1,2) ,按照算法 3.5生成 的解為:1. J(

19、1)=7(2),2. J(1)=7(2), J(2)=3(4) ;3. J(1)=7(2), J(2)=4(3),J(3)=3(4);4. J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)證明即使作業(yè)有不同的處理時間定理 5.3 亦真。這里,假定作業(yè) i 的效益pi>0,要用的處理時間ti>0,限期di >ti.(P106)定理5.3:設(shè)J是K個作業(yè)的集合,(T =i1i2i是J中作業(yè)的一種排序, 它使得di1< di2 <-< dik J是一個可行解,當且僅當J中的作業(yè)可以 按照(T的次序又不違反任何一個期限的情況下來處理.

20、證明:顯然即使ti>0 (di >ti ),如果J中的作業(yè)可以按照。的次 序而又不違反任何一個期限來處理,即對 °次序中的任一個作業(yè) k, 應(yīng)滿足dk=kjjt 1,則J就是一個可行解。下面證明如果 J是可行 解,° =i1i2ik使得J中的作業(yè)可以按照di1 <di2 <-< din序列 排列而又不違反任何一個期限。J是可行解,則必存在° ' =r1r2,使得對任意的rk,都有dk>E =kjjt 1,我們設(shè)°是按照di1 <di2 ww dft列的作業(yè)序列。假設(shè)°'工 °,

21、那么令a是使ra zia的最小下標,設(shè)rb=ia,顯然b>a,在° ' 中將ra與rb相交換,因為drbw dra顯然ra和rb可以按期完成作 業(yè),我們還要證明ra和rb之間的作業(yè)也能按期完成。因為drbw dra 而顯然二者之間的所有作業(yè)rt,都有drbwdrt又由于°'是可行解, 所以Ibtbkrrktdd二ww刀所以作業(yè)ra和rb交換后,仍滿足1 ttkrktd = w 藝,即所有作業(yè)可依新產(chǎn)生的排列 ° '=s1s2 的I次序處理而不違反任何一個期限,連續(xù)使用這種方法, °'就可轉(zhuǎn)換成 ° 且不違反

22、任 何一個期限,定理得證。P123-9 對于5.3節(jié)的作業(yè)排序問題證明:當且僅當子集合 J中的作業(yè)可以 按下述規(guī)則處理時它表示一個可行解; 如果J中的作業(yè)I還沒分配處理 時間,則將它分配在時間片a-1, a處理,其中a是使得1<r<di的最 大整數(shù)r,且時間片a-1, a是空的。 仿照例5.4的格式,在習(xí)題5.8的所提供的數(shù)據(jù)集上執(zhí)行算法5.5。易證如果J中的作業(yè)能按上述規(guī)則處理,顯然J是可行解;如果J是可行解,根據(jù)定理5.3可知,J中的作業(yè)根據(jù)時間期限的非 降次序排列,得到i1i2ikin并且按照這個順序,可以處理J中所 有作業(yè),而對這一序列中的任意作業(yè)ik,如果它的時間期限是d

23、k,且 時間片dk-1,dk是空的,則分配之;若時間片dk-1 , dk非空,則向 前找最大的非空r-1,r時間片,1< r< dk因為J是可行解,所以一定 可以找到如此時間片。故命題得證。n=7(p1, , p7)=(3,5,20,18,1,6,30)(d1,d7)=(1,3,4,3,2,1,2)(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1) ,對應(yīng)的期限為 (2,4,3,1,3,1,2)b=minn,maxd(i) =min7,4 =4F(0)F(DFFF01234F(0)F(1)F(2)F(3)F01134F(0)FF(2)F(

24、3)F(4)01133012340 ® (p7, p3, p4, p6, p2, pl, p5)=(30,2(M8g3,l),對應(yīng)的期限為(2,4,3,1,3丄2)F(0) F(1) F(2) F(3) F(4)011130 17.3,474,6(p7, p3, p4, p6, p2. ph p5)=(30,20,18,6,5,3,1),對應(yīng)的期限為(2,4,3,1,32)P123-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元樹中,

25、每個節(jié)點的度至多為k)。進而證明T 中所有內(nèi)部節(jié)點的度為k.證明:設(shè)某棵樹內(nèi)部節(jié)點的個數(shù)是i,外部結(jié)點的個數(shù)是n,邊的 條數(shù)是e,則有e=i+n-1ik=e? ik=i+n-1? (k-1)i=n-1? n mod (k-1)=1利用數(shù)學(xué)歸納法(m表示外部結(jié)點數(shù)目)。當時,存在外部結(jié)點數(shù)目為k的k元樹T, 并且T中內(nèi)部結(jié)點的度為池m-33mod(3-1)=1假設(shè)當m <n,且滿足m mod(k4)=4時,存 在一棵具有m個外部結(jié)點的k元樹T,且所有內(nèi) 部結(jié)點的度為k;我們將外部結(jié)點數(shù)為m的符合上述性質(zhì)的樹T 中某個外部結(jié)點用內(nèi)部結(jié)點a替代,且結(jié)點a 生出k個外部結(jié)點.易知新生成的樹中外部

26、結(jié)點的數(shù)目為m1+k= m +(k-1),因為 m mod顯然n為滿足n mod (k-1)=1,且比m大的最小整數(shù), 而樹每個內(nèi)結(jié)點的度為k,所以n=m+(k-1) 時,存在符合上述性質(zhì)的樹。故命題得證。P123-12證明如果 n mod (k-1)=1 ,則在定理 5.4 后面所描述的貪心規(guī)則對 于所有的(q1,q2,qn )生成一棵最優(yōu)的k元歸并樹。(P111)當(q1,q2,q11) = (3,7,8,9,15,16,18,20,23,25,28 )時,畫出 使用這一規(guī)則所得到的最優(yōu) 3元歸并樹。通過數(shù)學(xué)歸納法證明:對于 n=1 ,返回一棵沒有內(nèi)部結(jié)點的樹且這棵樹顯然是最優(yōu)的。假定該算

27、法對于(q1,q2,qm,其中m=(k-1)s+1 (s >0),都生 成一棵最優(yōu)樹,則只需證明對于(q1,q2,qn)其中n=(k-1)(s+1)+1,也能生成最 優(yōu)樹即可。不失一般性,假定q1 < q2 Ww qn,且q1,q2,qk是算法所找到 的k棵樹的WEIGHT信息段的值。于是q1,q2,qk可生成子樹T,設(shè)T' 是一棵對于(q1,q2,qn)的最優(yōu)k元歸并樹。設(shè)P是距離根最遠的 一個內(nèi)部結(jié)點。如果P的k個兒子不是q1,q2,qk,則可以用 q1,q2,qk和 P現(xiàn)在的兒子進行交換,這樣不增加的帶權(quán)外部路徑 長度。因此T也是一棵最優(yōu)歸并樹中的子樹。于是在 T中如

28、果用其權(quán)為 q1+q2+qk的一個外部結(jié)點來代換T,貝卩所生成的樹T'是關(guān)于 (T,qk+1,qn)的一棵最優(yōu)歸并樹。由歸納假設(shè),在使用其權(quán)為 q1+q2+qk的那個外部結(jié)點代換了 T以后,過程TREE轉(zhuǎn)化成去求 取一棵關(guān)于(T,qk+1,qn)的最優(yōu)歸并樹。因此TREE生成一棵關(guān)于(q1,q2,qn的最優(yōu)歸并樹18(q“q2,耳1)= (3,7,8,9,15,16,1 &20,23,25,28)(q1jq2,.,q11) = (3,7,8,9,15,16,1 &20,23,25,28)0 00(q“q2,,qii)= (3,7,8,9,*15,46,48,20,23,

29、25,28)計算機算法分析 習(xí)題課 第六章1 2 3 4 5 6 8 13 17動態(tài)規(guī)劃1. 多階段過程2. 滿足最優(yōu)性原理3. 建立遞推關(guān)系式P151-1 遞推關(guān)系式(6.8 )對右圖成立嗎?為什么? 遞推關(guān)系式(6.8)為什么對于含有負長度環(huán)的圖不能成立??解:?成立,不包含負長度環(huán)?可以使節(jié)點間的長度任意小。P151-2修改過程ALL_PATHS,使其輸出每對結(jié)點(i,j)間的最短路徑,這個新算法的時間和空間復(fù)雜度是多少?回憶算法:P127 算法 6.1P131 算法 6.3P127 算法 6.1D(i,j)/D(j):從節(jié)點j到匯點t的最優(yōu)路徑中下一個節(jié)點,即最優(yōu)路徑 中j的后繼節(jié)點。

30、算法6.1在計算COST(j)的同時也計算了 D(j)計算出D( j )之后,即可計算最短路徑。9- 11 行P131 算法 6.3對矩陣進行初始化,每個元素賦值為邊的長度(如果沒邊則賦值成MAX)1 5行迭代計算最短路徑長度6 12 行仿照6.1,在每次計算最短路徑的時候計算出D(j)再通過D(j)就可以表示出最短路徑Procedure ShortestPath(COST, minteger i, krenl COST(n5 n), A(n, n), Path(n, n) Msix for i-I to n do 初始化最吒路徑矩陣for j to n doA(iJ)-COST(i,j)if

31、 ij and A(i, j)llax thenelseendifrepeatPath(iJ )*-jPath(iJ)-0Pmh(hj)是從i ” 到j(luò)的最短路徑 上,結(jié)點i的后 續(xù)結(jié)點編號“repeatfor kJ 1 to n do /迭代計算 for i J1 to n dofor j 1 to n doif 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)endifrepeatrepeat repeatfor i1 to n do/輸出最優(yōu)路徑for j1 to n do print(“thepat

32、h of i to j is”i) kpath(i, j)while kz 0 doprint(k)kpath(k, j)repeatrepeatrepeatendShortestPath時間復(fù)雜度第一個循環(huán): O(n2) 第一個循環(huán): O(n3)第一個循環(huán): O(n2)空間復(fù)雜度Cost(n,n) A(n,n) Path(n,n)O(n2)P151-3對于標識符集(a1,a2,a3,a4) = (end, goto, print, stop,已知成功 檢索概率為 P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20,不成功檢索概 率為 Q(0)=1/5, Q(1

33、)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20,用算法 OBST對其計算 W(i,j),R(i, j)和C(i, j)( 0< i, j < 4)。P136 算法 6.5P ( i)P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20Q( i )Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20,Q(4)=1/20P ( i)P(1)=1, P(2)=4, P(3)=2, P(4)=1Q( i )Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=11w11R11c F4

34、4+2+1-7010722+4+4=100201044+1+2=7J030711+1+1=30403100wRC44+2+1=77+4+44+4=1010+2+1=130220102044+1+2=77+1+1-903307121i+1+i =30403100'1 - r ' i rtwC44+2+1節(jié)/7+4+4-1515+2+1=181=20卄I222072232392+4+4 -1010fl +1=13134I 1502Jr2010202744+1+2 =7屮十1一933071211+1+1=30403一 一10(1P151 -4 證明算法OBS

35、T的計算時間是0(n2)。 在已知根R(i, j) ,0< i < j <4的情況下寫一個構(gòu)造最優(yōu)二分檢索樹T的算法。證明這樣的樹能在0(n)時間內(nèi)構(gòu)造出來。 將C中元素的加法看做基本運算,則算法 0BST的時間復(fù)雜性為:20(1,)(,1)1) nnm miRijRij-=+- +藝藝=20(1,)(,1)1 )nnm miRiimRiim-=+_+-+藝藝=2(1,)(0,1)1)nmRnmnRmnnff- +- +-+藝 0(n2) Procedure BuildTree(m, n, R, Root)in teger R(n,n), kTreeNodeRoot, LR,

36、 RRk R(m, n)if k 工 0 then data(Root) k,BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR)left(Root) J LR, right(Root) J RR else data(Root) J m, left(Root) J null, right(Root) J null, endif endBuildTree時間復(fù)雜性分析:T(n)=c+T(k)+T(n-k-1) ,此遞推式保證算法的時間復(fù)雜性為0(n),也可從遞歸的角度出發(fā),遞歸的次數(shù)正是結(jié)點的個數(shù), 而每次遞歸時間復(fù)雜性為常數(shù),所以算法的時間復(fù)雜度也為

37、 O(n)。P151-5由于我們通常只知道成功檢索和不成功檢索概率的近似值,因此, 若能在較短的時間內(nèi)找出幾乎是最優(yōu)的二分檢索樹, 也是一件很有意 義的工作。所謂幾乎是最優(yōu)的二分檢索樹,就是對于給定的P和Q, 該樹的成本(由( 6.9)式計算)幾乎最小。已經(jīng)證明,由以下方法 獲得這種檢索樹的算法可以有 0(nlogn) 的時間復(fù)雜度,選取這樣的 k 為根,它使 |W(0, k-1)-W(k, n) | 盡可能地小。重復(fù)以上步驟去找這根 的左、右子樹。 對于題 6.3的數(shù)據(jù),用上述方法找出一棵這樣的二分檢索樹。它的 成本是什么? 用SPAKS寫一個實現(xiàn)上述方法的算法,你的算法的計算時間為 0(n

38、logn) 嗎?解:矩陣W如下所示,相應(yīng)的k從1到4得式如下: |W(0,0)-W(1,4)|=11,|W(0,1)-W(2,4)|=2,|W(0,2)-W(3,4)|=12,|W(0,3)- W(4,4)|=17所以該樹的根是 T(0,4)=2 ,依次計算得到 T(0,1)=1 , T(2,4)=3 ,T(3,4)=4總體成本是 4+2*(2+1)+2*(4+2+4)+3*(1+1+1 )=39 Procedure CreateTree(m, n, root, w)integer r, k, root(n, n), w(n, n)real ww, min Jgif m=n the n roo

39、t(m, n)J 0else if m=n-1 then root(m,n) Jnelsefor k Jm+1 to n doww J|w(m, k-1)-w(k, n)|if ww< min then minJww, r Jkendifrepeatroot(m, n) JrCall CreateTree(m, r-1)Call CreateTree(r, n)endifEnd BuildTree時間復(fù)雜性最好和平均的情況應(yīng)該是 O(nlogn) ,但最壞的情況是O(n2)P151-6設(shè)(w1,w2,w3,w4)=(10,15,6,9), (p1,p2,p3,p4)=(2,5,8,1)。

40、生成每個 fi階躍點的序偶集合Si, 0< i < 4。膽)£=(2M)SJ(0g(2M)=(545),(7,25)£=),(2丄嘰伍(7,25)£=(&6), (10 J6) ,(13.211 (15,31)1f 珂(0 俶(8,6) J 10,161, (1J,21), (1531)=(1),(945141125). (14). (16.40|;住珂(皿)他6),他14(1山16)、(1玄2%14旳氐3口 16,40給出一個使得DKNAP(算法6.7)出現(xiàn)最壞情況的例子,它使得|Si|=2i, 0 <i<n。還要求對n的任意取值

41、都適用。取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P和W取值相同,使支配原則成立,也就是說不會因為支配原則而刪 除元素;只要說明不會出現(xiàn)相同元素被刪除一個的情形,即可知是最壞的情況??捎脷w納法證明此結(jié)論。P152-13假定兩個倉庫W1和W2都存有同一種貨物,其庫存量分別為r1和r2 想要將其全部發(fā)往n個目的地D1,D2,Dn.設(shè)發(fā)往Dj的貨物為dj,因 此r1+r2=藝dj.如果由倉庫Wi發(fā)送量為刈的貨物到目的地Dj的花費為 Cij,那么倉庫問題就是求各個倉庫應(yīng)給每個目的地發(fā)多少貨才使總 的花費最小。即要求出這些非負整數(shù) 刈,iwi<2,1 w j< n,它使得x1j+x2j=dj, 1 < j< n,并且使藝ijcij(xij)取最小值。假設(shè)當W1有x的庫存且按最優(yōu)方式全部發(fā)往目的地 D1,D2,Di時所需的花費為gi(x)(W2的庫存為藝dj

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論