算法設(shè)計(jì)與分析-遞歸與分治

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

2、個(gè)遞歸式，按照數(shù)學(xué)歸納法滿足條件。即用數(shù)學(xué)歸納法證明推測(cè)的正確性。n3.找出常數(shù)。n例1：T(n)=4T(n/2)+n; T(1)=1;n1.猜T(n)=O ( n3 )；想辦法證明T(n)c * n 3 n2.假設(shè)T(k ) c k3 ( k=n/2)即對(duì)k滿足T(n)=O ( n3 ),即有T(n/2 ) c (n/2)3 nT(n)=4T(n/2)+n (對(duì)T(n/2)即對(duì)k+1看是否滿足假設(shè))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ù)符號(hào)O的定義，對(duì)nn0，有T(n) c n2n2.假設(shè)T(k ) c k2 ( kn )n把這個(gè)解代入遞歸方程，得到 nT(n)=4T(n/2)+nn 4c (n/2) 2 +nn = c* n 2 +nn = c * n 2 (n)n而n不是一個(gè)正數(shù)，無(wú)法得出c * n 2 (n) c * n 2 n但假定歸納假設(shè)條件為：nT(k ) c1k2 -c2 k ( kn ) 這里減去c2 k ，因其是低階項(xiàng)，不會(huì)影響到n足夠大時(shí)的漸近性）， 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 ，對(duì)任意的c1， c2 1成立；n但必須注意c1要足夠大，因?yàn)椋簄基本情況T(1) c1 - c2n而T(1)= (1 )即T(1)是常數(shù)，我們需要選擇c1 ，至少比c2大，而c2 1，因此c1要足夠大。n如何求出下界，解決辦法之一是假設(shè)T(k ) c1k2 -c2 k ( kn )，其余步驟類似。n因此遞歸

