算法設(shè)計(jì)與分析基礎(chǔ)課后習(xí)題答案中文版

1、Program算法設(shè)計(jì)與分析根底中文版答案習(xí)題1.11.1. 明等式gcd(m,n)=gcd(n,mmodn)對每一對正整數(shù)m,n都成立.Hint:根據(jù)除法的定義不難證實(shí)：如果d整除u和v,那么d一定能整除u±v;如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.對于任意一正整數(shù)m,n,假設(shè)d能整除m和n,那么d一定能整除n和r=mmodn=m-qn;顯然,假設(shè)d能整除n和r,也一定能整除m=r+qn和n.數(shù)又(m,n)和(n,r)具有相同的公約數(shù)的有限非空集,其中也包括了最大公約數(shù).故gcd(m,n)=gcd(n,r)6 .對于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對數(shù)字,歐幾里得算法將會(huì)如何處

2、理該算法在處理這種輸入的過程中,上述情況最多會(huì)發(fā)生幾次Hint:對于任彳S形如0<=mgcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次.7 .a.對于所有1wm,nw10輸入,Euclid算法最少要做幾次除法(1次)b.對于所有1wm,nw10的輸入,Euclid算法最多要做幾次除法(5次)gcd(5,8)習(xí)題1.21.(農(nóng)夫過河)P一農(nóng)夫W狼G山羊C白菜2.(過橋問題)1,2,5,10-分別代表4個(gè)人,f一手電筒4 .對于任意實(shí)系數(shù)a,b,c,某個(gè)算法能求方程axA2+bx+c=0的實(shí)根,寫出上述算法的偽代碼(可以假設(shè)sqrt(x)是求平方的函數(shù))算法Quadratic(a

3、,b,c)求方程ax2+bx+c=0的實(shí)根的算法/輸入:實(shí)系數(shù)a,b,c輸出：實(shí)根或者無解信息IfawoAb*b-4*a*cIfD>0temp-2*ax1(-b+sqrt(D)/tempx2-b-sqrt(D)/tempreturnx1,x2elseifD=0returnb/(2*a)elsereturn“norealroots“else/a=0ifbw0returc/belse/a=b=0ifc=0return“norealnumbers"elsereturn“norealroots5 .描述將十進(jìn)制整數(shù)表達(dá)為二進(jìn)制整數(shù)的標(biāo)準(zhǔn)算法a用文字描述b.用偽代碼描述解答：a.將十進(jìn)制

4、整數(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根據(jù)i從高到低的順序輸出b.偽代碼算法DectoBin(n)將十進(jìn)制整數(shù)n轉(zhuǎn)換為二進(jìn)制整數(shù)的算法輸入：正整數(shù)n輸出：該正整數(shù)相應(yīng)的二進(jìn)制數(shù),該數(shù)存放于數(shù)組Bin1.n中i=1whilen!=0doBini=n%2;n=(int)n/2;i+;whilei!=0doprintBini;i-;9.考慮下面這個(gè)算法,它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略)對這個(gè)算法做盡可能多的改良.算法Min

5、Distance(A0.n-1)輸入:數(shù)組A0.n-1輸出:thesmallestdistancedbetweentwoofitselements習(xí)題1.31.考慮這樣一個(gè)排序算法,該算法對于待排序的數(shù)組中的每一個(gè)元素,計(jì)算比它小的元素個(gè)數(shù),然后利用這個(gè)信息,將各個(gè)元素放到有序數(shù)組的相應(yīng)位置上去.a.應(yīng)用該算法對列表II60,35,81,98,14,4洲序b.該算法后I定嗎c該算法在位嗎解：a.該算法對列表II60,35,81,98,14,4洲序的過程如下所示b.該算法不穩(wěn)定.比方對列表II2,2卻序c.該算法不在位.額外空間forSandCount4.(古老的七橋問題)習(xí)題1.41 .請分別

6、描述一下應(yīng)該如何實(shí)現(xiàn)以下對數(shù)組的操作,使得操作時(shí)間不依賴數(shù)組的長度.a.刪除數(shù)組白勺第i個(gè)元素(1<=i<=n)b.刪除有序數(shù)組的第i個(gè)元素(依然有序)hints:a. Replacetheithelementwiththelastelementanddecreasethearraysizeof1b. Replacetheithelementwithaspecialsymbolthatcannotbeavalueofthearray'selement(e.g.,0foranarrayofpositivenumbers)tomarktheithpositionisempty.

7、(lazydeletionII)第2章習(xí)題2.17 .對以下斷言進(jìn)行證實(shí)：(如果是錯(cuò)誤的,請舉例)a.如果t(n)CO(g(n),那么g(n)CQ(t(n)b.a>0時(shí),0(ag(n)=O(g§pi:)a.這個(gè)斷言是正確的.它指出如果t(n)的增長率小于或等于g(n)的增長率,那么g(n)的增長率大于或等于t(n)的增長率由t(n)<c-g(n)foralln>n0,wherec>01那么：()t(n)g(n)foralln>n0cb.這個(gè)斷言是正確的.只需證實(shí)(g(n)(g(n),(g請)f(n)(ag(rtl有：f(n)cg(n)foralln=n0

8、,c>0f(n)c1g(n)foralln>=n0,c1=ca>0即：f(n)C同(g(n)又設(shè)f(n)CO(g(n)那么有：f(n)cg(n)foralln>=n0,c>0f(n)cg(n)c1g(n)foralln>=n0,c1=c/a>0即：f(n)0(ag(n)8 .證實(shí)本節(jié)定理對于以下符號(hào)也成立：a.符號(hào)b.日符號(hào)證實(shí)：a.weneedtoproofthatift1(n)£Q(g1(n)andt2(n)CQ(g2(n),thent1(n)+t2(n)£Q(max,g1(n),g2(n).由t1(n)CQ(g1(n),t1(

9、n)>c1g1(n)foralln>=n1,wherec1>0t2(n)Q(g2(n)T2(n)>c2g2(n)foralln>=n2,wherec2>0那么,取c>=minc1,c2,當(dāng)n>=maxn1,n2時(shí)：t1(n)+t2(n)命題成立.>c1g1(n)+c2g2(n)g2(n)R叁c*gn(nC+g2(n)+b.t1(n)+t2(n)£O(max(g1(n),g2(n)證實(shí)：由大的定義知,必須確定常數(shù)c1、c2和n0,使得對于所有n>=n0,有：c1max(g1(n),g2(n)t1(n)t2(n)max(g1(n

10、),g2(n)由t1(n)CO(g1(n)和,存在非負(fù)整數(shù)a1,a2和n1使：a1*g1(n)<=t1(n)<=a2*g1(n)-(1)由t2(n)CG)(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)不失一般性假設(shè)max(g1(n),g2(n)=

11、g1(n).顯然,g1(n)+g2(n)又g2(n)>0,g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2).貝U(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.x(n)x(n1)當(dāng)n>1時(shí)x(1)解：b.x(n)3x(n當(dāng))n>1時(shí)x(1)4解：2 .對于af算n!的遞歸算法F(n),建立其遞

12、歸調(diào)用次數(shù)的遞推關(guān)系并求解.解：3 .考慮以下遞歸算法,該算法用來計(jì)算前n個(gè)立方白W口：S(n)=13+23+n算法S(n)輸入：正整數(shù)n輸出：前n個(gè)立方的和ifn=1return1elsereturnS(n-1)+n*n*na.建立該算法的根本操作次數(shù)的遞推關(guān)系并求解b.如果將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比,你做何評價(jià)解：a.7.a.請基于公式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.對于該問題的求解來說,這是一個(gè)好的算法嗎解

13、：a.算法power(n)基于公式2n=2n-1+2n-1,計(jì)算2n輸入:非負(fù)整數(shù)n輸出：2n的值Ifn=0return1Elsereturnpower(n-1)+power(n-1)c.習(xí)題2.61.考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來對關(guān)鍵比擬次數(shù)進(jìn)行計(jì)數(shù)算法SortAnalysis(A0.n-1)/input:包含n個(gè)可排序元素的一個(gè)數(shù)組A0.n-1/output:所做的關(guān)鍵比擬的總次數(shù)count-0fori-1to1ndovwhilej>0andA*j+>vdo-A*i+-1jicountA*jcount+1A*j+j-j+1A*j+1+-vreturncount比擬

14、計(jì)數(shù)器是否插在了正確的位置粢口果不對,請改正.解:應(yīng)改為：算法SortAnalysis(A0.n-1)/input:包含n個(gè)可排序元素的一個(gè)數(shù)組A0.n-1/output:所做的關(guān)鍵比擬的總次數(shù)count-0A*jcount+1A*j+j-j+1vreturncountfori-1to1ndov-A*i+-1jwhilej>0andA*j+>vdocountifj>=0count=count+1A*j+1+6 .選擇排序是穩(wěn)定的嗎?不穩(wěn)定7 .用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的©(n2效率Yes.Bothoperationfindingthesmall

15、estelementandswappingit-canbedoneasefficientlywiththelinkedlistaswithanarray.9.a.請證實(shí),如果對列表比擬一遍之后沒有交換元素的位置,那么這個(gè)表已經(jīng)排好序了,算法可以停止了.b.結(jié)合所做的改良,為冒泡排序?qū)懸欢蝹未a.c.請證實(shí)改良的算法最差效率也是平方級(jí)的Hints:a.第i趟冒泡可以表示為：如果沒有發(fā)生交換位置,那么：b.AlgorithmsBetterBubblesort(A0.n-1)用改良的冒泡算法對數(shù)組A0.n-1排序輸入:數(shù)組A0.n-1/輸出：升序排列的數(shù)組A0.n-1count一上1/進(jìn)行比擬的相鄰

16、元素對的數(shù)目flagtrue應(yīng)換標(biāo)志whileflagdoflagfalsefori=0tocount-1doifAi+1swap(Ai,Ai+1)flagtruecountcbuntc最差情況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改良的冒泡排序會(huì)蛻化為原來的冒泡排序.10.冒泡排序是穩(wěn)定的嗎(穩(wěn)定)習(xí)題3.21 .對限位器版的順序查找算法的比擬次數(shù)：a.在最差情況下b.在平均,f#況下.假設(shè)成功查找的概率是p(0<=p<=1)Hints:a.Cworst(n)=n+1b.在成功查找下,對于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比擬次數(shù)是i.在查找不成功時(shí),比擬次數(shù)是n+1,

17、可能性是1-p.6 .給出一個(gè)長度為n的文本和長度為m的模式構(gòu)成的實(shí)例,它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出,對于這樣的輸入需要做多少次字符比擬運(yùn)算.Hints:文本：由n個(gè)0組成的文本模式:前m-1個(gè)是0,最后一個(gè)字符是1比擬次數(shù)：m(n-m+1)7 .為蠻力字符匹配算法寫一個(gè)偽代碼,對于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.AlgorithmsBFStringmatch(T0.n-1,P0.m-1)/蠻力字符匹配輸入:數(shù)組T0.n-1長度為n的文本,數(shù)組P0.m-1長度為m的模式輸出：在文本中匹配成功的子串?dāng)?shù)量count-0fori0tomdoj-0whilejco

18、untcount+1returncount8 .如果所要搜索的模式包含一些英語中較少見的字符,我們應(yīng)該如何修改該蠻力算法來利用這個(gè)信息.Hint:每次都從這些少見字符開始比擬,如果匹配,那么向左邊和右邊進(jìn)行其它字符的比擬.elseifrl=1/有兩個(gè)元素時(shí)ifA*l+wA*r+Max-A*r+;Min-A*l+elseMax-A*l+;Min-A*r+else/rl>1MaxMin(Al,(l+r)/2,Max1,Min1);/遞歸解決前一局部MaxMin(A(l+r/)2.r,Max2,Min2);遞歸解決后一局部ifMax1<Max2Max=Max2從兩局部的兩個(gè)最大值中選擇大

19、值ifMin2b.假設(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=22C(2k-2)+2+2=22C(2k-2)+22+2=222C(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/22b.蠻力法的算法如下：算法simpleMaxMin(Al.r)用蠻力法得到數(shù)組A的最大值和最小值輸入：

20、數(shù)值數(shù)組Al.r輸出：最大值Max和最小值MinMax=Min=Al;fori=l+1tordoifA*i+>MaxMax-A*i+;elseifA*i+時(shí)間復(fù)雜度t(n)=2(n-1)算法MaxMin的時(shí)間復(fù)雜度為3n/2-2,simpleMaxMin的時(shí)間復(fù)雜度為2n-2,都屬于<9(n),但比擬一下發(fā)現(xiàn),MaxMin的速度要比simpleMaxMin的快一些.6.應(yīng)用合并排序?qū)π蛄蠩,X,A,M,PL,E按字母順序排序.c.鍵值比擬次數(shù)M(n)M(n)=2M(n)+2nforn>1M(1)=0習(xí)題4.21.應(yīng)用快速排序?qū)π蛄蠩,X,A,M,PL,E按字母順序排序4.請舉

21、一個(gè)n個(gè)元素?cái)?shù)組的例子,使得我們有必須對它使用本節(jié)提到的“限位器限位器的值應(yīng)是多少年來為什么一個(gè)限位器就能?t足所有的輸入呢Hints:Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.Appendingasentinel(限位器)ofvalueequalA*0+(orlargerthanA*0+)afterthearray'lastelement,thequicksortalgorithmsw

22、illstoptheindexoftheleft-to-rightscanofA0.n-1fromgoingbeyondpositionn.8.設(shè)計(jì)一個(gè)算法對n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列,使得其中所有的負(fù)元素都位于正元素之前.這個(gè)算法需要兼顧空間和時(shí)間效率.Algorithmsnetbeforepos(A0.n-1)/使所有負(fù)元素位于正元素之前輸入:實(shí)數(shù)組A0.n-1/輸出：所有負(fù)元素位于于正元素之前的實(shí)數(shù)組A0.n-1A-1+1;A*n+-1陂位器i0;j-1WhileiWhileA*i+<0doi-i+1whileA*j+>0do-1jjswapAiandAjswapAian

23、dAj/undothelastswap當(dāng)全是非負(fù)數(shù)或全是非正數(shù)時(shí)需要限位器.習(xí)題4.31.(題略)習(xí)題5.12.a.設(shè)計(jì)一個(gè)遞歸的減一算法,求n個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置.b.確定該算法的時(shí)間效率,然后把它與該問題的蠻力算法作比擬AlgorithmsMinLocation(A0.n-1)/findthelocationofthesmallestelementinagivenarray/anarrayA0.n-1ofrealnumbers/AnindexofthesmallestelementinA0.n-1ifn=1return0elsetempMinLocation(A*0-2j)if

24、Atemp時(shí)間效率分析見習(xí)題2.4中8C(n)=C(n-1)+1forn>1C(1)=04 .應(yīng)用插入排序?qū)π蛄衑xample根據(jù)字母順序排序5 .a.對于插入排序來說,為了防止在內(nèi)部循環(huán)的每次迭代時(shí)判斷邊界條件j>=0,應(yīng)該在待排序數(shù)組的第一個(gè)元素前放一個(gè)什么樣的限位器b.帶限位器版本和原版本的效率類型相同嗎解：a.應(yīng)該在待排序數(shù)組的第一個(gè)元素前放-8或者小于等于最小元素值的元素.b.效率類型相同.對于最差情況(數(shù)組是嚴(yán)格遞減):7.算法InsertSort2(A0.n-1)fori-1to1ndojJ-1whilej>=0andA*j+>A*j+1+doswap(A

25、*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í)間的比率是(3ca+cd)/(ca+cd)習(xí)題5.21.a.(略)b.4.習(xí)題5.31.DFS的棧狀態(tài)：退棧順序：efgbcad拓?fù)渑判颍篸acbgfeb.這是一個(gè)有環(huán)有向圖.DFS從a出發(fā)“,遇到一條從e到a的回邊.4 .能否利用頂點(diǎn)進(jìn)入DFS戔的順序(代替它們從棧中退出的順序)來解決拓?fù)渑判騿栴}Hint

26、s：不能.5 .對第1題中的有向圖應(yīng)用源刪除算法.拓?fù)湫蛄校篸abcgef習(xí)題5.44.下面是生成排列的B.Heap算法.算法HeapPermute(n)/實(shí)現(xiàn)生成排列的Heap算法輸入:一個(gè)正整數(shù)n和一個(gè)全局?jǐn)?shù)組A1.n輸出：A中元素的全排列Ifn=1WriteAElseFori1tondoHeapPermute(n)IfnisoddSwapA1andAnElseswapAiandAn對于n=2,3,4的情況,手工跟蹤該算法.解:對于n=2fori=1doheappermute(1)writeA即12這時(shí)nnotodd,sodoA1與A2互換,A=21fori=2doheappermute(1)writeA即21對于n=3Fori=1doHeappermute