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

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

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

3、函數(shù)) 算法Quadratic(a,b,c)/求方程ax2+bx+c=0的實(shí)根的算法 /輸入:實(shí)系數(shù)a,b,c/輸出:實(shí)根或者無解信息If a0Db*b-4*a*c If D>0temp2*ax1(-b+sqrt(D)/temp x2(-b-sqrt(D)/temp return x1,x2else if D=0 return b/(2*a) else return “no real roots” else /a=0if b0 return c/b else /a=b=0if c=0 return “no real numbers” else return “no real roots”

4、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+; while i!=0 do pr

5、int Bini; i-; 9.考慮下面這個(gè)算法,它求的是數(shù)組中大小相差最小的兩個(gè)元素的差.(算法略) 對這個(gè)算法做盡可能多的改進(jìn). 算法 MinDistance(A0.n-1) /輸入:數(shù)組A0.n-1/輸出:the smallest distance d between two of its elements習(xí)題1.31. 考慮這樣一個(gè)排序算法,該算法對于待排序的數(shù)組中的每一個(gè)元素,計(jì)算比它小的元素個(gè)數(shù),然后利用這個(gè)信息,將各個(gè)元素放到有序數(shù)組的相應(yīng)位置上去.a.應(yīng)用該算法對列表60,35,81,98,14,47排序 b.該算法穩(wěn)定嗎? c.該算法在位嗎? 解:a. 該算法對列表60,35

6、,81,98,14,47排序的過程如下所示:b.該算法不穩(wěn)定.比如對列表2,2*排序 c.該算法不在位.額外空間for S and Count 4.(古老的七橋問題)習(xí)題1.41.請分別描述一下應(yīng)該如何實(shí)現(xiàn)下列對數(shù)組的操作,使得操作時(shí)間不依賴數(shù)組的長度. 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 ith element with a spe

7、cial 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. (lazy deletion)第2章 習(xí)題2.17.對下列斷言進(jìn)行證明:(如果是錯(cuò)誤的,請舉例) 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)的增長率由

8、t(n)c·g(n) for all nn0, where c>01則：()t(n)£g(n) for all nn0cb. 這個(gè)斷言是正確的。只需證明Q(ag(n)ÍQ(g(n),Q(g(n)ÍQ(ag(n)。 設(shè)f(n)(g(n),則有：f(n)£cag(n) for all n>=n0, c>0 f(n)£c1g(n) for all n>=n0, c1=c>0即：f(n)(g(n)又設(shè)f(n)(g(n),則有：f(n)£cg(n) for all n>=n0,c>0f(n)&

9、#163;caag(n)=c1ag(n) 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)，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 那么

10、，取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) (max(g1(n),g2(n)證明：由大的定義知，必須確定常數(shù)c1、c2和n0，使得對于所有n>=n0，有：c1max(g1(n),g2(n)£t1(n)+t2(n)£max(g1(n),g2(n)由t1(n)(g1(n)知，存在非負(fù)整數(shù)a1,a2和n1使： a1*g1(n)<=t1(n)<

11、=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)又g2(n)>0，g1(n)+g2(n)>g1(n)

12、,即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.41. 解下列遞推關(guān)系 （做a,b） a.ìx(n)=x(n-1)+5當(dāng)n>1時(shí) íîx(1)=0 解：b. ìíx(n)=3x(n-1)當(dāng)n>1時(shí)îx(1)=4解：2. 對于計(jì)算n!的遞歸算法F(n)，建立其遞

13、歸調(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歸算法比，你做何評價(jià)？ 解： a.7. a. 請基于公式2n=2n-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)用樹，然后計(jì)算它所做的遞歸調(diào)用次數(shù)。 d.

14、對于該問題的求解來說，這是一個(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.習(xí)題2.61. 考慮下面的排序算法,其中插入了一個(gè)計(jì)數(shù)器來對關(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-1while j>0 and Aj>v do c

15、ountcount+1 Aj+1Aj jj+1 Aj+1v return count比較計(jì)數(shù)器是否插在了正確的位置?如果不對,請改正. 解:應(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-1while j>0 and Aj>v do countcount+1 Aj+1Aj jj+1if j>=0 count=count+1 Aj+1v return count6.選擇排序是穩(wěn)定的嗎?(不穩(wěn)定)7.用鏈表實(shí)現(xiàn)選擇排序的話

16、,能不能獲得和數(shù)組版相同的(n2)效率?Yes.Both operationfinding the smallest element and swapping it can be done as efficiently with the linked list as with an array.9.a.請證明,如果對列表比較一遍之后沒有交換元素的位置,那么這個(gè)表已經(jīng)排好序了,算法可以停止了.b.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a. c.請證明改進(jìn)的算法最差效率也是平方級的. Hints:a. 第i趟冒泡可以表示為:如果沒有發(fā)生交換位置,那么:b.Algorithms BetterBubbl

17、esort(A0.n-1)/用改進(jìn)的冒泡算法對數(shù)組A0.n-1排序 /輸入:數(shù)組A0.n-1/輸出:升序排列的數(shù)組A0.n-1countn-1 /進(jìn)行比較的相鄰元素對的數(shù)目 flagtrue /交換標(biāo)志 while flag do flagfalsefor i=0 to count-1 do if Ai+1swap(Ai,Ai+1) flagtrue countcount-1c最差情況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來的冒泡排序. 10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定) 習(xí)題3.21. 對限位器版的順序查找算法的比較次數(shù):a. 在最差情況下b. 在平均情況下.假設(shè)成功查找的概率

18、是p(0<=p<=1) Hints:a. Cworst(n)=n+1b. 在成功查找下,對于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比較次數(shù)是i.在查找不成功時(shí),比較次數(shù)是n+1,可能性是1-p.6.給出一個(gè)長度為n的文本和長度為m的模式構(gòu)成的實(shí)例,它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出,對于這樣的輸入需要做多少次字符比較運(yùn)算.Hints:文本:由n個(gè)0組成的文本模式:前m-1個(gè)是0,最后一個(gè)字符是1 比較次數(shù): m(n-m+1)7.為蠻力字符匹配算法寫一個(gè)偽代碼,對于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.Algorithms BFStringm

19、atch(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 j0while jcountcount+1 return count8.如果所要搜索的模式包含一些英語中較少見的字符,我們應(yīng)該如何修改該蠻力算法來利用這個(gè)信息. Hint:每次都從這些少見字符開始比較,如果匹配, 則向左邊和右邊進(jìn)行其它字符的比較.elseif rl=1 /有兩個(gè)元素時(shí)if AlArMaxAr; MinAlelseMaxAl; MinArelse /rl>1MaxMi

20、n(Al,(l+r)/2,Max1,Min1); /遞歸解決前一部分 MaxMin(A(l+r/)2.r,Max2,Min2); /遞歸解決后一部分if Max1Max2 Max= Max2 /從兩部分的兩個(gè)最大值中選擇大值 if Min2b.假設(shè)n=2k,比較次數(shù)的遞推關(guān)系式:C(n)=2C(n/2)+2 for n>2 C(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)

21、=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和最小值Min Max=Min=Al; for i=l+1 to r doif Ai>Max MaxAi; else if Ai時(shí)間復(fù)雜度t(n)=2(n-1)算法MaxMin的時(shí)間復(fù)雜度為3n/2-2，simpleMaxMin的時(shí)間復(fù)雜度為2n-2，都屬于(n)，但比較一下發(fā)現(xiàn)，MaxM

22、in的速度要比simpleMaxMin的快一些。 6.應(yīng)用合并排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序.c.鍵值比較次數(shù)M(n)M(n)=2M(n)+2n for n>1 M(1)=0 習(xí)題4.21.應(yīng)用快速排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序4. 請舉一個(gè)n個(gè)元素?cái)?shù)組的例子,使得我們有必須對它使用本節(jié)提到的”限位器”.限位器的值應(yīng)是多少年來?為什么一個(gè)限位器就能滿足所有的輸入呢? Hints:With the pivot being the leftmost element, the left-to-right scan will get out of boun

23、ds if and only if the 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è)算法對n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列,使得其中所有的負(fù)

24、元素都位于正元素之前.這個(gè)算法需要兼顧空間和時(shí)間效率.Algorithms netbeforepos(A0.n-1) /使所有負(fù)元素位于正元素之前 /輸入:實(shí)數(shù)組A0.n-1/輸出:所有負(fù)元素位于于正元素之前的實(shí)數(shù)組A0.n-1A-1-1; An1 /限位器 i0; jn-1 While iWhile Ai0 do ii+1while Aj0 do jj-1swap Aiand Ajswap Aiand Aj /undo the last swap當(dāng)全是非負(fù)數(shù)或全是非正數(shù)時(shí)需要限位器. 習(xí)題4.3 1.(題略)習(xí)題5.12.a.設(shè)計(jì)一個(gè)遞歸的減一算法,求n個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置. b

25、.確定該算法的時(shí)間效率,然后把它與該問題的蠻力算法作比較Algorithms MinLocation(A0.n-1)/find the location of the smallest element in a given array /an array A0.n-1 of real numbers/An index of the smallest element in A0.n-1 if n=1 return 0else tempMinLocation(A0.n-2)if Atemp時(shí)間效率分析見習(xí)題2.4中8 C(n)=C(n-1)+1 for n>1 C(1)=04.應(yīng)用插入排序?qū)?/p>

26、序列example按照字母順序排序5.a.對于插入排序來說,為了避免在內(nèi)部循環(huán)的每次迭代時(shí)判斷邊界條件j>=0,應(yīng)該在待排序數(shù)組的第一個(gè)元素前放一個(gè)什么樣的限位器?b.帶限位器版本和原版本的效率類型相同嗎?解: a. 應(yīng)該在待排序數(shù)組的第一個(gè)元素前放-或者小于等于最小元素值的元素. b. 效率類型相同.對于最差情況(數(shù)組是嚴(yán)格遞減):7.算法InsertSort2(A0.n-1) for i1 to n-1 doji-1while j>=0 and Aj>Aj+1 do swap(Aj,Aj+1) jj+1分析:在教材中算法InsertSort的內(nèi)層循環(huán)包括一次鍵值賦值和一次

27、序號遞減,而算法InsertSort2的內(nèi)層循環(huán)包括一次鍵值交換和一次序號遞減,設(shè)一次賦值和一次序號遞減的時(shí)間分別為ca和cd,那么算法InsertSort2和算法InsertSort運(yùn)行時(shí)間的比率是(3ca+cd)/(ca+cd)習(xí)題5.2 1.a.(略) b.4.習(xí)題5.3 1.DFS的棧狀態(tài):退棧順序: efgbcad 拓?fù)渑判? dacbgfe b.這是一個(gè)有環(huán)有向圖.DFS 從a出發(fā),遇到一條從e到a的回邊.4.能否利用頂點(diǎn)進(jìn)入DFS棧的順序(代替它們從棧中退出的順序)來解決拓?fù)渑判騿栴}? Hints: 不能.5. 對第1題中的有向圖應(yīng)用源刪除算法.拓?fù)湫蛄? dabcgef習(xí)題5.

28、44.下面是生成排列的B.Heap算法. 算法HeapPermute(n)/實(shí)現(xiàn)生成排列的Heap算法/輸入:一個(gè)正整數(shù)n和一個(gè)全局?jǐn)?shù)組A1.n /輸出:A中元素的全排列If n=1 Write A ElseFor i1 to n do HeapPermute(n-1) If n is oddSwap A1 and An Else swap Ai and An 對于n=2,3,4的情況,手工跟蹤該算法. 解:對于n=2 for i=1 doheappermute(1）write A即12這時(shí)n not odd, so do A1與A2互換，A=21for i=2 doheappermute(1）writ