chap递推关系举例、fibonacci数列

1、chap递推关系举例、fibonacci数列 例例1 1 Hanoi塔塔问题：问题：这是组合数学中的一 个著名问题。n个圆盘依其半径大小，从 下而上套在A柱上。每次只允许取一个移 到柱B或C上，而且不允许大盘放在小盘 上方。若要求把柱A上的n个盘移到C柱上, 请设计一种方法并估计要移动几个盘次。 现在只有A、B、C三根柱子可用。 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 Hanoi问题是个典型的组合问题,第一步要设计 算法，进而估计它的复杂性，即估计工作量。 A B C 2.6 2.6 递推关系递推关系 算法：算法：n=2时 第一步先把最上面的一个圆盘套在

2、B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕 chap递推关系举例、fibonacci数列 对于一般n个圆盘的问题， w 假定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 A B C 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 上述算法是递归的运用。n=2时已给出 算法；n=3时，第一步便利用算法把上面 两个盘移到B上，第二步再把第三个圆盘 转移到柱C上；最后把柱B上两个圆盘转 移到柱C上。n=4，5，依此类推。 2.6

3、 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 算法分析：算法分析：令h(n)表示n个圆盘所需要 的转移盘次。根据算法先把前面n-1个盘 子转移到B上；然后把第n个盘子转到C上； 最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法 是对的。依此类推。于是有 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 算法复杂度为： ( )2 (1)1, (1)1 (a)h nh nh ,)3()2() 1 ()( 32 xhxhxhxH H(x)是序列h(1),h(2),h(3) 的母函数。给定了 序列，对应的母函

4、数也确定了。反过来也一样， 求得了母函数，对应的序列也就可得而知了。 当然，利用递推关系(a)式也可以依次求得 h(1),h(2),h(3) ，这样的连锁反应关系，叫做递递 推关系推关系。 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 下面介绍如何从(a)式求得母函数H(x)的一种形 式算法。所谓形式算法说的是假定这些幂级数 在作四则运算时，一如有限项的代数式一样。 ,)3()2() 1 ()( 32 xhxhxhxH 23 ) 2( ) -2 (1)2 (2),xH xhxhx _ 3 2 )2(2)3( )1 (2)2() 1 ()()21 ( xhh x

5、hhxhxHx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 根据(a)， , 1)2(2)3(, 1) 1 (2)2(, 1) 1 ( hhhhh )1/()()21 ( 32 xxxxxxHx 或利用递推关系(a)有 1) 1 (2)2(: 2 hhx 1)2(2)3(: 3 hhx ) _ )1/()(2)( 2 xxxxHxxH 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 整理得 2 (12 )( ) 11 xx x H xx xx )21)(1 ( )( xx x xH 这两种做法得到的结果是一样的。即： 2.6

6、2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 令 (1 2 )(1) ( ) 11 2(1)(1 2 ) () (2) (1)(1 2 ) ABAxBx H x xxxx AB -AB x xx xxBABA)2()( 如何从母函数得到序列 h(1),h(2),h(3) ？ 下面介绍一种化为部分分数的算法。 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 由上式可得： . 1 , 1BA 即： 12BA 0 BA 22332 2233 1 11 ( ) 121 (1222)(1) (21)(21)(21) (21) kk k H x x

7、x xxxxx xxx x 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 因为： 1 )()( k k xkhxH 12)( k kh 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 例例2. 求n位十进制数中出现偶数个5的数的 个数。 解:先从分析n位十进制数出现偶数个5的数 的结构入手,p1p2pn-1 是n-1位十进制数， 若含有偶数个5，则pn 取5以外的 0,1,2,3,4,6,7,8,9 九个数中的一个，若 p1p2pn-1只有奇数个5，则取pn=5，使 p1p2pn-1 pn成为出现偶数个5的十进制数。 2.6 2

8、.6 递推关系递推关系 chap递推关系举例、fibonacci数列 解法解法1： 令 an= n位十进制数中出现偶数个5的数的个数， bn= n位十进制数中出现奇数个5的数的个数。 有： 11 9 nnn baa 11 9 nnn abb 且 11 8, 1 (b) ab 2.6 2.6 递推关系递推关系 (b)是关于序列an和bn的联立关系。 chap递推关系举例、fibonacci数列 设序列an 的母函数为A(x)，序列bn 的母函数为B(x) 。 2 123 2 12 2 12 ( ) 9( )99 ) ( ) A xaa xa x xA xa xa x xB xb xb x 则有

9、_ 8)()()91 (xxBxAx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 ) 9 : 9 : 9 : 334 3 223 2 112 baax baax baax _ )()(98)(xxBxxAxA 8)()()91 ( xxBxAx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 又： _ 1)()()91 (xxAxBx 故得关于母函数A(x)和B(x)的联立方程组： 1)()91 ()( 8)()()91 ( xBxxxA xxBxAx 2 123 2 12 2 12 ( ) 9( )99 ) ( ) B xb

