算法設(shè)計(jì)與分析課后答案

習(xí)題1.15..證明等式gcd(m,n)=gcd(n,mmodn)對(duì)每一對(duì)正整數(shù)m,n都成立.Hint:根據(jù)除法的定義不難證明：?如果d整除u和v,那么d一定能整除u±v;?如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.對(duì)于任意一對(duì)正整數(shù)m,n,若d能整除m和n,那么d一定能整除n和r=mmodn=m-qn；顯然，若d能整除n和r，也一定能整除m=r+qn和n。數(shù)對(duì)(m,n)和(n,r)具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故gcd(m,n)=gcd(n,r)對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字，歐幾里得算法將會(huì)如何處理？該算法在處理這種輸入的過程中,上述情況最多會(huì)發(fā)生幾次？Hint:對(duì)于任何形如0<=m<n的一對(duì)數(shù)字,Euclid算法在第一次疊代時(shí)交換m和n,即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次.a.對(duì)于所有1Wm,nW10的輸入,Euclid算法最少要做幾次除法?(1次)對(duì)于所有1Wm,nW10的輸入,Euclid算法最多要做幾次除法?(5次)gcd(5,8)習(xí)題1.21.(農(nóng)夫過河)pggPwgwPwcwcPwgcPwgcwtP一農(nóng)夫W—狼2.(過橋問題):PwccG一山羊C一白菜pgcgpg2f25,105.10(0)⑵(L5)(17)卻時(shí)。11,2,5,10---分別代表4個(gè)人,f一手電筒4.對(duì)于任意實(shí)系數(shù)a,b,c,某個(gè)算法能求方程axA2+bx+c=0的實(shí)根，寫出上述算法的偽代碼(可以假設(shè)sqrt(x)是求平方根的函數(shù))算法Quadratic(a,b,c)//求方程axA2+bx+c=0的實(shí)根的算法〃輸入：實(shí)系數(shù)a,b,c〃輸出:實(shí)根或者無解信息Ifa尹0D—b*b-4*a*cIfD>0temp—2*ax1—(-b+sqrt(D))/tempx2—(-b-sqrt(D))/tempreturnx1,x2elseifD=0return-b/(2*a)elsereturn“norealroots"else//a=0ifb尹0return-c/belse//a=b=0ifc=0return“norealnumbers"elsereturn“norealroots"5.描述將十進(jìn)制整數(shù)表達(dá)為二進(jìn)制整數(shù)的標(biāo)準(zhǔn)算法用文字描述用偽代碼描述解答：a?將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)的算法輸入：一個(gè)正整數(shù)n輸出：正整數(shù)n相應(yīng)的二進(jìn)制數(shù)第一步：用n除以2,余數(shù)賦給Ki(i=0,1,2...),商賦給n第二步：如果n=0,則到第三步，否則重復(fù)第一步第三步：將Ki按照i從高到低的順序輸出b,偽代碼算法DectoBin(n)//將十進(jìn)制整數(shù)n轉(zhuǎn)換為二進(jìn)制整數(shù)的算法〃輸入：正整數(shù)n〃輸出：該正整數(shù)相應(yīng)的二進(jìn)制數(shù)，該數(shù)存放于數(shù)組Bin[1...n]中i=1whilen!=0do(Bin[i]=n%2;n=(int)n/2;i++;}whilei!=0do(printBin[i];i--;}9.考慮下面這個(gè)算法，它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略)對(duì)這個(gè)算法做盡可能多的改進(jìn).算法MinDistance(A[0..n-1])〃輸入:數(shù)組A[0..n-1]〃輸出:thesmallestdistancedbetweentwoofitselementsdmin—ocfori—0ton—2doforj—E+1t□冗一1dotemp—/IE—A\jif<dmindmin—tempreturndmin習(xí)題1.3考慮這樣一個(gè)排序算法,該算法對(duì)于待排序的數(shù)組中的每一個(gè)元素，計(jì)算比它小的元素個(gè)數(shù)，然后利用這個(gè)信息，將各個(gè)元素放到有序數(shù)組的相應(yīng)位置上去.forE。to—1doCount\i]—0fori—0ton—2doforj—E+1ton—1doifA[i]<A[j]Count[j—Co7tnt[j\+1elseC(7imt\i—Count補(bǔ)+1forE—Uton—1doSCounti\]—A'i應(yīng)用該算法對(duì)列表60,35,81,98,14,47排序該算法穩(wěn)定嗎？該算法在位嗎？解：a.該算法對(duì)列表60,35,81,98,14,47排序的過程如下所示:ArrayA0..56035SI9S1447hiiriallyCount0(J0000Afterpassi—0Count3(]1100Aft(?rpassi—1Count12201Afterpassi=2Count4301Aft(?rpassi—3Count501Afterpassi=4Count02Finalsr.ar.cCount314502ArrayS0..514354760SI!)S該算法不穩(wěn)定.比如對(duì)列表2,2*排序該算法不在位.額外空間forSandCount[]4.（古老的七橋問題）習(xí)題1.41.請(qǐng)分別描述一下應(yīng)該如何實(shí)現(xiàn)下列對(duì)數(shù)組的操作,使得操作時(shí)間不依賴數(shù)組的長(zhǎng)度.刪除數(shù)組的第i個(gè)元素(1<=i<=n)刪除有序數(shù)組的第i個(gè)元素(依然有序)hints:Replacetheithelementwiththelastelementanddecreasethearraysizeof1Replacetheithelementwithaspecialsymbolthatcannotbeavalueofthearray’selement(e.g.,0foranarrayofpositivenumbers)tomarktheithpositionisempty.(—lazydeletion")第2章習(xí)題2.1對(duì)下列斷言進(jìn)行證明:(如果是錯(cuò)誤的，請(qǐng)舉例)如果t(n)GO(g(n),則g(n)G。(t(n))a>0時(shí),。(ag(n))=0(g(n))解：這個(gè)斷言是正確的。它指出如果t(n)的增長(zhǎng)率小于或等于g(n)的增長(zhǎng)率，那么g(n)的增長(zhǎng)率大于或等于t(n)的增長(zhǎng)率由t(n)Wc?g(n)forallnNn0,wherec>01…一一則V：(-)t(n)<g(n)forallnNn0c這個(gè)斷言是正確的。只需證明。(以g(n))c0(g(n)),0(g(n))c0(ag(n))。設(shè)f(n)G0(ag(n)),則有：f(n)<cag(n)foralln>=n0,c>0f(n)<C]g(n)foralln>=n0,c1=ca>0即：f(n)G0(g(n))又設(shè)f(n)G0(g(n))，則有：f(n)<cg(n)foralln>=n0,c>0cf(n)<—^g(n)=cag(n)foralln>=n0,c1=c/a>0a1即：f(n)e0(ag(n))證明本節(jié)定理對(duì)于下列符號(hào)也成立：Q符號(hào)0符號(hào)證明：a。weneedtoproofthatift(n)e。(g(n))andt(n)e。(gjn)),thent(n)+t(n)112212e。(max{g1(n),g2(n)})。由ti(n)e。(g1(n)),t(n)Ncg](n)foralln>=n1,wherec1>0由t2(n)e。(g2(n)),T2(n)Nc2g2(n)foralln>=n2,wherec2>0那么，取c>=min{c1,c2},當(dāng)n>=max{n1,n2}時(shí)：t1(n)+t2(n)Nc1g1(n)+c2g2(n)Ncg1(n)+cg2(n)Nc[g1(n)+g2(n)]Ncmax(g1(n),g2(n)}所以以命題成立。t1(n)+t2(n)e0(max(g1(n),g2(n)))證明：由大的定義知，必須確定常數(shù)c1、c2和n0,使得對(duì)于所有n>=n0,有：c1max((g1(n),g2(n))<t1(n)+12(n)<max(g1(n),g2(n))TOC\o"1-5"\h\z由t1(n)e0(g1(n))知，存在非負(fù)整數(shù)a1,a2和n1使：a1*g1(n)<=t](n)<=a2*g1(n)(1)由t2(n)e0(g2(n))知，存在非負(fù)整數(shù)b1,b2和n2使:b1*g2(n)<=t2(n)<=b2*g2(n)(2)(1)+(2):a1*g1(n)+b1*g2(n)<=t1(n)+t2(n)<=a2*g1(n)+b2*g2(n)令c1=min(a1,b1),c2=max(a2,b2),則C1*(g1+g2)<=t1(n)+t2(n)<=c2(g1+g2)(3)不失一般性假設(shè)max(g1(n),g2(n))=g1(n).顯然，g1(n)+g2(n)<2g1(n),即g1+g2<2max(g1,g2)又g2(n)>0，g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。則(3)式轉(zhuǎn)換為：C1*max(g1,g2)<=t1(n)+t2(n)<=c2*2max(g1,g2)所以當(dāng)c1=min(a1,b1),c2=2c2=2max(c1,c2)，n0=max(n1,n2)時(shí)，當(dāng)n>=n0時(shí)上述不等式成立。證畢。習(xí)題2.41.解下列遞推關(guān)系(做a,b)a.Jx(n)=x(n-1)+5當(dāng)n>1時(shí)Ix(1)=0

