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

1、word算法設(shè)計(jì)與分析根底課后練習(xí)答案習(xí)題1.1 4.設(shè)計(jì)一個(gè)計(jì)算的算法，n是任意正整數(shù)。除了賦值和比擬運(yùn)算，該算法只能用到根本的四那么運(yùn)算操作。算法求 /輸入：一個(gè)正整數(shù)n2 /輸出：。step1:a=1； step2:假設(shè)a*an 轉(zhuǎn)step 3，否那么輸出a； step3:a=a+1轉(zhuǎn)step 2；5. a用歐幾里德算法求gcd31415，14142。 b. 用歐幾里德算法求gcd31415，14142,比檢查minm，n和gcdm，n間連續(xù)整數(shù)的算法快多少倍？請(qǐng)估算一下。a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618)

2、=gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1.b.有a可知計(jì)算gcd31415，14142歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法，或者兩次除法，因此這個(gè)算法做除法的次數(shù)鑒于114142 和 214142之間，所以歐幾里德算法比此算法快114142/11 1300 與 214142/11 2600 倍之間。6.證明等式gcd(m,n)

3、=gcd(n,m mod n)對(duì)每一對(duì)正整數(shù)m,n都成立.Hint:根據(jù)除法的定義不難證明: l 如果d整除u和v, 那么d一定能整除uv; l 如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.對(duì)于任意一對(duì)正整數(shù)m,n,假設(shè)d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；顯然，假設(shè)d能整除n和r，也一定能整除m=r+qn和n。數(shù)對(duì)(m,n)和(n,r)具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故gcd(m,n)=gcd(n,r)7.對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字,歐幾里得算法將會(huì)如何處理該算法在處理這種輸入的過程中,上述情況最多會(huì)發(fā)生幾次Hint:對(duì)于任何形

4、如0=m0 temp2*a x1(-b+sqrt(D)/temp x2(-b-sqrt(D)/temp return x1,x2 else if D=0 return b/(2*a) else return “no real rootselse /a=0 if b0 return c/b else /a=b=0 if c=0 return “no real numbers else return “no real roots5. 描述將十進(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ù)

5、第一步：用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ù)組Bin1.n中i=1while n!=0 do Bini=n%2;n=(int)n/2;i+;while i!=0 doprint Bini;i-;9.考慮下面這個(gè)算法,它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略)對(duì)這個(gè)算法做盡可能多的改良.算法 MinDistance(A0.n-1)/輸入:數(shù)組A0

