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

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

2、8) =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ì)算gcd（31415，14142）歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測(cè)算法在14142每次迭代過(guò)程中或者做了一次除法，或者兩次除法，因此這個(gè)算法做除法的次數(shù)鑒于1·14142 和 2·14142之間，所以歐幾里德算法比此算法快1·14142/11 1300 與 2·141

3、42/11 2600 倍之間。6.證明等式gcd(m,n)=gcd(n,m mod n)對(duì)每一對(duì)正整數(shù)m,n都成立.Hint:根據(jù)除法的定義不難證明: l 如果d整除u和v, 那么d一定能整除u±v; l 如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.對(duì)于任意一對(duì)正整數(shù)m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；顯然，若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ì)如何處理該算法

4、在處理這種輸入的過(guò)程中,上述情況最多會(huì)發(fā)生幾次Hint:對(duì)于任何形如0<=m<n的一對(duì)數(shù)字,Euclid算法在第一次疊代時(shí)交換m和n, 即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次.8.a.對(duì)于所有1m,n10的輸入, Euclid算法最少要做幾次除法(1次) b. 對(duì)于所有1m,n10的輸入, Euclid算法最多要做幾次除法(5次) gcd(5,8)習(xí)題1.2 1.(農(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è)算法能求方程ax2+bx+c=0的實(shí)根,寫(xiě)出上述算法的偽代碼

5、(可以假設(shè)sqrt(x)是求平方根的函數(shù))算法Quadratic(a,b,c)/求方程ax2+bx+c=0的實(shí)根的算法/輸入:實(shí)系數(shù)a,b,c/輸出:實(shí)根或者無(wú)解信息If a0 Db*b-4*a*c If D>0 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 roots”else /a=0 if b0 return c/b else /a=b=0 if c=0 return “no real numbers” else r

6、eturn “no real roots”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ù)賦給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+;whi

7、le i!=0 doprint Bini;i-;9.考慮下面這個(gè)算法,它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略)對(duì)這個(gè)算法做盡可能多的改進(jìn).算法 MinDistance(A0.n-1)/輸入:數(shù)組A0.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ì)列表