5、式的上界是O ( n2 )；n練習(xí)1：T(n)=4T(n/2)+n; T(1)= (1 );n1.猜T(n)=O ( nlogn )；n代換法求解遞歸式需要先猜出答案大概是多少，這比較困難。2.遞歸樹(shù)法n遞歸樹(shù)法不嚴(yán)謹(jǐn)，但很直觀，讓你知道答案大概是多少。一般我們可以用這種方法求出答案，然后用代換法驗(yà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樹(shù)的高度是logn，葉節(jié)點(diǎn)的個(gè)數(shù)是n，用遞歸樹(shù)求解遞歸式就是將每層的復(fù)雜度加起來(lái)。如第一層是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的漸進(jìn)復(fù)雜度是O(nlogn)n例:2：T(n)= T(n/4)+ T(n/2)+n2n即假設(shè)有個(gè)算法，問(wèn)題的規(guī)模為n，先四等分地遞歸，再二等分地遞歸，再做一個(gè)非遞歸的n2復(fù)雜度的工作。下面用樹(shù)的形式展開(kāi)遞歸。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上述遞歸樹(shù)的葉節(jié)點(diǎn)是多少個(gè)？要注意的是，第二層表示的意思是將問(wèn)題規(guī)模為n的算法通過(guò)遞歸將問(wèn)題規(guī)模縮小為n/4+n/2=3n/4;n第三層最左分支表示的意思是將問(wèn)題規(guī)模為n / 4的算法通過(guò)遞歸將問(wèn)題規(guī)?？s小為n/16+n/8=3n/16;nn因此葉節(jié)點(diǎn)的個(gè)數(shù)至少是小于n。n另外，遞歸樹(shù)的另一個(gè)特點(diǎn)是左分支的分解速度明顯快于右分支，如第二層最左分支為n / 4，最右分支為n /2；第三層最左分支為n / 16，最右分支為n /4因此左分支遞歸樹(shù)的深度要小于右分支的深度。n對(duì)各層求和，第

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).可以看出這是一個(gè)等比數(shù)列，對(duì)各層累加， 即n2 + 5/16n2 +52 /162 n2 + + 5k/16kn2 + (1) n(1) (1+ 5/16 +52 /162 + + 5k/16k + ) n2 n等比數(shù)列性質(zhì)：n1+1/2+1/4+1/8+=2;n因?yàn)閷?duì)二進(jì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(子問(wèn)題規(guī)模要減少) ， f(n)漸進(jìn)趨正。漸進(jìn)趨正即對(duì)足夠大的n， f(n) 0.即存在特定的n0 ，當(dāng)n n0時(shí)f(n) 0. 主方法的簡(jiǎn)單思路是比較f(n) 和nlogba(logba是遞歸樹(shù)葉節(jié)點(diǎn)的個(gè)數(shù)) .n有三種情況：n1.小于。 f(n) 較小，它多項(xiàng)式的小于nlogba，即f(n) =O(n(logba-u),u0n則T(n)= (nlogba );n2.等于， f(n)比nlogba大一個(gè)多項(xiàng)式因式logn 。即f(n) = (n(logba)n則T(n)= (nlogba*logn);n3.大于. f(n) 比nlog

10、ba 增長(zhǎng)的快，而且是多項(xiàng)式的大于nlogba ，即f(n)比nlogba大一個(gè)多項(xiàng)式因式。即f(n) =(n(logba+u)。n同時(shí)f(n) 在遞歸的過(guò)程中要不斷變小，否則相加后得到無(wú)限大就麻煩了。即a f(n/b) (1-u)*f(n), u0. f(n)即遞歸樹(shù)的最高層，它應(yīng)該大于下一層所有值之和。最高層需要比下一層大某個(gè)常數(shù)因子。即下一層至多等于(1-u)*f。這樣才能保證每層的數(shù)量越來(lái)越小。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 小一個(gè)多項(xiàng)式因式，因此是小

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)漸進(jì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大一個(gè)多項(xiàng)式因式，因此是大于的情況。n則T(n)= (f(n)= (n3);n主方法的證明（遞歸樹(shù)法證明）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個(gè)葉節(jié)點(diǎn)，因此該層所有節(jié)點(diǎn)的和是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)占主導(dǎo)地位，以下各層會(huì)呈幾何級(jí)數(shù)ak f(n/bk)逐漸減小。n2.如果f(n) nlogba,即第1種情況，在這種情況下， f(n)占

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

14、下方法與一個(gè)函數(shù)聯(lián)系起來(lái)： nG(x) = a0 + a1x + a2x*2 + a3x3 +.+ anxn 則稱G(x)是數(shù)列的生成函數(shù)(generating function) .n研究生成函數(shù)時(shí)，我們都假設(shè)級(jí)數(shù)收斂，因?yàn)樯珊瘮?shù)的x沒(méi)有實(shí)際意義，我們可以任意取值。nFibonacci數(shù)列是這樣一個(gè)遞推數(shù)列：f(n)=f(n-1)+f(n-2),f(0)=1, f(1)=1 。ng(x)應(yīng)該是一個(gè)這樣的函數(shù)： g(x)=1+x+2x2+3x3+5x4+8x5+13x6+21x7+. +f(n)*xnn等式兩邊同時(shí)乘以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的兩個(gè)根是：(1-sqrt(5)/2, (1+sqrt(5)/2,n令g(x) =A / (1+sqrt(5)/2 +B / (1-sqrt(5)/2;n練習(xí)：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ī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。n對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(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ī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。n將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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ī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。分而治之。2.1 n直接或間接地調(diào)用自身的算

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

21、結(jié)果。第n個(gè)階乘數(shù)可遞歸地計(jì)算如下：int factorial(int n) if (n = 1) return 1; return n* factorial( n-1); 2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：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)的增長(zhǎng)速度非常慢。nA(4)= (其中2的層數(shù)為65536)n對(duì)于通常所見(jiàn)到的正整數(shù)n，有(n)4(n)4

23、。但在理論上(n)沒(méi)有上界，隨著n的增加，它以難以想象的慢速度趨向正無(wú)窮大。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 排列問(wèn)題排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。集合X中元素的全排列記為

24、perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 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全排列問(wèn)題。如n=3，假定要對(duì)1,2,3進(jìn)行全排列；n則可變?yōu)閷?duì)1,2,3n 2,1,3n 3,2,1n分別對(duì)內(nèi)元素再全排列，即問(wèn)題的規(guī)模更小一個(gè)得到；這步由 for (i=k;i=m;i+)n swap(listk,listi);nperm(l

26、ist,k+1,m);n swap(listk,listi);n實(shí)現(xiàn)。當(dāng)集合中元素只有一個(gè)時(shí)，一組排列結(jié)果已得到。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如果沒(méi)有最后一句swap(listk,listi);結(jié)果會(huì)和預(yù)期的不一致。n例：n1,2,3-1,2,3-1,2,3一個(gè)排列已得到。n再回溯到1,2,3-1,3,2一個(gè)排列已得到。n如果不把1,3,2歸位為1,2,3，即2,3交換后得到

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

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

29、+ 1 + 1 + 1 + 1 可用程序表示為if(n = 1 | m = 1) return 1;n下面看一看m 和 n的關(guān)系。它們有三種關(guān)系 (1) m n 在整數(shù)劃分中實(shí)際上最大加數(shù)不能大于n，因此在這種情況可以等價(jià)為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時(shí)， 需利用塔座Y作輔助塔座，

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

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

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

33、; if ( w!=0) print(w-1); for(i=1;i1時(shí)，先把上面n-1個(gè)圓盤從A移到B,然后將n號(hào)盤從A移到C,再將n-1個(gè)盤從B移到C。即把求解n個(gè)圓盤的Hanoi問(wèn)題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問(wèn)題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問(wèn)題算法：執(zhí)行情況： 遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址 返回地址用行編號(hào)表示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棧空3 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?？? 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)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存

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

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

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

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

48、 (int n)/計(jì)算Fib(n)的遞歸算法，假定輸入n=0, 見(jiàn)圖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以下的計(jì)算依賴圖如圖2-5所示。顯然，F(xiàn)ib(n)有計(jì)算依賴關(guān)系是一個(gè)樹(shù)形結(jié)構(gòu)，樹(shù)上每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的計(jì)算直接依賴于它的所有孩子，直接或間接地依賴于它的所有子孫。圖2-5 例2-8的遞歸調(diào)用的實(shí)現(xiàn)過(guò)程 從圖2-5中亦可看出，遞歸算法Fib(n)的效率不高。其中，F(xiàn)ib(3)被計(jì)算了兩次，F(xiàn)ib(2)三次，F(xiàn)ib(1)和Fib

49、(0)分別為五次和三次。既然遞歸消除的目的是提高效率，不妨試著把重復(fù)的結(jié)點(diǎn)“合并”在一起以便減少重復(fù)計(jì)算。第一步將兩個(gè)Fib(3)結(jié)點(diǎn)合并，得到子圖。再將得到子圖中兩個(gè)Fib(1)結(jié)點(diǎn)合并,得到新的子圖。上述過(guò)程稱為計(jì)算依賴圖的化簡(jiǎn)。 由圖2-5可知，當(dāng)n=2時(shí)每個(gè)Fib(n)直接依賴于剛剛算出的前兩個(gè)值，需引入兩個(gè)工作變量x, y分別記錄中間結(jié)果。算法如下：function Fib1(int n)/計(jì)算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.分：一個(gè)問(wèn)題的特殊實(shí)例劃分成若干子問(wèn)題，并且這些子問(wèn)題在一定程度上更小了，即比原問(wèn)題的規(guī)模n更小了。即現(xiàn)在有一個(gè)或若干個(gè)子問(wèn)題需要解決，并且每個(gè)子問(wèn)題的規(guī)模更小。2.治：遞歸的解決每個(gè)子問(wèn)題。3.合：把子問(wèn)題的解合并成為整個(gè)大問(wèn)題的解。人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。即將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。這種

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

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

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

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

55、元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計(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; 算法復(fù)雜度分析：算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn

56、) 。1.設(shè)表長(zhǎng)為設(shè)表長(zhǎng)為n，low、high和和mid分別指向待分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)查元素所在區(qū)間的上界、下界和中點(diǎn),k為給為給定值。定值。2.初始時(shí)，令初始時(shí)，令low=1,high=n,mid= (low+high)/2 讓讓k與與mid指向的記錄比較指向的記錄比較若若k=rmid.key，查找成功，查找成功若若krmid.key，則，則low=mid+13.重復(fù)上述操作，直至重復(fù)上述操作，直至lowhigh時(shí)，查找失時(shí)，查找失敗。敗。例如例如 key =21 的查找過(guò)程的查找過(guò)程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 的查找過(guò)程的查找過(guò)程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當(dāng)下界當(dāng)下界low大于上界大于上界hig

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

60、 ( n-1) /2 *x.即當(dāng)n為奇數(shù)時(shí)需要一次遞歸調(diào)用和兩次乘法。n用分治法可以使得求xn的時(shí)間復(fù)雜度由(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 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算u小學(xué)的方法：O(n2) 效率太低u分治法: X = Y = X = a 2n/2 + b Y