1、1主要內(nèi)容主要內(nèi)容l 遞推方程的定義及實(shí)例遞推方程的定義及實(shí)例l 遞推方程的公式解法遞推方程的公式解法l 遞推方程的其他解法遞推方程的其他解法l 生成函數(shù)及其應(yīng)用生成函數(shù)及其應(yīng)用l 指數(shù)生成函數(shù)及其應(yīng)用指數(shù)生成函數(shù)及其應(yīng)用l Catalan數(shù)與數(shù)與Stirling數(shù)數(shù)第十三章第十三章 遞推方程與生成函數(shù)遞推方程與生成函數(shù)213.1遞推方程的定義及實(shí)例遞推方程的定義及實(shí)例定義定義13.1 設(shè)序列設(shè)序列 a0, a1, , an, , 簡(jiǎn)記為簡(jiǎn)記為 an . 一個(gè)把一個(gè)把 an 與與某些個(gè)某些個(gè)ai (in) 聯(lián)系起來(lái)的等式叫做關(guān)于序列聯(lián)系起來(lái)的等式叫做關(guān)于序列 an 的的遞推方遞推方程程. 當(dāng)給

2、定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_定了序列當(dāng)給定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_定了序列. Fibonacci數(shù)列數(shù)列：1，1，2，3，5，8， ，記作，記作 fn . 遞推方程遞推方程 fn = fn 1 + fn 2 初值初值 f0 = 1，f1 = 1 階乘計(jì)算數(shù)列：階乘計(jì)算數(shù)列： 1，2，6，24，5！，！，, 記作記作 F(n) 遞推方程遞推方程 F(n) = nF(n 1) 初值初值 F(1) = 1 3例例1 從從A柱將這些圓盤(pán)移到柱將這些圓盤(pán)移到C柱上去柱上去. 如果把一個(gè)圓盤(pán)從如果把一個(gè)圓盤(pán)從一個(gè)柱子移到另一個(gè)柱子稱(chēng)作一次移動(dòng)，在移動(dòng)和放置一個(gè)柱子移到另一個(gè)柱子稱(chēng)作一次移動(dòng)，在移動(dòng)和

3、放置時(shí)允許使用時(shí)允許使用B柱，但不允許大圓盤(pán)放到小圓盤(pán)的上面柱，但不允許大圓盤(pán)放到小圓盤(pán)的上面. 問(wèn)問(wèn)把所有的圓盤(pán)的從把所有的圓盤(pán)的從A移到移到C總計(jì)需要多少次移動(dòng)？總計(jì)需要多少次移動(dòng)？初值是初值是 T(1)=1 可證明解是可證明解是 T(n)=2n 1 移動(dòng)移動(dòng)n個(gè)盤(pán)子的總次數(shù)為個(gè)盤(pán)子的總次數(shù)為T(mén)(n). 因此得到遞推方程因此得到遞推方程 T(n) = 2T(n 1) +1. 遞推方程的實(shí)例遞推方程的實(shí)例:Hanoi塔塔4兩個(gè)排序算法兩個(gè)排序算法歸并算法歸并算法 Mergesort (A,p,r) / 對(duì)對(duì)A的下標(biāo)的下標(biāo)p到到r之間數(shù)排序之間數(shù)排序1. if p 0 and Ai key5.

4、 do Ai+1 Ai; i i 17. Ai+1 key 5遞推方程的實(shí)例遞推方程的實(shí)例:算法分析算法分析例例2 哪種排序算法在最壞情況下復(fù)雜度比較低？哪種排序算法在最壞情況下復(fù)雜度比較低？ 插入排序，歸并排序插入排序，歸并排序 插入排序插入排序 W(n) = W(n 1) + n 1 W(1) = 0解得解得 W(n) = O(n2). 歸并排序，不妨設(shè)歸并排序，不妨設(shè) n = 2k. W(n) = 2W(n/2) + n1 W(1) = 0解得解得 W(n) = O(nlogn) 613.2 遞推方程的公式解法遞推方程的公式解法l 特征方程、特征根特征方程、特征根l 遞推方程的解與特征根

