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

共享知識(shí) 分享快樂(lè)算法設(shè)計(jì)技巧與分析參考答案第1章算法分析基本概念1.1(a)6 (b)5 (c)6 (d)61.4算法執(zhí)行了 7+6+5+4+3+2+1=28次比較45 33 24 45 12 12 24 1212 33 24 45 45 12 24 1212 12 24 45 45 33 24 1212 12 12 45 45 33 24 2412 12 12 24 45 33 45 2412 12 12 24 24 33 45 4512 12 12 24 24 33 45 4512 12 12 24 24 33 45 451.5(a)算法MODSELECTIONSORT 執(zhí)行的元素賦值的最少次數(shù)是0,元素已按非降序排列的時(shí)候達(dá)到最小值。(b)算法MODSELECTIONSORT 執(zhí)行的元素賦值的最多頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)次數(shù)是3n(n1),元素已按非升序排列的時(shí)候達(dá)到最小值。21.74 3 12 5 6 7 2 91次 3 41次 3 4 122次 3 4 5 122次 3 4 5 6 122次 3 4 5 6 7 126次 2 3 4 5 6 7 122次 2 3 4 5 6 7 9 12由上圖可以看到執(zhí)行的比較次數(shù)為 1+1+2+2+2+6+2=16次。1.11比較9次24578111213151719比較為6次2 4 5 8 11 13 17 19 7 12 15比較為3次，517194811137121522次，1次比較均為217519111348121571次，共5次21719513114815127由上圖可以得出比較次數(shù)為 5+6+6+9=26次。頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)1.13FTF,TTT,FTF,TFF,FTF1.16執(zhí)行該算法，元素比較的最少次數(shù)是n-1。元素已按非降序排列時(shí)候達(dá)到最小值。(b)執(zhí)行該算法，元素比較的最多次數(shù)是n(n1)。元素已2按非升序排列時(shí)候達(dá)到最大值。執(zhí)行該算法，元素賦值的最少次數(shù)是0。元素已按非降序排列時(shí)候達(dá)到最小值。(d)執(zhí)行該算法，元素賦值的最多次數(shù)是3n(n1)。元素已2按非升序排列時(shí)候達(dá)到最大值。(e)n用O符號(hào)和符號(hào)表示算法BUBBLESORT的運(yùn)行時(shí)間：tO(n2)，t(n)(f)不可以用符號(hào)來(lái)表示算法的運(yùn)行時(shí)間：是用來(lái)表示算法的精確階的，而本算法運(yùn)行時(shí)間由線性到平方排列，因此不能用這一符號(hào)表示。1.27不能用 關(guān)系來(lái)比較 n2和100n2增長(zhǎng)的階。∵limn2120n100n100n2不是o(100n2)的，即不能用關(guān)系來(lái)比較n2和100n2增長(zhǎng)的階。1.32頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)(a)當(dāng)n為2的冪時(shí)，第六步執(zhí)行的最大次數(shù)是：n 2k,j 2k1時(shí)，n nk [logn] nlogni1 i1(b)由(a)可以得到：當(dāng)每一次循環(huán) j都為2的冪時(shí)，第六步執(zhí)行的次數(shù)最大，則當(dāng)n3k,j3k2m（其中3k取整）時(shí)，22nnmi[log(3k1)]nlog(n1)i1i1(c)用符號(hào)表示的算法的時(shí)間復(fù)雜性是O(nlogn)已證明n=2k的情況，下面證明n=2k+1的情況：因?yàn)橛?k2k122所以n=2k+1時(shí)，第六步執(zhí)行的最大次數(shù)仍是nlogn。用符號(hào)表示的算法的時(shí)間復(fù)雜性是(n)。當(dāng)n滿足jn/2取整為奇數(shù)時(shí)，算法執(zhí)行的次數(shù)是n次，其他情況算法執(zhí)行次數(shù)均大于n。O更適合表示算法的時(shí)間復(fù)雜性。因?yàn)楸舅惴〞r(shí)間復(fù)雜性從 (n)到O(nlogn)，而 是表示精確階的。1.38對(duì)n個(gè)數(shù)進(jìn)行排序。頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)第5章歸納法5.3（本題不僅有以下一個(gè)答案）1.max(n)過(guò)程：max(i)ifn=1returna[1]t=max(i-1)ifa[i-1]>treturna[i-1]elsereturntendif5.6最多次數(shù)：0,n 1C(n)c(n 1) (n 1),n 2nn(n 1)C(n) jj 1 2最少次數(shù)：0,n 1C(n)C(n 1) 1,n 2C(n)=n-15.7頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)參考例5.15.14(a)不穩(wěn)定，例如：12 45 45 2412 45 45 2412 24 45 4512 24 45 45可見(jiàn)SELECTIONSORT中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定5.17(a)利用

