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

1、Program算法設(shè)計(jì)與分析基礎(chǔ)中文版答案習(xí)題1.1 5.證明等式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)6.對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字,歐幾里

2、得算法將會(huì)如何處理?該算法在處理這種輸入的過(guò)程中,上述情況最多會(huì)發(fā)生幾次?Hint:對(duì)于任何形如0<=m<n的一對(duì)數(shù)字,Euclid算法在第一次疊代時(shí)交換m和n, 即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次.7.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

3、=0的實(shí)根,寫出上述算法的偽代碼(可以假設(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

4、 numbers” else return “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

5、=(int)n/2;i+;while 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.

6、該算法在位嗎?解:a. 該算法對(duì)列表”60,35,81,98,14,47”排序的過(guò)程如下所示:b.該算法不穩(wěn)定.比如對(duì)列表”2,2*”排序c.該算法不在位.額外空間for S and Count4.(古老的七橋問(wèn)題)習(xí)題1.41.請(qǐng)分別描述一下應(yīng)該如何實(shí)現(xiàn)下列對(duì)數(shù)組的操作,使得操作時(shí)間不依賴數(shù)組的長(zhǎng)度.a.刪除數(shù)組的第i個(gè)元素(1<=i<=n)b.刪除有序數(shù)組的第i個(gè)元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the

7、 ith element with a special symbol that cannot be a value of the arrays element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty.(“l(fā)azy deletion”)第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(

8、n)的增長(zhǎng)率大于或等于t(n)的增長(zhǎng)率 由 t(n)c·g(n) for all nn0, where c>0 則： for all nn0b. 這個(gè)斷言是正確的。只需證明。設(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 th

9、at 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 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)所

10、以以命題成立。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(a2,b2)，則 C1*(g

11、1+g2)<= t1(n)+t2(n) <=c2(g1+g2)-(3)不失一般性假設(shè)max(g1(n),g2(n)=g1(n).顯然，g1(n)+g2(n)<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í)

12、題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à)？解：a.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)用樹(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 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 n>1n=1b.9.考慮用于解決第8題問(wèn)題的另一個(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

15、和Min2哪個(gè)更快?有其他更好的算法嗎?解:a.習(xí)題2.6 1. 考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來(lái)對(duì)關(guān)鍵比較次數(shù)進(jìn)行計(jì)數(shù).算法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è)

16、可排序元素的一個(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 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并確定該算法的最差效率類型.b.如果你設(shè)計(jì)的算法屬于(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法.C.對(duì)于該問(wèn)題來(lái)說(shuō),能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢

17、?解: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=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

18、 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 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

19、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次加法運(yùn)算) 5.應(yīng)用選擇排序?qū)π蛄衑xample按照字母順序排序.6.選擇排序是穩(wěn)定的嗎?(不穩(wěn)定)7.用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版相同的(n2)效率?Yes.Both operationfinding the smallest element and swapping it can be done as effi

20、ciently with the linked list as with an array. 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)志whil

21、e flag do flagfalse for i=0 to count-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+

22、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ù): m(n-m+1)7.為蠻力字符匹配算法寫一個(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 j

23、0 while j<m and Pj=Ti+j jj+1 if j=m countcount+1return count8.如果所要搜索的模式包含一些英語(yǔ)中較少見(jiàn)的字符,我們應(yīng)該如何修改該蠻力算法來(lái)利用這個(gè)信息.Hint:每次都從這些少見(jiàn)字符開(kāi)始比較,如果匹配, 則向左邊和右邊進(jìn)行其它字符的比較.習(xí)題4.11.a.為一個(gè)分治算法編寫偽代碼,該算法求一個(gè)n個(gè)元素?cái)?shù)組中最大元素的位置.b.如果數(shù)組中的若干個(gè)元素都具有最大值,該算法的輸出是怎樣的呢?c.建立該算法的鍵值比較次數(shù)的遞推關(guān)系式并求解.d.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較解:a.Algorithms MaxIndex(Al

24、.r)Input:A portion of array A0.n-1 between 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(

25、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 =. =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è)分治算法編寫偽代碼，該算法同時(shí)求出一個(gè)n元數(shù)組的最大元素和最小元素的值。b.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較。c.請(qǐng)拿該算法與

