算法設計與分析基礎課后習題答案中文版

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

2、理該算法在處理這種輸入的過程中,上述情況最多會發(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)習題1.21.(農(nóng)夫過河)P一農(nóng)夫W狼G山羊C白菜2.(過橋問題)1,2,5,10-分別代表4個人,f一手電筒4 .對于任意實系數(shù)a,b,c,某個算法能求方程axA2+bx+c=0的實根,寫出上述算法的偽代碼(可以假設sqrt(x)是求平方的函數(shù))算法Quadratic(a

3、,b,c)求方程ax2+bx+c=0的實根的算法/輸入:實系數(shù)a,b,c輸出：實根或者無解信息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 .描述將十進制整數(shù)表達為二進制整數(shù)的標準算法a用文字描述b.用偽代碼描述解答：a.將十進制

4、整數(shù)轉換為二進制整數(shù)的算法輸入：一個正整數(shù)n輸出：正整數(shù)n相應的二進制數(shù)第一步：用n除以2,余數(shù)賦給Ki(i=0,1,2.),商賦給n第二步：如果n=0,那么到第三步,否那么重復第一步第三步：將Ki根據(jù)i從高到低的順序輸出b.偽代碼算法DectoBin(n)將十進制整數(shù)n轉換為二進制整數(shù)的算法輸入：正整數(shù)n輸出：該正整數(shù)相應的二進制數(shù),該數(shù)存放于數(shù)組Bin1.n中i=1whilen!=0doBini=n%2;n=(int)n/2;i+;whilei!=0doprintBini;i-;9.考慮下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差.(算法略)對這個算法做盡可能多的改良.算法Min

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

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

7、(lazydeletionII)第2章習題2.17 .對以下斷言進行證實：(如果是錯誤的,請舉例)a.如果t(n)CO(g(n),那么g(n)CQ(t(n)b.a>0時,0(ag(n)=O(g§pi:)a.這個斷言是正確的.它指出如果t(n)的增長率小于或等于g(n)的增長率,那么g(n)的增長率大于或等于t(n)的增長率由t(n)<c-g(n)foralln>n0,wherec>01那么：()t(n)g(n)foralln>n0cb.這個斷言是正確的.只需證實(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)又設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 .證實本節(jié)定理對于以下符號也成立：a.符號b.日符號證實：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,當n>=maxn1,n2時：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ù)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)和,存在非負整數(shù)a1,a2和n1使：a1*g1(n)<=t1(n)<=a2*g1(n)-(1)由t2(n)CG)(g2(n)和,存在非負整數(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)不失一般性假設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)式轉換為：C1*max(g1,g2)<=t1(n)+t2(n)<=c2*2max(g1,g2)所以當c1=min(a1,b1),c2=2c2=2max(c1,c2),n0=max(n1,n2)時,當n>=n0時上述不等式成立.證畢.習題2.41 .解以下遞推關系(做a,b)a.x(n)x(n1)當n>1時x(1)解：b.x(n)3x(n當)n>1時x(1)4解：2 .對于af算n!的遞歸算法F(n),建立其遞

12、歸調(diào)用次數(shù)的遞推關系并求解.解：3 .考慮以下遞歸算法,該算法用來計算前n個立方白W口：S(n)=13+23+n算法S(n)輸入：正整數(shù)n輸出：前n個立方的和ifn=1return1elsereturnS(n-1)+n*n*na.建立該算法的根本操作次數(shù)的遞推關系并求解b.如果將這個算法和直截了當?shù)姆沁f歸算法比,你做何評價解：a.7.a.請基于公式2n=2n-1+2n-1,設計一個遞歸算法.當n是任意非負整數(shù)的時候,該算法能夠計算2n的值.b.建立該算法所做的加法運算次數(shù)的遞推關系并求解c.為該算法構造一棵遞歸調(diào)用樹,然后計算它所做的遞歸調(diào)用次數(shù).d.對于該問題的求解來說,這是一個好的算法嗎解

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

14、計數(shù)器是否插在了正確的位置粢口果不對,請改正.解:應改為：算法SortAnalysis(A0.n-1)/input:包含n個可排序元素的一個數(shù)組A0.n-1/output:所做的關鍵比擬的總次數(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 .用鏈表實現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的©(n2效率Yes.Bothoperationfindingthesmall

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

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

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

18、untcount+1returncount8 .如果所要搜索的模式包含一些英語中較少見的字符,我們應該如何修改該蠻力算法來利用這個信息.Hint:每次都從這些少見字符開始比擬,如果匹配,那么向左邊和右邊進行其它字符的比擬.elseifrl=1/有兩個元素時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從兩局部的兩個最大值中選擇大

19、值ifMin2b.假設n=2k,比擬次數(shù)的遞推關系式：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+時間復雜度t(n)=2(n-1)算法MaxMin的時間復雜度為3n/2-2,simpleMaxMin的時間復雜度為2n-2,都屬于<9(n),但比擬一下發(fā)現(xiàn),MaxMin的速度要比simpleMaxMin的快一些.6.應用合并排序對序列E,X,A,M,PL,E按字母順序排序.c.鍵值比擬次數(shù)M(n)M(n)=2M(n)+2nforn>1M(1)=0習題4.21.應用快速排序對序列E,X,A,M,PL,E按字母順序排序4.請舉

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

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

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

24、Atemp時間效率分析見習題2.4中8C(n)=C(n-1)+1forn>1C(1)=04 .應用插入排序對序列example根據(jù)字母順序排序5 .a.對于插入排序來說,為了防止在內(nèi)部循環(huán)的每次迭代時判斷邊界條件j>=0,應該在待排序數(shù)組的第一個元素前放一個什么樣的限位器b.帶限位器版本和原版本的效率類型相同嗎解：a.應該在待排序數(shù)組的第一個元素前放-8或者小于等于最小元素值的元素.b.效率類型相同.對于最差情況(數(shù)組是嚴格遞減):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)包括一次鍵值賦值和一次序號遞減,而算法InsertSort2的內(nèi)層循環(huán)包括一次鍵值交換和一次序號遞減,設一次賦值和一次序號遞減的時間分別為ca和cd,那么算法InsertSort2和算法InsertSort運行時間的比率是(3ca+cd)/(ca+cd)習題5.21.a.(略)b.4.習題5.31.DFS的棧狀態(tài)：退棧順序：efgbcad拓撲排序：dacbgfeb.這是一個有環(huán)有向圖.DFS從a出發(fā)“,遇到一條從e到a的回邊.4 .能否利用頂點進入DFS戔的順序(代替它們從棧中退出的順序)來解決拓撲排序問題Hint

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