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

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

2、（;），元素已按非升序排列的時(shí)候達(dá)到最小值。1.71次由上圖可以看到執(zhí)行的比較次數(shù)為1+1+2+2+2+6+2=16次1.11由上圖可以得出比較次數(shù)為5+6+6+9=26次1.13FTF,TTT,FTF,TFF,FTF1.16(a) 執(zhí)行該算法，元素比較的最少次數(shù)是n-1。元素已按非降序排列時(shí)候達(dá)到最小值。(b) 執(zhí)行該算法，元素比較的最多次數(shù)是(；一1)。元素已按非升序排列時(shí)候達(dá)到最大值。(c) 執(zhí)行該算法，元素賦值的最少次數(shù)是0。元素已按非降序排列時(shí)候達(dá)到最小值。(d) 執(zhí)行該算法，元素賦值的最多次數(shù)是3。元素已按非升序排列時(shí)候達(dá)到最大值。(e) n用O符號和符號表示算法 BUBBLESO

3、RT的運(yùn)行時(shí) 間：t=0(n2)， tf 】(n)(f) 不可以用。符號來表示算法的運(yùn)行時(shí)間：。是用來表示算法的精確階的，而本算法運(yùn)行時(shí)間由線性到平方排列， 因此不能用這一符號表示。1.27不能用-關(guān)系來比較n2和100n2增長的階1100=02. n lim 2 n :100n2n2不是o(100n2)的，即不能用-關(guān)系來比較n2和100n2增長 的階。1.32(a) 當(dāng)n為2的幕時(shí)，第六步執(zhí)行的最大次數(shù)是： n=2k,j=2kJ1 時(shí)，nn、k _、log n二 n log ni 4i 4(b) 由可以得到：當(dāng)每一次循環(huán)j都為2的幕時(shí)，第六步 執(zhí)行的次數(shù)最大，kk則當(dāng)n =3k,j=32m

4、 (其中-取整)時(shí)，22nn m log(3k-1)= nlog( n-1)i 4i 4(c)用門符號表示的算法的時(shí)間復(fù)雜性是 O(nlog n) 已證明n=2k的情況，下面證明 n=2k+1的情況:2k2k +12 一=12 一因?yàn)橛兴詎=2k+l時(shí)，第六步執(zhí)行的最大次數(shù)仍是n log n。(d)用門符號表示的算法的時(shí)間復(fù)雜性是i(n)。當(dāng)n滿足j =n/2取整為奇數(shù)時(shí)，算法執(zhí)行的次數(shù)是n次，其他情況算法執(zhí)行次數(shù)均大于n(e) O更適合表示算法的時(shí)間復(fù)雜性。因?yàn)楸舅惴〞r(shí)間復(fù) 雜性從門(n)到O(nlog n)，而心是表示精確階的。1.38對n個(gè)數(shù)進(jìn)行排序。第5章歸納法5.3 (本題不僅有以

5、下一個(gè)答案)1. max( n)過程：max(i)if n=1 retur n a1t=max(i-1)if ai-1t return ai-1else retur n tend if5.6最多次數(shù):C(n)二 1c(n-1) + (n-1),n Z2n(n -1)2nC(n)八j #最少次數(shù):C(n)0,n =1C(n 1)+1,n 王2C( n)二n-1 5.7參考例5.15.14(a)不穩(wěn)定，例如:12454524112454524122445451r12244545可見SELECTIONSORT中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定5.17(a)利用Fn(x)二 xR

6、(x) ao取 x=3，R(3)t R(3)t F3(3)t B(3)t R(3)t R(3)F2(3)=3*R(3)+4=37 R(3) =3* F0(3) + 2 = 1仆 F0(3)=3P3(3)=3*P(3) +1=112t 巳(3)=3* PJ3)+2 = 338t 巳(3) =3* 巳(3)+5 = 10195.18(a)p(2, 5) p (2/2P (2p1 )y=42*2 - y=22=4 y=12*2 y=1第6章分治6.3輸入：A1,2,n輸出： max,min1. for i=1 to mid2. j=high-i3. if aiaj, then exchange ai

7、,aj4. end for5. for i=low to mid6. if ai+1ahigh, then exchange ahigh,ai+110. end for6.5輸入：一個(gè)整數(shù)數(shù)組 A1,2,n輸出： sum1.if high-low=1 then2. sum=alow+ahigh3. else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+sum28. end if9. return sum算法需要的工作空間為 36.10.1225171951324518223715121517181

8、922253237455112251719513212171925325145182237151518223745122517121725J12251225122512251951321932514518221822453715153732223715195119511717195145181845221845195145183715326.31271331184516175327133118451617532713311845161753271318314516175327131831451617532713181645311753271318161731455317131816273145

9、53彩色代表i,j所指的數(shù)字j總在i前6.362332271845116312191625521414181112191623324527255263141811121916121114181916121111121111181916161819161619193245272552632527324552632527252727274552634552635263526363VIFvVIFvvVvVV11121416181923252732455263636.42Quicksort不是穩(wěn)定的。6.43bcefg均為適應(yīng)的，a、h不是適應(yīng)的第7章動(dòng)態(tài)規(guī)劃7.1(c),算法 BOTTOMUPSOR

10、T7.5字符串A= ”xzyzzyx”和B=”zxyyzxz”的最長公共子序列長度為4,共有6個(gè)最長公共子序列，分別是： 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=372C1,5=C1,4+C5,5+r1*r5*r6=260所以最優(yōu)括號表達(dá)式為(M1M2)(M3M4)M5)7.150513、DUjmi nDi, j,D0i,1 + D1, j12 0 9 11434021620*0716、009 coD1 =44 021 8 2 0D2i,j =minUi, j,皿,2 D12, j廣0716 C 0 9 00D2 =44 027.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時(shí)，運(yùn)行算法會(huì)發(fā)生溢出錯(cuò)誤。