算法設(shè)計(jì)與分析第二版課后習(xí)題及解答

算法設(shè)計(jì)與分析第二版課后習(xí)題及解答算法設(shè)計(jì)與分析基礎(chǔ)課后練習(xí)答案習(xí)題1.14.設(shè)計(jì)一個(gè)計(jì)算的算法,n是任意正整數(shù)。除了賦值和比較運(yùn)算,該算法只能用到基本的四則運(yùn)算操作。算法求//輸入:一個(gè)正整數(shù)n2//輸出:。step1:a1;step2:若a*an轉(zhuǎn)step3,否則輸出a;step3:aa+1轉(zhuǎn)step2;5.a.用歐幾里德算法求gcd(31415,14142)。b.用歐幾里德算法求gcd(31415,14142),比檢查min{m,n}和gcd(m,n)間連續(xù)整數(shù)的算法快多少倍?請(qǐng)估算一下。a.gcd31415,14142gcd14142,3131gcd3131,1618gcd1618,1513gcd1513,105gcd1513,105gcd105,43gcd43,19gcd19,5gcd5,4gcd4,1gcd1,01.b.有a可知計(jì)算gcd(31415,14142)歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測(cè)算法在14142每次迭代過(guò)程中或者做了一次除法,或者兩次除法,因此這個(gè)算法做除法的次數(shù)鑒于1?14142和2?14142之間,所以歐幾里德算法比此算法快1?14142/11≈1300與2?14142/11≈2600倍之間。6.證明等式gcdm,ngcdn,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和rmmodnm-qn;顯然,若d能整除n和r,也一定能整除mr+qn和n。數(shù)對(duì)m,n和n,r具有相同的公約數(shù)的有限非空集,其中也包括了最大公約數(shù)。故gcdm,ngcdn,r7.對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字,歐幾里得算法將會(huì)如何處理?該算法在處理這種輸入的過(guò)程中,上述情況最多會(huì)發(fā)生幾次?Hint:對(duì)于任何形如0mn的一對(duì)數(shù)字,Euclid算法在第一次疊代時(shí)交換m和n,即gcdm,ngcdn,m并且這種交換處理只發(fā)生一次.8.a.對(duì)于所有1≤m,n≤10的輸入,Euclid算法最少要做幾次除法?1次b.對(duì)于所有1≤m,n≤10的輸入,Euclid算法最多要做幾次除法?5次gcd5,8習(xí)題1.21.農(nóng)夫過(guò)河P?農(nóng)夫W?狼G?山羊C?白菜2.過(guò)橋問(wèn)題1,2,5,10---分別代表4個(gè)人,f?手電筒4.對(duì)于任意實(shí)系數(shù)a,b,c,某個(gè)算法能求方程ax^2+bx+c0的實(shí)根,寫(xiě)出上述算法的偽代碼可以假設(shè)sqrtx是求平方根的函數(shù)算法Quadratica,b,c//求方程ax^2+bx+c0的實(shí)根的算法//輸入:實(shí)系數(shù)a,b,c//輸出:實(shí)根或者無(wú)解信息Ifa≠0D←b*b-4*a*cIfD0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturnx1,x2elseifD0return?b/2*aelsereturn“norealroots”else//a0ifb≠0return?c/belse//ab0ifc0return“norealnumbers”elsereturn“norealroots”5.描述將十進(jìn)制整數(shù)表達(dá)為二進(jìn)制整數(shù)的標(biāo)準(zhǔn)算法a.用文字描述b.用偽代碼描述解答:a.將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)的算法輸入:一個(gè)正整數(shù)n輸出:正整數(shù)n相應(yīng)的二進(jìn)制數(shù)第一步:用n除以2,余數(shù)賦給Kii0,1,2,商賦給n第二步:如果n0,則到第三步,否則重復(fù)第一步第三步:將Ki按照i從高到低的順序輸出b.偽代碼算法DectoBinn//將十進(jìn)制整數(shù)n轉(zhuǎn)換為二進(jìn)制整數(shù)的算法//輸入:正整數(shù)n//輸出:該正整數(shù)相應(yīng)的二進(jìn)制數(shù),該數(shù)存放于數(shù)組Bin[1n]中i1whilen!0doBin[i]n%2;nintn/2;i++;whilei!0doprintBin[i];i--;9.考慮下面這個(gè)算法,它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.算法略對(duì)這個(gè)算法做盡可能多的改進(jìn).算法MinDistanceA[0..n-1]//輸入:數(shù)組A[0..n-1]//輸出:thesmallestdistancedbetweentwoofitselements習(xí)題1.3考慮這樣一個(gè)排序算法,該算法對(duì)于待排序的數(shù)組中的每一個(gè)元素,計(jì)算比它小的元素個(gè)數(shù),然后利用這個(gè)信息,將各個(gè)元素放到有序數(shù)組的相應(yīng)位置上去.a.應(yīng)用該算法對(duì)列表”60,35,81,98,14,47”排序b.該算法穩(wěn)定嗎?c.該算法在位嗎?解:a.該算法對(duì)列表”60,35,81,98,14,47”排序的過(guò)程如下所示:b.該算法不穩(wěn)定.比如對(duì)列表”2,2*”排序c.該算法不在位.額外空間forSandCount[]4.古老的七橋問(wèn)題第2章習(xí)題2.17.對(duì)下列斷言進(jìn)行證明:如果是錯(cuò)誤的,請(qǐng)舉例a.如果tn∈Ogn,則gn∈Ωtnb.α0時(shí),ΘαgnΘgn解:a這個(gè)斷言是正確的。它指出如果tn的增長(zhǎng)率小于或等于gn的增長(zhǎng)率,那么gn的增長(zhǎng)率大于或等于tn的增長(zhǎng)率由tn≤c?gnforalln≥n0,wherec0則:foralln≥n0b.這個(gè)斷言是正確的。只需證明。設(shè)fn∈Θαgn,則有:forallnn0,c0forallnn0,c1cα0即:fn∈Θgn又設(shè)fn∈Θgn,則有:forallnn0,c0forallnn0,c1c/α0即:fn∈Θαgn8.證明本節(jié)定理對(duì)于下列符號(hào)也成立:a.Ω符號(hào)b.Θ符號(hào)證明:a。weneedtoproofthatift1n∈Ωg1nandt2n∈Ωg2n,thent1n+t2n∈Ωg1n,g2n。由t1n∈Ωg1n,t1n≥c1g1nforallnn1,wherec10由t2n∈Ωg2n,T2n≥c2g2nforallnn2,wherec20那么,取cminc1,c2,當(dāng)nn1,n2時(shí):t1n+t2n≥c1g1n+c2g2n≥cg1n+cg2n≥c[g1n+g2n]≥cg1n,g2n所以以命題成立。b.t1n+t2n∈Θ證明:由大?的定義知,必須確定常數(shù)c1、c2和n0,使得對(duì)于所有nn0,有: 由t1n∈Θg1n知,存在非負(fù)整數(shù)a1,a2和n1使:a1*g1nt1na2*g1n-----1由t2n∈Θg2n知,存在非負(fù)整數(shù)b1,b2和n2使:b1*g2nt2nb2*g2n-----21+2:a1*g1n+b1*g2nt1n+t2na2*g1n+b2*g2n令c1mina1,b1,c2a2,b2,則C1*g1+g2t1n+t2nc2g1+g2-----3不失一般性假設(shè)g1n,g2ng1n.顯然,g1n+g2n2g1n,即g1+g22g1,g2又g2n0,g1n+g2ng1n,即g1+g2g1,g2。則(3)式轉(zhuǎn)換為:C1*g1,g2t1n+t2nc2*2g1,g2所以當(dāng)c1=mina1,b1,c2=2c22c1,c2,n0=n1,n2時(shí),當(dāng)nn0時(shí)上述不等式成立。證畢。習(xí)題2.2請(qǐng)用的非正式定義來(lái)判斷下列斷言是真還是假。a.nn+1/2∈On3b.nn+1/2∈On2c.nn+1/2∈Θn3d.nn+1/2∈Ωn答:c假,其它真。5.按照下列函數(shù)的增長(zhǎng)次數(shù)對(duì)它們進(jìn)行排列(按照從低到高的順序)n?2!,5lgn+10010,22n,0.001n4+3n3+1,ln2n,,3n.答:習(xí)題2.3計(jì)算下列求和表達(dá)式的值。答:考慮下面的算法。該算法求的是什么?它的基本操作是什么?該基本操作執(zhí)行了多少次?該算法的效率類型是什么?對(duì)該算法進(jìn)行改進(jìn),或者設(shè)計(jì)一個(gè)更好的算法,然后指出它們的效率類型。如果做不到這一點(diǎn),請(qǐng)?jiān)囍C明這是不可能做到的。9.證明下面的公式:可以使用數(shù)學(xué)歸納法,也可以像10歲的高斯一樣,用洞察力來(lái)解決該問(wèn)題。這個(gè)小學(xué)生長(zhǎng)大以后成為有史以來(lái)最偉大的數(shù)學(xué)家之一。數(shù)學(xué)歸納法:高斯的方法:習(xí)題2.4解下列遞推關(guān)系(做a,b)a.解:b.解:對(duì)于計(jì)算n!的遞歸算法Fn,建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求解。解:考慮下列遞歸算法,該算法用來(lái)計(jì)算前n個(gè)立方的和:Sn13+23+…+n3。算法Sn//輸入:正整數(shù)n//輸出:前n個(gè)立方的和ifn1return1elsereturnSn-1+n*n*na.建立該算法的基本操作次數(shù)的遞推關(guān)系并求解b.如果將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比,你做何評(píng)價(jià)?解:7.a.請(qǐng)基于公式2n2n-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)用樹(shù),然后計(jì)算它所做的遞歸調(diào)用次數(shù)。d對(duì)于該問(wèn)題的求解來(lái)說(shuō),這是一個(gè)好的算法嗎?解:a.算法powern//基于公式2n2n-1+2n-1,計(jì)算2n//輸入:非負(fù)整數(shù)n//輸出:2n的值Ifn0return1Elsereturnpowern-1+powern-1c.8.考慮下面的算法算法Min1A[0..n-1]//輸入:包含n個(gè)實(shí)數(shù)的數(shù)組A[0..n-1]Ifn1returnA[0]Elsetemp←Min1A[0..n-2]Iftemp≤A[n-1]returntempElsereturnA[n-1]a.該算法計(jì)算的是什么?b.建立該算法所做的基本操作次數(shù)的遞推關(guān)系并求解解:a.計(jì)算的給定數(shù)組的最小值b.9.考慮用于解決第8題問(wèn)題的另一個(gè)算法,該算法遞歸地將數(shù)組分成兩半.我們將它稱為Min2A[0..n-1]算法MinA[r..l]IflrreturnA[l]Elsetemp1←Min2A[l..l+r/2]Temp2←Min2A[l..l+r/2]+1..rIftemp1≤temp2returntemp1Elsereturntemp2a.建立該算法所做的的操作次數(shù)的遞推關(guān)系并求解b.算法Min1和Min2哪個(gè)更快?有其他更好的算法嗎?解:a.習(xí)題2.53.java的基本數(shù)據(jù)類型int和long的最大值分別是當(dāng)n最小為多少的時(shí)候,第n個(gè)斐波那契數(shù)能夠使下面的類型溢出。類型b.long類型4.爬梯子假設(shè)每一步可以爬一個(gè)或兩格梯子,爬一部n格梯子一共可以用幾種的不同方法?(例如,一部3格的梯子可以用三種不同的方法爬:1-1-1,1-2和2-1)。6.改進(jìn)算法Fib,使它只需要?(1)的額外空間。7.證明等式:答:數(shù)學(xué)歸納法證明習(xí)題2.6考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來(lái)對(duì)關(guān)鍵比較次數(shù)進(jìn)行計(jì)數(shù).算法SortAnalysisA[0..n-1]//input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[0..n-1]//output:所做的關(guān)鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej0andA[j]vdocount←count+1A[j+1]←A[j]j←j+1A[j+1]←vreturncount比較計(jì)數(shù)器是否插在了正確的位置?如果不對(duì),請(qǐng)改正.解:應(yīng)改為:算法SortAnalysisA[0..n-1]//input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[0..n-1]//output:所做的關(guān)鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej0andA[j]vdocount←count+1A[j+1]←A[j]j←j+1ifj0countcount+1A[j+1]←vreturncount習(xí)題3.14.a.設(shè)計(jì)一個(gè)蠻力算法,對(duì)于給定的x0,計(jì)算下面多項(xiàng)式的值:Pxanxn+an-1xn-1+…+a1x+a0并確定該算法的最差效率類型.b.如果你設(shè)計(jì)的算法屬于Θn2,請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法.C.對(duì)于該問(wèn)題來(lái)說(shuō),能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢?解:AlgorithmsBruteForcePolynomialEvaluationP[0..n],x//由高冪到低冪用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低冪到高冪的常系數(shù),以及定值x//輸出:多項(xiàng)式p在給定點(diǎn)x的值p0.0forinto0dopower1forj1toidopowerpower*xpp+P[i]*powerreturnp算法效率分析:基本操作:兩個(gè)數(shù)相乘,且Mn僅依賴于多項(xiàng)式的階nthaabovealgorithmsisveryinefficient,becausewerecomputepowersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputexibyusingxi-1.AlgorithmsBetterBruteForcePolynomialEvaluationP[0..n],x//由高冪到低冪用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低冪到高冪的常系數(shù),以及定值x//輸出:多項(xiàng)式p在給定點(diǎn)x的值PP[0]power1fori←1tondopower←power*xp←p+P[i]*powerreturnp基本操作乘法運(yùn)算總次數(shù)Mn:c.不行.因?yàn)橛?jì)算任意一個(gè)多項(xiàng)式在任意點(diǎn)x的值,都必須處理它的n+1個(gè)系數(shù).例如:x1,pxan+an-1+..+a1+a0,至少要做n次加法運(yùn)算5.應(yīng)用選擇排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.6.選擇排序是穩(wěn)定的嗎?不穩(wěn)定7.用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的Θn2效率?Yes.Bothoperation?findingthesmallestelementandswappingit?canbedoneasefficientlywiththelinkedlistaswithanarray8.應(yīng)用冒泡排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.9.a.請(qǐng)證明,如果對(duì)列表比較一遍之后沒(méi)有交換元素的位置,那么這個(gè)表已經(jīng)排好序了,算法可以停止了.b.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a.c.請(qǐng)證明改進(jìn)的算法最差效率也是平方級(jí)的.Hints:第i趟冒泡可以表示為:如果沒(méi)有發(fā)生交換位置,那么:b.AlgorithmsBetterBubblesortA[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←falsefori0tocount-1doifA[i+1]A[i]swapA[i],A[i+1]flag←truecount←count-1c最差情況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來(lái)的冒泡排序.10.冒泡排序是穩(wěn)定的嗎?穩(wěn)定習(xí)題3.2對(duì)限位器版的順序查找算法的比較次數(shù):在最差情況下在平均情況下.假設(shè)成功查找的概率是p0p1Hints:Cworstnn+1在成功查找下,對(duì)于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比較次數(shù)是i.在查找不成功時(shí),比較次數(shù)是n+1,可能性是1-p.6.給出一個(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ù):mn-m+17.為蠻力字符匹配算法寫(xiě)一個(gè)偽代碼,對(duì)于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.AlgorithmsBFStringmatchT[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←0whilejmandP[j]T[i+j]j←j+1ifjmcount←count+1returncount8.如果所要搜索的模式包含一些英語(yǔ)中較少見(jiàn)的字符,我們應(yīng)該如何修改該蠻力算法來(lái)利用這個(gè)信息.Hint:每次都從這些少見(jiàn)字符開(kāi)始比較,如果匹配,則向左邊和右邊進(jìn)行其它字符的比較.習(xí)題3.48.解釋一下如何對(duì)排序問(wèn)題應(yīng)用窮舉查找,并確定這種算法的效率類型。答:生成給定元素的一個(gè)排列,通過(guò)連續(xù)比較它們之間的元素,檢查他們是否符合排序的要求。如果符合就停止,否則重新生成新的排列。最差情況生成排列的個(gè)數(shù)是n!,每趟連續(xù)元素比較次數(shù)為n-1次。所以效率類型為O(n!(n-1))。9.幻方一個(gè)n階幻方是把從1到n2的整數(shù)填入一個(gè)n階方陣,每個(gè)整數(shù)只出現(xiàn)一次,使得每一行,每一列,每一條主對(duì)角線的和都相等。a.證明:如果一個(gè)n階幻方存在的話,所討論的和一定等于nn2+1/2。答:令s為n階幻方的每一行的和。則把從1到n2的整數(shù)求和可得如下式子由上式可得:習(xí)題4.11.a.為一個(gè)分治算法編寫(xiě)偽代碼,該算法求一個(gè)n個(gè)元素?cái)?shù)組中最大元素的位置b.如果數(shù)組中的若干個(gè)元素都具有最大值,該算法的輸出是怎樣的呢c.建立該算法的鍵值比較次數(shù)的遞推關(guān)系式并求解d.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較解:a.AlgorithmsIndexA[l..r]Input:Aportion