1、課件,1,第10章 遞推方程與生成函數(shù),課件,2,第10章 遞推方程與生成函數(shù),10.1 遞推方程及其應(yīng)用 10.2 生成函數(shù)及其應(yīng)用 10.3 指數(shù)生成函數(shù)及其應(yīng)用 10.4 Catalan數(shù)與Stirling數(shù),課件,3,10.1 遞推方程及其應(yīng)用,10.1.1 遞推方程的定義及實(shí)例 10.1.2 常系數(shù)線性齊次遞推方程的求解 10.1.3 常系數(shù)線性非齊次遞推方程的求解 10.1.4 遞推方程的其他解法 10.1.5 遞推方程與遞歸算法,課件,4,遞推方程的定義,定義10.1 設(shè)序列 a0, a1, , an, , 簡(jiǎn)記為 an . 一個(gè)把 an 與 某些個(gè)ai (in) 聯(lián)系起來的等式

2、叫做關(guān)于序列 an 的遞推方 程. 當(dāng)給定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_定了序列. 例如， Fibonacci數(shù)列：1，1，2，3，5，8， ，記作 fn . 遞推方程 fn = fn1 + fn2 初值 f0 = 1，f1 = 1 階乘計(jì)算數(shù)列： 1，2，6，24，5！，, 記作 F(n) 遞推方程 F(n) = nF(n1) 初值 F(1) = 1,課件,5,化簡(jiǎn)得 an = 6an1 + 8n1, 可以解得 an=(6n+8n)/2,遞推方程的實(shí)例計(jì)數(shù)編碼,例1 一個(gè)編碼系統(tǒng)用八進(jìn)制數(shù)字對(duì)信息編碼，一個(gè)碼是 有效的當(dāng)且僅當(dāng)含有偶數(shù)個(gè)7, 求 n 位長(zhǎng)的有效碼字有多 少個(gè)？ 解 設(shè)所求有效碼

3、字為 an個(gè). 分類處理、分步處理得到遞 推方程和初值如下： an=7an1+ 8n1 an1 a1=7,課件,6,遞推方程的實(shí)例Hanoi塔,例2 從A柱將這些圓盤移到C柱上去. 如果把一個(gè)圓盤從 一個(gè)柱子移到另一個(gè)柱子稱作一次移動(dòng)，在移動(dòng)和放置 時(shí)允許使用B柱，但不允許大圓盤放到小圓盤的上面. 問 把所有的圓盤的從A移到C總計(jì)需要多少次移動(dòng)？,初值是 T(1)=1 可證明解是 T(n)=2n1,移動(dòng)n個(gè)盤子的總次數(shù)為T(n). 因此得到遞推方程 T(n) = 2T(n1) +1.,課件,7,遞推方程的實(shí)例算法分析,例3 哪種排序算法在最壞情況下復(fù)雜度比較低？ 插入排序，歸并排序 插入排序

4、W(n) = W(n 1) + n 1 W(1) = 0 解得 W(n) = O(n2). 歸并排序，不妨設(shè) n = 2k. W(n) = 2W(n/2) + n1 W(1) = 0 解得 W(n) = O(nlogn),課件,8,常系數(shù)線性齊次遞推方程求解,其中 a1, a2, , ak為常數(shù)，ak 0 稱為 k 階常系數(shù)線性齊次遞推方程 b0, b1, , bk1 為 k 個(gè)初值 實(shí)例：Fibonacci 數(shù)列的遞推方程,定義10.2 常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：,課件,9,常系數(shù)線性齊次遞推方程的公式解法,特征方程、特征根 遞推方程的解與特征根的關(guān)系 解的線性性質(zhì) 無重根下通解的結(jié)構(gòu)