解:rt.t:'n=x:'n—])+5fui'n.>L需：]:=UT(n.：=t(n.—]：+5=tfn.—2：+5]+5=tfn.—2：+5-2=■需m—3：+5]+5Mt:'n-3)+5■3444=t{n.—i)+5■t=…=t[]：■+5■fn.-1：■=5(n.—]I.b.x(n)=3x(n—1)當(dāng)n>1時(shí)x(1)=4解:b.解:對(duì)于計(jì)算n!的遞歸算法F(n),建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求解。解:'L=C：n.—1：，+Lf；：U：=1[thereis兀cd]butnmltipHcnti。]、Iwhc-nJ?=LJ：,C\n)=C\n_])+]=[C\n-2；+1]+]=C[n-2)+2==C(n.—i)+i==C：U：+n.=1H-n.3.考慮下列遞歸算法，該算法用來計(jì)算前n個(gè)立方的和：S(n)=13+23+…+股。算法S(n)〃輸入：正整數(shù)n〃輸出：前n個(gè)立方的和ifn=1return1elsereturnS(n-1)+n*n*na.建立該算法的基本操作次數(shù)的遞推關(guān)系并求解

如果將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比，你做何評(píng)價(jià)?解：a.reciim-iictn.LetM:'n.jbetheiniinberofinidtijilicrTtions]t]?ulebyt]i(-n]舟We]i?ive+]lsr(-cum-lirer(-h\ti()]itorit:reciim-iictAf:-fi'；Af:-fi'；=_Un.—1.：+[A/:]：=U.7.a.請(qǐng)基于公式2n=2n-1+2n-1，設(shè)計(jì)一個(gè)遞歸算法。當(dāng)n是任意非負(fù)整數(shù)的時(shí)候，該算法能夠計(jì)算2n的值。b.建立該算法所做的加法運(yùn)算次數(shù)的遞推關(guān)系并求解C.為該算法構(gòu)造一棵遞歸調(diào)用樹，然后計(jì)算它所做的遞歸調(diào)用次數(shù)。d.對(duì)于該問題的求解來說，這是一個(gè)好的算法嗎？解：a.算法power(n)〃基于公式2n=2n-1+2n-1,計(jì)算2n〃輸入:非負(fù)整數(shù)n//輸出:2n的值Ifn=0return1Elsereturnpower(n-1)+power(n-l)b._4(n；i='2A[n-1)+k.4(0)=0.A{n)=(2A[r).-1)+1=2[2.4(n-2)+!]+!=''l2A[n-2j+2+1=22[2A(n一3)+1|+?+1=^A[n-3)+22+2+1???=wmf+/'+212+...+12Tl-4(i)；i+2Tl-1+2+...+1=/1+曾q+...+1=一1.

C(n)=W2i=2n+1—1i=0考慮下面的算法算法Min1(A[0..n-1])//輸入:包含n個(gè)實(shí)數(shù)的數(shù)組A[0..n-1]Ifn=1returnA[0]Elsetemp—Min1(A[0..n-2])IftempWA[nT]returntempElsereturnA[n-1]該算法計(jì)算的是什么？建立該算法所做的基本操作次數(shù)的遞推關(guān)系并求解解：計(jì)算的給定數(shù)組的最小值b.C(n)=C(n—1)+10forallb.C(n)=C(n—1)+10foralln>1n=1Ifl=rreturnA[l]Elsetemp1—Min2(A[l..(l+r)/2])Temp2—Min2(A[l..(l+r)/2]+1..r)Iftemp1Wtemp2returntemp1Elsereturntemp2建立該算法所做的的操作次數(shù)的遞推關(guān)系并求解算法Min1和Min2哪個(gè)更快?有其他更好的算法嗎？解：a.C[n)=+C(+1forn>LC(l)=0.

Solvingilforn=2kbybackwaulsul)fiLiLuLiansyiclilsthefollowing:C((2k)=2G(2fe-1)+1=2[2Cf2fc-2)+1]+1=&片T)+2+1=22[(2C(2k-3)+1]+2+1="(7(砂7)+?+2+1+2l'2+...++2l'2+...+1算法SortAnalysis(A[0..n-1])//input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[0..n-1]//output:所做的關(guān)鍵比較的總次數(shù)count—0fori—1ton-1dov—A[i]j—i-1whilej>0andA[j]>vdocount—count+1A[j+1]—A[j]j—j+1A[j+1]—vreturncount比較計(jì)數(shù)器是否插在了正確的位置?如果不對(duì)，請(qǐng)改正.解:應(yīng)改為：算法SortAnalysis(A[0..n-1])//input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[0..n-1]//output:所做的關(guān)鍵比較的總次數(shù)count—0fori—1ton-1dov—A[i]j—i-1whilej>0andA[j]>vdocount—count+1A[j+1]—A[j]j—j+1ifj>=0count=count+1A[j+1]—vreturncount習(xí)題3.1a.設(shè)計(jì)一個(gè)蠻力算法，對(duì)于給定的X0,計(jì)算下面多項(xiàng)式的值：P(x)=anxn+an_1xn-i+^+a1x+a0并確定該算法的最差效率類型.如果你設(shè)計(jì)的算法屬于0(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法.C.對(duì)于該問題來說，能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢？解：AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)//由高幕到低幕用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低幕到高幕的常系數(shù)，以及定值x//輸出：多項(xiàng)式p在給定點(diǎn)x的值p=0.0fori=nto0dopower=1forj=1toidopower=power*xp=p+P[i]*powerreturnp算法效率分析：基本操作:兩個(gè)數(shù)相乘，且M(n)僅依賴于多項(xiàng)式的階nM(n)=￡￡1=&也eO(n2)i=0j=1i=0thaabovealgorithmsisveryinefficient,becausewerecomputepowersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputexibyusingxi-1.AlgorithmsBetterBruteForcePolynomialEvaluation(P[0..n],x)//由高幕到低幕用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低幕到高幕的常系數(shù)，以及定值x//輸出：多項(xiàng)式p在給定點(diǎn)x的值P=P[0]power=1fori—1tondopower—power*xp—p+P[i]*powerreturnp基本操作乘法運(yùn)算總次數(shù)M(n):M(n)=￡2=2ne0(n)i=1不行.因?yàn)橛?jì)算任意一個(gè)多項(xiàng)式在任意點(diǎn)x的值，都必須處理它的n+1個(gè)系數(shù).例如:(x=1,p(x)=a+a1+..+a1+a0,至少要做n次加法運(yùn)算)應(yīng)用選擇排序?qū)π蛄衑xample按照字母順序排序.TOC\o"1-5"\h\z\EXAMPLEA\XEMPLEAE1|XMPLEAEE\MPLXAEEL\PMXAEELM|PXAEELMP\X選擇排序是穩(wěn)定的嗎？(不穩(wěn)定)用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的0(n2)效率？Yes.Bothoperation—findingthesmallestelementandswappingit-canbedoneasefficientlywiththelinkedlistaswithanarray.a.請(qǐng)證明，如果對(duì)列表比較一遍之后沒有交換元素的位置，那么這個(gè)表己經(jīng)排好序了，算法可以停止了.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a.請(qǐng)證明改進(jìn)的算法最差效率也是平方級(jí)的.Hints:第i趟冒泡可以表示為：7…1務(wù)廠：，jlj-Li-]&三…三】Intheirfinalpofiitions如果沒有發(fā)生交換位置，那么：W—禹—』訐]—JJJ—AlgorithmsBetterBubblesort(A[0..n-1])〃用改進(jìn)的冒泡算法對(duì)數(shù)組A[0..n-1]排序//輸入:數(shù)組A[0..n-1]〃輸出:升序排列的數(shù)組A[0..n-1]count—n-1〃進(jìn)行比較的相鄰元素對(duì)的數(shù)目flag^true〃交換標(biāo)志whileflagdoflag—falsefori=0tocount-1doifA[i+1]<A[i]swap(A[i],A[i+1])flag—truecount—count-1c最差情況是數(shù)組是嚴(yán)格遞減的，那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來的冒泡排序.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)習(xí)題3.21.對(duì)限位器版的順序查找算法的比較次數(shù)：在最差情況下在平均情況下.假設(shè)成功查找的概率是p(0<=p<=1)Hints:土Cwors(n)=n+1b.在成功查找下，對(duì)于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比較次數(shù)是i.在查找不成功時(shí)，比較次數(shù)是n+1,可能性是1-p.r,E+2，E+…+e?日+…+私R+m+1：,，(]nnnn—1+2+…+i+…+n]+(n+1)(1—P)nTlZ2給出一個(gè)長(zhǎng)度為n的文本和長(zhǎng)度為m的模式構(gòu)成的實(shí)例，它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出，對(duì)于這樣的輸入需要做多少次字符比較運(yùn)算.Hints:文本:由n個(gè)0組成的文本模式:前m-1個(gè)是0,最后一個(gè)字符是1比較次數(shù):m(n-m+1)為蠻力字符匹配算法寫一個(gè)偽代碼，對(duì)于給定的模式，它能夠返回給定的文本中所有匹配子串的數(shù)量.AlgorithmsBFStringmatch(T[0..n-1],P[0..m-1])〃蠻力字符匹配〃輸入:數(shù)組T[0..n-1]—長(zhǎng)度為n的文本，數(shù)組P[0..m-1]—長(zhǎng)度為m的模式〃輸出:在文本中匹配成功的子串?dāng)?shù)量count—0fori—0ton-mdoj—0whilej<mandP[j]=T[i+j]j—j+1ifj=mcount—count+1returncount如果所要搜索的模式包含一些英語中較少見的字符，我們應(yīng)該如何修改該蠻力算法來利用這個(gè)信息.Hint:每次都從這些少見字符開始比較，如果匹配，則向左邊和右邊進(jìn)行其它字符的比較.習(xí)題4.1a.為一個(gè)分治算法編寫偽代碼,該算法求一個(gè)n個(gè)元素?cái)?shù)組中最大元素的位置.b?如果數(shù)組中的若干個(gè)元素都具有最大值,該算法的輸出是怎樣的呢？c?建立該算法的鍵值比較次數(shù)的遞推關(guān)系式并求解?d?請(qǐng)拿該算法與解同樣問題的蠻力算法做一個(gè)比較解：a.AlgorithmsMaxIndex(A[l..r]){Input:AportionofarrayA[0..n-1]betweenindiceslandr(l<r)Output:TheindexofthelargestelementinA[l..r]ifl=rreturnlelsetemp1^MaxIndex(A[l..|(Z+r)/2])temp2^MaxIndex(A[(Z+r)/2..r])ifA[temp1]>A[temp2]returntemp1elsereturntemp2}返回?cái)?shù)組中位于最左邊的最大元素的序號(hào).鍵值比較次數(shù)的遞推關(guān)系式：C(n)=C(四2J)+C(回2)+1forn>1C(1)=0設(shè)n=2k，C(2k)=2C(2k-1)+1=2[2C(2k-2)+1]+1=22C(2k-2)+2+1=2[22C(2k-3)+1]+2+1=23C(2k-3)+22+2+1=...=2iC(2k-i)+2i-1+2i-2+...+2+1=...=2kC(2k-k)+2k-1+2k-2+...+2+1=2k—1=n-1可以證明C(n)=n-1對(duì)所有n>1的情況都成立(n是偶數(shù)或奇數(shù))比較的次數(shù)相同，但蠻力算法不用遞歸調(diào)用。2、a.為一個(gè)分治算法編寫偽代碼，該算法同時(shí)求出一個(gè)n元數(shù)組的最大元素和最小元素的值。b?請(qǐng)拿該算法與解同樣問題的蠻力算法做一個(gè)比較。c?請(qǐng)拿該算法與解同樣問題的蠻力算法做一個(gè)比較。解答：a.同時(shí)求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個(gè)部分中的最大值和最小值，然后經(jīng)過比較就可以得到整個(gè)問題的最大值和最小值。算法MaxMin(A[l..r],Max,Min)〃該算法利用分治技術(shù)得到數(shù)組A中的最大值和最小值〃輸入：數(shù)值數(shù)組A[l..r]〃輸出：最大值Max和最小值Minif(r=l)Max—A[l]；Min—A[l];//只有一個(gè)元素時(shí)elseifr~l=1〃有兩個(gè)元素時(shí)ifA[l]<A[r]Max—A[r];Min—A[l]elseMax—A[l];Min—A[r]else//r—1>1MaxMin(A[l,(l+r)/2],Max1,Min1);//遞歸解決前一部分MaxMin(A[(l+r/)2..r],Max2,Min2);//遞歸解決后一部分ifMax1<Max2Max=Max2//從兩部分的兩個(gè)最大值中選擇大值ifMin2<Min1Min=Min2;//從兩部分的兩個(gè)最小值中選擇小值}b.假設(shè)n=2k,比較次數(shù)的遞推關(guān)系式：C(n)=2C(n/2)+2forn>2C(1)=0,C(2)=1C(n)=C(2k)=2C(2k-1)+2=2[2C(2k-2)+2]+2=22C(2k-2)+22+2=22[2C(2k-3)+2]+22+2=23C(2k-3)+23+22+2...=2k-1C(2)+2k-1+2k-2+...+2//C(2)=1=2k-1+2k-1+2k-2+...+2〃后面部分為等比數(shù)列求和=2k-1+2k-2〃2(k-1)=n/2,2k=n=n/2+n-2=3n/2—2b,蠻力法的算法如下：算法simpleMaxMin(A[l..r])//用蠻力法得到數(shù)組A的最大值和最小值〃輸入：數(shù)值數(shù)組A[l..r]〃輸出：最大值Max和最小值MinMax=Min=A[l];fori=l+1tordoifA[i]>MaxMax—A[i];elseifA[i]<MinMin—A[i]returnMax,Min}時(shí)間復(fù)雜度t(n)=2(n-1)算法MaxMin的時(shí)間復(fù)雜度為3n/22,simpleMaxMin的時(shí)間復(fù)雜度為2n2,都屬于O(n)，但比較一下發(fā)現(xiàn)，MaxMin的速度要比simpleMaxMin的快一些。6.應(yīng)用合并排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序.EXAMPLE8.a.對(duì)合并排序的最差鍵值比較次數(shù)的遞推關(guān)系式求解.(forn=2k)建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關(guān)系式求解.(forn=2k)對(duì)于4.1節(jié)給出的合并排序算法，建立它的鍵值移動(dòng)次數(shù)的遞推關(guān)系式.考慮了該算法的鍵值移動(dòng)次數(shù)之后，是否會(huì)影響它的效率類型呢？解：a.遞推關(guān)系式見4.1節(jié).C^(2fc)=2Cu,(2fc-1)+2fc-l=2[2C^(2fc-2)+-1]+2fc-1=22Cw(2k-'2)+2■2fc-2-1=2勺2Gb(2」，)+渺3-l]+2-2fc-2-l=2Y；.iL,(2fc-'s)+3■2fc-22-2-1???=+i：2k-￥一1--21-2-...-12kCw(2k~k)^k2k-2k~1-27-...-1=k2k-(2k-1)=nlogn一冗T1.b.最好情況(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2forn>1(n=2k)best⑴二0best⑴二0。俱)=2。俱T)+2J=2[2C"“)+2fc-2]+2k~1=22Cb(2k~2)+2k~1+2fc-1=2化團(tuán)"項(xiàng))+2"T]+畔T+驢T=2：iC[f(2k~：i)+渺T+乎T+2k~lppp=2iCb(2k~i)+必t???=2kCtf(2k-k)+此i=耕t=inlogmc.鍵值比較次數(shù)M(n)M(n)=2M(n)+2nforn>1M(1)=0習(xí)題4.21.應(yīng)用快速排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序4.請(qǐng)舉一個(gè)n個(gè)元素?cái)?shù)組的例子，使得我們有必須對(duì)它使用本節(jié)提到的"限位器”.限位器的值應(yīng)是多少年來?為什么一個(gè)限位器就能滿足所有的輸入呢？Hints:Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.Appendingasentinel(限位器)ofvalueequalA[0](orlargerthanA[0])afterthearray’slastelement,thequicksortalgorithmswillstoptheindexoftheleft-to-rightscanofA[0..n-1]fromgoingbeyondpositionn.8.設(shè)計(jì)一個(gè)算法對(duì)n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列，使得其中所有的負(fù)元素都位于正元素之前.這個(gè)算法需要兼顧空間和時(shí)間效率?Algorithmsnetbeforepos(A[0..n-1])〃使所有負(fù)元素位于正元素之前〃輸入:實(shí)數(shù)組A[0..n-1]〃輸出:所有負(fù)元素位于于正元素之前的實(shí)數(shù)組A[0..n-1]A[-1]—-1;A[n]—1〃限位器i—0;j—n-1Whilei<jdoWhileA[i]<0doi—i+1whileA[j]>0doj—j-1swapA[i]andA[j]swapA[i]andA[j]//undothelastswap當(dāng)全是非負(fù)數(shù)或全是非正數(shù)時(shí)需要限位器.習(xí)題4.31.(題略)解：由公式4.4得:4次二分查找判定樹：所以,14,31,42,74,85,98需要比較4次c.TOC\o"1-5"\h\z\o"CurrentDocument"Cyes=1.1.1+_1.2.2+1.3.4+_!.4.6=41W3.2sg1313131313d.\o"CurrentDocument"1154Cno=_?3-2+_?4?12=二23.9avg1414142.當(dāng)n=2k時(shí),用反向替換法求下面的遞推方程：當(dāng)n>1時(shí)，Cw（n）=Cw（n/2）+1?？散?1（略）4.如果對(duì)于一個(gè)100000個(gè)元素的數(shù)組成功查找的話，使用折半查找比順序查找要快多少倍？諾a主=(fOTn,=I。')壬=-L工=工=3000.C尚(n)log2n'log210°2log210log210如何將折半查找應(yīng)用于范圍查找?范圍查找就是對(duì)于一個(gè)有序數(shù)組，找出位于給定值L、U之間（包含L、U）的所有元素，L<=U。該算法的最差效率是多少？Hints:Step1:檢查A[0]WL，A[n-1]NU是否成立，若不成立，則無解。否則進(jìn)入step2Step2:在數(shù)組A中用二分查找法查找值L，如果查找成功，則返回?cái)?shù)組下標(biāo)m，否則l二分查找結(jié)束時(shí)的值.Step3:在數(shù)組A中用二分查找法查找值U，如果查找成功，則返回?cái)?shù)組下標(biāo)m，否則r為二分查找結(jié)束時(shí)的值.最后，結(jié)果就是在數(shù)組序號(hào)范圍在low和high（包含low,high）之間的范圍。（low和high是step2和step3的值。）為折半查找寫遞歸的偽代碼AlgorithmsBSR(A[o..n-1],K)〃折半查找遞歸算法〃有序子數(shù)組A[Z..r]和查找鍵值K〃查找成功則輸出其下標(biāo)，否則輸出-1ifl>rreturn-1elsem—l(Z+r)/2jifK=A[m]returnmelseifK<A[m]returnBSR(A[l..m-1],K)elseifK>A[m]returnBSR(A[m+1,r],K)設(shè)計(jì)一個(gè)只使用兩路比較的折半查找算法，即只用0和=,或者只用2和=.AlgorithmsTwoWaysBinarySearch(A[o..n-1],K)//二路比較的折半查找〃有序子數(shù)組A[l..r]和查找鍵值K〃查找成功則輸出其下標(biāo)，否則輸出-1l—0,r—n-1whilel<rdom—(l+r)/2ifKWA[m]r—melsel—m+1ifK=A[l]returnlelsereturn-1習(xí)題4.4設(shè)計(jì)一個(gè)分治算法來計(jì)算二叉樹的層數(shù).(空樹返回0,單頂點(diǎn)樹返回1),并分析效率類型.AlgorithmsLevel(TreeT)〃遞歸計(jì)算二叉樹的層數(shù)〃輸入:二叉樹T〃輸出:二叉樹T的層數(shù)IfT=NULLreturn0Elsereturnmax{Level(T),Level(T)}+1算法效率類型是。(n)(同4.4節(jié)算法height(T))選擇一個(gè)二叉樹的經(jīng)典遍歷算法(前'中\(zhòng)后序),寫出它的遞歸偽代碼，并求它的遞歸調(diào)用次數(shù).Algorithmspreorder(T)〃先序遍歷二叉樹T〃輸入：二叉樹T〃輸出:先序遍歷的結(jié)點(diǎn)序列表If岸NULLVisitT’srootPreorder(TL)Preorder(TR)遞歸調(diào)用次數(shù)C(n)=擴(kuò)展樹中內(nèi)部結(jié)點(diǎn)+外部結(jié)點(diǎn)=n+(n+1)=2n+1設(shè)計(jì)一個(gè)算法計(jì)算有根有序樹的高度.Algorithmsheight(T)〃遞歸計(jì)算有根有序樹的高度〃輸入:一棵有根有序樹的高度T〃輸出:T的高度z=NumChildren(T)〃根的孩子個(gè)數(shù)ifi=0return0elsereturnmax{height(T1),height(T2),^,height(Ti)}+1下面的算法試圖計(jì)算一棵二叉樹中葉子的數(shù)量AlgorithmsLeafCount(T)〃遞歸計(jì)算二叉樹中葉子的數(shù)量〃輸入:一棵二叉樹〃輸出:T中葉子的數(shù)量ifT=NULLreturn0elsereturnLeafCount(TL)+LeafCount(TR)應(yīng)為:ifT=NULLreturn0//emptytreeelseifTl=NULLANDTr=NULLreturn1//single-nodetreeelsereturnLeafCount(TL)+LeafCount(TR)//generalcase習(xí)題4.61.a.為最近對(duì)問題的一維版本設(shè)計(jì)一個(gè)直接基于分治技術(shù)的算法,并確定它的效率類型b.對(duì)于這個(gè)問題，它是一個(gè)好算法嗎？解：a.AlgorithmsClosestNumber(A[Z..r])〃分治計(jì)算最近對(duì)問題的一維版本〃輸入:升序排列的實(shí)數(shù)子數(shù)組A[Z..r]〃輸出:最近數(shù)對(duì)的距離Ifr=lreturn8Elseifr—1=1returnA[r]—A[l]Elsereturnmin{ClosestNumber(A[/…世+r)/2]),ClosestNumber(A[[(Z+r)/2|...r])A[墮畛+1]-A[[(/+r)/2|]設(shè)遞歸的時(shí)間效率為T(n):對(duì)n=2k,貝lj：T(n)=2T(n/2)+c利用主定理求解.T(n)=O(n)2.(題略)T(nj=2T(n/2)+2|log2|forn>2(andn=2k\T(2)=1,T(2fc)=2T(2fc-1)+2fc(fc-1)=2[2T(2&—勺+2血T(k-2)]+2fc(fe-1)=22T(2fc-2)+2fc(fe-2)+2fc(fc-1)=22[2T(2fc-J)+2fc-2(fc-3)]+2fe(fc-2)+2fc(fc-l)=23T(2fc-3)+2fc(A;-3)+2fc(k-2)+2k(k-Y)=2項(xiàng)(2自T)+2fc(fe一4)+2fc(fe一4+1)+…+渺儂一1)=2fe-1T(21)+2fc+2fe2+…+2fe(fe一1)=2k~1+2fc(l+2+…+儂一1))=2k~l+砂伉；1)*=2fell+(fc-U)=與(1+(1。險(xiǎn)n-1)n)Ee(ntog2心習(xí)題5.1a.設(shè)計(jì)一個(gè)遞歸的減一算法，求n個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置.確定該算法的時(shí)間效率，然后把它與該問題的蠻力算法作比較AlgorithmsMinLocation(A[L..c-0)//findthelocationofthesmallestelementinagivenarray//anarrayA[0..n-1]ofrealnumbers//AnindexofthesmallestelementinA[0..c-1]ifc=1return0elsetemp?MinLocation(A[0..c-2])ifA[temp]<A[c-1]returntempelsereturnc-1時(shí)間效率分析見習(xí)題2.4中8C(c)=C(c-1)+1forc>1C(1)=04.應(yīng)用插入排序?qū)π蛄衑xample按照字母順序排序|xMPLEX|AExIM1EXPEpxLEMPxEELMPXEE444445.a.對(duì)于插入排序來說,為了避免在內(nèi)部循環(huán)的每次迭代時(shí)判斷邊界條件j>=0,應(yīng)該在待排序數(shù)組的第一個(gè)元素前放一個(gè)什么樣的限位器？b.帶限位器版本和原版本的效率類型相同嗎？解：a.應(yīng)該在待排序數(shù)組的第一個(gè)元素前放-8或者小于等于最小元素值的元素.b.效率類型相同.對(duì)于最差情況(數(shù)組是嚴(yán)格遞減)：n—1i—1n—1n—1n—1._■Gg頑(冗)=工1=工項(xiàng)十1)=>?十〉21=S十m一1)w劍冗勺?￡=1j=~1i=li=li=l—7.算法InsertSort2(A[0..n-1])fori—1ton-1dojl-1whilej>=0acdA[j]>A[j+1]doswap(A[j],A[j+1])j—j+1分析:在教材中算法InsertSort的內(nèi)層循環(huán)包括一次鍵值賦值和一次序號(hào)遞減，而算法InsertSort2的內(nèi)層循環(huán)包括一次鍵值交換和一次序號(hào)遞