6、.n-1/輸出:the smallest distance d between two of its elements習(xí)題1.3 1. 考慮這樣一個(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”排序的過程如下所示:b.該算法不穩(wěn)定.比方對(duì)列表2,2*排序c.該算法不在位.額外空間for S and Count4.(古老的七橋問題)第2章習(xí)題2.1 7.對(duì)以下斷言進(jìn)行證

7、明:(如果是錯(cuò)誤的,請(qǐng)舉例)a. 如果t(n)O(g(n),那么g(n)(t(n)b.0時(shí),(g(n)= (g(n)解:a. 這個(gè)斷言是正確的。它指出如果t(n)的增長率小于或等于g(n)的增長率，那么 g(n)的增長率大于或等于t(n)的增長率 由 t(n)cg(n) for all nn0, where c0 那么： for all nn0b. 這個(gè)斷言是正確的。只需證明。設(shè)f(n)(g(n),那么有： for all n=n0, c0 for all n=n0, c1=c0即：f(n)(g(n)又設(shè)f(n)(g(n),那么有： for all n=n0,c0 for all n=n0,c

8、1=c/0即：f(n)(g(n)8證明本節(jié)定理對(duì)于以下符號(hào)也成立：a.符號(hào)b.符號(hào)證明：a。we need to proof that if t1(n)(g1(n) and t2(n)(g2(n), then t1(n)+ t2(n)(maxg1(n), g2(n)。由 t1(n)(g1(n)， t1(n)c1g1(n) for all n=n1, where c10由 t2(n)(g2(n)， T2(n)c2g2(n) for all n=n2, where c20那么，取c=minc1,c2,當(dāng)n=maxn1,n2時(shí)： t1(n)+ t2(n)c1g1(n)+ c2g2(n) c g1(n

9、)+c g2(n)cg1(n)+ g2(n) cmax g1(n), g2(n)所以以命題成立。b. t1(n)+t2(n) (證明：由大的定義知，必須確定常數(shù)c1、c2和n0，使得對(duì)于所有n=n0，有：由t1(n)(g1(n)知，存在非負(fù)整數(shù)a1,a2和n1使： a1*g1(n)=t1(n)=a2*g1(n)-(1)由t2(n)(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(a

10、2,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+g20，g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。那么3式轉(zhuǎn)換為：C1*max(g1,g2) = t1(n)+t2(n) =n0時(shí)上述不等式成立。證畢。習(xí)題2.22. 請(qǐng)用的非正式定義來判斷以下斷言是真還是假。a. n(n + 1)/2 O(n3) b. n(n + 1)/2 O(n2)c. n(n + 1)/2 (n3) d. n(n + 1)/2 (n)答：c假，其

11、它真。5.按照以下函數(shù)的增長次數(shù)對(duì)它們進(jìn)行排列按照從低到高的順序 (n2)!, 5lg(n+100)10, 22n, 0.001n4+3n3+1, ln2 n, ， 3n.答：習(xí)題2.31. 計(jì)算以下求和表達(dá)式的值。答：3. 考慮下面的算法。a 該算法求的是什么？b 它的根本操作是什么？c 該根本操作執(zhí)行了多少次？d 該算法的效率類型是什么？e 對(duì)該算法進(jìn)行改良，或者設(shè)計(jì)一個(gè)更好的算法，然后指出它們的效率類型。如果做不到這一點(diǎn)，請(qǐng)?jiān)囍C明這是不可能做到的。9.證明下面的公式：可以使用數(shù)學(xué)歸納法，也可以像10歲的高斯一樣，用洞察力來解決該問題。這個(gè)小學(xué)生長大以后成為有史以來最偉大的數(shù)學(xué)家之一。數(shù)

12、學(xué)歸納法：高斯的方法：習(xí)題2.41. 解以下遞推關(guān)系 做a,b當(dāng)n1時(shí)a. 解：當(dāng)n1時(shí)b.解：2. 對(duì)于計(jì)算n!的遞歸算法F(n)，建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求解。解：3. 考慮以下遞歸算法，該算法用來計(jì)算前n個(gè)立方的和：S(n)=13+23+n3。算法S(n) /輸入：正整數(shù)n /輸出：前n個(gè)立方的和if n=1 return 1else return S(n-1)+n*n*na. 建立該算法的根本操作次數(shù)的遞推關(guān)系并求解b. 如果將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比，你做何評(píng)價(jià)？解：7. a. 請(qǐng)基于公式2n=2n-1+2n-1，設(shè)計(jì)一個(gè)遞歸算法。當(dāng)n是任意非負(fù)整數(shù)的時(shí)候，該算法能夠計(jì)

13、算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的值If n=0 return 1Else return power(n-1)+ power(n-1)c.8.考慮下面的算法 算法 Min1(A0.n-1) /輸入:包含n個(gè)實(shí)數(shù)的數(shù)組A0.n-1 If n=1 return A0 Else tempMin1(A0.n-2) If tempAn-1 return t

14、emp Else return An-1a.該算法計(jì)算的是什么b.建立該算法所做的根本操作次數(shù)的遞推關(guān)系并求解解:a.計(jì)算的給定數(shù)組的最小值for all n1n=1b.9.考慮用于解決第8題問題的另一個(gè)算法,該算法遞歸地將數(shù)組分成兩半.我們將它稱為Min2(A0.n-1)算法 Min(Ar.l) If l=r return Al Else temp1Min2(Al.(l+r)/2) Temp2Min2(Al.(l+r)/2+1.r) If temp1temp2 return temp1 Else return temp2a.建立該算法所做的的操作次數(shù)的遞推關(guān)系并求解b.算法Min1和Min2

15、哪個(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.改良算法Fib，使它只需要1的額外空間。7.證明等式：答：數(shù)學(xué)歸納法證明習(xí)題2.6 1. 考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來對(duì)關(guān)鍵比擬次數(shù)進(jìn)行計(jì)數(shù).算法SortAnalysis(A0.n-1)/input:包含n個(gè)可排序元素的一個(gè)數(shù)組A0.

16、n-1/output:所做的關(guān)鍵比擬的總次數(shù)count0for i1 to n-1 do vAi ji-1 while j0 and Ajv do countcount+1 Aj+1Aj jj+1 Aj+1vreturn count比擬計(jì)數(shù)器是否插在了正確的位置如果不對(duì),請(qǐng)改正.解:應(yīng)改為:算法SortAnalysis(A0.n-1)/input:包含n個(gè)可排序元素的一個(gè)數(shù)組A0.n-1/output:所做的關(guān)鍵比擬的總次數(shù)count0for i1 to n-1 do vAi ji-1 while j0 and Ajv do countcount+1 Aj+1Aj jj+1 if j=0 co

17、unt=count+1 Aj+1vreturn count習(xí)題3.14. a.設(shè)計(jì)一個(gè)蠻力算法,對(duì)于給定的x0,計(jì)算下面多項(xiàng)式的值:P(x)=anxn+an-1xn-1+a1x+a0并確定該算法的最差效率類型.b.如果你設(shè)計(jì)的算法屬于(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法.C.對(duì)于該問題來說,能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢解:a. Algorithms BruteForcePolynomialEvaluation(P0.n,x)/由高冪到低冪用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值/輸入:P0.n是多項(xiàng)式按低冪到高冪的常系數(shù),以及定值x/輸出: 多項(xiàng)式p在給定點(diǎn)x的值p=0.0for i=

18、n to 0 do power=1 for j=1 to i do power=power*x p=p+Pi*powerreturn p算法效率分析:根本操作:兩個(gè)數(shù)相乘,且M(n)僅依賴于多項(xiàng)式的階nb. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from the lowest term to the highest and

19、compute xi by using xi-1.Algorithms BetterBruteForcePolynomialEvaluation(P0.n,x)/由高冪到低冪用蠻力法計(jì)算多項(xiàng)式p在給定點(diǎn)x的值/輸入:P0.n是多項(xiàng)式按低冪到高冪的常系數(shù),以及定值x/輸出: 多項(xiàng)式p在給定點(diǎn)x的值 P=P0 power=1 for i1 to n do powerpower*x pp+Pi*power return p根本操作乘法運(yùn)算總次數(shù)M(n):c.不行.因?yàn)橛?jì)算任意一個(gè)多項(xiàng)式在任意點(diǎn)x的值,都必須處理它的n+1 個(gè)系數(shù).例如: (x=1,p(x)=an+an-1+.+a1+a0,至少要做n

20、次加法運(yùn)算) 5.應(yīng)用選擇排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.6.選擇排序是穩(wěn)定的嗎(不穩(wěn)定)7.用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的(n2)效率Yes.Both operationfinding the smallest element and swapping it can be done as efficiently with the linked list as with an array. 8.應(yīng)用冒泡排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.9.a.請(qǐng)證明,如果對(duì)列表比擬一遍之后沒有交換元素的位置,那么這個(gè)表已經(jīng)排好序了,算法可以停止了.b

21、.結(jié)合所做的改良,為冒泡排序?qū)懸欢蝹未a.c.請(qǐng)證明改良的算法最差效率也是平方級(jí)的.Hints:a. 第i趟冒泡可以表示為:如果沒有發(fā)生交換位置,那么:b.Algorithms BetterBubblesort(A0.n-1)/用改良的冒泡算法對(duì)數(shù)組A0.n-1排序/輸入:數(shù)組A0.n-1/輸出:升序排列的數(shù)組A0.n-1countn-1 /進(jìn)行比擬的相鄰元素對(duì)的數(shù)目flagtrue /交換標(biāo)志while flag do flagfalse for i=0 to count-1 do if Ai+1Ai swap(Ai,Ai+1) flagtrue countcount-1c最差情況是數(shù)組是嚴(yán)

22、格遞減的,那么此時(shí)改良的冒泡排序會(huì)蛻化為原來的冒泡排序.10.冒泡排序是穩(wěn)定的嗎(穩(wěn)定)習(xí)題3.21. 對(duì)限位器版的順序查找算法的比擬次數(shù):a. 在最差情況下b. 在平均情況下.假設(shè)成功查找的概率是p(0=p=1)Hints:a. Cworst(n)=n+1b. 在成功查找下,對(duì)于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比擬次數(shù)是i.在查找不成功時(shí),比擬次數(shù)是n+1,可能性是1-p.6.給出一個(gè)長度為n的文本和長度為m的模式構(gòu)成的實(shí)例,它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出,對(duì)于這樣的輸入需要做多少次字符比擬運(yùn)算.Hints:文本:由n個(gè)0組成的文本模式:前m-1個(gè)是0,最

23、后一個(gè)字符是1比擬次數(shù): m(n-m+1)7.為蠻力字符匹配算法寫一個(gè)偽代碼,對(duì)于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.Algorithms BFStringmatch(T0.n-1,P0.m-1)/蠻力字符匹配/輸入:數(shù)組T0.n-1長度為n的文本,數(shù)組P0.m-1長度為m的模式/輸出:在文本中匹配成功的子串?dāng)?shù)量count0for i0 to n-m do j0 while j1 C(1)=0 設(shè)n=2k，C(2k)=2C(2k-1)+1 =22 C(2k-2)+1+1=22C(2k-2)+2+1 =222C(2k-3)+1+2+1=23C(2k-3)+ 22+2+1 =.

24、=2iC(2k-i)+ 2i-1+2 i-2 +.+2+1 =. =2kC(2k-k)+ 2k-1+2 k-2 +.+2+1=2k1=n-1可以證明C(n)=n-1對(duì)所有n1的情況都成立n是偶數(shù)或奇數(shù)d.比擬的次數(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è)問題的最大值和最小值。 算法 MaxM

25、in(Al.r,Max,Min) /該算法利用分治技術(shù)得到數(shù)組A中的最大值和最小值/輸入：數(shù)值數(shù)組Al.r/輸出：最大值Max和最小值Minif(r=l) MaxAl；MinAl; /只有一個(gè)元素時(shí)elseif rl=1 /有兩個(gè)元素時(shí)if AlArMaxAr; MinAlelseMaxAl; MinArelse /rl1MaxMin(Al,(l+r)/2,Max1,Min1); /遞歸解決前一局部MaxMin(A(l+r/)2.r,Max2,Min2); /遞歸解決后一局部if Max1Max2 Max= Max2 /從兩局部的兩個(gè)最大值中選擇大值if Min22C(1)=0, C(2)=1

26、C(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的最大值和最小值/輸入：數(shù)值數(shù)組Al.r/輸出：最大值Max和最小值MinMax=Min=Al;for i=l+1 to r do

27、if AiMax MaxAi;else if Ai1 (n=2k)Cbest(1)=0c. 鍵值比擬次數(shù)M(n)M(n)=2M(n)+2n for n1M(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: With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the

28、pivot is larger than the other elements.Appending a sentinel(限位器) of value equal A0(or larger than A0) after the arrays last element , the quicksort algorithms will stop the index of the left-to-right scan of A0.n-1 from going beyond position n.8.設(shè)計(jì)一個(gè)算法對(duì)n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列,使得其中所有的負(fù)元素都位于正元素之前.這個(gè)算法需要兼顧空間和

29、時(shí)間效率. Algorithms netbeforepos(A0.n-1)/使所有負(fù)元素位于正元素之前/輸入:實(shí)數(shù)組A0.n-1/輸出:所有負(fù)元素位于于正元素之前的實(shí)數(shù)組A0.n-1A-1-1; An1 /限位器i0; jn-1While i1時(shí), Cw(n)=Cw(n/2)+1, Cw(1)=1(略)4.如果對(duì)于一個(gè)100000個(gè)元素的數(shù)組成功查找的話,使用折半查找比順序查找要快多少倍6 如何將折半查找應(yīng)用于范圍查找范圍查找就是對(duì)于一個(gè)有序數(shù)組,找出位于給定值L、U之間包含L、U的所有元素，Lr return -1else m (l+r)/2if K=Am return melse if K

30、 Am return BSR(Am+1,r,K)8.設(shè)計(jì)一個(gè)只使用兩路比擬的折半查找算法，即只用和=, 或者只用和=.Algorithms TwoWaysBinarySearch(Ao.n-1,K)/二路比擬的折半查找/有序子數(shù)組Al.r和查找鍵值K/查找成功那么輸出其下標(biāo)，否那么輸出-1l0, rn-1while lr do m (l+r)/2if KAmr melse l m+1if K=Al return lelse return -1習(xí)題4.53. 用課文中介紹的分治算法來計(jì)算2101*1130.習(xí)題4.61.a.為最近對(duì)問題的一維版本設(shè)計(jì)一個(gè)直接基于分治技術(shù)的算法,并確定它的效率類型

31、b.對(duì)于這個(gè)問題,它是一個(gè)好算法嗎解:a. Algorithms ClosestNumber(Al.r)/分治計(jì)算最近對(duì)問題的一維版本/輸入:升序排列的實(shí)數(shù)子數(shù)組Al.r/輸出:最近數(shù)對(duì)的距離If r=l return Else if rl=1 return ArAl Else return minClosestNumber(Al (l+r)/2 ), ClosestNumber(A (l+r)/2 .r) A (l+r)/2 +1A (l+r)/2 設(shè)遞歸的時(shí)間效率為T(n):對(duì)n=2k, 那么: T(n)=2T(n/2)+c利用主定理求解.T(n)=(n)2.(題略)習(xí)題5.14. 應(yīng)用插入排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.答:插入排序過程如下:習(xí)題5.42. 使用下面的方法生成1,2,3,4的全部排列:a. 從底向上的最小變化算法。b. Johnson-Trotter算法。c. 字典序算法。答：從底向上的最小變化算法過程如下：bJohnson-Trotter算法實(shí)現(xiàn)如下： c .字典序算法實(shí)現(xiàn)如下