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

1、算法設(shè)計(jì)技巧與分析答案算法設(shè)計(jì)技巧與分析參考答案第1章算法分析基本概念1.1(a) 6(b)5(c)6(d)61.4算法執(zhí)行了 7+6+5+4+3+2+1=28次比較1.5(a)算法MODSELECTIONSORT執(zhí)行的元素賦值的最少 次數(shù)是0,元素已按非降序排列的時(shí)候達(dá)到最小值。(b)算法 MODSELECTIONSORT執(zhí)行的元素賦值的最多次數(shù)是,元素已按非升序排列的時(shí)候達(dá)到最小值。1.71次1次2次2次2次6次-2次由上圖可以看到執(zhí)行的比較次數(shù)為1+1+2+2+2+6+2=16次。1.11比較971112142比較公空竺晝1.13FTF,TTT,FTF,TFF,FTF1.161.27不能

2、用P關(guān)系來比較n2和100n2增長(zhǎng)的階。n2-lim 2 n100 n2100 0 執(zhí)行該算法，元素比較的最少次數(shù)是n-1。元素已按非降序排列時(shí)候達(dá)到最小值。(b) 執(zhí)行該算法，元素比較的最多次數(shù)是噸嚴(yán)。元素已按非升序排列時(shí)候達(dá)到最大值。(c) 執(zhí)行該算法，元素賦值的最少次數(shù)是0。元素已按非降序排列時(shí)候達(dá)到最小值。(d) 執(zhí)行該算法，元素賦值的最多次數(shù)是空異。元素已按非升序排列時(shí)候達(dá)到最大值。(e) n用o符號(hào)和 符號(hào)表示算法 BUBBLESORT 的運(yùn)行時(shí)間：t O(n2)，t (n)不可以用 符號(hào)來表示算法的運(yùn)行時(shí)間：是用來表示算法的精確階的，而本算法運(yùn)行時(shí)間由線性到平方 排列，因此不能用

3、這一符號(hào)表示。n2不是o(100n2)的，即不能用p關(guān)系來比較n2和100n2增 長(zhǎng)的階。1.32(a)當(dāng)n為2的幕時(shí)，第六步執(zhí)行的最大次數(shù)是:n 2k,j 2k1 時(shí)，nnk log n nlog ni 1i 1(b) 由(a)可以得到：當(dāng)每一次循環(huán)j都為2的幕時(shí)，第六步執(zhí)行的次數(shù)最大，kk則當(dāng)n 3k,j - 2m (其中-取整)時(shí)，22nnmilog(3k 1) nlog(n 1)i 1i 1(c) 用符號(hào)表示的算法的時(shí)間復(fù)雜性是 0(nlog n) 已證明n=2k的情況，下面證明 n=2k+1的情況：kk因?yàn)橛?2 2所以n=2k+1時(shí)，第六步執(zhí)行的最大次數(shù)仍是n log n。(d)

4、用 符號(hào)表示的算法的時(shí)間復(fù)雜性是(n)。當(dāng)n滿足j n/2取整為奇數(shù)時(shí)，算法執(zhí)行的次數(shù)是n次，其他情況算法執(zhí)行次數(shù)均大于n。(e) 0更適合表示算法的時(shí)間復(fù)雜性。因?yàn)楸舅惴〞r(shí)間 復(fù)雜性從(n)到0(nlog n)，而 是表示精確階的。1.38對(duì)n個(gè)數(shù)進(jìn)行排序。第5章歸納法5.3 （本題不僅有以下一個(gè)答案）1. max( n)過程：max(i)if n=1 retur n a1t=max(i-1)if ai-1t return ai-1 else retur n tend if5.6最多次數(shù)：0,n 1C(n)c(n 1) (n 1),n 2n(n 1)2nC(n) jj 1最少次數(shù):0,n1C

5、(n 1) 1,n2C( n)二n-1 5.7參考例5.15.14(a)不穩(wěn)定，例如:可見SELECTIONSORT中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定5.17(a)利用 Fn(x) xPn i(x) ao取x 3，F(xiàn)5(3) P4(3)P5(3)P2(3)R(3)P(3)F2(3)3*R(3)437R(3)3* P(3)211P(3)3B3* P2(3)1 112P4(3) 3* PJ3) 2 338P5(3) 3* 巳(3) 55.18(a)p(2,5)p(2,2)p(2,1)P(2,0)Iy42*2y 224y 12 *2y 1第6章分治10196.3輸入：A1,2,

6、n輸出：max,min1. for i=1 to mid2. j=high-i3. if aiaj, the n excha nge ai,aj4. e nd for5. for i=low to mid6. if ai+1ahigh, the n excha nge ahigh,ai+110. e nd for6.5輸入：一個(gè)整數(shù)數(shù)組 A1,2，,n輸出：sum1.if high-low=1 the n2. sum=alow+ahigh3. else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+

7、sum28. e nd if9. retur n sum算法需要的工作空間為36.10.丄1112厶丄丄丄5Q 111丄2丄丄厶2厶亠亠斗斗12-241-5-丄O,153-11斗1JvJ 與亠丄O丄V-11A厶-2-v213J114A12O*M.111226.316.366.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

8、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=372C1,5=C1,4+C5,5+r1*r5*r6=260所以最優(yōu)括號(hào)表達(dá)式為（M1M2)(M3M4)M5)7.150513Ddi,j minDi,j, D。i,1 D1,j D12091143402162007160 9D1440218 2 0D2【i,j min Dji, j, Ddi,2D/2, j07160 9D244 0218 20D3【i,jmin D2【i, j,D2【i,3 D2【3,j051313 09 11D3440216 2 0D4【i,j min D3【i, j,D3【i,4 D3【4,jD40512 0341 61 39 110 22 07.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時(shí)，運(yùn)行算法會(huì)發(fā)生溢出錯(cuò) 誤。8.12第八章貪心算法由算法從s到t要選擇先到a然后到t,其結(jié)果為4,而從s到t距離為2,所以探索不總是產(chǎn)生從 s到t的