減,設(shè)一次賦值和一次序號(hào)遞減的時(shí)間分別為Ca和Cd，那么算法InsertSort2和算法InsertSort運(yùn)行時(shí)間的比率是(3c+c)/(c+c)adad習(xí)題5.21.a.（略）b.習(xí)題5.31.退棧順序：efgbcad拓?fù)渑判颍篸acbgfeb.

習(xí)題5.21.a.（略）b.習(xí)題5.31.退棧順序：efgbcad拓?fù)渑判颍篸acbgfeb.這是一個(gè)有環(huán)有向圖.DFS從a出發(fā)，…,遇到一條從e到a的回邊.4.能否利用頂點(diǎn)進(jìn)入DFS棧的順序（代替它們從棧中退出的順序）來解決拓?fù)渑判騿栴}?Hints:不能.5.對(duì)第1題中的有向圖應(yīng)用源刪除算法.拓?fù)湫蛄校篸abcgefd-sletab5.對(duì)第1題中的有向圖應(yīng)用源刪除算法.拓?fù)湫蛄校篸abcgefd-sletabdeleteCdelete3習(xí)題5.44.下面是生成排列的B.Heap算法.算法HeapPermute(n)〃實(shí)現(xiàn)生成排列的Heap算法〃輸入:一個(gè)正整數(shù)n和一個(gè)全局?jǐn)?shù)組A[1..n]〃輸出:A中元素的全排列Ifn=1WriteAElseFori—1tondoHeapPermute(n-l)IfnisoddSwapA[1]andA[n]ElseswapA[i]andA[n]對(duì)于n=2,3,4的情況，手工跟蹤該算法.解:對(duì)于n=2fori=1doheappermute(1)(writeA即12}這時(shí)nnotodd,sodoA[1]與A[2]互換，A=21fori=2doheappermute(1)(writeA即21}對(duì)于n=3Fori=1doHeappermute(2)(heappermute(1)writeA即123這時(shí)2notodd,so,doA[1]與A[2]互換，A=213heappermute(1)writeA即213這時(shí)2notodd,doA⑵與A⑵互換，A=213}由于3isodd,sodoA[1]與A[3]互換,A=312Fori=2doHeappermute(2)(heappermute(1)writeA即312這時(shí)2notodd,so,doA[1]與A[2]互換，A=132heappermute(1)writeA即132這時(shí)2notodd,doA⑵與A⑵互換，A=231}由于3isodd,sodoA[1]與A[3]互換,A=231Fori=3doHeappermute(2)(heappermute(1)writeA即231這時(shí)2notodd,so,doA[1]與A[2]互換，A=321heappermute(1)writeA即321這時(shí)2notodd,doA⑵與A⑵互換，A=321}由于3isodd,sodoA[1]與A[3]互換,A=123n=4的的情況：lurn=1:readaluiyllicrowfi);123121313121132123113211123121313121132123113211113211323112131213123112112311232113121312432113習(xí)題5.52.Hints:減常因子b.C(n)=2+C(n/3)for3fc(k>t)),。⑴=Lc.C(3k)=2+C(：iki)[sub.C(3k~1)=2+C(；ik'2)]=2+[2+(?(：/2)]=2-2+Cf3fc2)=[fiiib.C(3k2)=2+C(3fc-3)]=2■2+[2+Gf3fc-3)]=2■3+G(3fc"3)=...=四+Gf3fc弓=...=(2k+C(3kfc)=2log3n+1.折半查找在最壞情況下的查找效率是log2n+1.而瞄普…2習(xí)題6.11.hintsortthelistandthensimplyreturnthen/2thelementsofthesortedlist.效率：假設(shè)排序算法的效率是O(nlogn),那么該算法的效率是O(nlogn)+0(1)=O(nlogn)hinta.初始化C=A^B=^foreveryelementa.inAdo(1<=i<=n)foreveryelementb.inB(1<=j<=m)Ifa.=b.'ijadda.toCdeleteb.fromB最差情況:C為空，比較的次數(shù)是nm.b.方法一：排序集合AForeveryelementb.inB用二分查找的辦法在A中查找與bj相匹配的元素aIf查找成功'AddatoC效率分析：假設(shè)排序的效率是O(nlogn),則該算法效率O(nlogn)+mO(logn)=(n+m)O(logn)方法二：首先對(duì)A和B都分別排序.然后對(duì)A和B應(yīng)用合并排序，只輸出它們的公有元素.效率分析：假設(shè)排序的效率是O(nlogn),則該算法效率O(nlogn)+O(mlogm)+0(n+m)=O(slogs)wheres=max{n,m}方法三：首先將A和B合并為L(zhǎng)排序L從左至右成對(duì)掃描LIfL=L.,I1+1AddL.toCi—i+2‘效率分析：假設(shè)排序的效率是O(nlogn),則該算法效率O((n+m)logn))+0(n+m)=O(slogs)wheres=max{n,m}4.hinta.排序數(shù)組，然后返回它的第一和最后元素.假設(shè)排序的效率是O(nlogn),則該算法效率O(nlogn)+。(1)+0(1)=O(nlogn)b.蠻力和分治都是線性的,所以優(yōu)于基于預(yù)排序的算法習(xí)題6.3

-2-15.a.二叉查找樹中最大值和最小值分別是樹中最右邊和最左邊的結(jié)點(diǎn).因此，從根開始，沿著向左的路徑一直走到這樣的結(jié)點(diǎn)：它的左孩子為空.這個(gè)結(jié)點(diǎn)里的值就是最小值.同理，可以找到最大值.最后，這兩個(gè)值做一次減法運(yùn)算即可.算法的效率：0(logn)+0(logn)+0(1)=0(logn)b.錯(cuò)誤.不成立.例如:列表{A,B},查找A,二分查找只做1次比較.而在2-3樹中查找則要做2次比較習(xí)題6.41.a.1865371187536118753611875361n8571361b.118818168165—856185613856137—8571368571364c.錯(cuò)誤.對(duì)于列表{1,2,3}按自頂向下：{3,1,2}自底向上：{3,2,1}5.a.設(shè)計(jì)一個(gè)算法，尋找并刪除堆中最小元素，然后確定其時(shí)間效率Hints:最小元素一定在堆的葉子中.|在堆H[1..n]的后半部分，(H[|n/2+1],…,H[n])中查找最小元素，并與最后的元素H[n]互換，刪除最后的元素.堆規(guī)模降1,如果必要的話，調(diào)整元素H[n],使其滿足雙親優(yōu)勢(shì).效率分析：查找:0(n)交換并刪除：0(1)+0(1)調(diào)整為堆:O(logn)設(shè)計(jì)一個(gè)算法，在給定的堆H中尋找并刪除一個(gè)包含給定值v的元素，然后確定其時(shí)間效率.Hints:在H中順序查找滿足條件的第一個(gè)元素H[i].H[i]與H[n]互換.刪除最后元素堆規(guī)模降1調(diào)整元素H[n]使其滿足雙親優(yōu)勢(shì)效率分析：查找:0(n)交換并刪除：0(1)+0(1)調(diào)整為堆：O(logn)習(xí)題6.5AlgorithmBrutA^ForccPolynomialEvaluationiPO..n,x]//ThealgorithmcomputesthevalueofpolynomialPatagivenpointx//byr.hc^highesr.r.olowt^sr.「erm"brur.(^-forccalgorir.hmInput:AnarrayP()..nofr.hccocfficicnr.sofapotyiiomialofdegree^n//sr.orcdfromrli(?lowest,rorheliigli(?sr.andanmnb(?rx//Output.:Thevalueofr.hcpolynomialar.rhepoint,xp—0.()fori—ndowntoUdopou^r—1forj—1tcHdopoiccr—pouw+xp—p+Pi*poieerreturnp乘法總次數(shù)M(n)ninjijiMin)=EtE1+1)E^+E1i=〔〕J=]i=0i=0i=()=也掃+"i)=心*也*2)加法總次數(shù)A(n)Tl=〉:1=異十1.i=0習(xí)題7.1假設(shè)列表的可能值屬于集合{a,b,c,d},用分布計(jì)數(shù)算法對(duì)下面的列表按照字母順序排序.b,c,d,c,b,a,a,b解：輸入A:b,c,d,c,b,a,a,babc.d戲bcdI2I3I2I1II2I5I7ISI頻率：____分布值：____S[0..7yl[t"]=byl[t"]=byl[(j=ayl[5=ayl[4=byl[3=cj4[2]—dA1=c/I0|=b25飛S24飛S14S04了S037S03()80367035ribaabcdcb是穩(wěn)定的.因?yàn)樗惴◤挠抑磷髵呙栎斎?，等值元素也是被從右至左地放入排序好的?shù)組里.習(xí)題7.2應(yīng)用Horspool算法在下面的文本中查找模式BAOBAB:BESS_KNEW_ABOUT_BAOBABS解:字符移動(dòng)表：cABCD□z—W)126S(i36(i匹配過程:BE33_KNEW_AB□UT_BA□BAB3BA□BABBA□BABBA□BABBA□BABBA□BAB用Horspool算法在一個(gè)長(zhǎng)度為n的文本中查找一個(gè)長(zhǎng)度為m的模式，請(qǐng)分別給出下面兩種例子.a.最差輸入b.最優(yōu)輸入hints:在n個(gè)”0”組成的文本中查找”10..0”(長(zhǎng)度為m),查找次數(shù)Cw=m(n-m+1)在n個(gè)”0”組成的文本中查找由m個(gè)”0”組成的模式，查找次數(shù)Cb=m習(xí)題7.3對(duì)于輸入30,20,56,75,31,19和散列函數(shù)h(K)=Kmod11構(gòu)造它們的開散列表求在本表中成功查找的最大鍵值比較次數(shù)求在本表中成功查找的平均比較次數(shù)Hints:鍵值列表：30,20,56,75,31,19Hash函數(shù)：h(K)=Kmod11Hash地址：K3020臬i753i1!)5!)1!)!)S開散列表：01234567S910563020111975I31b.3(查找鍵值31)c.(題略)a.鍵值列表：30,20,56,75,31,19Hash函數(shù)：h(K)=Kmod11Hash地址：K3020753i1!)5S!)1!)!)S閉散列表:b.6(查找鍵值19)c.11ii1114—■1-F—■1—,1—,2—■3-F—■(i=—f二2.3.6(i(i(i(i(i(i第8章動(dòng)態(tài)規(guī)劃習(xí)題8.1a.動(dòng)態(tài)規(guī)劃與分治法有什么共同點(diǎn)？（基于分解為更小的子問題）b.這兩種技術(shù)之間有什么主要的不同點(diǎn)？分治法分解出的子問題相對(duì)獨(dú)立，而動(dòng)態(tài)規(guī)劃則相互交疊；分治法通常不需要保存子問題的結(jié)果，而動(dòng)態(tài)規(guī)劃則保存a.應(yīng)用動(dòng)態(tài)規(guī)劃求解C（6,3）b.為了計(jì)算C（n，k），需要填充算法的動(dòng)態(tài)規(guī)劃表，在填表時(shí)是否可以一列接一列地填，而不是一行接一行地填？解:a.012301111212131；i1414(j4515101()G1G1520b.可以.每一列從主對(duì)線由1開始，自上而下填表.證明：(k—Y}kT.『、_廠、，r、-—廣Hk[n—k)E解：伏2"+k(n-k)=nk-2k2一2k對(duì)n,k>=0,顯然：1nk-k2-k<nk成立.22對(duì)n>=2,0<=k<=n,則有:nk-—k2-—k>nk-—nk-—k—n=—nk222224習(xí)題8.21.對(duì)由下面鄰接矩陣定義的有向圖，應(yīng)用warshall算法求它的傳遞閉包0100000100010000解