遞歸及遞歸算法分析課件

1、1遞歸及遞歸算法分析2主要內(nèi)容v遞歸的實(shí)現(xiàn)機(jī)制遞歸的實(shí)現(xiàn)機(jī)制v遞歸算法編制遞歸算法編制v遞歸關(guān)系式求解遞歸關(guān)系式求解3遞歸的實(shí)現(xiàn)機(jī)制1.遞歸的概念遞歸的概念v直接或間接地調(diào)用自身的算法稱為直接或間接地調(diào)用自身的算法稱為遞歸算遞歸算法法。v用函數(shù)自身給出定義的函數(shù)稱為用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。v直接調(diào)用自身的算法稱為直接遞歸直接調(diào)用自身的算法稱為直接遞歸v間接調(diào)用自身的算法稱為間接遞歸間接調(diào)用自身的算法稱為間接遞歸4v由分治法產(chǎn)生的子問題往往是原問題的較小由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在模式，這就為使用遞歸技術(shù)提供了方便。在這種情況

2、下，反復(fù)應(yīng)用分治手段，可以使子這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。這自然導(dǎo)致遞歸過程的產(chǎn)生。v分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。5主程序主程序call A1：2.子程序的內(nèi)部實(shí)現(xiàn)原理子程序的內(nèi)部實(shí)現(xiàn)原理v1）子程序調(diào)用的一般形式）子程序調(diào)用的一般形式 一次調(diào)用一次調(diào)用 N次調(diào)用次調(diào)用 嵌套調(diào)用

3、嵌套調(diào)用 平行調(diào)用平行調(diào)用子程序子程序A主程序主程序 call A1：call A2：子程序子程序A主程序主程序 call A1：子程序子程序A子程序子程序Bcall B2：主程序主程序 call B1：子程序子程序Bcall A2：子程序子程序A6v2）值的回傳）值的回傳v實(shí)參和形參的數(shù)據(jù)傳遞實(shí)參和形參的數(shù)據(jù)傳遞傳值傳值 實(shí)參的值不發(fā)生改變實(shí)參的值不發(fā)生改變傳地址傳地址 實(shí)參的值發(fā)生改變實(shí)參的值發(fā)生改變v值的回傳通常有兩種形式：值的回傳通常有兩種形式：兩次傳值方式：按照指定類型為變參設(shè)置相應(yīng)的兩次傳值方式：按照指定類型為變參設(shè)置相應(yīng)的存儲空間，在執(zhí)行調(diào)用時，將實(shí)參值傳送給變參存儲空間，在執(zhí)行

4、調(diào)用時，將實(shí)參值傳送給變參在返回時將變參的值傳給實(shí)參。在返回時將變參的值傳給實(shí)參。傳地址：在內(nèi)部將變參用一個地址替換，調(diào)用時，傳地址：在內(nèi)部將變參用一個地址替換，調(diào)用時，先執(zhí)行地址傳送，將實(shí)參地址傳送給變參，在執(zhí)先執(zhí)行地址傳送，將實(shí)參地址傳送給變參，在執(zhí)行過程中，對變參的操作實(shí)際變成對實(shí)參的操作。行過程中，對變參的操作實(shí)際變成對實(shí)參的操作。實(shí)參實(shí)參變參變參12實(shí)參實(shí)參變參變參X地址地址X7v3)子程序調(diào)用的內(nèi)部操作子程序調(diào)用的內(nèi)部操作v執(zhí)行調(diào)用時，系統(tǒng)完成的操作執(zhí)行調(diào)用時，系統(tǒng)完成的操作返回地址進(jìn)棧，為子程序的局部變量開辟空間返回地址進(jìn)棧，為子程序的局部變量開辟空間為子程序準(zhǔn)備數(shù)據(jù)：計(jì)算實(shí)參值