5、的關(guān)系遞推方程的解與特征根的關(guān)系l 無(wú)重根下通解的結(jié)構(gòu)無(wú)重根下通解的結(jié)構(gòu)l 求解實(shí)例求解實(shí)例l 有重根下通解的結(jié)構(gòu)有重根下通解的結(jié)構(gòu)l 求解實(shí)例求解實(shí)例7 121021)1(,.,)2(,)1(,)0(0)(.)2()1()(kkbkHbHbHbHknHanHanHanH其中其中 a1, a2, , ak為常數(shù)，為常數(shù)，ak 0 稱(chēng)為稱(chēng)為 k 階常系數(shù)線性齊次遞推方程階常系數(shù)線性齊次遞推方程 b0, b1, , bk 1 為為 k 個(gè)個(gè)初值初值定義定義13.2 常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形： 1, 11021fffffnnn常系數(shù)線性齊次遞推方程常系數(shù)線性齊次

6、遞推方程實(shí)例：實(shí)例：Fibonacci 數(shù)列的遞推方程數(shù)列的遞推方程8特征方程與特征根特征方程與特征根 121021)1(,.,)2(,)1(,)0(0)(.)2()1()(kkbkHbHbHbHknHanHanHanH 定義定義13.3 特征方程特征方程 xk a1xk 1 ak = 0， 特征方程的根稱(chēng)為遞推方程的特征方程的根稱(chēng)為遞推方程的 特征根特征根 實(shí)例：實(shí)例： 遞推方程遞推方程 fn = fn 1 + fn 2 特征方程特征方程 x2 x 1 = 0 251,251 特征根特征根9遞推方程解與特征根的關(guān)系遞推方程解與特征根的關(guān)系定理定理13.1 設(shè)設(shè) q 是非零復(fù)數(shù)，則是非零復(fù)數(shù)，

7、則 qn 是遞推方程的解當(dāng)且僅當(dāng)是遞推方程的解當(dāng)且僅當(dāng)q 是它的特征根是它的特征根. qn是遞推方程的解是遞推方程的解 qn a1qn 1 a2qn 2 akqn k = 0 qn k (qk a1qk 1 a2qk 2 ak) = 0 qk a1qk 1 a2qk 2 ak = 0 （因?yàn)椋ㄒ驗(yàn)閝 0） q 是它的特征根是它的特征根 定理定理13.2 設(shè)設(shè) h1(n) 和和 h2(n) 是遞推方程的解，是遞推方程的解，c1,c2為任意常數(shù)為任意常數(shù),則則 c1h1(n)+c2h2(n) 也是這個(gè)遞推方程的解也是這個(gè)遞推方程的解.推論推論 若若 q1, q2, , qk 是遞推方程的特征根，則

8、是遞推方程的特征根，則 c1q1n + c2q2n + + ckqkn 是該遞推方程的解，其中是該遞推方程的解，其中c1, c2, , ck 是任意常數(shù)是任意常數(shù). 10無(wú)重根下通解的結(jié)構(gòu)無(wú)重根下通解的結(jié)構(gòu)定義定義13.4 若對(duì)常系數(shù)線性齊次遞推方程的每個(gè)解若對(duì)常系數(shù)線性齊次遞推方程的每個(gè)解 h(n) 都都存在一組常數(shù)存在一組常數(shù)c1 ,c2 , ck 使得使得 h(n) = c1 q1n+c2 q2n+ck qkn 成立，則稱(chēng)成立，則稱(chēng) c1q1n + c2q2n + + ckqkn 為該遞推方程的為該遞推方程的通解通解 定理定理13.3 設(shè)設(shè)q1, q2, , qk 是是常系數(shù)線性齊次常系

