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

1、算法設(shè)計(jì)技巧與分析參考答案第1章算 法分析基本概念 1.1 (a)6 (b)5 (c)6 (d)6 1.4算法執(zhí) 行了 7+6+5+4+3+2+仁28次比較 45 33 24 45 12 12 24 12 1233 24 45 45 12 24 1212 12 24 45 45 33 24 1212 12 12 45 45 3324 2412 2412 12 45 33 45 2412 12 12 24 24 33 45 4512 1212 24 24 33 45 4512 12 12 24 24 33 45 451.5 算法MODSELECTIONSOR執(zhí)行的元素賦值的最少次數(shù)是0,元素已按

2、非降序排列的時(shí)候達(dá)到最小值。(b)算法MODSELECTIONSORT執(zhí)行的元素賦值的最多3n(n 1)次數(shù)是,元素已按非升序排列的時(shí)候達(dá)到最小值。21.74 3 12 5 6 7 2 91 次 3 41 次 3 4 12 2 次 3 4 5 123 4 5 6 12 2 次 7 123 4 5 6 2 次 2 3 4 5 6 7 12 6 次 7 923 4 5 6 12 2次由上圖可以看到執(zhí)行的比較次數(shù)為1+1+2+2+2+6+2=16次。1.11 比較 9 次 2 4 5 7 8 11 12 13 1517 19 比較為6次 2 4 5 8 11 13 17 19 7 12 15 比較為

3、3次，2 5 17 19 4 8 11 13 7 12 15 2次，1 次 2 17 5 19 11 13 4 8 12 15 7 比較均為1次，共5次 2 17 19 5 13 11 4 8 15 12 7由上圖可以 得出比較次數(shù)為 5+6+6+9=26次。1.13 FTF,TTT,FTF,TFF,FTF 1.1執(zhí)!(行該算法，元素比較的最少次數(shù)是n-1。元素已按非降序排列時(shí)候達(dá)到最小值。(b)執(zhí)行該算法，元素比較的最多次數(shù)是。元素已2按非升序排列時(shí)候達(dá)到最大值。 (C)執(zhí)行該算法，元素賦值的最少次數(shù)是 0。元素已按非降序排列時(shí)候達(dá)到最小值。(d)執(zhí)行該算法，元素賦值的最多 次數(shù)是。元素已2

4、按非升序排列時(shí)候達(dá)到 最大值。(e)用0符號(hào)和符號(hào)表示算法 BUBBLESORT的運(yùn)行時(shí) R 間:， 2(f)不可以用符號(hào)來(lái)表示算法的運(yùn)行時(shí)間：是用來(lái)表示算法的精確階的，而本算法運(yùn)行時(shí)間由線性到平方 排列，因此不能用這一符號(hào)表示。 1.27 不能用關(guān)系來(lái)比較和增長(zhǎng)的階。22 100nn2n1 /22 不是的，即不能用關(guān)系來(lái)比較和增長(zhǎng) 222 o(100n)1OOnn 的階。 1.32(a)當(dāng)n為2的冪時(shí)，第六步執(zhí)行的最大次數(shù)是：時(shí)，kk In 2J 2nn(b)由(a)可以得到：當(dāng)每一次循環(huán)j都為2的冪時(shí)，第六步執(zhí) 行的次數(shù)最大，kk33則當(dāng)(其中取整)時(shí)，22nnkm log(3 1) nl

5、ogfn l)ii li l(c)用符號(hào)32 37 45 5112 25 17 19 51 32 45 18 22 37 1512 17 19 25 32 5132 37 45 5112 25 17 19 51 32 45 18 22 37 1512 17 19 25 32 510000表示的算法的時(shí)間復(fù)雜性是 O(nlogn) kk已 證明n=2的情況，下面證明 n=2+1的情 況：因?yàn)橛兴詎=2+1時(shí)，第六步執(zhí)行的 最大次數(shù)仍是n log n。(d)用符號(hào)表示的算法的時(shí)間復(fù)雜性是。當(dāng)滿足取整為奇數(shù)時(shí)，算法執(zhí)行的次數(shù)是次，其他情況算法執(zhí)行次數(shù)均大于。n(e)O更適合表示算法的時(shí)間復(fù)雜性。因

6、為本 算法時(shí)間復(fù)雜性從到，而是表示精確階的。1.38對(duì)個(gè)數(shù)進(jìn)行排序。n第5章歸納法 5.3 (本題不僅有以下一個(gè)答案)1.max(n)過(guò)程：max(i) if n=1 return a1 t=max(i-1) if ai-1t return ai-1 else return t end if 5.6 最多次數(shù)：0川1 qn)1)価1)川2 nn(n 1)C(n) j 2j 1最少次數(shù):01 C(n) C(n 1 12 C(n)=n-1 5.7參考例5.1 5.14 (a)不穩(wěn)定，例如：12 45 452412 45 45 2412 24 45 4512 24 45 45 可見(jiàn)SELECTION

7、SOR中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定 5.17 (a)利 用10 取，x 3P(3) P(3) P(3) P(3) P(3) P(3)543210PP(3) 3*P(3) 1 112 P3) 3*P(3) 2 338 P(3) 3* P(3) 5 10193243545.18(a)p即)p(2 ,2p) (2p,l)222y 4*2 y 2 4 y 1*2 y 1 第 6 章分治6.3 輸入：A1,2,n輸出：max,min 1for i=1 to mid 2. j=highi 3. if aiaj, then exchange ai,aj 4.end for 5.f