5、 求解實(shí)例 有重根下通解的結(jié)構(gòu) 求解實(shí)例,課件,10,特征方程與特征根,課件,11,遞推方程解與特征根的關(guān)系,定理10.1 設(shè) q 是非零復(fù)數(shù)，則 qn 是遞推方程的解 當(dāng)且僅當(dāng) q 是它的特征根. 證 qn 是遞推方程的解 qn a1qn1 a2qn2 ak qnk = 0 qnk ( qk a1qk1 a2qk2 ak ) = 0 qk a1qk1 a2qk2 ak = 0 q 是它的特征根 注：這里遞推方程指常系數(shù)線性齊次遞推方程,課件,12,解的線性性質(zhì),定理10.2 設(shè) h1(n) 和 h2(n) 是遞推方程的解，c1,c2為任 意常數(shù)，則 c1h1(n)+c2h2(n) 也是這個(gè)遞

6、推方程的解. 證 將 c1h1(n)+c2h2(n) 代入該遞推方程進(jìn)行驗(yàn)證. 推論 若 q1, q2, , qk 是遞推方程的特征根，則 c1q1n + c2q2n + + ckqkn 是該遞推方程的解，其中c1, c2, , ck 是任意常數(shù). 注：這里的遞推方程指的是常系數(shù)線性齊次遞推方程,課件,13,無重根下通解的結(jié)構(gòu),定義10.4 若對(duì)常系數(shù)線性齊次遞推方程的每個(gè)解 h(n) 都 存在一組常數(shù)c1,c2, ck 使得 h(n) = c1q1n+c2q2n+ckqkn 成立，則稱 c1q1n + c2q2n + + ckqkn 為該遞推方程的通解 定理10.3 設(shè)q1, q2, , q

7、k 是常系數(shù)線性齊次遞推方程不等 的特征根，則 H(n)= c1q1n + c2q2n + + ckqkn 為該遞推方程的通解.,課件,14,定理的證明,證： H(n)是解. 設(shè) h(n) 是遞推方程的任意解，h(0), h(1), , h(k1)由初 值 b0, b1, , bk1唯一確定. 代入方程得到方程組,系數(shù)行列式,當(dāng) qi qj 時(shí)，方程組有唯一解,課件,15,求解實(shí)例,例4 Fibonacci 數(shù)列： fn=fn1+fn2 ，特征根為,通解為,代入初值 f0 =1, f1=1, 得,解得,解是,課件,16,有重根下求解中的問題,例5,解 特征方程 x24x+4 = 0 通解 H(

8、n) = c12n + c22n = c2n 代入初值得： c無解. 問題：兩個(gè)解線性相關(guān),課件,17,有重根下的通解結(jié)構(gòu),定理10.4 設(shè) q1, q2, , qt 是遞推方程的不相等的特征根， 且 qi 的重?cái)?shù)為 ei，i=1, 2, , t，令,那么通解,課件,18,求解實(shí)例,例6 求解以下遞推方程,其中待定常數(shù)滿足以下方程組,原方程的解為,解 特征方程 x4+x33x25x2 = 0 , 特征根21,1,2,通解為,課件,19,常系數(shù)線性非齊次遞推方程求解,遞推方程的標(biāo)準(zhǔn)型 通解結(jié)構(gòu) 特解的求法 多項(xiàng)式函數(shù) 指數(shù)函數(shù) 組合形式,課件,20,遞推方程的標(biāo)準(zhǔn)型及通解,課件,21,特解的形式

