chap23递推关系举例、fibonacci数列

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

2、定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 A B C 2.6 2.6 递推关系递推关系4 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。n=4，5，依此类推。 2.6 2.6 递推关系递推关系5 算法分析：算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算

3、法是对的，因此，n=3是算法是对的。依此类推。于是有 2.6 2.6 递推关系递推关系6算法复杂度为：( )2 (1)1, (1)1 (a)h nh nh,)3()2() 1 ()(32xhxhxhxH H(x)是序列h(1),h(2),h(3) 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。 当然，利用递推关系(a)式也可以依次求得h(1),h(2),h(3) ，这样的连锁反应关系，叫做递递推关系推关系。2.6 2.6 递推关系递推关系7 下面介绍如何从(a)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时

4、，一如有限项的代数式一样。,)3()2() 1 ()(32xhxhxhxH23) 2( ) -2 (1)2 (2),xH xhxhx_32)2(2)3( )1 (2)2() 1 ()()21 (xhhxhhxhxHx2.6 2.6 递推关系递推关系8 根据(a)，, 1)2(2)3(, 1) 1 (2)2(, 1) 1 ( hhhhh)1/()()21 ( 32xxxxxxHx 或利用递推关系(a)有1) 1 (2)2(:2 hhx1)2(2)3(:3 hhx )_)1/()(2)( 2xxxxHxxH2.6 2.6 递推关系递推关系9 整理得2(12 )( )11xxx H xxxx)21)

5、(1 ()(xxxxH 这两种做法得到的结果是一样的。即： 2.6 2.6 递推关系递推关系10 令(1 2 )(1)( )11 2(1)(1 2 )() (2) (1)(1 2 )ABAxBxH xxxxxAB -AB xxxxxBABA)2()( 如何从母函数得到序列 h(1),h(2),h(3) ？下面介绍一种化为部分分数的算法。2.6 2.6 递推关系递推关系11 由上式可得：. 1 , 1BA 即：12BA0 BA223322233111( )121 (1222)(1) (21)(21)(21) (21)kkkH xxxxxxxxxxxx2.6 2.6 递推关系递推关系12因为：1)

6、()(kkxkhxH12)( kkh2.6 2.6 递推关系递推关系13 例例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.6 递推关系递推关系14 解法解法1：令 an= n位十进制数中出现偶数个5的数的个数， bn= n位十进制数中出现奇数个5的数的个数。 有：119nnnbaa119nnnabb且118,

7、 1 (b)ab2.6 2.6 递推关系递推关系 (b)是关于序列an和bn的联立关系。15设序列an 的母函数为A(x)，序列bn的母函数为B(x) 。2123212212 ( ) 9( )99) ( ) A xaa xa xxA xa xa xxB xb xb x则有_8)()()91 (xxBxAx 2.6 2.6 递推关系递推关系16 )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(xxBxxAxA8)()()91 ( xxBxAx 2.6 2.6 递推关系递推关系17 又：_1)()()91 (xxAxBx故得关于母函数A(x)和B(x)的联

8、立方程组：1)()91 ()(8)()()91 (xBxxxAxxBxAx2123212212( )9( )99) ( ) B xbb xb xxB xb xb xxA xa xa x 2.6 2.6 递推关系递推关系18xxxxD91 91 22(19 )xx280181xx)101)(81 (xx)101)(81 (87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB 2.6 2.6 递推关系递推关系190)10987(21)1019817(21)( kkkkxxxxA111029827 kkka 2.6 2.6

9、递推关系递推关系20 解法二：解法二： n-1位的十进制数的全体共 ,从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有： 2109n121111099nnnnnnabbaa8 ,1098 121aaannn 2.6 2.6 递推关系递推关系21令221232188)(8 )(xaxaxxAxaxaaxA_22312)8()8(8)()81 (xaaxaaxAx 2.6 2.6 递推关系递推关系22xxxxxxxAx10171810198 10998)()81 ( 20)10987(21 )1019817(21)101)(101 (718)( kkkkxxxxxxxA1179

10、 81022kkka 2.6 2.6 递推关系递推关系23表示，其结果可能有以下两种情况。 naaa,21例例3：从n个元素中取r个进行允许重复),(rnC的组合。假定允许重复的组合数用1) 1) 不出现某特定元素设为a1，其组合数为), 1(rnCnaa,2,相当于排除a1后从中取r个做允许重复的组合。 2.6 2.6 递推关系递推关系24 2）至少出现一个 a1 ，取组合数为 相当于从 中取r-1个做允许重复的组合然后再加上一个a1得从n个元素中取r个允许重复的组合。) 1,(rnCnaaa,21依据加法原则可得： (1)( , )( ,1)(1, )C n rC n rC nr1) 1