26、解同樣問(wèn)題的蠻力算法做一個(gè)比較。解答： a.同時(shí)求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個(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); /

27、遞歸解決前一部分MaxMin(A(l+r/)2.r,Max2,Min2); /遞歸解決后一部分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(

28、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 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ù)雜度為2

29、n-2，都屬于(n)，但比較一下發(fā)現(xiàn)，MaxMin的速度要比simpleMaxMin的快一些。 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ì)影響它的效率類型呢?解:a. 遞推關(guān)系式見(jiàn)4.1節(jié).b. 最好情況(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 for n>1 (n=2k)Cbes

30、t(1)=0c. 鍵值比較次數(shù)M(n)M(n)=2M(n)+2n for n>1M(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è)限位器就能滿足所有的輸入呢? 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 othe

31、r 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è)算法需要兼顧空間和時(shí)間效率. Algorithms netbeforepos

32、(A0.n-1)/使所有負(fù)元素位于正元素之前/輸入:實(shí)數(shù)組A0.n-1/輸出:所有負(fù)元素位于于正元素之前的實(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.31.(題略)解:a.由公式4.4得:4次b.二分查找判定樹(shù):所以,14,31,42,74,85,98需要比較4次c. d.2. 當(dāng)n=2k時(shí),用反向替換法求下面的遞推方程:當(dāng)n>1時(shí),

33、 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）的所有元素，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í)的值

34、.最后，結(jié)果就是在數(shù)組序號(hào)范圍在low和high（包含low,high）之間的范圍。（low和high是step2和step3的值。）7 為折半查找寫遞歸的偽代碼。Algorithms BSR(Ao.n-1,K)/折半查找遞歸算法/有序子數(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è)只使用兩路比較的折半查找算法，即只用和=,

35、或者只用和=.Algorithms TwoWaysBinarySearch(Ao.n-1,K)/二路比較的折半查找/有序子數(shù)組Al.r和查找鍵值K/查找成功則輸出其下標(biāo)，否則輸出-1l0, rn-1while l<r do m (l+r)/2if KAmr melse l m+1if K=Al return lelse return -1習(xí)題4.41. 設(shè)計(jì)一個(gè)分治算法來(lái)計(jì)算二叉樹(shù)的層數(shù).(空樹(shù)返回0,單頂點(diǎn)樹(shù)返回1),并分析效率類型.Algorithms Level(Tree T)/遞歸計(jì)算二叉樹(shù)的層數(shù)/輸入:二叉樹(shù)T/輸出:二叉樹(shù)T的層數(shù)If T=NULL return 0Else

36、return maxLevel(TL),Level(TR)+1算法效率類型是(n)(同4.4節(jié)算法height(T)2.選擇一個(gè)二叉樹(shù)的經(jīng)典遍歷算法(前中后序),寫出它的遞歸偽代碼,并求它的遞歸調(diào)用次數(shù).Algorithms preorder(T)/先序遍歷二叉樹(shù)T/輸入: 二叉樹(shù)T/輸出:先序遍歷的結(jié)點(diǎn)序列表If TNULL Visit Ts root Preorder(TL) Preorder(TR)遞歸調(diào)用次數(shù)C(n)=擴(kuò)展樹(shù)中內(nèi)部結(jié)點(diǎn)+外部結(jié)點(diǎn)=n+(n+1)=2n+17.設(shè)計(jì)一個(gè)算法計(jì)算有根有序樹(shù)的高度.Algorithms height(T)/遞歸計(jì)算有根有序樹(shù)的高度/輸入:一棵有

37、根有序樹(shù)的高度T/輸出:T的高度i=NumChildren(T) /根的孩子個(gè)數(shù)if i=0 return 0else return maxheight(T1),height(T2),height(Ti)+18.下面的算法試圖計(jì)算一棵二叉樹(shù)中葉子的數(shù)量Algorithms LeafCount(T)/遞歸計(jì)算二叉樹(shù)中葉子的數(shù)量/輸入:一棵二叉樹(shù)/輸出:T中葉子的數(shù)量if T=NULL return 0else return LeafCount(TL)+LeafCount(TR)應(yīng)為:if T=NULL return 0 /empty treeelse if TL =NULL AND TR=NUL

38、L return 1 /single-node treeelse return LeafCount(TL)+LeafCount(TR) /general case習(xí)題4.61.a.為最近對(duì)問(wèn)題的一維版本設(shè)計(jì)一個(gè)直接基于分治技術(shù)的算法,并確定它的效率類型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)/