5、，并將其值送給為子程序準(zhǔn)備數(shù)據(jù)：計(jì)算實(shí)參值，并將其值送給形參形參轉(zhuǎn)入子程序入口地址轉(zhuǎn)入子程序入口地址v返回時，系統(tǒng)完成的操作：返回時，系統(tǒng)完成的操作：變參或函數(shù)的值保存到回傳變量中變參或函數(shù)的值保存到回傳變量中從棧頂取返回地址從棧頂取返回地址返回調(diào)用程序返回調(diào)用程序?qū)⒒貍髯兞康闹邓徒o實(shí)參將回傳變量的值送給實(shí)參8v3.遞歸過程的內(nèi)部實(shí)現(xiàn)原理遞歸過程的內(nèi)部實(shí)現(xiàn)原理程序程序A if 出口條件出口條件 then 簡單語句簡單語句 else 簡單語句；簡單語句；call A ； 1：簡單語句；：簡單語句； endifendAv遞歸程序的執(zhí)行令人擔(dān)心是否引遞歸程序的執(zhí)行令人擔(dān)心是否引發(fā)死循環(huán)。擔(dān)心是多余的

6、！發(fā)死循環(huán)。擔(dān)心是多余的！v因?yàn)槊看握{(diào)用，必有一些數(shù)據(jù)發(fā)因?yàn)槊看握{(diào)用，必有一些數(shù)據(jù)發(fā)生變化，直到出現(xiàn)一組數(shù)據(jù)終止生變化，直到出現(xiàn)一組數(shù)據(jù)終止遞歸。這組數(shù)據(jù)就是遞歸出口。遞歸。這組數(shù)據(jù)就是遞歸出口。1。1。1執(zhí)行到出口條件執(zhí)行到出口條件開始出棧開始出棧9遞歸舉例遞歸舉例v直接遞歸直接遞歸proc fact（n） if n=0 then return 1 else return n*fact(n-1)v間接遞歸間接遞歸proc p1(n) if n0 then if odd(n) then p1(n-1); print n; else p2(n-1);print n;proc p2(n) if n

7、0 then if n mod 3=0 then p1(n-1) else p2(n-1)10例例1 1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計(jì)算后得出數(shù)只有具備了這兩個要素，才能在有限次計(jì)算后得出結(jié)果。結(jié)果。遞歸函數(shù)舉例遞歸函數(shù)舉例11遞歸函數(shù)舉例例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci

8、數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第第n個個Fibonacci數(shù)可遞歸地計(jì)算如下：數(shù)可遞歸地計(jì)算如下：public static int fibonacci(int n) if (n 1n1時，時，perm(R)perm(R)由由(r(r1 1)perm(R)perm(R1 1) )，(r(r2 2)perm(R)perm(R2 2) )，(r(rn n)perm(R)perm(Rn n) )構(gòu)成。構(gòu)成。 N!17vr1-t(1)=1vr1、r2-r1perm(R1) r2perm(R2) vt(2)=2*t(1)vr1、r

9、2、r3vr1perm(R1)vr2perm(R2)vr3perm(R3)vt(3)=3*T(2)v.vt(n)=n*t(n-1)18v例例5 整數(shù)劃分問題整數(shù)劃分問題v將正整數(shù)將正整數(shù)n表示成一系列正整數(shù)之和：表示成一系列正整數(shù)之和：n=n1+n2+nk，v其中其中n1n2nk1，k1。v正整數(shù)正整數(shù)n的這種表示稱為正整數(shù)的這種表示稱為正整數(shù)n的劃分。求正整數(shù)的劃分。求正整數(shù)n的不同劃分個數(shù)。的不同劃分個數(shù)。 v例如正整數(shù)例如正整數(shù)6有如下有如下11種不同的劃分：種不同的劃分：v 6；v 5+1；v 4+2，4+1+1；v 3+3，3+2+1，3+1+1+1；v 2+2+2，2+2+1+1，

10、2+1+1+1+1；v 1+1+1+1+1+1。19v前面的幾個例子中，問題本身都具有比較明顯的前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。v在本例中，如果設(shè)在本例中，如果設(shè)p(n)為正整數(shù)為正整數(shù)n的劃分?jǐn)?shù)，則難的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)最大加數(shù)n1不大于不大于m的劃分個數(shù)記作的劃分個數(shù)記作q(n,m)?？??？梢越⒁越(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnq

11、mnqnnqnnqmnq?20(3) q(n,n)=1+q(n,n-1);v正整數(shù)正整數(shù)n的劃分由的劃分由n1=n的劃分和的劃分和n1n-1的劃的劃分組成。分組成。(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1m-1 的劃分組成。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即nn111(2) q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。包含包含m的劃分的劃分不包含不包含m21遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)v用遞歸求解問題的用遞歸求解問題

12、的3個要求：個要求：1.問題的描述涉及規(guī)模問題的描述涉及規(guī)模2.規(guī)模發(fā)生變化后，問題性質(zhì)不改變規(guī)模發(fā)生變化后，問題性質(zhì)不改變3.問題的解決有出口問題的解決有出口proc f（參數(shù)表）（參數(shù)表） if 遞歸出口遞歸出口 then 簡單語句；簡單語句； else 簡單語句；簡單語句；call f（參數(shù)表）；簡單語句；（參數(shù)表）；簡單語句； endifendf2223例例6 Hanoi6 Hanoi塔問題塔問題設(shè)設(shè)a,b,ca,b,c是是3 3個塔座。開始時，在塔座個塔座。開始時，在塔座a a上有一疊共上有一疊共n n個圓盤，這個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編些圓盤自下

13、而上，由大到小地疊在一起。各圓盤從小到大編號為號為1,2,1,2,n,n,現(xiàn)要求將塔座現(xiàn)要求將塔座a a上的這一疊圓盤移到塔座上的這一疊圓盤移到塔座b b上，上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則規(guī)則1 1：每次只能移動：每次只能移動1 1個圓盤；個圓盤；規(guī)則規(guī)則2 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則規(guī)則3 3：在滿足移動規(guī)則：在滿足移動規(guī)則1 1和和2 2的前提下，可將圓盤移至的前提下，可將圓盤移至a,b,ca,b,c中中任一塔座上。任一塔座上。2

14、4在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計(jì)出解Hanoi塔問題的遞歸算法如下。例例6 Hanoi6 Hanoi塔問題塔問題 public static void hano

15、i(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 25vn=3 t(3)=7vn=4 t(4)=15vn=10 t(10)=1023vn=16 t(16)=6553426遞歸小結(jié)優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。序帶來很大方便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算遞歸算法的運(yùn)行效率較低，

16、無論是耗費(fèi)的計(jì)算時間還是占用的存儲空間都比非遞歸算法要多。時間還是占用的存儲空間都比非遞歸算法要多。27遞歸算法的時間復(fù)雜度分析遞歸算法的時間復(fù)雜度分析v遞歸函數(shù)求解遞歸函數(shù)求解簡單遞歸式求解簡單遞歸式求解master method 遞推方程的特征方程求解遞推方程的特征方程求解28vpublic static void hanoi(int n, int a, int b, int c)v v if (n 0)v v hanoi(n-1, a, c, b);v move(a,b);v hanoi(n-1, c, b, a);v v vT(n)=2T(n-1)+O(1) n1 0 n=0T(n)=

17、2n-1429簡單遞歸式的求解1.T(n)=T(n-1)+c1 n1 c2 n=12. T(n)=2T(n/2)+c1 n 2 c2 n23. T(n)=2T(n/2)+(n) n 2 O(1) n 1) 0 (n = 1) 例例1 T(n) = 解解 ：T(n)=2T(n/2)+1 =22T(n/22)+2+1 =23T(n/23)+22+2+1 令令2r=n =2rT(1)+2r-1+。+2+1 =(1-2r)/(1-2)=n-1 T( n ) = n - 131 解上述遞推式：解上述遞推式： T( n ) = 3 T( n/2 ) + k n = 3 3 T( n/22 ) + k (n

18、 / 2 ) + k n =32T(n/22)+3k(n/2)+kn = =3rT(n/2r)+(3/2)r-1kn+.+kn =3rk+ (3/2)r-1kn+.+kn = 3 r+1 k - 2 k n= 3 k 3log2n - 2 k n 3 k n 1.59 - 2 k n = O( n 1. 59 ) 例例2 遞推關(guān)系式：遞推關(guān)系式： 3 T( n/2 ) + k n (n 1) k ( n = 1)T (n ) =32 例例3 T( n/2 ) + T( n/2 ) + (n - 1) (n 1) 0 (n = 1)T(n) = 設(shè)：設(shè)：n = 2r （ r:非負(fù)整數(shù)）。非負(fù)整數(shù)

19、）。 有：有：T(n) = 2 T(n/2 ) + ( n - 1 ) T(n/2) = 2 T(n/22 ) + (n/2 - 1) T(n/22) = 2 T(n/23 ) + (n/22 - 1) T(n/2r-1) = 2 T(n/2r ) + (n/2r-1 - 1)+) 2 22 2 22 23 + 22 2r-1 2r 2r-1 T( n ) = 2r T(1) + rn - (2r-1 + 2r-2 + +20) = nlog2n - n +1 = O(nlog n)33Master MethodvT(n)=aT(n/b)+f(n) a1b1vf(n)是一個非負(fù)漸進(jìn)函數(shù)是一個非