9、多項(xiàng)式,例7 找出遞推方程 an 2an1 = 2n2 的通解,如果f(n)為n次多項(xiàng)式，則特解一般也是n次多項(xiàng)式,課件,22,實(shí)例,例8 Hanoi塔 T(n) = 2T(n1)+1 T(1)=1 解 令 T*(n) = P 代入方程 P = 2P + 1 解得 P = 1 T(n) = c 2n1, 代入初值得 c=1, 解為 T(n) = 2n 1.,課件,23,例9 求解關(guān)于順序插入排序算法的遞推方程,解 設(shè)特解為W*(n)=P1n+P2，代入遞推方程，得 P1n+P2 ( P1(n1)+P2) = n1 無解. 設(shè)特解W*(n) = P1n2+P2n, 代入遞推方程得 (P1n2+P

10、2n)(P1(n1)2+P2(n1)= n1 解得 P1=1/2, P2= 1/2. 通解為 W(n) = c 1n + n(n1)/2 = c + n(n1)/2 代入初值W(1)=0，得到W(n)= n(n1)/2=O(n2).,實(shí)例(續(xù)),課件,24,特解的形式指數(shù),f(n)為指數(shù)函數(shù) n，若 不是特征根，則特解為 H*(n) = P n 其中P為待定常數(shù). 例10 通信編碼問題 解 an = 6an1 + 8n1, a1=7 設(shè) a*n = P 8n1 , 代入得 P = 4 通解 an = c6n + 48n1 代入初值得 an = (6n+8n)/2,課件,25,特解的形式指數(shù)(續(xù)

11、),若是e重特征根，則特解為Pne n 例11 H(n)5H(n1)+6H(n2) = 2n， 解 令 H*(n)=Pn2n 代入得 Pn2n 5P(n1)2n1 + 6P(n2)2n2 = 2n 解得 P = 2 特解 H*(n) = n2n+1,課件,26,特解的組合形式,例12 an 2an1 = n +3n a0 = 0 解 設(shè)特解為 an* = P1n + P2 + P33n 代入原方程得 (P1n+P2+P33n)2P1(n1)+P2+P33n1 = n +3n 解得 P1 = 1, P2 = 2, P3 = 3 通解 an = c2n n 2 + 3n+1 代入初值得 c = 1

12、， an= 2n n 2 + 3n+1,課件,27,換元法 迭代歸納法遞歸樹 差消法 嘗試法 應(yīng)用實(shí)例,遞推方程的其他解法,課件,28,換元法,思想：通過換元轉(zhuǎn)化成常系數(shù)線性遞推方程,解 令,代入得 bn = 2 bn1 + 1， b0 = 4 解得,例13,an0,課件,29,實(shí)例,解 H(k) = 2 H(k1) + 2k1 H(1) = 1 令 H*(k) = P1k2k + P2 , 解得 P1=P2=1 H*(k) = k2k + 1 通解 H(k) = c 2k + k2k + 1 代入初值得 c = 1 H(k) = 2k + k2k +1 W(n) = n log n n +

13、1,例14 歸并排序,課件,30,迭代歸納法歸并排序,例15,課件,31,迭代歸納法錯(cuò)位排列,例16 Dn = (n1)(Dn1 + Dn2),解：,課件,32,差消法化簡(jiǎn)遞推方程,例17,課件,33,積分近似,課件,34,遞歸樹二分歸并排序,T(n),T(n/2) T(n/2),T(n/4) T(n/4) T(n/4) T(n/4),1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,T(n) = nk (1+2+2k1) = nk (2k 1) = n log n n + 1,課件,35,(1) T(n)=C, 左邊=O(1),嘗試法,例18,(2) T(n)=cn, 左邊=c

14、n,課件,36,嘗試法(續(xù)),(3) T(n)=cn2, 左邊=cn2,(4) T(n)=cnlogn , 左邊=cnlogn,課件,37,積分近似,課件,38,分治策略與遞歸算法,n為輸入規(guī)模，n/b為子問題輸入規(guī)模， a為子問題個(gè)數(shù)，d(n)為分解及綜合的代價(jià),課件,39,分治策略與遞歸算法(續(xù)),(1) d(n)=c,實(shí)例： 二分搜索 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n) = O(logn),課件,40,分治策略與遞歸算法(續(xù)),(2) d(n)=cn,實(shí)例：歸并排序 W(n) = 2W(n/2) + n1 a = 2, b = 2, d(n) = O(n), W(n)= O(nlogn),課件,41,實(shí)例位乘問題,位乘問題：X,Y 為 n 位二進(jìn)制數(shù)，n=2k, 求 XY 一般方法：W(n)= O(n2) 分