算法常用數(shù)學工具_遞歸方程求解

1、第2章 常用數(shù)學工具1. 用生成函數(shù)求解遞歸方程2. 用特征方程求解遞歸方程3. 用遞推方法求解遞歸方程1. 用生成函數(shù)求解遞歸方程1.1 什么是生成函數(shù)1.2 生成函數(shù)的性質(zhì)1.3 用生成函數(shù)求解漢諾塔問題1.4 用生成函數(shù)求解Fabanacci數(shù)列通項1.1 什么是生成函數(shù),.,.,10naaa 010.kkknnzazazaazG對于實數(shù)序列：下面函數(shù)：稱為序列的生成函數(shù)。生成函數(shù)的作用是進行演算，一般不考慮其收斂性。1.2 生成函數(shù)的性質(zhì)v加法v位移v乘法vz變換v微分和積分 0kkkzazG 0kkkzbzH都是生成函數(shù)，則 )(zHzG都是兩個序列加權(quán)合成后的生成函數(shù)1.3 用生成

2、函數(shù)求解漢諾塔問題 111) 1(2hnhnh 132.321kkxkhxhxhxhxG遞推公式：生成函數(shù)： xxxxxxhhxhhxhxGx1.2231221)(213232推導(dǎo)：)21)(1 ()(xxxxG)21)(1 ()2()()21 ()1 ()(xxxBABAxBxAxG求得，A=-1, B=113322323322) 12(.) 12() 12() 12(.)1 (.)2221 ()1 (1)21 (1)(kkkxxxxxxxxxxxxxG1.4 用生成函數(shù)求解Fabanacci數(shù)列通項 1)2(, 11)2() 1(hhnhnhnh 132.321kkxkhxhxhxhxG遞

3、推公式：生成函數(shù)： xxxxhhhxhhhxhhxhxGxx001.234)1 (23121)(124232推導(dǎo)： 25125125125125211222xBxAxxxxxxxxxG解出A和B，可以把G(x)寫成無窮級數(shù)和112512512512512512512511251251251nnnnnnxBxAxxBxAxBxA2. 用特征方程求解遞歸方程2.1 k階常系數(shù)線性齊次遞歸方程2.2 k階常系數(shù)線性齊次遞歸方程舉例（一）2.3 k階常系數(shù)線性齊次遞歸方程舉例（二）2.4 k階常系數(shù)線性齊次遞歸方程舉例（三）重根的情況2.5 k階常系數(shù)線性非齊次遞歸方程2.6 k階常系數(shù)線性非齊次遞歸

4、方程舉例（一）2.7 k階常系數(shù)線性非齊次遞歸方程舉例（二）2.1 k階常系數(shù)線性齊次遞歸方程初始條件)(.)2() 1()(21knfanfanfanfk變換到冪次最低（最后一項是0次冪）得特征方程：kkkkaxaxax.2211若方程有k個不同不同的根q1, ,qk，則遞歸方程的通解為：nkknnqcqcqcnf.)(2211若特征方程有t個不等的根q1, q2, , qt, 且qi的重數(shù)為ei, 那么令nieieiiiqncnccnfii121.)(那么遞推方程的通解是 niinfnf1)(2.2 k階常系數(shù)線性齊次遞歸方程舉例（一）5) 1 () 1(3)(fnfnf3x齊次遞推方程：

5、得到一元方程：3x該方程只有一個解：ncnf3)(遞推方程的帶參數(shù)的通解為：由于f(1)=5，因此c=5/3，所以，問題的通解為：nnf335)(2.3 k階常系數(shù)線性齊次遞歸方程舉例（二） 32, 112) 1()(ffnfnfnf012 xx齊次遞推方程：得到一元二次特征方程：251,251xx該方程兩個解：nnccnf251251)(21遞推方程的帶參數(shù)的通解為：由于f(1)=1, f(2)=3，因此325325312512512121cccc由于行列式02253253251251325325312512512121cccc而(1, 1)是方程*的解，因此原方程的通項是nnnf25125

6、1)(2.4 k階常系數(shù)線性齊次遞歸方程舉例（三）重根的情況0)2(, 0) 1 (, 5)0(0)3-(4) 1(3-)(fffnfnfnf043-23xx齊次遞推方程：得到一元特征方程：2 , 2 ,-1x特征根：nncnccnf) 1(-2)()(321遞推方程的帶參通解為：待定系數(shù)的線性方程組的解是：c1=5/9, c2=-1/3, c3=4/90840-22132132131cccccccc nnnnnf1-94231-295)(通解：2.5 k階常系數(shù)線性非齊次遞歸方程初始條件)()(.)2() 1()(21ngknfanfanfanfk通解為：)()()(*nfnfnf即齊次通解

7、+特解確定特解的任務(wù)就成為關(guān)鍵。根據(jù)齊次特征方程根的情況，特解可以分為兩種情況：l沒有等于1的特征根：特解的多項式次數(shù)與g(n)相同；l含有等于1的特征根：特解的多項式次數(shù)比g(n)大1，但不含常數(shù)項。2.6 k階常系數(shù)線性非齊次遞歸方程舉例（一）3)2(, 1) 1 (1) 1(2)(ffnfnf非齊次遞推方程：齊次方程的解為：ncnf2)(1特解為：2*)(cnf帶參數(shù)的通解為：212)(ccnfn帶入初始條件得通解為：12)(nnf2.7 k階常系數(shù)線性非齊次遞歸方程舉例（二）1) 1 (1) 1()(fnnfnf非齊次遞推方程：齊次方程的解為：ncnf1)(1特解為：ncncnf322

8、*)(帶入特解：1) 1-() 1-()(322322n-ncncncnc解得：21-,2132cc這是順序插入算法的復(fù)雜度注意特解形式！通解為：12)/1-()(cnnnf帶入求解通解為：12)/1-()(nnnf3. 用遞推方法求解遞歸方程3.1 求平方和序列的通解3.2 用遞推方法求漢諾塔問題的復(fù)雜度3.1 求平方和序列的通解11*31*31212*32*323.1) 1(3) 1(3) 1(133) 1(233233233233nnnnnnnn2222.321)(nnf求解析通解：3131) 1()(113nknkknnf3.2 用遞推方法求漢諾塔問題的復(fù)雜度1) 1 (1) 1(2)(fnfnf1) 1 (2)2(1)2(2) 3(.1)2(2) 1(1) 1(2)(fff