20、負(fù)漸進(jìn)函數(shù)vcase1： 0,使使f(n)=O(nlog ba-) 即即0f(n)0,c0,使使f(n)= (nlog ba+) ,af(n/b)cf(n)v 則則T(n)=(f(n)34v例例1 T(n)=4T(n/2)+nva=4 b=2 f(n)=O(n2-)取取=1 則則T(n)=(n(n2 2) )v例例2 T(n)=4T(n/2)+n2va=4 b=2 f(n)= (n2lgnk)取取K=0v則則T(n)=(n2lgn)v例例3 T(n)=4T(n/2)+n3va=4 b=2 f(n)=n3= (nlog ba+)取取=1v且且4f(n/2)=n3/2 1) 1 ( n = 1)

21、0 ( n = 0)38 解：解：(R): F(n) = F(n -1) + F(n - 2) (E): x2 - x - 1 = 0 (E)的根：的根： x1 = 1/2 + 5 2 , x2 = 1/2 - 5 2 因?yàn)橐驗(yàn)?x1 x2 所以所以 F(n) = c1(1/2 + 5 2)n +c2 (1/2 - 5 2)n c1 + c2 = 0 c1( 1/2 + 5 2 ) + c2(1/2 - 5 2 ) = 1C1 = 1/ 5C2 = - 1/ 5 F(n) = 1/ 5 (1/2 + 5 2)n - (1/2 - 5 2)n 由由 F(0) = 0 和和F(1) = 1 知：知

