算法設計與分析-遞歸與分治

1、 學習要點學習要點:理解遞歸的概念。掌握設計有效算法的分治策略。通過下面的范例學習分治策略設計技巧。（1）二分搜索技術； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤覆蓋；（5）合并排序和快速排序；（6）線性時間選擇；（7）最接近點對問題；（8）循環(huán)賽日程表。n學習如何求解遞歸式這對于分析遞歸算法非常有用，主要有5種方法求解遞歸式。n1.代換法n2.遞歸樹法n3.主方法n4.生成函數(shù)法n5.特征方程根1.代換法求解遞歸式n1.猜答案（可以不需要知道常數(shù)系數(shù)確切是多少，僅需要猜它的形式，如n2 ，再試圖解出它的常數(shù)。即先推測遞歸方程的顯式解）n2.數(shù)學歸納法驗證遞歸式。驗證是否這

2、個遞歸式，按照數(shù)學歸納法滿足條件。即用數(shù)學歸納法證明推測的正確性。n3.找出常數(shù)。n例1：T(n)=4T(n/2)+n; T(1)=1;n1.猜T(n)=O ( n3 )；想辦法證明T(n)c * n 3 n2.假設T(k ) c k3 ( k=n/2)即對k滿足T(n)=O ( n3 ),即有T(n/2 ) c (n/2)3 nT(n)=4T(n/2)+n (對T(n/2)即對k+1看是否滿足假設)n 4c (n/2) 3 +nn = c/2* n 3 +nn = c * n 3 (c/2* n 3 n )n c * n 3 (c/2* n 3 n 0,即只要c 2就可以）n因此遞歸式的上界

3、是O ( n3 )；n例1：T(n)=4T(n/2)+n; T(1)= (1 );n1.猜T(n)=O ( n2 )；根據(jù)符號O的定義，對nn0，有T(n) c n2n2.假設T(k ) c k2 ( kn )n把這個解代入遞歸方程，得到 nT(n)=4T(n/2)+nn 4c (n/2) 2 +nn = c* n 2 +nn = c * n 2 (n)n而n不是一個正數(shù)，無法得出c * n 2 (n) c * n 2 n但假定歸納假設條件為：nT(k ) c1k2 -c2 k ( kn ) 這里減去c2 k ，因其是低階項，不會影響到n足夠大時的漸近性）， n因此T(n)=4T(n/2)+n

4、n 4(c1 (n/2) 2 -c2 (n/2) )+nn = c1n2 +n - 2c2 n n = c1n2 - c2 n -(c2 n - n)n c1n2 - c2 n (要滿足條件 c2 n n 0， 即只要 c2 1 0,即c2 1即可) n即T(k ) c1k2 -c2 k ，對任意的c1， c2 1成立；n但必須注意c1要足夠大，因為：n基本情況T(1) c1 - c2n而T(1)= (1 )即T(1)是常數(shù)，我們需要選擇c1 ，至少比c2大，而c2 1，因此c1要足夠大。n如何求出下界，解決辦法之一是假設T(k ) c1k2 -c2 k ( kn )，其余步驟類似。n因此遞歸

5、式的上界是O ( n2 )；n練習1：T(n)=4T(n/2)+n; T(1)= (1 );n1.猜T(n)=O ( nlogn )；n代換法求解遞歸式需要先猜出答案大概是多少，這比較困難。2.遞歸樹法n遞歸樹法不嚴謹，但很直觀，讓你知道答案大概是多少。一般我們可以用這種方法求出答案，然后用代換法驗證其正確性。n例1：(n)=2T(n/2)+n;n nn n/2 n/2n n/4 n/4 n/4 n/4n.n1 1 1 . 1 1n樹的高度是logn，葉節(jié)點的個數(shù)是n，用遞歸樹求解遞歸式就是將每層的復雜度加起來。如第一層是n，第二層是n/2 + n/2 =n，第三層是n/4 + n/4 + n

6、/4 + n/4 =n.最后一層（即logn層)是1+1+1=n;n第一層+第二層+第三層+最后一層=nlogn。n(n)=2T(n/2)+n的漸進復雜度是O(nlogn)n例:2：T(n)= T(n/4)+ T(n/2)+n2n即假設有個算法，問題的規(guī)模為n，先四等分地遞歸，再二等分地遞歸，再做一個非遞歸的n2復雜度的工作。下面用樹的形式展開遞歸。nT(n)=n2 = n2n T(n/4) T(n/2) (n/4)2 (n/2)2n T(n/16) T(n/8) T(n/8) T(n/4) n= n2 = n2 n (n/4)2 (n/2)2 5/16 n2 n (n/16) 2 (n/8)

