Program算法設計與分析基礎中文版答案習題1.15.證明等式gcd(m,n)=gcd(n,m mod n)對每一對正整數m,n都成立. Hint:根據除法的定義不難證明:l 如果d整除u和v, 那么d一定能整除uv;l 如果d整除u,那么d也能夠整除u的任何整數倍ku.對于任意一對正整數m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；顯然，若d能整除n和r，也一定能整除m=r+qn和n。數對(m,n)和(n,r)具有相同的公約數的有限非空集，其中也包括了最大公約數。故gcd(m,n)=gcd(n,r)6.對于第一個數小于第二個數的一對數字,歐幾里得算法將會如何處理?該算法在處理這種輸入的過程中,上述情況最多會發生幾次? Hint:對于任何形如00temp2*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”5. 描述將十進制整數表達為二進制整數的標準算法 a.用文字描述 b.用偽代碼描述 解答：a.將十進制整數轉換為二進制整數的算法 輸入：一個正整數n輸出：正整數n相應的二進制數第一步：用n除以2，余數賦給Ki(i=0,1,2.)，商賦給n 第二步：如果n=0，則到第三步，否則重復第一步 第三步：將Ki按照i從高到低的順序輸出b.偽代碼算法 DectoBin(n)/將十進制整數n轉換為二進制整數的算法 /輸入：正整數n/輸出：該正整數相應的二進制數，該數存放于數組Bin1.n中 i=1while n!=0 do Bini=n%2; n=(int)n/2; i+; while i!=0 do print Bini; i-; 9.考慮下面這個算法,它求的是數組中大小相差最小的兩個元素的差.(算法略) 對這個算法做盡可能多的改進. 算法 MinDistance(A0.n-1) /輸入:數組A0.n-1/輸出:the smallest distance d between two of its elements習題1.31. 考慮這樣一個排序算法,該算法對于待排序的數組中的每一個元素,計算比它小的元素個數,然后利用這個信息,將各個元素放到有序數組的相應位置上去.a.應用該算法對列表60,35,81,98,14,47排序 b.該算法穩定嗎? c.該算法在位嗎? 解:a. 該算法對列表60,35,81,98,14,47排序的過程如下所示:b.該算法不穩定.比如對列表2,2*排序 c.該算法不在位.額外空間for S and Count 4.(古老的七橋問題)習題1.41.請分別描述一下應該如何實現下列對數組的操作,使得操作時間不依賴數組的長度. a.刪除數組的第i個元素(1=i0時,(g(n)= (g(n) 解:a. 這個斷言是正確的。它指出如果t(n)的增長率小于或等于g(n)的增長率，那么 g(n)的增長率大于或等于t(n)的增長率由 t(n)cg(n) for all nn0, where c01則：()t(n)g(n) for all nn0cb. 這個斷言是正確的。只需證明Q(ag(n)Q(g(n),Q(g(n)Q(ag(n)。 設f(n)(g(n),則有：f(n)cag(n) for all n=n0, c0 f(n)c1g(n) for all n=n0, c1=c0即：f(n)(g(n)又設f(n)(g(n),則有：f(n)cg(n) for all n=n0,c0f(n)caag(n)=c1ag(n) for all n=n0,c1=c/0即：f(n)(g(n)8證明本節定理對于下列符號也成立： 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 c10 由 t2(n)(g2(n)，T2(n)c2g2(n) for all n=n2, where c20 那么，取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) (max(g1(n),g2(n)證明：由大的定義知，必須確定常數c1、c2和n0，使得對于所有n=n0，有：c1max(g1(n),g2(n)t1(n)+t2(n)max(g1(n),g2(n)由t1(n)(g1(n)知，存在非負整數a1,a2和n1使： a1*g1(n)=t1(n)=a2*g1(n)-(1)由t2(n)(g2(n)知，存在非負整數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) 0，g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。 則（3）式轉換為：C1*max(g1,g2) = t1(n)+t2(n) =n0時上述不等式成立。 證畢。習題2.41. 解下列遞推關系 （做a,b） a.x(n)=x(n-1)+5當n1時 x(1)=0 解：b. x(n)=3x(n-1)當n1時x(1)=4解：2. 對于計算n!的遞歸算法F(n)，建立其遞歸調用次數的遞推關系并求解。 解：3. 考慮下列遞歸算法，該算法用來計算前n個立方的和：S(n)=13+23+n3。算法S(n)/輸入：正整數n/輸出：前n個立方的和 if n=1 return 1else return S(n-1)+n*n*na. 建立該算法的基本操作次數的遞推關系并求解b. 如果將這個算法和直截了當的非遞歸算法比，你做何評價？ 解： a.7. a. 請基于公式2n=2n-1+2n-1，設計一個遞歸算法。當n是任意非負整數的時候，該算法能夠計算2n的值。b. 建立該算法所做的加法運算次數的遞推關系并求解c. 為該算法構造一棵遞歸調用樹，然后計算它所做的遞歸調用次數。 d. 對于該問題的求解來說，這是一個好的算法嗎？解:a.算法power(n)/基于公式2n=2n-1+2n-1,計算2n /輸入:非負整數n /輸出: 2n的值 If n=0 return 1Else return power(n-1)+ power(n-1)c.習題2.61. 考慮下面的排序算法,其中插入了一個計數器來對關鍵比較次數進行計數.算法SortAnalysis(A0.n-1)/input:包含n個可排序元素的一個數組A0.n-1 /output:所做的關鍵比較的總次數 count0for i1 to n-1 do vAi ji-1while j0 and Ajv do countcount+1 Aj+1Aj jj+1 Aj+1v return count比較計數器是否插在了正確的位置?如果不對,請改正. 解:應改為:算法SortAnalysis(A0.n-1)/input:包含n個可排序元素的一個數組A0.n-1 /output:所做的關鍵比較的總次數 count0for i1 to n-1 do vAi ji-1while j0 and Ajv do countcount+1 Aj+1Aj jj+1if j=0 count=count+1 Aj+1v return count6.選擇排序是穩定的嗎?(不穩定)7.用鏈表實現選擇排序的話,能不能獲得和數組版相同的(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.請證明,如果對列表比較一遍之后沒有交換元素的位置,那么這個表已經排好序了,算法可以停止了.b.結合所做的改進,為冒泡排序寫一段偽代碼. c.請證明改進的算法最差效率也是平方級的. Hints:a. 第i趟冒泡可以表示為:如果沒有發生交換位置,那么:b.Algorithms BetterBubblesort(A0.n-1)/用改進的冒泡算法對數組A0.n-1排序 /輸入:數組A0.n-1/輸出:升序排列的數組A0.n-1countn-1 /進行比較的相鄰元素對的數目 flagtrue /交換標志 while flag do flagfalsefor i=0 to count-1 do if Ai+1swap(Ai,Ai+1) flagtrue countcount-1c最差情況是數組是嚴格遞減的,那么此時改進的冒泡排序會蛻化為原來的冒泡排序. 10.冒泡排序是穩定的嗎?(穩定) 習題3.21. 對限位器版的順序查找算法的比較次數:a. 在最差情況下b. 在平均情況下.假設成功查找的概率是p(0=p1MaxMin(Al,(l+r)/2,Max1,Min1); /遞歸解決前一部分 MaxMin(A(l+r/)2.r,Max2,Min2); /遞歸解決后一部分if Max1Max2 Max= Max2 /從兩部分的兩個最大值中選擇大值 if Min2b.假設n=2k,比較次數的遞推關系式:C(n)=2C(n/2)+2 for n2 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)=1=2k-1+2k-1+2k-2+.+2 /后面部分為等比數列求和 =2k-1+2k-2 /2(k-1)=n/2,2k=n =n/2+n-2 =3n/22b.蠻力法的算法如下： 算法 simpleMaxMin(Al.r)/用蠻力法得到數組A的最大值和最小值 /輸入：數值數組Al.r/輸出：最大值Max和最小值Min Max=Min=Al; for i=l+1 to r doif AiMax MaxAi; else if Ai時間復雜度t(n)=2(n-1)算法MaxMin的時間復雜度為3n/2-2，simpleMaxMin的時間復雜度為2n-2，都屬于(n)，但比較一下發現，MaxMin的速度要比simpleMaxMin的快一些。 6.應用合并排序對序列E,X,A,M,P,L,E按字母順序排序.c.鍵值比較次數M(n)M(n)=2M(n)+2n for n1 M(1)=0 習題4.21.應用快速排序對序列E,X,A,M,P,L,E按字母順序排序4. 請舉一個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 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個實數組成的數組進行重新排列,使得其中所有的負元素都位于正元素之前.這個算法需要兼顧空間和時間效率.Algorithms netbeforepos(A0.n-1) /使所有負元素位于正元素之前 /輸入:實數組A0.n-1/輸出:所有負元素位于于正元素之前的實數組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當全是非負數或全是非正數時需要限位器. 習題4.3 1.(題略)習題5.12.a.設計一個遞歸的減一算法,求n個實數構成的數組中最小元素的位置. b.確定該算法的時間效率,然后把它與該問題的蠻力算法作比較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時間效率分析見習題2.4中8 C(n)=C(n-1)+1 for n1 C(1)=04.應用插入排序對序列example按照字母順序排序5.a.對于插入排序來說,為了避免在內部循環的每次迭代時判斷邊界條件j=0,應該在待排序數組的第一個元素前放一個什么樣的限位器?b.帶限位器版本和原版本的效率類型相同嗎?解: a. 應該在待排序數組的第一個元素前放-或者小于等于最小元素值的元素. b. 效率類型相同.對于最差情況(數組是嚴格遞減):7.算法InsertSort2(A0.n-1) for i1 to n-1 doji-1while j=0 and AjAj+1 do swap(Aj,Aj+1) jj+1分析:在教材中算法InsertSort的內層循環包括一次鍵值賦值和一次序號遞減,而算法InsertSort2的內層循環包括一次鍵值交換和一次序號遞減,設一次賦值和一次序號遞減的時間分別為ca和cd,那么算法InsertSort2和算法InsertSort運行時間的比率是(3ca+cd)/(ca+cd)習題5.2 1.a.(略) b.4.習題5.3 1.DFS的棧狀態:退棧順序: efgbcad 拓撲排序: dacbgfe b.這是一個有環有向圖.DFS 從a出發,遇到一條從e到a的回邊.4.能否利用頂點進入DFS棧的順序(代替它們從棧中退出的順序)來解決拓撲排序問題? Hints: 不能.5. 對第1題中的有向圖應用源刪除算法.拓撲序列: dabcgef習題5.44.下面是生成排列的B.Heap算法. 算法HeapPermute(n)/實現生成排列的Heap算法/輸入:一個正整數n和一個全局數組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這時n not odd, so do A1與A2互換，A=21for i=2 doheappermute(1）write A即21對于n=3 For i=1 doHeappermute(2) heappermute(1) write A 即123 這時2 not odd,so,do A1與A2互換，A=213heappermute(1) write A 即213 這時 2 not odd, do A2與A2互換，A=213 由于 3 is odd,so do A1與A3互換,A=312For i=2 doHeappermute(2) heappermute(1) writ