22、：392 T( n - 1) + 2 T( n - 2 ) ( n 2 ) 3 ( n = 1 ) 8 ( n = 2 )例例 T( n ) = (R): T( n ) = 2 T( n - 1) + 2 T( n - 2 ) (E): x2 - 2x - 2 = 0 x1 = 1 + 3, x2 = 1 - 3 因?yàn)椋阂驗(yàn)椋簒1 x2 T(n) = c1(1 + 3)n + c2( 1 - 3)n 由：由：T(1) = 3 和和 T(2) = 8 得：得： c1 = 1/2 + 3/3, c2 = 1/2 - 3/3, 故：故：T(n) = (1/2 + 3/3)(1 + 3)n + (1/

23、2 - 3/3)( 1 - 3)n40 例例 求：求：Sn = K2k = 0n 解：由：解：由： Sn = 12 + 22 + + n2 (1) 遞推：遞推：S n-1 = 12 + 22 + +(n - 1)2 (2) 由（由（1）- （2） 得：得：Sn - S n-1 = n2 (3) 對（對（3）遞推：）遞推：Sn-1 - Sn-2 = (n - 1)2 (4) 由由(3) - (4) 得：得：Sn - 2S n-1 + S n-2 = 2n - 1 反復(fù)使用上面的方法，消去等號右邊多項(xiàng)式，得：反復(fù)使用上面的方法，消去等號右邊多項(xiàng)式，得： S n - 4Sn-1 + 6Sn-2 -

