算法設計與分析第二版課后習習題解答

1、算法設計與分析基礎課后練習答案習題1.1 4.設計一個計算的算法，n是任意正整數(shù)。除了賦值和比較運算，該算法只能用到基本的四則運算操作。算法求 /輸入：一個正整數(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ù)的算法快多少倍？請估算一下。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可知計算gcd（31415，14142）歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法，或者兩次除法，因此這個算法做除法的次數(shù)鑒于1·14142 和 2·14142之間，所以歐幾里德算法比此算法快1·14142/11 1300 與 2·141

3、42/11 2600 倍之間。6.證明等式gcd(m,n)=gcd(n,m mod n)對每一對正整數(shù)m,n都成立.Hint:根據(jù)除法的定義不難證明: l 如果d整除u和v, 那么d一定能整除u±v; l 如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.對于任意一對正整數(shù)m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；顯然，若d能整除n和r，也一定能整除m=r+qn和n。數(shù)對(m,n)和(n,r)具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故gcd(m,n)=gcd(n,r)7.對于第一個數(shù)小于第二個數(shù)的一對數(shù)字,歐幾里得算法將會如何處理該算法

4、在處理這種輸入的過程中,上述情況最多會發(fā)生幾次Hint:對于任何形如0<=m<n的一對數(shù)字,Euclid算法在第一次疊代時交換m和n, 即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次.8.a.對于所有1m,n10的輸入, Euclid算法最少要做幾次除法(1次) b. 對于所有1m,n10的輸入, Euclid算法最多要做幾次除法(5次) gcd(5,8)習題1.2 1.(農(nóng)夫過河)P農(nóng)夫 W狼 G山羊 C白菜2.(過橋問題)1,2,5,10-分別代表4個人, f手電筒4. 對于任意實系數(shù)a,b,c, 某個算法能求方程ax2+bx+c=0的實根,寫出上述算法的偽代碼