9、數(shù)線性齊次遞推方程不等遞推方程不等的特征根，則的特征根，則 H(n)= c1q1n + c2q2n + + ckqkn為該遞推方程的通解為該遞推方程的通解.11251,251 例例3 Fibonacci 數(shù)列：數(shù)列： fn=fn 1+fn 2 ，特征根為，特征根為 nnnccf 25125121 通解為通解為 125125112121cccc代入初值代入初值 f0 =1, f1=1, 得得 25151,2515121 cc解得解得 112515125151 nnnf解是解是實(shí)例實(shí)例12有重根下求解中的問(wèn)題有重根下求解中的問(wèn)題 1)1(, 0)0(0)2(41)(4)(HHnHnHnH例例4 4

10、解解 特征方程特征方程 x2 4x+4 = 0 通解通解 H(n) = c12n + c22n = c2n 代入初值得：代入初值得： c 無(wú)解無(wú)解. 問(wèn)題：兩個(gè)解線性相關(guān)問(wèn)題：兩個(gè)解線性相關(guān) 120cc13有重根下的通解結(jié)構(gòu)有重根下的通解結(jié)構(gòu)neiiiiiiieqncnccnH).()(121 定理定理13.4 設(shè)設(shè) q1, q2, , qt 是遞推方程的不相等的特征根，是遞推方程的不相等的特征根，且且 qi 的重?cái)?shù)為的重?cái)?shù)為 ei，i=1, 2, , t，令，令 tiinHnH1)()(那么通解那么通解 14例例5 求解以下遞推方程求解以下遞推方程 2(3)1(2)0,(1)1(0)0)4(

11、2)3(5)2(31)()(,HH,HHnHnHnHnHnH其中待定常數(shù)滿(mǎn)足以下方程組其中待定常數(shù)滿(mǎn)足以下方程組 92, 0,31,9728931442021432143214321432141 ccccccccccccccccccnnnnnH292)1(31)1(97)( 原方程的解為原方程的解為 解解 特征方程特征方程 x4+x3 3x2 5x 2 = 0 , 特征根特征根 1, 1, 1,2nncncnccnH2)1)()(42321 通解為通解為求解實(shí)例求解實(shí)例15l 遞推方程的標(biāo)準(zhǔn)型遞推方程的標(biāo)準(zhǔn)型l 通解結(jié)構(gòu)通解結(jié)構(gòu)l 特解的求法特解的求法 多項(xiàng)式函數(shù)多項(xiàng)式函數(shù) 指數(shù)函數(shù)指數(shù)函數(shù)

12、組合形式組合形式常系數(shù)線性非齊次遞推方程求解常系數(shù)線性非齊次遞推方程求解160)(*)(.)1(*)1()(*)()()(*.)1(*)(*)()(.)1()(111 knHknhanHnhanHnhnfknHanHanHnfknhanhanhkkk證證 代入驗(yàn)證代入驗(yàn)證, H(n)是解是解. 下面證明任意解下面證明任意解 h(n) 為某個(gè)齊次為某個(gè)齊次解與特解解與特解H*(n)之和之和. 設(shè)設(shè) h(n)為遞推方程的解，則為遞推方程的解，則h(n) H*(n)是齊次解，即是齊次解，即 h(n) 是一個(gè)齊次解與是一個(gè)齊次解與H*(n)之和之和. 0)(, 0,),()(.)1()(1 nfakn

13、nfknHanHanHkk定理定理13.5 設(shè)設(shè))(nH是對(duì)應(yīng)齊次方程的通解，是對(duì)應(yīng)齊次方程的通解，H*(n)是一個(gè)特解，則是一個(gè)特解，則 )(*)()(nHnHnH 是遞推方程的通解是遞推方程的通解. . 遞推方程的標(biāo)準(zhǔn)型及通解遞推方程的標(biāo)準(zhǔn)型及通解17解解 設(shè)設(shè) an* = P1n2 + P2n + P3 , 代入遞推方程得代入遞推方程得 P1n2 + P2n + P3 2P1(n 1)2 + P2(n 1) + P3 = 2n2 整理得整理得 P1n2+(4P1 P2)n+( 2P1+2P2 P3) = 2n2 022042321211PPPPPP解得解得 P1= 2, P2 = 8,

14、P3= 12，原方程的通解為原方程的通解為 an = c2n 2(n2+4n+6) 例例6 找出遞推方程找出遞推方程 an 2an 1 = 2n2 的通解的通解如果如果 f(n)為為n次多項(xiàng)式，則特解一般也是次多項(xiàng)式，則特解一般也是 n 次多項(xiàng)式次多項(xiàng)式特解的形式：多項(xiàng)式特解的形式：多項(xiàng)式18例例7 Hanoi塔塔 T(n) = 2T(n 1)+1 T(1)=1 實(shí)例實(shí)例解解 令令 T*(n) = P代入方程代入方程 P = 2P + 1解得解得 P = 1 T(n) = c 2n1, 代入初值得代入初值得 c=1, 解為解為 T(n) = 2n 1.19例例8 求解關(guān)于順序插入排序算法的遞推

15、方程求解關(guān)于順序插入排序算法的遞推方程 0)1( 1)1()(WnnWnW解解 設(shè)特解為設(shè)特解為W*(n)=P1n+P2，代入遞推方程，得，代入遞推方程，得 P1n+P2 ( P1(n 1)+P2) = n 1無(wú)解無(wú)解. 設(shè)特解設(shè)特解W*(n) = P1n2+P2n, 代入遞推方程得代入遞推方程得 (P1n2+P2n) (P1(n 1)2+P2(n 1)= n 1 解得解得 P1=1/2, P2= 1/2. 通解為通解為 W(n) = c 1n + n(n 1)/2 = c + n(n 1)/2代入初值代入初值W(1)=0，得到，得到W(n)= n(n 1)/2=O(n2). 實(shí)實(shí) 例例( (

16、續(xù)續(xù)) )20特解的形式特解的形式: :指數(shù)指數(shù)f(n)為指數(shù)函數(shù)為指數(shù)函數(shù) n，若若 是是 e 重特征根重特征根(e可以等于可以等于0)，則特，則特解為解為Pne n , 其中其中P為待定常數(shù)為待定常數(shù). 例例9 通信編碼問(wèn)題通信編碼問(wèn)題 解解 an = 6an 1 + 8n 1, a1=7 設(shè)設(shè) a*n = P 8n 1 , 代入得代入得 P = 4 通解通解 an = c 6n + 4 8n 1 代入初值得代入初值得 an = (6n+8n)/2 例例10 H(n)5H(n1)+6H(n2) = 2n， 解解 令令 H*(n)=Pn2n 代入得代入得 Pn2n 5P(n1)2n1 + 6

17、P(n2)2n2 = 2n 解得解得 P = 2, 特解特解 H*(n) = n2n+1 21l 換元法換元法l 迭代歸納法迭代歸納法l 應(yīng)用實(shí)例應(yīng)用實(shí)例 13.3 遞推方程的其他解法遞推方程的其他解法22思想：通過(guò)換元轉(zhuǎn)化成常系數(shù)線性遞推方程思想：通過(guò)換元轉(zhuǎn)化成常系數(shù)線性遞推方程 ,2nnab 解解 令令125125 nnnnab代入得代入得 bn = 2 bn1 + 1， b0 = 4解得解得 例例11 2120212aaannan0換元法換元法23解解 H(k) = 2 H(k1) + 2k1 H(1) = 1 令令 H*(k) = P1k2k + P2 , 解得解得 P1=P2=1 H

18、*(k) = k2k + 1通解通解 H(k) = c 2k + k2k + 1 代入初值得代入初值得 c = 1 H(k) = 2k + k2k +1 W(n) = n log n n + 1 0 (1)2 , 1 ) /2 (2 )(WnnnWnWk例例12 歸并排序歸并排序換元法換元法:實(shí)例實(shí)例24迭代歸納法：歸并排序迭代歸納法：歸并排序 0 (1)2 , 1 ) /2 (2 )(WnnnWnWk例例131log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWW

19、WWWnWkkkkkkkkkkkkkkkkkkkkkk解解25迭代歸納法：錯(cuò)位排列迭代歸納法：錯(cuò)位排列例例14 Dn = (n1)(Dn1 + Dn2) 0,)1()1(2)1(.)1(112122211 DnDDDDDnDnDDnnnnnnnnn解：解：!1)1(.! 21! 111 !)1()1(.)1(4).1()1(3).1(2).1(.)1()1()1)(1()2)(1()1()1(13211232nnnnnnnDnnnnnDnnnnDnnDnnnnnnnnnn 26快速排序算法快速排序算法算法算法 Quicksort (A,p,r) / p 和和 r 分別表示分別表示A首和末元素下

20、標(biāo)首和末元素下標(biāo) 1. if p r 2. then qPartition(A, p, r) / 劃分為劃分為Ap.q 1和和Aq+1.r 3. ApAq 4. Quicksort(A,p,q 1) 5. Quicksort(A,q+1,r)27劃分過(guò)程劃分過(guò)程算法算法 Partition(A,p,r) 1. x Ap /選首元素作為劃分標(biāo)準(zhǔn)選首元素作為劃分標(biāo)準(zhǔn)x2. i p 1 3. j r+14. while true 5. do repeat j j 1 6. until A j x /Ai是從前找的第一個(gè)比是從前找的第一個(gè)比x大的元素大的元素9. if i j / 繼續(xù)搜索繼續(xù)搜索Ai

21、到到Aj之間的范圍之間的范圍10 then A i A j / A i 與與A j 交換，回到行交換，回到行411. else return j /結(jié)束結(jié)束While循環(huán)循環(huán)28實(shí)例實(shí)例 27 99 0 8 13 64 86 16 7 10 88 25 90 i j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 29平均情況時(shí)間復(fù)雜

22、度分析平均情況時(shí)間復(fù)雜度分析 0)1(2),()(2)(11TnnOiTnnTni為為某某個(gè)個(gè)常常數(shù)數(shù)cnciTnTncniTnnTnini 2122111)()(21)()1()(2)(遞推方程遞推方程差消法化簡(jiǎn)差消法化簡(jiǎn))()1()1()(nOnTnnnT 1)1(1)( ncnnTnnT30迭代求解迭代求解 31.1112)1(31.1111)(nncTnncnnT)(log2ln)1ln(ln131.1111212nOnxdxxnnnn )log()(nnOnT 31遞歸樹(shù)遞歸樹(shù)0 (1),2 , 1 ) /2 (2 )( WnnnWnWk12111114141414142121211

23、 knnnnnnnnnnnW(n)= n k (1+2+2k 1) = nk (2k 1) = n log n n + 13213.4 生成函數(shù)及其應(yīng)用生成函數(shù)及其應(yīng)用l 牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理l 生成函數(shù)的定義生成函數(shù)的定義l 生成函數(shù)的應(yīng)用生成函數(shù)的應(yīng)用33牛頓二項(xiàng)式系數(shù)牛頓二項(xiàng)式系數(shù) 0!)1).(1(0100nnnrrrnnnr定義定義13.5 設(shè)設(shè) r 為實(shí)數(shù)，為實(shí)數(shù)，n為整數(shù)，引入形式符號(hào)為整數(shù)，引入形式符號(hào)65!6)5)(4)(3)(2)(52 1285! 42)5)(3(1)1(! 4)321)(221)(121(2142/14 4! 32

24、3434 稱(chēng)為稱(chēng)為牛頓二項(xiàng)式系數(shù)牛頓二項(xiàng)式系數(shù). . 實(shí)例實(shí)例34牛頓二項(xiàng)式定理牛頓二項(xiàng)式定理定理定理13.6 （牛頓二項(xiàng)式定理）（牛頓二項(xiàng)式定理）設(shè)設(shè) 為實(shí)數(shù)，則對(duì)一切實(shí)數(shù)為實(shí)數(shù)，則對(duì)一切實(shí)數(shù)x, y，|x/y|0為常為常數(shù)數(shù). 當(dāng)當(dāng) p 上漲時(shí)上漲時(shí) q 將減少將減少. 供給關(guān)系：供給關(guān)系：p=kr，其中，其中p為價(jià)格，為價(jià)格，r 為供給量，為供給量，k0為常數(shù)為常數(shù). 當(dāng)當(dāng)p上漲時(shí)，上漲時(shí)，r 將增加將增加. 假設(shè)價(jià)格隨需求量能做到即時(shí)變化，而商品生產(chǎn)和流通需要假設(shè)價(jià)格隨需求量能做到即時(shí)變化，而商品生產(chǎn)和流通需要時(shí)間，因此供給量隨價(jià)格的變化需要時(shí)間，因此供給量隨價(jià)格的變化需要1個(gè)單位時(shí)間

25、的延遲個(gè)單位時(shí)間的延遲. 假假定每個(gè)時(shí)間的需求量都和供給量相等，考慮一個(gè)時(shí)間序列定每個(gè)時(shí)間的需求量都和供給量相等，考慮一個(gè)時(shí)間序列0,1,n,，設(shè)時(shí)間，設(shè)時(shí)間0的價(jià)格是的價(jià)格是 p0，求時(shí)間，求時(shí)間 n 的價(jià)格的價(jià)格 pn. 練習(xí)練習(xí)683設(shè)第設(shè)第 n 時(shí)間的價(jià)格為時(shí)間的價(jià)格為 pn, 需求量為需求量為 qn，供給量為，供給量為 rn，那么有，那么有 nnnnnnqrkrpbqap1練習(xí)練習(xí)6appnkbn 1bkkakbcpnn )(bkkapcbkkacp 00bkkapbkkakbpnn )()(0代入得到代入得到 解得解得847用三個(gè)用三個(gè)1、兩個(gè)、兩個(gè)2、五個(gè)、五個(gè)3可以組成多少個(gè)不

26、同的四位數(shù)？可以組成多少個(gè)不同的四位數(shù)？如果這個(gè)四位數(shù)是偶數(shù)，那么又有多少個(gè)？如果這個(gè)四位數(shù)是偶數(shù)，那么又有多少個(gè)？ 練習(xí)練習(xí)7)! 5! 4! 3! 21()! 21)(! 3! 21()(5432232xxxxxxxxxxxAe 其中其中x4的系數(shù)為的系數(shù)為! 4714x 因此因此 a4=71. 85練習(xí)練習(xí)8方法一方法一. n 個(gè)編號(hào)球恰放入個(gè)編號(hào)球恰放入 k 個(gè)相同盒子且不允許相鄰編號(hào)個(gè)相同盒子且不允許相鄰編號(hào)在同一盒的方法數(shù)在同一盒的方法數(shù). 選定球選定球a1, 進(jìn)行變換：如果進(jìn)行變換：如果a1自己在一自己在一個(gè)盒子，將盒子拿走，得到個(gè)盒子，將盒子拿走，得到 n 1個(gè)不同球恰放入個(gè)不同球恰放入k 1個(gè)相同個(gè)相同盒且相鄰編號(hào)不落入同一盒子的方法盒且相鄰編號(hào)不落入同一盒子的方法. 如果與如果與a1在同一盒子的球有在同一盒子的球有 將球?qū)⑶?放入放入 所在的盒子，所在的盒子， 然后拿走含然后拿走含a1的盒子，從而得到的盒子，從而得到n 1個(gè)不同球個(gè)不同球恰好放到恰好放到 k 1個(gè)盒子且至少兩個(gè)相鄰標(biāo)號(hào)球落入同一盒的個(gè)盒子且至少兩個(gè)相鄰標(biāo)號(hào)球落入同一盒的方法方法. 所求方法數(shù)等于所求方法數(shù)等于n 1個(gè)不同球恰好放入個(gè)不同球恰好放入