7、 2 (n/8) 2 (n/4) 2n 25/256n2 n .n (1 ) (1 ) . (1 ) (1 )n上述遞歸樹的葉節(jié)點是多少個？要注意的是，第二層表示的意思是將問題規(guī)模為n的算法通過遞歸將問題規(guī)?？s小為n/4+n/2=3n/4;n第三層最左分支表示的意思是將問題規(guī)模為n / 4的算法通過遞歸將問題規(guī)?？s小為n/16+n/8=3n/16;nn因此葉節(jié)點的個數(shù)至少是小于n。n另外，遞歸樹的另一個特點是左分支的分解速度明顯快于右分支，如第二層最左分支為n / 4，最右分支為n /2；第三層最左分支為n / 16，最右分支為n /4因此左分支遞歸樹的深度要小于右分支的深度。n對各層求和，第

8、一層的和是n2 ，第二層的和是5/16n2 (n/4)2 +(n/2)2 ),第三層的和是52 /162 n2 (n/16) 2 + (n/8) 2 +(n/8) 2 + (n/4) 2).可以看出這是一個等比數(shù)列，對各層累加， 即n2 + 5/16n2 +52 /162 n2 + + 5k/16kn2 + (1) n(1) (1+ 5/16 +52 /162 + + 5k/16k + ) n2 n等比數(shù)列性質：n1+1/2+1/4+1/8+=2;n因為對二進制而言1+1/2=1.1n 1+1/2+1/4=1.11n1+1/2+1/4+1/8+=1.111=2;n而(1+ 5/16 +52 /

9、162 + + 5k/16k + ) n2中n5/161(子問題規(guī)模要減少) ， f(n)漸進趨正。漸進趨正即對足夠大的n， f(n) 0.即存在特定的n0 ，當n n0時f(n) 0. 主方法的簡單思路是比較f(n) 和nlogba(logba是遞歸樹葉節(jié)點的個數(shù)) .n有三種情況：n1.小于。 f(n) 較小，它多項式的小于nlogba，即f(n) =O(n(logba-u),u0n則T(n)= (nlogba );n2.等于， f(n)比nlogba大一個多項式因式logn 。即f(n) = (n(logba)n則T(n)= (nlogba*logn);n3.大于. f(n) 比nlog

10、ba 增長的快，而且是多項式的大于nlogba ，即f(n)比nlogba大一個多項式因式。即f(n) =(n(logba+u)。n同時f(n) 在遞歸的過程中要不斷變小，否則相加后得到無限大就麻煩了。即a f(n/b) (1-u)*f(n), u0. f(n)即遞歸樹的最高層，它應該大于下一層所有值之和。最高層需要比下一層大某個常數(shù)因子。即下一層至多等于(1-u)*f。這樣才能保證每層的數(shù)量越來越小。n則T(n)= (f(n);n例1：T(n)= 4T(n/2)+n。nA=4,b=2,f(n)=n. logba=2, nlogba =n2;nf(n)比nlogba 小一個多項式因式，因此是小

11、于的情況。n則T(n)= (nlogba) = (n2);n例2：T(n)= 4T(n/2)+ n2 。nA=4,b=2,f(n)= n2. logba=2, nlogba =n2;nf(n)漸進的等于nlogba ，因此是等于的情況。n則T(n)= (nlogba *logn ) = (n2 *logn );n例3：T(n)= 4T(n/2)+ n3 。nA=4,b=2,f(n)= n3. logba=2, nlogba =n2;nf(n)比nlogba大一個多項式因式，因此是大于的情況。n則T(n)= (f(n)= (n3);n主方法的證明（遞歸樹法證明）n f(n) f(n)n n f(

12、n/b) f(n/b)f(n/b) a f(n/b) nf(n/b2). f(n/b2) a2 f(n/b2) nn(1) (1) . (1) n最后一層即n/bk=1，因此k=logbn，而最后一層共有nak個葉節(jié)點，因此該層所有節(jié)點的和是a logbn,即nlogba n即nlogba，所以各層相加，即nf(n)+ a f(n/b) + a2 f(n/b2) + ak f(n/bk) n1.如果f(n) nlogba,即第3種情況，在這種情況下， f(n)占主導地位，以下各層會呈幾何級數(shù)ak f(n/bk)逐漸減小。n2.如果f(n) nlogba,即第1種情況，在這種情況下， f(n)占

13、主導地位，以下各層會呈幾何級數(shù)ak f(n/bk)逐漸增長生成函數(shù)n生成函數(shù)即母函數(shù)，是組合數(shù)學中尤其是計數(shù)方面的一個重要理論和工具。最早提出母函數(shù)的人是法國數(shù)學家LaplaceP.S.在其1812年出版的概率的分析理論中明確提出。 生成函數(shù)有普通型生成函數(shù)和指數(shù)型生成函數(shù)兩種，其中普通型用的比較多。 生成函數(shù)的應用簡單來說在于研究未知（通項）數(shù)列規(guī)律，用這種方法在給出遞推式的情況下求出數(shù)列的通項，生成函數(shù)是推導Fibonacci數(shù)列的通項公式方法之一。 另外生成函數(shù)也廣泛應用于編程與算法設計、分析上，運用這種數(shù)學方法往往對程序效率與速度有很大改進。n對于任意數(shù)列a0,a1,a2.an 即用如

14、下方法與一個函數(shù)聯(lián)系起來： nG(x) = a0 + a1x + a2x*2 + a3x3 +.+ anxn 則稱G(x)是數(shù)列的生成函數(shù)(generating function) .n研究生成函數(shù)時，我們都假設級數(shù)收斂，因為生成函數(shù)的x沒有實際意義，我們可以任意取值。nFibonacci數(shù)列是這樣一個遞推數(shù)列：f(n)=f(n-1)+f(n-2),f(0)=1, f(1)=1 。ng(x)應該是一個這樣的函數(shù)： g(x)=1+x+2x2+3x3+5x4+8x5+13x6+21x7+. +f(n)*xnn等式兩邊同時乘以x，我們得到： x*g(x)=x+x2+2x3+3x4+5x5+8x6+1

15、3x7+. +f(n)*x(n+1)nx* x* g(x) = x2+x3+2x4+3x5+5x6+8x7+. + f(n)*x(n+2)n則： g(x)- x*g(x)- x* x* g(x) = 1，即n(1- x - x* x) * g(x) = 1ng(x) = 1/ (1- x - x* x) ;n1- x - x* x的兩個根是：(1-sqrt(5)/2, (1+sqrt(5)/2,n令g(x) =A / (1+sqrt(5)/2 +B / (1-sqrt(5)/2;n練習：1. f(n)=f(n-1)+f(n-2),nf(0)=0, f(1)=1 。求f (n)的解析表示n2.a

16、0=0,a1=1,an=7an-1-10an-2;n3.f(1)=1;nf(n)=2f(n-1)+1;n4. a0=1,a1=1,an=an-1+6an-2;n5. a0=1,a1=5,an=an-1+6an-2;n如：f(0)=0,f(1)=1,f(n)=7f(n-1)-10f(n-2);n則xn=7xn-10 x(n-2) ，等式同除以x (n-2) n得：特征方程：x2-7x+10=0n (x-2)*(x-5)=0n則有特征根： q1=2，q2=5;所以遞歸方程的通解為：f(n)=c1*q1n+c2*q2n;n由初始條件得：nf(0)=0, f(0)=c1*q10+c2*q20= c1+

17、c2=0nf(1)=1, f(1)=c1*q11+c2*q21= c1*2+c2 *5 =1n解此聯(lián)立方程，得c1=-1/3, c1=1/3n則遞歸方程的解為：f(n)=c1*q1n+c2*q2nn = 1/3(5 n-2 n)n將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。n對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容

18、易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T

19、(n/4)T(n/4)T(n/4)T(n/4)n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設計思想是，將一個難以直接解決的大問題，分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分而治之。2.1 n直接或間接地調用自身的算

20、法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。n由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。n分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。下面來看幾個實例。2.1 例例1 1 階乘函數(shù)階乘函數(shù) 階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出

21、結果。第n個階乘數(shù)可遞歸地計算如下：int factorial(int n) if (n = 1) return 1; return n* factorial( n-1); 2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個Fibonacci數(shù)可遞歸地計算如下：int fibonacci(int n) if (n =0)nA(1)= A(1,1)=2;nA(2)= A(2,2)=22=4;nA(

22、3)= A(3,3)=222=16;n(n)=minkA(k)nn(1)=minkA(k)1,滿足該條件的最小的k為0，n因此(1)=0；n(2)=minkA(k)2,滿足該條件的最小的k為1，n因此(2)=1；n(3)=minkA(k)3,滿足該條件的最小的k為2，n因此(3)=2；n(4)=minkA(k)4,滿足該條件的最小的k為2，n因此(4)=2；n(5)=minkA(k)5,滿足該條件的最小的k為3，n因此(5)=3；n(5)=(6)=(7) = (16) =3,可以看出(n)的增長速度非常慢。nA(4)= (其中2的層數(shù)為65536)n對于通常所見到的正整數(shù)n，有(n)4(n)4

23、。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。n2222ndouble acekerman(int n,int m)ndouble f;nif (n=1&m=0) f=2;nelse if (n=0&m=0) f=1;nelse if (n=2&m=0) f=n+2;nelse f=acekerman(acekerman(n-1,m),m-1);nreturn f;n2.1 例例4 4 排列問題排列問題設計一個遞歸算法生成n個元素r1,r2,rn的全排列。設R=r1,r2,rn是要進行排列的n個元素，Ri=R-ri。集合X中元素的全排列記為

24、perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；當n1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構成。 n#define N 4nvoid swap(int &a,int &b)nint t;n t=a;n a=b;n b=t;n nvoid perm(int list,int k,int m)nint i;nif (k=m)n for (i=0;i=m;i+)n printf(%d,

25、listi);n printf(n);n nelsen for (i=k;i=m;i+)n swap(listk,listi);nperm(list,k+1,m);nswap(listk,listi);nnnvoid main()nint listN,i;nfor (i=0;iN;i+)n listi=i+1;n perm(list,0,N-1);nn全排列問題。如n=3，假定要對1,2,3進行全排列；n則可變?yōu)閷?,2,3n 2,1,3n 3,2,1n分別對內元素再全排列，即問題的規(guī)模更小一個得到；這步由 for (i=k;i=m;i+)n swap(listk,listi);nperm(l

26、ist,k+1,m);n swap(listk,listi);n實現(xiàn)。當集合中元素只有一個時，一組排列結果已得到。n即if (k=m)n for (i=0;i=m;i+)n printf(%d,listi);n但在for (i=k;i=m;i+)n swap(listk,listi);nperm(list,k+1,m);n swap(listk,listi);n如果沒有最后一句swap(listk,listi);結果會和預期的不一致。n例：n1,2,3-1,2,3-1,2,3一個排列已得到。n再回溯到1,2,3-1,3,2一個排列已得到。n如果不把1,3,2歸位為1,2,3，即2,3交換后得到

27、的3,2，不換回為1,2,3的話，在1,3,2排列得到時再回溯到k=0，即本應做2，1,3的排列，現(xiàn)在是在1,3,2的基礎上對1,3交換，即3,1,2- 3 , 1, 2- 3 , 2 , 1 。再回溯到k=0，即在3 , 2 , 1的基礎上對3 , 1交換，即1,2,3該排列就和最開始的重復。n因此每次做完一次排列時要把序列還原為原序列，即排列完要把它換回來。nfor (i=k;im1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq2.1 例例5 5 整數(shù)劃分問

28、題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設p(n)為正整數(shù)n的劃分數(shù)，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關系。正整數(shù)n的劃分數(shù)p(n)=q(n,n)。 n遞歸函數(shù)的聲明為 int split(int n, int m)，遞歸函數(shù)的作用是求最大加數(shù)不超過m的劃分個數(shù);其中n為要劃分的正整數(shù)，m是劃分中的最大加數(shù)(當m n時，最大加數(shù)為n)， 1 當n = 1或m = 1時，split的值為1，可根據(jù)上例看出，只有一個劃分1 或 1 + 1

29、+ 1 + 1 + 1 + 1 可用程序表示為if(n = 1 | m = 1) return 1;n下面看一看m 和 n的關系。它們有三種關系 (1) m n 在整數(shù)劃分中實際上最大加數(shù)不能大于n，因此在這種情況可以等價為split(n, n); 可用程序表示為if(m n) return split(n, n); (2) m = n 這種情況可用遞歸表示為split(n, m - 1) + 1，從以上例子中可以看出，就是最大加數(shù)為6和小于6的劃分之和。 用程序表示為if(m = n) return (split(n, m - 1) + 1); (3) m 1時， 需利用塔座Y作輔助塔座，

30、若能設法將壓在編號為n的圓盤上的n-1個圓盤從塔座X(依照上述原則)移至塔座Y上， 則可先將編號為n的圓盤從塔座X 移至塔座Z上，然后再將塔座Y上的n-1個圓盤(依照上述原則)移至塔座Z上。而如何將n-1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小個1，因此可以用同樣方法求解。 由此可得如下算法所示的求解n階Hanoi塔問題的函數(shù)。 void hanoi(int n,char x,char y,char z) /*將塔座X上按直徑由小到大且至上而下編號為1至n的n個圓盤按規(guī)則搬到塔座Z上， Y可用作輔助塔座 */ if(n=1) move(x,1,z

31、); /* 將編號為1的圓盤從X移動Z */ else hanoi(n-1,x,z,y); /* 將X上編號為1至n-1的圓盤移到Y,Z作輔助塔 */ move(x,n,z); /* 將編號為n的圓盤從X移到Z */ hanoi(n-1,y,x,z); /* 將Y上編號為1至n-1的圓盤移動到Z， X作輔助塔 */ 圖3.8 Hanoi塔的遞歸函數(shù)運行示意圖 321a321abc321abc321abc321abcbc321abc321abc321abc 5) 遞歸過程的實現(xiàn) 遞歸進層（ii+1層）系統(tǒng)需要做三件事： (1) 保留本層參數(shù)與返回地址（將所有的實在參數(shù)、 返回地址等信息傳遞給被調

32、用函數(shù)保存）； (2) 給下層參數(shù)賦值（為被調用函數(shù)的局部變量分配存儲區(qū)）； (3) 將程序轉移到被調函數(shù)的入口。 而從被調用函數(shù)返回調用函數(shù)之前，遞歸退層（ii+1層）系統(tǒng)也應完成三件工作： (1) 保存被調函數(shù)的計算結果； (2) 恢復上層參數(shù)（釋放被調函數(shù)的數(shù)據(jù)區(qū)）； (3) 依照被調函數(shù)保存的返回地址， 將控制轉移回調用函數(shù)。 棧的應用n過程的嵌套調用r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3例例 遞歸的執(zhí)行情況分析遞歸的執(zhí)行情況分析 n遞歸過程及其實現(xiàn)遞歸：函數(shù)直接或間接的調用自身叫實現(xiàn)：建立遞歸工作棧void print(int w) int i

33、; if ( w!=0) print(w-1); for(i=1;i1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉化成只有一個圓盤的Hanoi問題算法：執(zhí)行情況： 遞歸工作棧保存內容：形參n,x,y,z和返回地址 返回地址用行編號表示n x y z 返回地址 main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); hanoi(m,A,

34、B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main() int m; printf(Input the number of disks scanf(%d,&m); p

35、rintf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main() int m; printf(Input th

36、e number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83

37、A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3

38、 A B C 02 B A C 83 A B C 0?？? A B C 02 B A C 8Hanoi.c D:fengyibkcpowerpower.c main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n

39、,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z)

40、;(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,

41、char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C

42、);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0棧空3 A B C 02 B A C 8Hanoi.c D:其中move函數(shù)可以用printf函數(shù)替換。nvoid hanoi(int n,char x,char y,char z)

43、nif (n=1)n printf(%d disc move from %c to %cn,n,x,z);n elsen hanoi(n-1,x,z,y);n printf(%d disc move from %c to %cn,n,x,z);n hanoi(n-1,y,x,z);n n 優(yōu)點：優(yōu)點：結構清晰，可讀性強，而且容易用結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。為設計算法、調試程序帶來很大方便。缺點：缺點：遞歸算法的運行效率較低，無論是遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存

44、儲空間都比耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。非遞歸算法要多。解決方法：解決方法：在遞歸算法中消除遞歸調用，使其在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。轉化為非遞歸算法。1 1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調用工作棧。該方法通用性強，但本質上還是遞用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。優(yōu)化效果不明顯。2 2、用遞推來實現(xiàn)遞歸函數(shù)。、用遞推來實現(xiàn)遞歸函數(shù)。3 3、通過變換能將一些遞歸轉化為尾遞歸，從而、通過變換能將一些遞歸轉化為

45、尾遞歸，從而迭代求出結果。迭代求出結果。 后兩種方法在時空復雜度上均有較大改善，后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。2.4 2.4 遞歸消除遞歸消除2.4.1 2.4.1 簡單遞歸消除簡單遞歸消除【例例2-72-7】將計算階乘函數(shù)n!的遞歸算法轉換成非遞歸算法。已知n!的遞歸算法如下：Int function f(int n) /計算n!的遞歸處法，假定輸入n=0 if n=0 then return(1) else return(n*f(n-1) 為了更好地理解和掌握遞歸算法的運行機制，可以畫出它的“計算依賴圖”的一部分，如圖2-4所示。繪制計算依賴圖的

46、規(guī)則是：對每一個遞歸調用，在圖中設立一個以該調用為標記的結點；對任意兩個遞歸調用p、q，若p的計算“直接依賴于”q，即p的執(zhí)行中調用了q，則圖中對應的結點之間有一條連線，并且p結點的位置高于q結點。通常只能且只需畫出計算依賴圖的一部分。對于計算n!的遞歸算法f(n)來說，遞歸調用f(3)的計算直接依賴于遞歸調用f(2)；因為f(3)調用了f(2)，僅當f(2)的計算完成之后f(3)的計算才能完成。類似地，f(2)直接依賴于f(1)；f(1)直接依賴于f(0);而f(0)不依賴于任何其他調用，只依賴于自己（即自己可以獨立完成計算）。相應地，包含這幾個遞歸調用的計算依賴圖如圖2-4所示。圖中虛線標

47、明遞歸調用返回的次序，向下的箭頭表示遞歸調用；向上的箭頭表示返回。根據(jù)計算依賴圖的繪制規(guī)則，這些虛線及箭頭可以省略。圖2-4 例2-7的遞歸調用的實現(xiàn)過程 事實上，計算依賴圖集中地反映了不同遞歸調用之間的依賴關系。通過對這種關系的分析，可以很方便地寫出完成同樣計算任務的循環(huán)算法。因此，整個計算完全可以只由后一個階段完成，引入一個工作變量y記錄中間結果，則計算n!的循環(huán)算法為：function f1(int n)/計算n!的循環(huán)算法，假定輸入n=0y=1; /計算y=f(0) for (i=1;I1 Fib(n)= 由于Fib(n)是遞歸定義的，可直接寫出其遞歸算法如下：function Fib

48、 (int n)/計算Fib(n)的遞歸算法，假定輸入n=0, 見圖2-5 if (n=0 ) then return(0); else if (n=1) then return(1) ; else return(Fib(n-1)+Fib(n-2) ; 算法Fib(n)在n=5以下的計算依賴圖如圖2-5所示。顯然，F(xiàn)ib(n)有計算依賴關系是一個樹形結構，樹上每個結點對應的計算直接依賴于它的所有孩子，直接或間接地依賴于它的所有子孫。圖2-5 例2-8的遞歸調用的實現(xiàn)過程 從圖2-5中亦可看出，遞歸算法Fib(n)的效率不高。其中，F(xiàn)ib(3)被計算了兩次，F(xiàn)ib(2)三次，F(xiàn)ib(1)和Fib

49、(0)分別為五次和三次。既然遞歸消除的目的是提高效率，不妨試著把重復的結點“合并”在一起以便減少重復計算。第一步將兩個Fib(3)結點合并，得到子圖。再將得到子圖中兩個Fib(1)結點合并,得到新的子圖。上述過程稱為計算依賴圖的化簡。 由圖2-5可知，當n=2時每個Fib(n)直接依賴于剛剛算出的前兩個值，需引入兩個工作變量x, y分別記錄中間結果。算法如下：function Fib1(int n)/計算Fib(n)的循環(huán)算法。假定輸入n=0if n=0 then return(0)else if n=1 then return(1) else x=0; y=1; /xFib1(0),yFib

50、1(1) for (I=2;Ilchild;nelsenPop(S,p); if(!Visit(p-data) return ERROR;np=p-rchild);n/elsen/whilenreturn OK;nabcde1.分：一個問題的特殊實例劃分成若干子問題，并且這些子問題在一定程度上更小了，即比原問題的規(guī)模n更小了。即現(xiàn)在有一個或若干個子問題需要解決，并且每個子問題的規(guī)模更小。2.治：遞歸的解決每個子問題。3.合：把子問題的解合并成為整個大問題的解。人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種

51、使子問題規(guī)模大致相等的做法是出自一種平衡平衡(balancing)子問題子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：11)()/() 1 ()(nnnfmnkTOnT通過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：遞歸方程及其解只給出n等于m的方冪時T(n)的

52、值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調上升的，從而當minmi+1時，T(mi)T(n)T(mi+1)。 分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的子問

53、題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。分解出的各個子問題是相互獨立的。 n這個算法只有一個子問題。n1.分：就是把x與

54、數(shù)組的中間元素相比較n2.治： x與數(shù)組的中間元素相比較，比中間元素小，則x一定在左邊，遞歸在左邊子數(shù)組中找x；否則x一定在右邊，遞歸在右邊子數(shù)組中找x；但x只會在左邊或右邊子數(shù)組中，即這個算法只有一個子問題，這是它和歸并排序的重要區(qū)別n3.合：找到x即可，不需工作量 (1 ) n (1 ) 為x與中間元素相比較的工作量）n即問題的初始規(guī)模為n，劃分后子問題只有一個,子問題的規(guī)模為n /2。該例沒有什么意義，但實際上很多情況，只需要在一邊做遞歸，而且通過該例可以看到做一個遞歸與做二個遞歸的差別。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個

55、元素中找出一特定元素出一特定元素x。據(jù)此容易設計出二分搜索算法二分搜索算法：int BinarySearch(int a, int x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 算法復雜度分析：算法復雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為O(logn

56、) 。1.設表長為設表長為n，low、high和和mid分別指向待分別指向待查元素所在區(qū)間的上界、下界和中點查元素所在區(qū)間的上界、下界和中點,k為給為給定值。定值。2.初始時，令初始時，令low=1,high=n,mid= (low+high)/2 讓讓k與與mid指向的記錄比較指向的記錄比較若若k=rmid.key，查找成功，查找成功若若krmid.key，則，則low=mid+13.重復上述操作，直至重復上述操作，直至lowhigh時，查找失時，查找失敗。敗。例如例如 key =21 的查找過程的查找過程n有序表查找：用有序表查找：用low，high指針表示表的上界、指針表示表的上界、下界

57、，查找下界，查找21是先從表中間的元素找起，即先和是先從表中間的元素找起，即先和mid（正中間位置）所指元素（正中間位置）所指元素56比起，如果相等比起，如果相等則返回則返回mid；否則比較大小，；否則比較大小，2119,修改修改low=mid+1；mid=(low+high/2;修改修改high=mid-1；mid=(low+high/2;如下表所示：如下表所示：例例key =70 的查找過程的查找過程1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13

58、19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92當下界當下界low大于上界大于上界hig

59、h時，則說明表中時，則說明表中沒有關鍵字等于沒有關鍵字等于Key的元素，查找不成功。的元素，查找不成功。用分治法求xn，x為實數(shù)，n為正整數(shù)n樸素算法：把x連乘n次，需要做n或n-1次乘法，即(n )的工作量；n分治法：nxn = xn/2 *xn/2n問題的規(guī)模為n，劃分后兩個子問題的規(guī)模是n/2,而且兩個子問題性質相同，所以只要解決一個子問題就行了。如果已經算出xn/2，則另一個xn/2也出來了，把它們相乘就得到了xn 。這和二分搜索算法一樣，因此設計復雜度可以變?yōu)閘ogn。n需要注意的是xn = xn/2 *xn/2只對n為偶數(shù)有效，當n為奇數(shù)時，可以令xn = x( n-1)/2 *x

60、 ( n-1) /2 *x.即當n為奇數(shù)時需要一次遞歸調用和兩次乘法。n用分治法可以使得求xn的時間復雜度由(n )變?yōu)?logn )n#include nfloat cheng(float x,int n)nfloat f,y;nif (n=1) return x;n else if (n%2=0) /* if n is ever*/n y=cheng(x,n/2);n return y*y;n nelseny=cheng(x,(n-1)/2);n return y*y*x;nn 請設計一個有效的算法，可以進行兩個請設計一個有效的算法，可以進行兩個n n位大整數(shù)的乘法運算位大整數(shù)的乘法運算u小學的方法：O(n2) 效率太低u分治法: X = Y = X = a 2n/2 + b Y