算法設(shè)計技巧與分析答案

1、算法設(shè)計技巧與分析參考答案第 1 章 算法分析基本概念1.1(a)6(b)5(c)6(d)61.4算法執(zhí)行了7+6+5+4+3+2+1=28 次比較453324451212241212332445451224121212244545332412121212454533242412121224453345241212122424334545121212242433454512121224243345451.5(a)算法MODSELECTIONSORT執(zhí)行的元素賦值的最少次數(shù)是 0,元素已按非降序排列的時候達(dá)到最小值。(b) 算法 MODSELECTIONSORT執(zhí)行的元素賦值的最多次數(shù)是 3n(

2、 n 1) ,元素已按非升序排列的時候達(dá)到最小值。21.74312567291 次341 次34122 次345122 次3456122 次34567126 次234567122 次234567912由上圖可以看到執(zhí)行的比較次數(shù)為1+1+2+2+2+6+2=16 次。1.11比較 9次24578111213151719比較為 6次24581113171971215比較為 3 次，517194811137121522次，1次比較均為217519111348121571次，共 5次21719513114815127由上圖可以得出比較次數(shù)為5+6+6+9=26 次。1.13FTF,TTT,FTF,T

3、FF,FTF1.16(a) 執(zhí)行該算法， 元素比較的最少次數(shù)是 n-1。元素已按非降序排列時候達(dá)到最小值。(b) 執(zhí)行該算法，元素比較的最多次數(shù)是n( n 1) 。元素已2按非升序排列時候達(dá)到最大值。(c) 執(zhí)行該算法，元素賦值的最少次數(shù)是 0。元素已按非降序排列時候達(dá)到最小值。(d) 執(zhí)行該算法，元素賦值的最多次數(shù)是按非升序排列時候達(dá)到最大值。3n(n1) 。元素已2(e) n 用 O 符號和符號表示算法BUBBLESORT 的運(yùn)行時間： tO(n2 ) ， t(n)(f) 不可以用符號來表示算法的運(yùn)行時間：是用來表示算法的精確階的，而本算法運(yùn)行時間由線性到平方排列，因此不能用這一符號表示。

4、1.27不能用關(guān)系來比較n2 和 100n2 增長的階。 limn2120n100n100n2 不是 o(100n2 ) 的，即不能用關(guān)系來比較 n2 和 100n2 增長的階。1.32(a)當(dāng) n 為 2 的冪時，第六步執(zhí)行的最大次數(shù)是：n2k , j2k 1 時，nnklog nn log ni1i 1(b)由(a)可以得到： 當(dāng)每一次循環(huán)j 都為 2 的冪時， 第六步執(zhí)行的次數(shù)最大，則當(dāng) n3k , j3k2m （其中 3k取整）時，22nnmilog(3 k 1) n log( n 1)i 1i 1(c)用符號表示的算法的時間復(fù)雜性是O( nlog n)已證明 n=2k 的情況，下面證

5、明 n=2k+1 的情況：因?yàn)橛?2k2k122所以 n=2k+1時，第六步執(zhí)行的最大次數(shù)仍是n log n 。(d) 用 符號表示的算法的時間復(fù)雜性是( n) 。當(dāng) n 滿足 j n / 2 取整為奇數(shù)時，算法執(zhí)行的次數(shù)是 n 次，其他情況算法執(zhí)行次數(shù)均大于 n 。(e) O 更適合表示算法的時間復(fù)雜性。因?yàn)楸舅惴〞r間復(fù)雜性從(n) 到 O (n log n) ，而是表示精確階的。1.38對 n 個數(shù)進(jìn)行排序。第5章歸納法5.3（本題不僅有以下一個答案）1.max(n)過程： max(i)if n=1 return a1t=max(i-1)if ai-1>t return ai-1el

6、se return tend if5.6最多次數(shù)：0,n1C(n)c(n1)( n1),n2nn(n 1)C(n)jj 12最少次數(shù)：0, n1C (n )C ( n1)1, n2C(n)=n-15.7參考例 5.15.14(a)不穩(wěn)定，例如：12454524124545241224454512244545可見 SELECTIONSORT 中相等元素的序在排序后改變。(b)(c)(d)(f) 穩(wěn)定5.17(a)利用Pn (x)xPn 1 ( x)a0取 x 3 ，P5 (3)P4 (3)P3 (3)P2 (3)P1 (3)P0 (3)P2 (3)3* P1 (3)437P1(3)3* P0 (

7、3)211P0 (3)3P3 (3)3* P2 (3)1112P4 (3)3* P3 (3)2338P5 (3)3* P4 (3) 5 10195.18(a)p( 2 , 5 )p( 2 , 2 p)( 2 p,1 )y 42 *2y 224 y 12 *2y 1第6章分治6.3輸入： A1,2,n輸出： max,min1.for i=1 to mid2. j=high-i3. if ai>aj, then exchange ai,aj 4.end for5.for i=low to mid6. if ai+1<alow, then exchange alow,ai+1 7.end

8、 for8.for i=mid+1 to high9. if ai+1>ahigh, then exchange ahigh,ai+1 10.end for6.5輸入：一個整數(shù)數(shù)組A1,2,n輸出： sum1.if high-low=1 then2. sum=alow+ahigh 3.else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+sum2 8.end if9.return sum算法需要的工作空間為36.10.3215141511172551111415151725325132151

9、4151117255114151532111725513215141511172551153214151117255132151415111725513215141511172551122517195132451822371512151718192225323745511225171951324518223715121719253251151822374512251719513245182237151217251932511822451537122517195132451822371512251719513218452237151225195145181225195145186.3127133

10、118451617532713311845161753271331184516175327131831451617532713183145161753271318164531175327131816173145531713181627314553彩色代表 i,j 所指的數(shù)字 j 總在 i 前6.36233227184511631219162552141418111219162332452725526314181112191612111418191612 1111 121111181916161819161619193245272552632527324552632527252727274552

11、63455263526352636363111214161819232527324552636.42Quicksort 不是穩(wěn)定的。6.43bcefg均為適應(yīng)的， a、h 不是適應(yīng)的。第 7章動態(tài)規(guī)劃7.1(c),算法 BOTTOMUPSORT7.5字符串 A= ”xzyzzyx ”和 B=”zxyyzxz”的最長公共子序列長度為 4，共有 6 個最長公共子序列，分別是： zyyx zyzz zyzx xyyx xyzz xyzx7.9C1,5=C1,1+C2,5+r1*r2*r6=307C1,5=C1,2+C3,5+r1*r3*r6=252C1,5=C1,3+C4,5+r1*r4*r6=37

12、2C1,5=C1,4+C5,5+r1*r5*r6=260所以最優(yōu)括號表達(dá)式為（M1M2 ） (M3M4)M5)7.150513D1i , j min D0 i, j , D0 i ,1D01, j 120911D4402316200716D10944021820D2 i , j min D1 i, j, D1i ,2D12, j 0716D20944021820D3 i , j min D2 i, j , D2 i ,3D2 3, j 0513D313091144021620D4 i , j min D3 i, j , D3i ,4 D3 4, j 0513D4120911340216207.

13、2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時，運(yùn)行算法會發(fā)生溢出錯誤。第八章貪心算法8.121sa23t由算法從 s 到 t 要選擇先到 a 然后到 t, 其結(jié)果為 4，而從 s 到 t 距離為 2，所以探索不總是產(chǎn)生從 s 到 t 的距離8.131292412145634153139125812921 4435134 12315569241214536415351349129251 4431348129251 44204 12315513164 12315662881216924121453286415351341331354