24、4Sn-3 + Sn-4 = 0 (R) (E): x4-4x3+6x2-4x+1=0 -(x - 1) 4 = 0 x1 = x2 = x3 = x4 = 1541 因?yàn)樘卣鞣匠痰慕馐撬闹馗?，所以：因?yàn)樘卣鞣匠痰慕馐撬闹馗?，所以?Sn = c11n +c2 n 1n + c3 n2 1n + c4 n3 1n = c1 + c2n + c3n2 + c4n3 由：由： S0 = 0, S1 = 1, S2 = 5, S3 = 14, 知：知： c1 = 0 , c2 = 1/6, c3 = 1/2, c4 = 1/3 所以：所以：Sn = 1/6 n ( n + 1 ) (2 n + 1

25、)42 2 非齊次常系數(shù)線性遞推方程的特征方程解法非齊次常系數(shù)線性遞推方程的特征方程解法 （1）定義：）定義：(R)為為k階非齊次常系數(shù)線性遞推方程階非齊次常系數(shù)線性遞推方程: (R): H(n) = a1H(n - 1)+a2H(n - 2)+ +akH(n - k)+f(n) 其中：其中： 1）a1, a2, , ak為常數(shù)；為常數(shù)； 2）ak 0, n k, f(n) 0。 （2）（）（R）的解結(jié)構(gòu)：）的解結(jié)構(gòu)： 設(shè)：（設(shè)：（R）的通解是）的通解是H(n)，且它有一個特解，且它有一個特解H*(n)； 而與（而與（R)相對應(yīng)的相對應(yīng)的 齊次方程齊次方程(R)的通解是的通解是H(n)。 則有

26、（則有（R）的解：）的解：H(n) = H(n) + H*(n) 43(3) (R)的特解形式討論的特解形式討論 1）當(dāng)）當(dāng)f(n) 形如形如bnt( b 0, t:非負(fù)整數(shù)）時，非負(fù)整數(shù)）時，(R)的特解為：的特解為： H*(n) = p1nt + p2nt-1+ + pt n + pt+1 其中：其中：p1, p2, ， pt+1是待定系數(shù)。是待定系數(shù)。 但，當(dāng)?shù)?dāng)x = 1是是(R)的的 j 重特征根（重特征根（j 1）時，其特解應(yīng)）時，其特解應(yīng) 改設(shè)為：改設(shè)為： H*(n) = p1nt+j + p2nt-1+j+ + pt+1nj 2）當(dāng)）當(dāng)f(n) 形如形如 b rn( b 0,

27、 r 0 ）時，）時，(R)的特解為：的特解為： H*(n) = p rn 其中：其中：p是待定系數(shù)。是待定系數(shù)。 但，當(dāng)?shù)?，?dāng) x = r 是是(R) 對應(yīng)的對應(yīng)的(R)的的 j 重特征根重特征根( j 1)時，時， (R)的特解應(yīng)改設(shè)為：的特解應(yīng)改設(shè)為： H*(n) = p nj rn44 T(n) = 2T( n - 1 ) + k (n 1) (k:正數(shù)）正數(shù)） k ( n = 1 ) 解：解：(R) : T(n) = 2T(n - 1) + k (R) : T(n) = 2T(n - 1) (E): x - 2 = 0 x = 2 (R)的通解：的通解： T(n) = c 2n 因?yàn)?/p>