5、(可以假設sqrt(x)是求平方根的函數(shù))算法Quadratic(a,b,c)/求方程ax2+bx+c=0的實根的算法/輸入:實系數(shù)a,b,c/輸出:實根或者無解信息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. 描述將十進制整數(shù)表達為二進制整數(shù)的標準算法a.用文字描述b.用偽代碼描述解答： a.將十進制整數(shù)轉(zhuǎn)換為二進制整數(shù)的算法 輸入：一個正整數(shù)n輸出：正整數(shù)n相應的二進制數(shù)第一步：用n除以2，余數(shù)賦給Ki(i=0,1,2.)，商賦給n第二步：如果n=0，則到第三步，否則重復第一步第三步：將Ki按照i從高到低的順序輸出b.偽代碼 算法 DectoBin(n)/將十進制整數(shù)n轉(zhuǎn)換為二進制整數(shù)的算法/輸入：正整數(shù)n/輸出：該正整數(shù)相應的二進制數(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.考慮下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差.(算法略)對這個算法做盡可能多的改進.算法 MinDistance(A0.n-1)/輸入:數(shù)組A0.n-1/輸出:the smallest distance d between two of its elements習題1.3 1. 考慮這樣一個排序算法,該算法對于待排序的數(shù)組中的每一個元素,計算比它小的元素個數(shù),然后利用這個信息,將各個元素放到有序數(shù)組的相應位置上去.a.應用該算法對列表”60,35,81,98,14,47”排序b.該算法穩(wěn)定嗎c.該算法在位嗎解:a. 該算法對列表

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

9、言是正確的。只需證明。設f(n)(g(n),則有： for all n>=n0, c>0 for all n>=n0, c1=c>0即：f(n)(g(n)又設f(n)(g(n),則有： for all n>=n0,c>0 for all n>=n0,c1=c/>0即：f(n)(g(n)8證明本節(jié)定理對于下列符號也成立：a.符號b.符號證明：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,當n>=maxn1,n2時： 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，使得對于所有n>=n0，有：由t1(n)(g1(n)知，存在非負整

11、數(shù)a1,a2和n1使： a1*g1(n)<=t1(n)<=a2*g1(n)-(1)由t2(n)(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)-(3)不失一般性假設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)所以當c1min(a1,b1),c22c2=2max(c1,c2)，n0max(n1,n2)時，當n>=n0時上述不等式成立。證畢。習題2.22. 請用的非正式定義來判斷下列斷言是真還是假。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ù)的增長次數(shù)對它們進行排列（按照從低到高的順序） (n2)!, 5lg(n+100)10, 22n, 0.001n4+3n3+1, ln2 n, ， 3n.答：習題2.31. 計算下列求和表達式的值。答：3. 考慮下面的算法。a 該算法求的是什么？b 它的基本操作是什么？c 該基本操作執(zhí)行了多少次？d 該算法的效率類型是什么？e 對該算法進行改進，或者設計一個更好的算法，然后指出它們的效率類型。如果做不到這一點，請試著證明這是不可能做到的。9.證明下面的公式：可以使用數(shù)學歸納法，也可以像10歲的高斯一樣，用洞察力來解決該問題

14、。這個小學生長大以后成為有史以來最偉大的數(shù)學家之一。數(shù)學歸納法：高斯的方法：習題2.41. 解下列遞推關系 （做a,b）當n>1時a. 解：當n>1時b.解：2. 對于計算n!的遞歸算法F(n)，建立其遞歸調(diào)用次數(shù)的遞推關系并求解。解：3. 考慮下列遞歸算法，該算法用來計算前n個立方的和：S(n)=13+23+n3。算法S(n) /輸入：正整數(shù)n /輸出：前n個立方的和if n=1 return 1else return S(n-1)+n*n*na. 建立該算法的基本操作次數(shù)的遞推關系并求解b. 如果將這個算法和直截了當?shù)姆沁f歸算法比，你做何評價？解：7. a. 請基于公式2n=2

15、n-1+2n-1，設計一個遞歸算法。當n是任意非負整數(shù)的時候，該算法能夠計算2n的值。 b. 建立該算法所做的加法運算次數(shù)的遞推關系并求解 c. 為該算法構(gòu)造一棵遞歸調(diào)用樹，然后計算它所做的遞歸調(diào)用次數(shù)。 d. 對于該問題的求解來說，這是一個好的算法嗎？解:a.算法power(n)/基于公式2n=2n-1+2n-1,計算2n/輸入:非負整數(shù)n/輸出: 2n的值If n=0 return 1Else return power(n-1)+ power(n-1)c.8.考慮下面的算法 算法 Min1(A0.n-1) /輸入:包含n個實數(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.該算法計算的是什么b.建立該算法所做的基本操作次數(shù)的遞推關系并求解解:a.計算的給定數(shù)組的最小值for all n>1n=1b.9.考慮用于解決第8題問題的另一個算法,該算法遞歸地將數(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

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

18、SortAnalysis(A0.n-1)/input:包含n個可排序元素的一個數(shù)組A0.n-1/output:所做的關鍵比較的總次數(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比較計數(shù)器是否插在了正確的位置如果不對,請改正.解:應改為:算法SortAnalysis(A0.n-1)/input:包含n個可排序元素的一個數(shù)組A0.n-1/output:所做的關鍵比較的總次數(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習題3.14. a.設計一個蠻力算法,對于給定的x0,計算下面多項式的值:P(x)=anxn+an-1xn-1+a1x+a0并確定該算法的最差效率類型.b.如果你設計的算法屬于(n2),請你為該算法設計一個線性的算法.C.對于該問題來說,能不能設計一個比線性效率還要好的算法呢解:a. Algorithms BruteForcePolynomialEvaluation(P0.n,x)/由高冪到低冪用蠻力法計算多項

20、式p在給定點x的值/輸入:P0.n是多項式按低冪到高冪的常系數(shù),以及定值x/輸出: 多項式p在給定點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算法效率分析:基本操作:兩個數(shù)相乘,且M(n)僅依賴于多項式的階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)/由高冪到低冪用蠻力法計算多項式p在給定點x的值/輸入:P0.n是多項式按低冪到高冪的常系數(shù),以及定值x/輸出: 多項式p在給定點x的值 P=P0 power=1 for i1 to n do powerpower*x pp+Pi*power return p基本操作乘法運算總次數(shù)M(n):c.不行.因為計算任

22、意一個多項式在任意點x的值,都必須處理它的n+1 個系數(shù).例如: (x=1,p(x)=an+an-1+.+a1+a0,至少要做n次加法運算) 5.應用選擇排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.6.選擇排序是穩(wěn)定的嗎(不穩(wěn)定)7.用鏈表實現(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.應用冒泡排序?qū)π蛄蠩,X,A,M,

23、P,L,E按照字母順序排序.9.a.請證明,如果對列表比較一遍之后沒有交換元素的位置,那么這個表已經(jīng)排好序了,算法可以停止了.b.結(jié)合所做的改進,為冒泡排序?qū)懸欢蝹未a.c.請證明改進的算法最差效率也是平方級的.Hints:a. 第i趟冒泡可以表示為:如果沒有發(fā)生交換位置,那么:b.Algorithms BetterBubblesort(A0.n-1)/用改進的冒泡算法對數(shù)組A0.n-1排序/輸入:數(shù)組A0.n-1/輸出:升序排列的數(shù)組A0.n-1countn-1 /進行比較的相鄰元素對的數(shù)目flagtrue /交換標志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ù)組是嚴格遞減的,那么此時改進的冒泡排序會蛻化為原來的冒泡排序.10.冒泡排序是穩(wěn)定的嗎(穩(wěn)定)習題3.21. 對限位器版的順序查找算法的比較次數(shù):a. 在最差情況下b. 在平均情況下.假設成功查找的概率是p(0<=p<=1)Hints:a. Cworst(n)=n+1b. 在成功查找下,對于任意的I,第一次匹配發(fā)生在第i個位置的可能性是p/n,比較次數(shù)是i.在查找不成功時,比較次數(shù)是n+1,可能性是1-p.6.給出一個長度為n的文本和長度為m的模式構(gòu)成的

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

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

27、只出現(xiàn)一次，使得每一行，每一列，每一條主對角線的和都相等。a.證明：如果一個n階幻方存在的話，所討論的和一定等于n(n2+1)/2。答：令s為n階幻方的每一行的和。則把從1到 n2的整數(shù)求和可得如下式子由上式可得：習題4.11.a.為一個分治算法編寫偽代碼,該算法求一個n個元素數(shù)組中最大元素的位置. b.如果數(shù)組中的若干個元素都具有最大值,該算法的輸出是怎樣的呢 c.建立該算法的鍵值比較次數(shù)的遞推關系式并求解. d.請拿該算法與解同樣問題的蠻力算法做一個比較解: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.返回數(shù)組中位于最左邊的最大元素的序號.c.鍵值比較次數(shù)的遞推關系式: C(n)=C( n/2 )+C( n/2 )+1 for n>1 C(1)=0 設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對所有n>1的情況都成立（n是偶數(shù)或奇數(shù)）d.比較的次數(shù)相同，但蠻力算法不用遞歸調(diào)用。2、a.為一個分治算法編寫偽代碼，該算法同時求出一個n元數(shù)組的最大元素和最小元素的值。b.請拿該算法與解同樣問題的蠻力算法做一個比較。c.請拿該算法與解同樣問題的蠻力算法做一個比較。解答： a.同時求出最大值和最小值，只需要將原數(shù)組一分

30、為二，再使用相同的方法找出這兩個部分中的最大值和最小值，然后經(jīng)過比較就可以得到整個問題的最大值和最小值。 算法 MaxMin(Al.r,Max,Min) /該算法利用分治技術得到數(shù)組A中的最大值和最小值/輸入：數(shù)值數(shù)組Al.r/輸出：最大值Max和最小值Minif(r=l) MaxAl；MinAl; /只有一個元素時elseif rl=1 /有兩個元素時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 /從兩部分的兩個最大值中選擇大值if Min2<Min1 Min=Min2; /從兩部分的兩個最小值中選擇小值b.假設n=2k,比較次數(shù)的遞推關系式: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時間復雜度t(n)=2(n-1)算法MaxMin的時間復雜度為3n/2-2，simpleMaxMin的時間復雜度為2n-2，都屬于(n)，但比較一下發(fā)現(xiàn)，MaxMin的速度要比simpleMaxMin的

33、快一些。 6.應用合并排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序.3218.a.對合并排序的最差鍵值比較次數(shù)的遞推關系式求解.(for n=2k)b.建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關系式求解.(for n=2k)c.對于4.1節(jié)給出的合并排序算法,建立它的鍵值移動次數(shù)的遞推關系式.考慮了該算法的鍵值移動次數(shù)之后,是否會影響它的效率類型呢解:a. 遞推關系式見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習題4.21.應用快速排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序4. 請舉一個n個元素數(shù)組的例子,使得我們有必須對它使用本節(jié)提到的”限位器”.限位器的值應是多少年來為什么一個限位器就能滿足所有的輸入呢 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.設計一個算法對n個實數(shù)組成的數(shù)組進行重新排列,使得其中所有的負元素都位于正元素之前.這個算法需要兼顧空間和時間效率. Algorithms netbeforepos(A0.n-1)/使所有負元素位于正元素之前/輸入:實數(shù)組A0.n-1/輸出:所有負元素位于

36、于正元素之前的實數(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當全是非負數(shù)或全是非正數(shù)時需要限位器.習題4.32. 當n=2k時,用反向替換法求下面的遞推方程:當n>1時, Cw(n)=Cw(n/2)+1, Cw(1)=1(略)4.如果對于一個100000個元素的數(shù)組成功查找的話,使用折半查找比順序查找要快多少倍6 如何將折半查找應用于范圍查找范圍查找就是對于一個有序數(shù)組,找出位于給

37、定值L、U之間（包含L、U）的所有元素，L<=U。該算法的最差效率是多少？Hints:Step1: 檢查A0L，An-1U是否成立，若不成立，則無解。否則進入step 2Step2:在數(shù)組A中用二分查找法查找值L，如果查找成功，則返回數(shù)組下標m，否則l二分查找結(jié)束時的值.Step3: 在數(shù)組A中用二分查找法查找值U，如果查找成功，則返回數(shù)組下標m，否則r為二分查找結(jié)束時的值.最后，結(jié)果就是在數(shù)組序號范圍在low和high（包含low,high）之間的范圍。（low和high是step2和step3的值。）7 為折半查找寫遞歸的偽代碼。Algorithms BSR(Ao.n-1,K)/折半

38、查找遞歸算法/有序子數(shù)組Al.r和查找鍵值K/查找成功則輸出其下標，否則輸出-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.設計一個只使用兩路比較的折半查找算法，即只用和=, 或者只用和=.Algorithms TwoWaysBinarySearch(Ao.n-1,K)/二路比較的折半查找/有序子數(shù)組Al.r和查找鍵值K/查找成功則輸出其下標，否則輸出-1l0, rn-1while l<

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