39、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.12.a.設(shè)計(jì)一個(gè)遞歸的減一算法,求n個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置.b.確定該算法的時(shí)間效率,然后把它與該問(wèn)題的蠻力算法作比較Algorithms MinLocation(A0.n-1)/find the location of the smallest element in a given array/an array A0.n-1 of real nu

40、mbers/An index of the smallest element in A0.n-1if n=1 return 0else tempMinLocation(A0.n-2)if Atemp<An-1 return tempelse return n-1時(shí)間效率分析見(jiàn)習(xí)題2.4中8C(n)=C(n-1)+1 for n>1 C(1)=04.應(yīng)用插入排序?qū)π蛄衑xample按照字母順序排序5.a.對(duì)于插入排序來(lái)說(shuō),為了避免在內(nèi)部循環(huán)的每次迭代時(shí)判斷邊界條件j>=0,應(yīng)該在待排序數(shù)組的第一個(gè)元素前放一個(gè)什么樣的限位器?b.帶限位器版本和原版本的效率類型相同嗎?解: a.

41、應(yīng)該在待排序數(shù)組的第一個(gè)元素前放-或者小于等于最小元素值的元素.b. 效率類型相同.對(duì)于最差情況(數(shù)組是嚴(yán)格遞減):7.算法InsertSort2(A0.n-1) for i1 to n-1 do ji-1 while j>=0 and Aj>Aj+1 do swap(Aj,Aj+1) jj+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)/(

42、ca+cd)習(xí)題5.21.a.(略)b.4.習(xí)題5.31.DFS的棧狀態(tài):退棧順序: efgbcad 拓?fù)渑判? dacbgfe b. 這是一個(gè)有環(huán)有向圖.DFS 從a出發(fā),遇到一條從e到a的回邊.4.能否利用頂點(diǎn)進(jìn)入DFS棧的順序(代替它們從棧中退出的順序)來(lái)解決拓?fù)渑判騿?wèn)題?Hints:不能.5. 對(duì)第1題中的有向圖應(yīng)用源刪除算法.拓?fù)湫蛄? dabcgef習(xí)題5.44.下面是生成排列的B.Heap算法.算法HeapPermute(n)/實(shí)現(xiàn)生成排列的Heap算法/輸入:一個(gè)正整數(shù)n和一個(gè)全局?jǐn)?shù)組A1.n/輸出:A中元素的全排列If n=1 Write AElse For i1 to n

43、do HeapPermute(n-1) If n is odd Swap A1 and An Else swap Ai and An對(duì)于n=2,3,4的情況,手工跟蹤該算法.解:對(duì)于n=2 for i=1  do heappermute(1）write A即12這時(shí)n not odd, so do A1與A2互換，A=21for i=2 do heappermute(1）write A即21對(duì)于n=3For i=1 doHeappermute(2) heappermute(1) write A 即123 這時(shí)2 not odd,so,do A1與A2互換，A=213 heapperm

44、ute(1) write A 即213 這時(shí) 2 not odd, do A2與A2互換，A=213 由于 3 is odd,so do A1與A3互換,A=312For i=2 do Heappermute(2) heappermute(1) write A 即312 這時(shí)2 not odd,so,do A1與A2互換，A=132 heappermute(1) write A 即132 這時(shí) 2 not odd, do A2與A2互換，A=231 由于 3 is odd,so do A1與A3互換,A=231For i=3 do Heappermute(2) heappermute(1) write A 即231 這時(shí)2 not odd,so,do A1與A2互換，A=321heappermute(1) write A 即321 這時(shí) 2 not odd, do A2與A2互換，A=3