28、因?yàn)?R)中，中，f(n) = k 所以，所以， 設(shè)：設(shè)： T*(n) = p 顯然，顯然， T*(n - 1) = p 45 把把T*(n)、T*(n - 1)代入代入(R) , 有：有：p = 2p + k p = - k 故：故：T*(n) = - k (R)的通解：的通解：T(n) = T(n) + T*(n) = c 2n - k 由由T(1) = k, 把它代入上式，把它代入上式， 有：有：2 c - k = k c = k (R)的通解：的通解：T(n) = k( 2n - 1) = O( 2n )46例例 T(n) = 2n-3 - T( n -2 ) ( n 4 ) 1 (

29、n = 3 ) 2 ( n = 4 ) 解：解：(R): T(n) = - T(n - 2 ) + 2n-3 (R): T(n) = - T(n - 2 ) (E): x2 + 1 = 0 (R) 的通解：的通解：T(n) = c1cos(n /2) + c2sin(n /2) （ 其中：其中： = 1， = /2）47 設(shè)：設(shè)：(R) 的特解是：的特解是：T*(n) = p 2n 把它代入把它代入(R),有：有：p 2n = - p 2 n-2 + 2 n-3 得：得：p = 1/10 T(n) = c1cos(n /2) + c2sin(n /2) + 2n/10 由：由：T(3) = 1

30、 和和 T(4) = 2, 知：知：c1 = 2/5, c2 = -1/5 故：故： T(n) = 2/5cos(n /2) - 1/5sin(n /2) + 2n/10 （ n 2 ）48 例例 再求：再求：Sn = K2k = 0 n 解：由：解：由： Sn = 12 + 22 + + n2 (1) 遞推：遞推：S n-1 = 12 + 22 + +(n - 1)2 (2) 由（由（1）- （2） 得：得：Sn - S n-1 = n2 (R) (E): x - 1 = 0 x = 1 (R): Sn - S n-1 = 0 (R)的通解：的通解：Sn = c 設(shè)：設(shè)：(R)的特解是：的特

31、解是：S*n = p1n3 + p2n2 + p3n 代入代入(R), 得：得：p1 = 1/3, p2 = 1/2, p3 = 1/6 (R)的通解：的通解：Sn = p1n3 + p2n2 + p3n + c 由由S0 = 0,知：知：c = 0 故：故： Sn = p1n3 + p2n2 + p3n49 變系數(shù)變系數(shù)/非線性遞推方程的求解非線性遞推方程的求解 原則：原則：“變換變換”。 一、變一、變“非線性非線性”為為“線性線性” 解：令：解：令：G(n) = H2(n),則有：則有：G(n) - 2G(n - 1) = 1 ( G(n) 0, n 0 ) G(0) = 4 解上述遞推式

32、，得：解上述遞推式，得：G(n) =5 2n - 1 H(n) = 5 2n - 1 H(0) = 2 例例 求求H(n)。已知：。已知：H2(n) - 2H2(n - 1) = 1 ( H(n) 0 , n 0 ) 50 二、變二、變“變系數(shù)變系數(shù)”為為“常系數(shù)常系數(shù)” b (n = 1; b:非負(fù)常數(shù)）非負(fù)常數(shù)）(n - 1) + 1/n T(k - 1) + 1/nT(n-k) (n 1)k=1 k=1nn T(n) = 51 整理、改寫上述遞推式：整理、改寫上述遞推式： T(n) = (n - 1) + 2/n T(k) n-1k=1 nT(n) = n(n - 1) + 2 T(k)

33、 n-1k=1(1)(n-1)T(n-1) = (n-1)(n - 2) + 2 T(k) n-2k=1(2)遞推：遞推： 由由(1) - (2) 得：得： nT(n) - (n - 1)T(n - 1) = 2(n - 1) + 2T(n - 1) 即：即： T(n) = T(n - 1) + n+11n12(n - 1)n(n + 1)(3) 令：令：Q(n) = T(n), 有：有：Q(n - 1) = T(n - 1)n+11n152 代入代入(3)式：式：Q(n) = Q(n - 1) + n(n + 1)2(n - 1)遞推：遞推：Q(n - 1) = Q(n - 2) + (n

34、- 1)n2(n - 2) Q(n - 2) = Q(n - 3) + (n - 2)(n - 1)2(n - 3) Q(2) = Q(1) + 2 12 3+) Q(n) - Q(1) = nk=2k(k + 1)2(k - 1) k=2n=k+14-k 2=n+14- 1 + 2 k=3nk153 因?yàn)椋阂驗(yàn)椋?k=3nk1 3n1xdx= ln n - ln 3 由：由：Q(n) = T(n), 及：及：T(1) = b, 知：知：Q(1) = 1/2bn+11 T(n) = (n + 1) Q(n) 2(n + 1) ln n + (b/2 - 1 - 2ln 3)(n +1) + 4