8、or i=low to mid 6. if ai+1valow, then exchange alow,ai+1 7. end for 8.for i=mid+1 to high 9. if ai+1ahigh, then exchange ahigh,ai+1 10.end for 6.5 輸入：一個(gè)整數(shù) 數(shù)組 A1,2,小輸出：sum 1.if high-low=1 then 2. sum=alow+ahigh 3. else 4. mid=(low+high)/2 5 sum1=sum(low,mid) 6 sum2=sum(mid+1,high) 7. sum=sum1+sum2end

9、 ifreturn sum算法需要的工作空間為3 6.10.32 15 14 15 11 17 25 5111141515 17 25 32 513215141511 17 25 5114 15 15 32 11 17 25 5132 15 14 15 11 17 25 5115 32 14 15 11 17 25 5132 15 14 15 11 17 25 5132 15 14 15 1117 25 5112 25 17 19 51 32 45 18 22 37 1512 15 17 18 19 22 2515 18 22 37 4512 25 17 19 51 32 45 18 22 3

10、7 1512 17 25 19 3215 18 22 37 4512 25 17 19 51 32 45 18 22 37 1512 17 25 19 3251 18 22 4515 3712 2517 19 51 32 45 18 22 37 151225 17 1951 32 18 4522 37 151225 19 51 45 1812 25 19 5145186.3127 13 31 18 45 16 17 5327 13 31 18 45 16 17 5327 13 31 1845 16 17 5313 18 27 31 45 16 17 532713 18 3145 16 17 5

11、327 13 18 16 45 31 17 5327 13 18 161731 45 5317 13 18 1627 31 45 53彩色代表i,j所指的數(shù)字j總在i前6.3623 32 27 18 45 11 63 12 19 16 25 52 14 14 11 1218 19 1623 3245 27 25 52 63 14 18 11 12 19 16 12 11 14 18 19 16 12 11 11 1211 1118 19 16 16 18 19 16 16 19 19 32 45 27 25 52 6325 27 32 45 52 63 25 27 25 27 27 27 45

12、 52 63 45 52 63 5263 52 6363 63 11 12 14 16 18 19 23 25 27 32 45 52 636.42 Quicksort 不是穩(wěn)定的。6.43 bcefg 均為適應(yīng)的，a、h不是適應(yīng)的。第7章動(dòng)態(tài)規(guī)劃7.1 ,算法BOTTOMUPSORT 75字符串A=” xzyzzy和”=” zxyyzxZ勺最長(zhǎng)公共子序列長(zhǎng)度為4,共有6個(gè)最長(zhǎng)公共子序列，分別是：zyyxzyzzzyzxxyyxxyzzxyzx 7.9C1,5=C1,1+C2,5+r1*r2*r =307C1,5=C1,2+C3,5+r1*r3*r =252C1,5=C1,3+C4,5+r1*

13、r4*r6=372C1,5=C1,4+C5,5+r1*r5*r6=260 所以最優(yōu)括號(hào)表達(dá) TOC o 1-5 h z 式 為(M1M2)(M3M4)M5)7ij minD譏D1J D1000434021620067109 D 144021820DiJ minDiJ,DL2 D2J2111067109 D 244021820DiJ minDiJLDL3 D訓(xùn) 3222344021620129 12 9 122 4 2 4129 12 9 122 4 2 4Di,j minDijLDt4 D4j43 3 34340216207.210 1 2 3 4 5 6 7 8 9

14、 10 11 0 0 00 0 0 0 0 0 0 0 0 0 1 0 0 3 3 3 3 3 3 3 3 3 3 2 00 3 4 4 7 7 7 7 7 7 7 3 0 0 3 4 4 7 7 8 9 9 12 12 4 0 0 3 4 4 7 7 8 10 11 12 147.23 當(dāng)物品體積為負(fù)值時(shí)，運(yùn)行算法會(huì)發(fā)生溢出錯(cuò)誤。第八章貪心算法 &121 s a 23 t由算法從s到t要選擇先到a然后到t,其 結(jié)果為4，而從s到t距離為2，所以探索 不總是產(chǎn)生從s到t的距離8.1312 9 12 2 4 5 4 316 4 15 35 138 91255433416164415153535 13134129 20:8 16 129 122 49 122 455 28431 64 31 644 15153 5133 54 13134 138 12 169 122 454 3281 6415 3134 138.23 （共有4棵最小生成樹(shù)，此處僅舉一例） TOC o 1-5 h z 1 3 51 3