算法-求解递归方程地方法

1、实用标准文案文档第二章常用的数学工具2.2用生成函数求解递归方程生成函数及其性质一、生成函数的定义定义2.1令aoa,a2,A是一个实数序列，构造如下的函数：Q02一 kG (z) =ao +az+a2z +A =Z akz(2.2.1 )k =0则函数G(z)称为序列ao,ai,a2,A的生成函数。例：函数n o 0 八1 八22 八n n(1 X ) C n CnX CnX CnX则函数(1+x)n便是序列CLCn.CnA.Cn的生成函数。二、生成函数的性质qQ.加法 设G(z) =E akzk是序列a0,a1 ,a2 ,A的生成函数， k=0QOH(z)=Z bkzk 是序列 bo,b1

2、，b2 ,A 的生成函数,则 aG(z) + 0H(z) k =0oOcOgG (z)，PH (z) = akzk - P： bkzkk=0k=0oO苞(aak +Bbk)zk(2.2.2 )k =0是序列 aao +Pb0 ,aai +Pbi , a a2 +Pb2 ,A 的生成函数。 od.移位 设G(z)苞akzk是序列a0,ai,a2,A的生成函数，则 k=0zmG(z)COzmG(z) = afzk(2.2.3 )k z=m是序列0,A ,0 ,ao, ai色,A的生成函数。qQ.乘法 设G(z)= akzk是序列a0,ai,a2,A的生成函数， k=0cO TOC o 1-5 h

3、z H(z)= bkzk 是序列 b0,bi,b2,A 的生成函数，则 G(z) H (z) k田 ,2.2.G(z) H (z) =( a0 , az a?z ,)(b0 , bz , b?z ) 2.=a0b0 ( a0bi 也。)z-(a0b2 aibi-a2b0)z;qQ= Ckzk(2.2.4 )k f n 是序列C0 ,Ci, C2 ,A的生成函数，其中，Cn = akbnA k 0QO. z 变换 设G(z)= akzk是序列a0,ai,a2,A的生成函数，则 k=0G(cz)23G(cz)=a0 ai( c z) a2 (cz)a3(cz) ,=a0+ca1z+c2a2z2 +