35、 = O(n ln n)54遞歸程序的閱讀法遞歸程序的閱讀法v用圖形方式描述執(zhí)行軌跡用圖形方式描述執(zhí)行軌跡1.按次序?qū)懗龀绦蛟诋?dāng)前調(diào)用層上實(shí)際執(zhí)行的語句，按次序?qū)懗龀绦蛟诋?dāng)前調(diào)用層上實(shí)際執(zhí)行的語句，并用有向弧表明語句執(zhí)行次序并用有向弧表明語句執(zhí)行次序2.對程序中的每個調(diào)用語句寫出實(shí)際調(diào)用形式，在對程序中的每個調(diào)用語句寫出實(shí)際調(diào)用形式，在其下（右）邊寫出本次調(diào)用的子程序?qū)嶋H執(zhí)行的其下（右）邊寫出本次調(diào)用的子程序?qū)嶋H執(zhí)行的語句，用有向弧指示。語句，用有向弧指示。3.被調(diào)用子程序執(zhí)行完有向弧指向其上級（標(biāo)上形被調(diào)用子程序執(zhí)行完有向弧指向其上級（標(biāo)上形參的值）參的值）4.變參：再返回路線上增加語句實(shí)參

36、變參：再返回路線上增加語句實(shí)參=變參變參 函數(shù)：函數(shù)： 實(shí)參實(shí)參=函數(shù)值函數(shù)值最后，順著有向弧的路徑寫出結(jié)果。最后，順著有向弧的路徑寫出結(jié)果。55例vproc f(w)v if w0 thenv f(w-1)v print wv f(w-1)v vend f56習(xí)題答案習(xí)題答案 答：答：T(n) = 2b nlog2n - 2b n + 3b = O(nlog2n) 2. 2. 求解：求解：T(nT(n)= )= aT(n/c) + bnaT(n/c) + bn (n 1) (n 1)b (n = 1)b (n = 1)(a, c:(a, c:正整數(shù)；正整數(shù)；b: b:正數(shù)）正數(shù)）答：當(dāng)答：當(dāng)

37、 n = cr(r：非負(fù)整數(shù)：非負(fù)整數(shù))時，有時，有 T(n) = (bn) ki(k = a/c)i=0logc nb (n = 1) (b:b (n = 1) (b:正數(shù)正數(shù)) )T(n/2) + b n logT(n/2) + b n log2 2 n (n 1)n (n 1)T(n) =T(n) =1. 1. 用遞推法求解用遞推法求解57(1) 當(dāng)當(dāng) ac 時時, T(n) = bn (kr+1 - 1) / (k-1) = bk / (k - 1) ar - bn / (k - 1) = bk/(k - 1) alogcn - bn/(k - 1) = O ( nlogca )3. 3. 用特征方程法求解用特征方程法求解T(n)T(n)。已知：。已知： 2 T(n - 1) + n (n 1)2 T(n - 1) + n (n 1) 1 (n = 1) 1 (n = 1)（1）T(n) =T(n) =答：答：T(n) = 2n+1 - ( n + 2 )587T(n 1) - 12T(n 2) + 37T(n 1) - 12T(n 2