8、”60,35,81,98,14,47”排序的過(guò)程如下所示:b.該算法不穩(wěn)定.比如對(duì)列表”2,2*”排序c.該算法不在位.額外空間for S and Count4.(古老的七橋問(wèn)題)第2章習(xí)題2.1 7.對(duì)下列斷言進(jìn)行證明:(如果是錯(cuò)誤的,請(qǐng)舉例)a. 如果t(n)O(g(n),則g(n)(t(n)b.>0時(shí),(g(n)= (g(n)解:a. 這個(gè)斷言是正確的。它指出如果t(n)的增長(zhǎng)率小于或等于g(n)的增長(zhǎng)率，那么 g(n)的增長(zhǎng)率大于或等于t(n)的增長(zhǎng)率 由 t(n)c·g(n) for all nn0, where c>0 則： for all nn0b. 這個(gè)斷

9、言是正確的。只需證明。設(shè)f(n)(g(n),則有： for all n>=n0, c>0 for all n>=n0, c1=c>0即：f(n)(g(n)又設(shè)f(n)(g(n),則有： for all n>=n0,c>0 for all n>=n0,c1=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)，

10、t1(n)c1g1(n) for all n>=n1, where c1>0由 t2(n)(g2(n)， T2(n)c2g2(n) for all n>=n2, where c2>0那么，取c>=minc1,c2,當(dāng)n>=maxn1,n2時(shí)： t1(n)+ t2(n)c1g1(n)+ c2g2(n) c g1(n)+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ù)整

11、數(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(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)

12、<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)c1min(a1,b1),c22c2=2max(c1,c2)，n0max(n1,n2)時(shí)，當(dāng)n>=n0時(shí)上述不等式成立。證畢。習(xí)題2.22. 請(qǐng)用的非正式定義來(lái)判斷下列斷言是真還是假。a. n(n + 1)/2 O(n3) b. n(n + 1)/2 O(n2)c. n(n + 1)/2 (n3

13、) d. n(n + 1)/2 (n)答：c假，其它真。5.按照下列函數(shù)的增長(zhǎng)次數(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 該算法的效率類(lèi)型是什么？e 對(duì)該算法進(jìn)行改進(jìn)，或者設(shè)計(jì)一個(gè)更好的算法，然后指出它們的效率類(lèi)型。如果做不到這一點(diǎn)，請(qǐng)?jiān)囍C明這是不可能做到的。9.證明下面的公式：可以使用數(shù)學(xué)歸納法，也可以像10歲的高斯一樣，用洞察力來(lái)解決該問(wèn)題

14、。這個(gè)小學(xué)生長(zhǎng)大以后成為有史以來(lái)最偉大的數(shù)學(xué)家之一。數(shù)學(xué)歸納法：高斯的方法：習(xí)題2.41. 解下列遞推關(guān)系 （做a,b）當(dāng)n>1時(shí)a. 解：當(dāng)n>1時(shí)b.解：2. 對(duì)于計(jì)算n!的遞歸算法F(n)，建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求解。解：3. 考慮下列遞歸算法，該算法用來(lái)計(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=2

15、n-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.算法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

16、tempMin1(A0.n-2) If tempAn-1 return temp Else return An-1a.該算法計(jì)算的是什么b.建立該算法所做的基本操作次數(shù)的遞推關(guān)系并求解解:a.計(jì)算的給定數(shù)組的最小值for all n>1n=1b.9.考慮用于解決第8題問(wèn)題的另一個(gè)算法,該算法遞歸地將數(shù)組分成兩半.我們將它稱(chēng)為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

17、temp2a.建立該算法所做的的操作次數(shù)的遞推關(guān)系并求解b.算法Min1和Min2哪個(gè)更快有其他更好的算法嗎解:a.習(xí)題2.53.java的基本數(shù)據(jù)類(lèi)型int和long的最大值分別是當(dāng)n最小為多少的時(shí)候，第n個(gè)斐波那契數(shù)能夠使下面的類(lèi)型溢出。類(lèi)型 b.long類(lèi)型4.爬梯子 假設(shè)每一步可以爬一個(gè)或兩格梯子，爬一部n格梯子一共可以用幾種的不同方法（例如，一部3格的梯子可以用三種不同的方法爬：1-1-1，1-2和2-1）。6.改進(jìn)算法Fib，使它只需要（1）的額外空間。7.證明等式：答：數(shù)學(xué)歸納法證明習(xí)題2.6 1. 考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來(lái)對(duì)關(guān)鍵比較次數(shù)進(jìn)行計(jì)數(shù).算法

18、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 j>0 and Aj>v 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 wh

19、ile j>0 and Aj>v do countcount+1 Aj+1Aj jj+1 if j>=0 count=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并確定該算法的最差效率類(lèi)型.b.如果你設(shè)計(jì)的算法屬于(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法.C.對(duì)于該問(wèn)題來(lái)說(shuō),能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢解:a. Algorithms BruteForcePolynomialEvaluation(P0.n,x)/由高冪到低冪用蠻力法計(jì)算多項(xiàng)

20、式p在給定點(diǎn)x的值/輸入:P0.n是多項(xiàng)式按低冪到高冪的常系數(shù),以及定值x/輸出: 多項(xiàng)式p在給定點(diǎn)x的值p=0.0for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+Pi*powerreturn p算法效率分析:基本操作:兩個(gè)數(shù)相乘,且M(n)僅依賴(lài)于多項(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 th

21、em.In fact ,we can move from the lowest term to the highest and 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ì)算任

22、意一個(gè)多項(xiàng)式在任意點(diǎn)x的值,都必須處理它的n+1 個(gè)系數(shù).例如: (x=1,p(x)=an+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.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,

23、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:a. 第i趟冒泡可以表示為:如果沒(méi)有發(fā)生交換位置,那么:b.Algorithms BetterBubblesort(A0.n-1)/用改進(jìn)的冒泡算法對(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 co

24、unt-1 do if Ai+1<Ai swap(Ai,Ai+1) flagtrue countcount-1c最差情況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來(lái)的冒泡排序.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è)長(zhǎng)度為n的文本和長(zhǎng)度為m的模式構(gòu)成的

25、實(shí)例,它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出,對(duì)于這樣的輸入需要做多少次字符比較運(yùn)算.Hints:文本:由n個(gè)0組成的文本模式:前m-1個(gè)是0,最后一個(gè)字符是1比較次數(shù): m(n-m+1)7.為蠻力字符匹配算法寫(xiě)一個(gè)偽代碼,對(duì)于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.Algorithms BFStringmatch(T0.n-1,P0.m-1)/蠻力字符匹配/輸入:數(shù)組T0.n-1長(zhǎng)度為n的文本,數(shù)組P0.m-1長(zhǎng)度為m的模式/輸出:在文本中匹配成功的子串?dāng)?shù)量count0for i0 to n-m do j0 while j<m and Pj=Ti+j jj+1 if

26、 j=m countcount+1return count8.如果所要搜索的模式包含一些英語(yǔ)中較少見(jiàn)的字符,我們應(yīng)該如何修改該蠻力算法來(lái)利用這個(gè)信息.Hint:每次都從這些少見(jiàn)字符開(kāi)始比較,如果匹配, 則向左邊和右邊進(jìn)行其它字符的比較.習(xí)題3.48.解釋一下如何對(duì)排序問(wèn)題應(yīng)用窮舉查找，并確定這種算法的效率類(lèi)型。答：生成給定元素的一個(gè)排列，通過(guò)連續(xù)比較它們之間的元素，檢查他們是否符合排序的要求。如果符合就停止，否則重新生成新的排列。最差情況生成排列的個(gè)數(shù)是n！，每趟連續(xù)元素比較次數(shù)為n-1次。所以效率類(lèi)型為O（n！（n-1）。9.幻方 一個(gè)n階幻方是把從1到 n2的整數(shù)填入一個(gè)n階方陣，每個(gè)整數(shù)

27、只出現(xiàn)一次，使得每一行，每一列，每一條主對(duì)角線的和都相等。a.證明：如果一個(gè)n階幻方存在的話，所討論的和一定等于n(n2+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.Algorithms MaxIndex(Al.r)Input:A portion of array A0.n-1 between

28、indices l and r(lr)Output: The index of the largest element in Al.rif l=r return lelse temp1MaxIndex(Al.(l+r)/2)temp2MaxIndex(A(l+r)/2.r)if Atemp1Atemp2 return temp1else return temp2b.返回?cái)?shù)組中位于最左邊的最大元素的序號(hào).c.鍵值比較次數(shù)的遞推關(guān)系式: C(n)=C( n/2 )+C( n/2 )+1 for n>1 C(1)=0 設(shè)n=2k，C(2k)=2C(2k-1)+1 =22 C(2k-2)+1+1

29、=22C(2k-2)+2+1 =222C(2k-3)+1+2+1=23C(2k-3)+ 22+2+1 =. =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ì)所有n>1的情況都成立（n是偶數(shù)或奇數(shù)）d.比較的次數(shù)相同，但蠻力算法不用遞歸調(diào)用。2、a.為一個(gè)分治算法編寫(xiě)偽代碼，該算法同時(shí)求出一個(gè)n元數(shù)組的最大元素和最小元素的值。b.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較。c.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較。解答： a.同時(shí)求出最大值和最小值，只需要將原數(shù)組一分

30、為二，再使用相同的方法找出這兩個(gè)部分中的最大值和最小值，然后經(jīng)過(guò)比較就可以得到整個(gè)問(wèn)題的最大值和最小值。 算法 MaxMin(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 /rl>1MaxMin(Al,(l+r)/2,Max1,Min1); /遞歸解決前一部分MaxMin(A(l+r/)2.r,Max2,Min2); /遞歸解決

31、后一部分if Max1Max2 Max= Max2 /從兩部分的兩個(gè)最大值中選擇大值if Min2<Min1 Min=Min2; /從兩部分的兩個(gè)最小值中選擇小值b.假設(shè)n=2k,比較次數(shù)的遞推關(guān)系式:C(n)=2C(n/2)+2 for n>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+2

32、k-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 if Ai>Max MaxAi;else if Ai<Min MinAireturn Max,Min時(shí)間復(fù)雜度t(n)=2(n-1)算法MaxMin的時(shí)間復(fù)雜度為3n/2-2，simpleMaxMin的時(shí)間復(fù)雜度為2n-2，都屬于(n)，但比較一下發(fā)現(xiàn)，MaxMin的速度要比simpleMaxMin的

33、快一些。 6.應(yīng)用合并排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序.3218.a.對(duì)合并排序的最差鍵值比較次數(shù)的遞推關(guān)系式求解.(for n=2k)b.建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關(guān)系式求解.(for n=2k)c.對(duì)于4.1節(jié)給出的合并排序算法,建立它的鍵值移動(dòng)次數(shù)的遞推關(guān)系式.考慮了該算法的鍵值移動(dòng)次數(shù)之后,是否會(huì)影響它的效率類(lèi)型呢解:a. 遞推關(guān)系式見(jiàn)4.1節(jié).b. 最好情況(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 for n>1 (n=2k)Cbest(1)=0c. 鍵值比較次數(shù)M(n)M(n)=2M(n)+2n for n>1M

34、(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)是多少年來(lái)為什么一個(gè)限位器就能滿(mǎn)足所有的輸入呢 Hints: With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the pivot is larger than the other elements.Appending a sentinel(限位器) of value

35、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è)算法需要兼顧空間和時(shí)間效率. Algorithms netbeforepos(A0.n-1)/使所有負(fù)元素位于正元素之前/輸入:實(shí)數(shù)組A0.n-1/輸出:所有負(fù)元素位于

36、于正元素之前的實(shí)數(shù)組A0.n-1A-1-1; An1 /限位器i0; jn-1While i<j do While Ai0 do ii+1while Aj0 do jj-1swap Aiand Ajswap Aiand Aj /undo the last swap當(dāng)全是非負(fù)數(shù)或全是非正數(shù)時(shí)需要限位器.習(xí)題4.32. 當(dāng)n=2k時(shí),用反向替換法求下面的遞推方程:當(dāng)n>1時(shí), Cw(n)=Cw(n/2)+1, Cw(1)=1(略)4.如果對(duì)于一個(gè)100000個(gè)元素的數(shù)組成功查找的話,使用折半查找比順序查找要快多少倍6 如何將折半查找應(yīng)用于范圍查找范圍查找就是對(duì)于一個(gè)有序數(shù)組,找出位于給

37、定值L、U之間（包含L、U）的所有元素，L<=U。該算法的最差效率是多少？Hints:Step1: 檢查A0L，An-1U是否成立，若不成立，則無(wú)解。否則進(jìn)入step 2Step2:在數(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的值。）7 為折半查找寫(xiě)遞歸的偽代碼。Algorithms BSR(Ao.n-1,K)/折半

38、查找遞歸算法/有序子數(shù)組Al.r和查找鍵值K/查找成功則輸出其下標(biāo)，否則輸出-1if l>r return -1else m (l+r)/2if K=Am return melse if K< Am return BSR(Al.m-1,K)else if K> 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 l<

39、;r do m (l+r)/2if KAmr melse l m+1if K=Al return lelse return -1習(xí)題4.53. 用課文中介紹的分治算法來(lái)計(jì)算2101*1130.習(xí)題4.61.a.為最近對(duì)問(wèn)題的一維版本設(shè)計(jì)一個(gè)直接基于分治技術(shù)的算法,并確定它的效率類(lèi)型b.對(duì)于這個(gè)問(wèn)題,它是一個(gè)好算法嗎解:a. Algorithms ClosestNumber(Al.r)/分治計(jì)算最近對(duì)問(wèn)題的一維版本/輸入:升序排列的實(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)/