4、c3a3 z3+A (2.2.5 ) 是序列ao ,cai , d ,A 的生成函数。特别地，有：-=1+cz+c2z2 +c3z3 +A(2.2.6 )1 -c z所以，是序列1,c,c2,c3,A的生成函数。-cz当c=1时，有：=1 +z +z2 +A(2.2.7 )-z则一是序列1,1,1,的生成函数。z利用：1-(G ( z) +G ( -z) =a0 +a2z2 +a4z4 +A (2.2.8 )可以去掉级数中的奇数项；同样，利用1-(G (z) G( z) =a1z+a3z +asz +A (2.2.9 )可以去掉级数中的偶数项。5.微分和积分 设G(z)= akzk是序列a0

5、,a1 , a2 ,A的生成函数, k =0对G(z)求导数QOG ( z) =a1 +2 a2z +3 a3z2 +A =E (k+1)ak+zk(2.2.10)k =0显然，G(z)是序列a1，2a2,3a3,A的生成函数。同样，对G(z)求积分z(2.2.11 )G(t)dt 二a0z 1alz2 -a2z3 上akzk023kJz则积分G(t)dt是ao，1ai ,1a2 ,A的生成函数。 230如果对(2.2.7 )式求导数，可得：1 =1 +2z+3z2 +A = (k+1) zk(2.2.12 )(I -z)2k则可是算术级数1,2,3的生成函数。(1 -z)2如果对(2.2.7

6、 )式求积分，可得：OQln =z+1z2 +1z3+A =Z 1zk(2.2.13)-z23kJ则ln，是调和数1,1 J,A的生成函数。1 -z2 32.2.2用生成函数求解递归方程例2.1 汉诺塔(Hanoi)问题。宝石针的编号为a、b、c, A针用着64片金盘。希望把它们移 到B针或C针。有可n是金盘的数量，h(n)是移动n个金盘的移动次数.当 n=1 时，h(1)=1。.当 n =2时， h(2) =2h(1)+1。.当 n =3时， h(3) =2h(2) +1。递归关系式：(2.2.14 )h(n) =2h(n-1) 1 h(1) =1用h(n)作为系数，构造一个生成函数：_23

7、.G(x) =h(1)x h(2)x2 h(3)x3 一；0CiC h(k)xkk=1 TOC o 1-5 h z 令 _2323G(x) -2xG(x)=h(1)x h(2)xh(3)x 七、-2h(1)x -2h(2)x -上23= h(1)x (h(2)-2h(1)x2 (h(3) -2h(2)x3 二由(2.2.14 )及(2.2.7 )式得:_23(1 -2x)G (x) =x x xx1 -x所以,令：有：G(x)x(1 -x)(1 -2x)、 A BG (x)二(1 -x) (1 -2x)A-2Ax B -Bx(1 -x)(1 -2x)A B =0-2 A-B =1求得A=_1,

8、B=1。所以:G(x)=(1 -2x)(1 -x)二(1 2x 22 x2 23x3)(1 x x2 x3 上)2233.=(2 -1) x (2 -1)x(2 -1)x,C(2k -1)xkk=1h(n)=2n-1,它是式中第n项的系数。当n=64时，移动次数为264 -1。 例2.2 菲波那契序列问题。t(n)、T(n)、f (n)表示第n个月小兔子、大兔子的数目，及第n个月兔子的总数目。则：(2.2.15 )(2.2.16 )(2.2.17 )T(n)=T(n 一1)t(n1)t(n) =T(n1) f(n)=T(n) t(n)第一式：第n个月大兔子的数量，为前一个月大兔子的数量加上前

9、一个月小兔子的数量；第二式：第n个月小兔子的数量，为前一个 月大兔子的数量；第三式：表示第n个月兔子的总量为该月大兔子的数量及小兔子的 数量之和。递归方程：(2.2.18 )f (n) =f (n -1) - f(n -2) f =f(2) =1用f(n)作为系数，构造生成函数： TOC o 1-5 h z 23F (x)=f (1)x , f (2)x , f (3)x. J：.令：2F ( x ) f F (x) x F (x)23 .22.= f(1)x f (2)x2 - f (3)x3 六. 一x( f (1)x f (2)x2 上) x2(f (1)x -上)23.=f(1)x (

10、 f(2)f (1)x2 - ( f (3) - f (2) - f (1) )x3 上二所以，有:x 2(1-, 5 x -1(1 . 5 TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document -1-x (15) x (1,5),2Ax -1(1 , 5) A Bx -1(1 - . 5)Bx -(1 - 5 x - - (1 - , 522有：A B - -1, (1 5) A (1 , 5)B =0解得:1-A :(1 一，. 5), 2:5B ： 1 (1 . 5)2/5把A、B代入F(x),得到:1F(x) 一 .52 x +1

11、 7r5 2 x +1 +小，则有：F (x)=(a _P)x +(c(2 p2 )x2 4AA ,5所以，第n项系数为：f(n)=3n).52.3用特征方程求解递归方程k阶常系数线性齐次递归方程、k阶常系数线性齐次递归方程1、递归方程的形式：(2.3.1 )f(n) =a1f(n -1)，a2 f (n -2)二 上. ak f (n -k )0 i kf(i) =bi2、递归方程的特征方程xn 取代 f (n)：nn 1n _2.n _kx =axa?x _ i ak x两边分别除以xn”，可得：kk 1kN,x = axzx-ak把上式写成：kk 1k -2x a x a2xA ak 0

12、(2.3.2 )则式(2.3.2 )称为递归方程(2.3.1 )的特征方程。二、k阶常系数线性齐次递归方程的求解1、q1,q2 ,A ,qk是特征方程的k个互不相同的根。则递归方程(2.3.1 )的通解为：f (n) =C1q； +c2qn +A+ckqn(2.3.3 )2、特征方程的k个根中有r个重根qi , qi书,A , qi十二，递归方程 (2.3.1 )的通解形式为：f (n) =C1q； +A+Ciqn十(Ci +g由n七、十白十二nr)qn+A +ckqn(2.3.4 )在(2.3.3 )及(2.3.4 )中，c1,C2,A,Ck为待定系数。3、求解过程：把递归方程的初始条件代入

13、(2.3.3 )或(2.3.4 ) 中，建立联立方程，确定系数a,C2,A,Ck,从而可求出通解f(n) o例2.3三阶常系数线性齐次递归方程如下：% (n) =6f (n1)11 f(n-2)+ 6f (n -3)J(0)=0f(1)=2f(2)=10解特征方程为：x3 -6x2 11x-6 =0把方程改写成：322x3 -3x2 -3x2 9x 2x -6 =0对特征方程进行因式分解，得：(x-1)(x-2)(x-3) =0则有特征根：q =1q2 =2 q3 =3所以，递归方程的通解为：nnnf (n) =c1q1 C2q2 - C3q3=c1 , c22n - c33n由初始条件得：f

14、 (0) =C1 C2 C3 =0f(1) =C1 2c2 3C3 =2f (2) =C1 4c2 9C3 =10解此联立方程，得：c1 = 0c2 = -2c3 = 2则递归方程的解为：f (n) =2(3n -2n)例2.4三阶常系数线性齐次递归方程如下：；f (n) =5f (n -1) -7f (n-2)+3f(n-3)、f(0) =1f (1) =2f (2) =7解特征方程为:32x -5 x 7 x -3=0把特征方程改写成:32x -5 x 6x x-3=0进行因式分解:2(x -3) ( x -2 x , 1) = 0最后得:(x -1)(x-1)(x-3) =0求得特征方程

15、的根为:q1 -1 q2 -1 q3 =3所以，递归方程的通解为:f (n) =(C1 C2 n) q1n - C3 qnn=C1 C2 n C3 3代入初始条件:f ( 0) = Ci C3 = 1f (1) =C1 C2 3C3 =2f(2) =c12c2 9C3 =7解此联立方程，得:C=0 C2=-1C3 1则递归方程的解为:f (n) =(g C2 n) q； C3 q3nn=3 -n2.3.2 k阶常系数线性非齐次递归方程、k阶常系数线性非齐次递归方程1、递归方程的形式：(2.3.5 )f (n) =ai f (n -1) , a2 f (n -2):二,二:ak f (nk )

16、, g (n)f (i) =bi0 _i :：: k2、通解形式：f (n) = f(n)，f*(n)其中，币5是对应齐次递归方程的通解，f*(n)是原非齐次递归方程 的特解。3、特解的求取g(n)是n的m次多项式，即g (n) =b1nm +b2nm,十A+bmn+bm4(2.3.6)其中，bi , i =1,2,A ,m+1是常数。特解f * ( n)也是n的m次多项式：f *( n) =A1nm+A2nm，+A+Amn+Am由(2.3.7)其中，Ai ,i =1,2,A,m+1为待定系数。g(n)是如下形式的指数函数：g (n) =(b1nm+b2nm十 +bmn+bm书)an(2.3.

17、8 )其中，a、bi , i =1,2,A ,m+1 为常数。a不是特征方程的重根，特解f*(n)为：f *(n) =( A1nm +A2nm二 十A 十Amn +Am4)an(2.3.9 )其中，Ai ,i =1,2,A,m+1为待定系数。a是特征方程的r重特征根，特解的形式为：f * (n) =(A1nm +A2nm,+A + Amn+Am) nran ( 2.3.10 )其中，Ai ,i =1,2,A,r +1是待定系数。例2.5二阶常系数线性非齐次递归方程如下：-，、-一，、-，、2f (n) =7f (n _1) _10f (n _2) +4n2f (0)=1f(1)=2解对应的齐次

18、递归方程的特征方程为：2_x -7x 10 =0把此方程转换为：(x-2)(x-5) =0得到特征根为：q1 =2q2 = 5所以，对应的齐次递归方程的通解为： 八 nnf ( n) =ci2 C2 5令非齐次递归方程的特解为：f * ( n ) = A1n2 A 2 n A3代入原递归方程，得：A1n2 A2n A3 -7(A1(n -1)2 A2(n -1) A3) 10(A1(n-2)2 A2( n -2) - A3) 4n2化简后得到：4A1n2 ( -26A1 4A2)n 33Al -13A2 - 4A3 =4n2由此，得到联立方程：4A1 =4-26A1 4A2 =033A1 -

19、13A2 4A3 =0解此联立方程，可得： TOC o 1-5 h z 7A1 =1A2 =6A3 =12 8所以，非齐次递归方程的通解为：f ( n) =c12n c25n n2 6 n 1228把初始条件代入，有:解此联立方程，得:f(0) ” C2 127 =183 f (1)=2g 5c2 20- =28ci = -132 3C2=1生24最后，非齐次递归方程的通解为：2 n 19 n 217f ( n) = -13 2 1 5 n 之 6 n 12 32428例2.6二阶常系数线性非齐次递归方程如下：f (n) =7f (n 一1) -12f (n -2) - n2nf (0) =1

20、f (1) =2解对应齐次递归方程的特征方程为：x2 -7x 12 =0此方程可改写成：(x-3)(x-4) =0所以，方程的解为：q =3q2 =4齐次递归方程的通解为：f(n)=c13n c2 4n令非齐次递归方程的特解为：f *(n) =( A1n A2) 2n把特解代入原非齐次递归方程，得：(A1n - A2) 2n -7(A1( n -1) A2)2n，12 ( A1(n -2) A2)2n =n2n整理得：2 A1n - 2 A2 -10A1 =4 n可得联立方程：2Ai =42A2 -10Ai =0解此联立方程得：Ai =2A2 =10所以，非齐次递归方程的通解为：f(n) =c

21、13n c24n 口门 . 10)2n用初始条件代入：f(0)=ci C2 10=1f (1) =3C1 4 c2 24 =2解此联立方程得：c1 - -14c2 = 5最后，非齐次递归方程的解为：f( n) = 14 3n 5 4n (2n 10)2n-14 3n 5 4n - (n - 5) 2n 1解方程步骤归纳(1)求齐次方程的解但系数项待定(2)确定特解 将特解带入原方程，确定各系数(3)确定通解，由给定的初值确定确定齐次方程的未定系数。2.4用递推方法求解递归方程2.4.1 递推非齐次递归方程：(2.4.1 ):f (n) =b f (n -1) +g (n) f (0) =c其中

22、，b、c是常数，g(n)是n的某一个函数。直接把公式应用于式中 的f (n _1),得到：f ( n) =b(b f (n -2) g(n -1) g (n)2=b f(n2) bg(n-1) g(n)2=b ( b f( n -3) g ( n -2) b g (n -1) g (n) 32=b f(n-3).b g(n-2)bg(n-1)-g(n)=A A A A=bn f (0) , bn,g (1)，b2g (n-2) - bg ( n -1) - g ( n)n=cbn + bng(i)(2.4.2 )i 1例2.7 汉诺塔问题。由(2.2.14 ),汉诺塔的递归方程为：:h(n)

23、=2h(n -1)土、h(1) =1直接利用(2.4.2 )式于汉诺塔的递归方程。此时，b =2c =1 g (n) =1从n递推到1,有：n 4h (n) =cbni.二 bn*g(i)i 1=2n4 2T gA +22 2 1(2.4.3 )(2.4.4 )(2.4.5 )(2.4.5 )式对 f (n)进2.4.2用递推法求解变系数递归方程一、变系数齐次递归方程：:f(n) =g(n)f(n 1)J(0) =c利用递推方法，容易得到：f(n)=cg(n)g(n1)上 g(1)例2.8解如下递归函数：f(n)=nf(n-1):f (0)=1由(2.4.4 )式，容易得到：f (n) =n(

24、n -1)(n -2). 1二n!二、变系数非齐次递归方程：f (n) =g (n) f ( n -1) +h( n) =J(0) =c其中，C是常数，g( n)和h( n)是n的函数。利用行递推，有：f(n) =g(n)f(n-1) h(n)= g(n)(g(n-1)f(n -2) h(n -1) h(n)=g (n) g( n -1)f( n -2) g ( n)h(n -1) h(n)=AAAA= g(n)g(n -1). g(1)f (0) g(n)g(n -1)上 g(2)h(1)上g(n)h(n-1) h(n)g (n) g (n T)上 g (2) g (1)h (1)= g(n

25、)g(n -1). g(1)f(0) g( )g(_) ,? )g( ) ( ) 二 g(1)g(n)g(n-1)上 g(2) g(1)h(n-1) g(n)g(n -1)上 g(2)g(1)h(n)g(n -1)上 g(2)g(1)g(n)g(n-1). g(2)g(1)h(i)g(i)g(i-1)Ag(1)，(2.4.6 )n=g(n)g(n1)Ag(1) f(0)+ I y例2.9解如下的递归函数：f(n)=n f(n-1)+n!J(0) =0对方程进行递推，有：f(n)=n(n-1)f(n-2) (n-1)!) n!=n (n -1) f (n -2) 2 n!=A A A A=n!

26、f (0)，n n!=n n!如果直接使用公式(2.4.6 ),此时，g (n) =n , h(n) =n!,有: i !f (n) =n(n-1)上,f(0)=01i (i -1)一； 1=n n!得到同样结果。例2.10解如下的递归方程f (n) =2 f ( n 1) +nJ(0) =0解 对方程进行递推，有：f (n)=2(2f (n-2) (n-1) n2=2 f ( n -2) , 2 (n -1) n=AAAAnnn _20=2 f (0) 222 - 2 nn_16 2i(n_i)i =0i2in=2ni 1由公式(2.1.24 ),得n n 2 n 1f (n) =2 2=2-n -22如果直接使用公式(2.4.6 ),此时，g(n)=2,h(n)=n ,同样有:一 n i 一,f (n) =2n