Pn(x) xPn1(x) a0取x3，P5(3)P4(3)P3(3)P2(3)P1(3)P0(3)P2(3)3*P1(3)437P1(3)3*P0(3)211P0(3)3P3(3)3*P2(3)1112P4(3)3*P3(3)2338P5(3)3*P4(3)510195.18(a)p(2,5)p(2,2p)(2p,1)y42*2y224y12*2y1第6章分治6.3輸入：A[1,2,?n]頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)輸出：max,min1.fori=1tomidj=high-iifa[i]>a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomidifa[i+1]<a[low],thenexchangea[low],a[i+1]7.endfor8.fori=mid+1tohighifa[i+1]>a[high],thenexchangea[high],a[i+1]10.endfor6.5輸入：一個(gè)整數(shù)數(shù)組 A[1,2,?,n]輸出：sum1.ifhigh-low=1thensum=a[low]+a[high]3.elsemid=(low+high)/2sum1=sum(low,mid)sum2=sum(mid+1,high)sum=sum1+sum28.endif頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)9.returnsum算法需要的工作空間為 36.10.頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)3215141511172551111415151725325132151415111725511415153211172551321514151117255115321415111725513215141511172551321514151117255112251719513245182237151215171819222532374551122517195132451822371512171925325115182237451225171951324518223715121725193251182245153712251719513245182237151225171951321845223715122519514518122519514518頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)6.3127 13 31 18 45 16 17 5327 13 31 18 45 16 17 5327 13 31 18 45 16 17 5327 13 18 31 45 16 17 5327 13 18 31 45 16 17 5327 13 18 16 45 31 17 5327 13 18 16 17 31 45 5317 13 18 16 27 31 45 53彩色代表i,j所指的數(shù)字j總在i前6.36頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)2332271845116312191625521414181112191623324527255263141811121916121114181916111211111819161618191616191932452725526325273245526325 2725 27272745526345526352 6352 6363頁(yè)眉內(nèi)容6311 12 14 16 18 19 23 25 27 32 45 52 63共享知識(shí) 分享快樂(lè)6.42Quicksort不是穩(wěn)定的。6.43bcefg均為適應(yīng)的，a、h不是適應(yīng)的。第7章動(dòng)態(tài)規(guī)劃7.1(c),算法BOTTOMUPSORT7.5字符串A=”xzyzzyx”和B=”zxyyzxz”的最長(zhǎng)公共子序列長(zhǎng)度為 4，共有6個(gè)最長(zhǎng)公共子序列，分別是：① zyyx②zyzz③zyzx④xyyx⑤xyzz⑥xyzx7.9C[1,5]=C[1,1]+C[2,5]+r[1]*r[2]*r[6]=307C[1,5]=C[1,2]+C[3,5]+r[1]*r[3]*r[6]=252C[1,5]=C[1,3]+C[4,5]+r[1]*r[4]*r[6]=372C[1,5]=C[1,4]+C[5,5]+r[1]*r[5]*r[6]=260所以最優(yōu)括號(hào)表達(dá)式為（ M1M2）((M3M4)M5)7.150513D1[i,j]min{D0[i,j],D0[i,1]D0[1,j]}120911D4402316200716D10944021820D2[i,j]min{D1[i,j],D1[i,2]D1[2,j]}0716D20944021820D3[i,j]min{D2[i,j],D2[i,3]D2[3,j]}頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)0513130911D340241620D4[i,j]min{D3[i,j],D3[i,4]D3[4,j]}0513120911D4402316207.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時(shí)，運(yùn)行算法會(huì)發(fā)生溢出錯(cuò)誤。第八章貪心算法8.121s a23t由算法從s到t要選擇先到a然后到t,其結(jié)果為4，而從s到t距離為2，所以探索不總是產(chǎn)生從s到t的距離頁(yè)眉內(nèi)容共享知識(shí) 分享快樂(lè)8.131292412145364153513912924121453641535139912201224145364153513413812169241214536284153513413

8129241214536415351348121692412145328641535134138.2