11、, 1(,) 1 ,(nnCnnC因1)0 ,(nC故令 2.6 2.6 递推关系递推关系25 递推关系(1)带有两个参数n和r。221( )( ,0)( ,1)( ,2)( ) ( ,0)( ,1) ( )(1,0)(1,1) nnnG xC nC nxC nxxG xC nxC nxGxC nC nx_1(1)( )( )0 (2)nnx GxGx 2.6 2.6 递推关系递推关系26 (2)式是关于Gn(x) 的递推关系，但系数 (1-x) 不是常数。xxxxCxCCxG111 )2 , 1 () 1 , 1 ()0 , 1 ()( 2211221-111 ( )( )( )1(1)11

12、 ( )(1- )(1- )nnnnnG xGxGxxxG xxx 2.6 2.6 递推关系递推关系27由二项式定理23(1)(1)(1)(2)12!3! nxn nn nnnxxx 可得), 1( )!1()!1(!) 1() 1(),(rrnCnrnrrnnnrnC 2.6 2.6 递推关系递推关系28 Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。问题：问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为On 对。nnnONF 2.6

13、 2.6 递推关系递推关系- -FibonacciFibonacci数列数列29 但211 , nnnnnFONFO即第n-2个月所产的兔子到第n个月都有繁殖能力了.1212 , 1 (1)nnnFFFFF由递推关系(1)式可依次得到 , 523 , 3 , 2 435324213FFFFFFFFF 2.6 2.6 递推关系递推关系30221)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 设 2.6 2.6 递推关系递推关系31xBxAxxxxxxxG25112511 )2511)(2511 (1)( 2 2.6

14、2.6 递推关系递推关系321)(250BABA520BABA51 , 51BA 2.6 2.6 递推关系递推关系33)()(51 251112511151)( 222xxxxxG() 5nnnF 2.6 2.6 递推关系递推关系34其中251512 ,251512111515()()() ) (2)2255nnnnnF618. 12511nnFF 2.6 2.6 递推关系递推关系35w 趣味结论趣味结论=21Fibonacci = 0 1 01( ) , ,niniiiiNNs Fss s任意正整数 可以表示为序列的有限和：21( )niiFibonacciFFF方形，即边长为的正方形可以分

15、解为若干边长为和的矩形的和 2.6 2.6 递推关系递推关系361221) 1 nnFFFF 证明：证明：1211342231 )nnnnnnFFFFFFFFFFFF_ 122221nnnFFFFFF 2.6 2.6 递推关系递推关系371352122) nnFFFFF 证明：证明：2221246524321 )nnnFFFFFFFFFFF_nnFFFFF212531 2.6 2.6 递推关系递推关系382221213) nnnFFFF F 证明：证明： )( )()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFF_122221 nnnFFFFF 2.6 2.6 递推关系递推关系39 2.6 2.6 递推关系递推关系( ) , f xa b求单峰函数在区间上的最大值。11,aa bb令,kka b设区间为，将其三等分，即三分法：三分法：12(),().33kkkkkkkkabaaba1111()(),kkkkkkkkkkffaa babb若，则取否则，取特点：每次区间长度缩短1/3缺点：上一步点的值下一步没有用到40 2.6 2.6 递推关系递推关系0.618方法：方法：将三