10、b xb x xB xb xb x xA xa xa x 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 x x x x D 91 91 22 (19 )xx 2 80181xx )101)(81 (xx )101)(81 ( 871 91 1 8 80181 1 )( 2 xx x x x xx xA )101)(81 ( 1 1 8 91 )101)(81 ( 1 )( xx x x x xx xB 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 0 )10987( 2 1 ) 101 9 81 7 ( 2 1 )( k kk

11、k x xx xA 11 10 2 9 8 2 7 kk k a 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 解法二：解法二： n-1位的十进制数的全体共 ,从中 去掉含有偶数个5的数，余下的便是n-1位 中含有奇数个5的数。故有： 2 109 n 1 2 1 11 109 9 n n n nnn ab baa 8 ,1098 1 2 1 aaa n nn 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 令 2 21 2 321 88)(8 ) )( xaxaxxA xaxaaxA _ 2 2312 )8()8(8)()81

12、(xaaxaaxAx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 x x x x xxxAx 101 718 101 9 8 10998)()81 ( 2 0 )10987( 2 1 ) 101 9 81 7 ( 2 1 )101)(101 ( 718 )( k kkk x xxxx x xA 11 79 810 22 kk k a 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 表示，其结果可能有以下两种情况。 n aaa, 21 例例3：从n个元素中取r个进行允许重复 ),(rnC的组合。假定允许重复的组合数用 1) 1)

13、 不出现某特定元素设为a1，其组合数为 ), 1(rnC n aa, 2 ,相当于排除a1后从 中取r个做允许重复的组合。 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 2）至少出现一个 a1 ，取组合数为 相当于从 中取r-1个做允许重复的组合 然后再加上一个a1得从n个元素中取r个允许重复 的组合。 ) 1,(rnC n aaa, 21 依据加法原则可得： (1)( , )( ,1)(1, )C n rC n rC nr 1) 1 , 1(,) 1 ,(nnCnnC 因 1)0 ,(nC 故令 2.6 2.6 递推关系递推关系 chap递推关系举例、fib

14、onacci数列 递推关系(1)带有两个参数n和r。 2 2 1 ( )( ,0)( ,1)( ,2) ( ) ( ,0)( ,1) ) ( )(1,0)(1,1) n n n G xC nC nxC nx xG xC nxC nx GxC nC nx _ 1 (1)( )( )0 (2) nn x GxGx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 (2)式是关于Gn(x) 的递推关系，但系数 (1-x) 不 是常数。 x xx xCxCCxG 1 1 1 )2 , 1 () 1 , 1 ()0 , 1 ()( 2 2 1 12 2 1 -1 11 (

15、)( )( ) 1(1) 11 ( ) (1- )(1- ) nnn nn G xGxGx xx G x xx 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 由二项式定理 23 (1) (1)(1)(2) 1 2!3! n x n nn nn nxxx 可得 ), 1( )!1( )!1( ! ) 1() 1( ),( rrnC n rn r rnnn rnC 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 Fibonacci数列是递推关系的又一个典型问题， 数列的本身有着许多应用。 问题：问题：有雌雄兔子一对，假定过两月便可繁

16、殖 雌雄各一的一对小兔。问过了n个月后共有多少 对兔子？ 设满n个月时兔子对数为 Fn其中当月新生兔数目设 为Nn 对。第n-1个月留下的兔子数目设为On 对。 nnn ONF 2.6 2.6 递推关系递推关系- -FibonacciFibonacci数列数列 chap递推关系举例、fibonacci数列 但 211 , nnnnn FONFO 即第n-2个月所产的兔子到第n个月都有繁殖能力了. 1212 , 1 (1) nnn FFFFF 由递推关系(1)式可依次得到 , 523 , 3 , 2 435 324213 FFF FFFFFF 2.6 2.6 递推关系递推关系 chap递推关系举

17、例、fibonacci数列 2 21 )(xFxFxG ) : : 234 4 123 3 FFFx FFFx _ )()()( 22 xGxxxGxxxxG xxGxx)()1 ( 2 设 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 x B x A xx x xx x xG 2 51 1 2 51 1 ) 2 51 1)( 2 51 1 ( 1 )( 2 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 1)( 2 5 0 BA BA 5 2 0 BA BA 5 1 , 5 1 BA 2.6 2.6 递推关系递推关系 chap

18、递推关系举例、fibonacci数列 )()( 5 1 2 51 1 1 2 51 1 1 5 1 )( 222 xx xx xG () 5 nn n F 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 其中 2 51 51 2 , 2 51 51 2 111515 ()()() ) (2) 2255 nnnn n F 618. 1 2 51 1 n n F F 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 w 趣味结论趣味结论 =2 1Fibonacci = 0 1 0 1 ( ) , , n in i iii N Ns F ss s 任意正整数 可以表示为序列的有 限和： 2 1 ( ) n ii FibonacciF FF 方形，即边长为的正方形 可以分解为若干边长为和的矩形的和 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 122 1) 1 nn FFFF 证明：证明： 12 11 342 231 ) nnn nnn FFF FFF FFF FFF _ 12222 1 nnn FFFFFF 2.6 2.6 递推关系递推关系 chap递推关系举例、fibonacci数列 135212 2) nn FFFFF 证明：证明：