2-2-递推关系与Fibonacci数列课件.ppt

1、2.2 递推关系与递推关系与Fibonacci数列数列 递推关系递推关系 Fibonacci数列数列1.递推关系递推关系Hanoi塔问题：这是组合数学中的一个著名问题。塔问题：这是组合数学中的一个著名问题。n个圆盘依其半径大小，从下而上套在个圆盘依其半径大小，从下而上套在A柱上。每柱上。每次只允许取一个移到柱次只允许取一个移到柱B或或C上，而且不允许大盘上，而且不允许大盘放在小盘上方。若要求把柱放在小盘上方。若要求把柱A上的上的n个盘移到个盘移到C柱上柱上，请设计一种方法并估计要移动几个盘次。现在只，请设计一种方法并估计要移动几个盘次。现在只有有A、B、C三根柱子可用。三根柱子可用。首先要设计

2、算法，进而估计它的复杂性，即估计工首先要设计算法，进而估计它的复杂性，即估计工作量。作量。当当n=2时，时，第一步把第一步把A柱的小圆盘移到柱的小圆盘移到B柱；柱；第二步把第二步把A柱的大圆盘移到柱的大圆盘移到C柱；柱；A B C第三步把第三步把B柱的小圆盘移到柱的小圆盘移到C柱，即完成移动。柱，即完成移动。假定假定n-1个盘子的转移算法已经确定，对于一般个盘子的转移算法已经确定，对于一般n个个圆盘的问题，圆盘的问题，A B C 首先把首先把A柱上面的柱上面的n-1个圆盘移到个圆盘移到B柱；柱；然后把然后把A柱最下面的圆盘移到柱最下面的圆盘移到C柱；柱；最后把最后把B柱的柱的n-1个圆盘移到个

3、圆盘移到C柱，即完成移动。柱，即完成移动。令令h(n)表示表示n个圆盘所需要的转移盘次。个圆盘所需要的转移盘次。因此有：因此有：()(),().h nh nh21111从这个递推关系式可以逐项递推得到所有的从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面根据算法先把前面n-1个盘子转移到个盘子转移到B上；然后把第上；然后把第n个盘子转到个盘子转到C上；最后将上；最后将B的的n-1个盘子转移到个盘子转移到C上。上。下面我们利用母函数来得到下面我们利用母函数来得到h(n)的通项表达式。的通项表达式。假设序列假设序列h(n)对应的母函数为对应的母函数为H(x)，即，即()()()()

4、H xhxhxhx 23123()()()()H xhxhxhx 23123)()-()(),xH xhxhx 2322122,xxxxx 231_()()()()()()()x H xhxhhxhhx23121221322因此有因此有 ().xH xxx 112或者利用或者利用()()hh 2211()()hh3221()()hh4231x2:x3:x4:_ ()()/()H xxxH xxx221+)同样可以得到：同样可以得到：().xH xxx 112假设假设 ().xABH xxxxx112121下面我们用幂级数展开的方法得到下面我们用幂级数展开的方法得到h(n).()H xxx 11

5、121()nnnnxx 002利用待定系数法容易得到利用待定系数法容易得到A=1，B=-1，即，即(),nnnx 121即即().nh n 21对于一个对于一个n位十进制数位十进制数 p1 p2pn-1 pn，则，则 p1 p2pn-1 是是n-1位十进制数。位十进制数。例例1 求求n位十进制数中出现偶数个位十进制数中出现偶数个5的数的个数。的数的个数。,nnnnnnaabbba 111199因此若令因此若令an表示表示n位十进制数中出现偶数个位十进制数中出现偶数个5的数的的数的个数，个数，bn表示出现奇数个表示出现奇数个5的数的个数，则有的数的个数，则有若它含有偶数个若它含有偶数个5，则，则

6、 pn必须取必须取5以外的九个数中的以外的九个数中的一个；一个；若若 p1 p2pn-1含有奇数个含有奇数个5，则，则 pn必须取成必须取成5。a1=8，b1=1.设设 an 的母函数为的母函数为A(x)，bn的母函数为的母函数为B(x)，则，则()A xaa xa x 2123()xA xa xa x 212999)()xB xb xb x 212_()()()x A xxB x 198或者利用或者利用aab2119aab 3229x2:x3:_()()()A xxA xxB x 89+)()()()x A xxB x 198类似的还有类似的还有()B xbb xb x2123()xB xb

7、 xb x 212999)()xA xa xa x 212_()()()x B xxA x 191这样就得到了关于这样就得到了关于A(x)和和B(x)的联立方程组：的联立方程组：()()(),()()(),x A xxB xxA xx B x 198191(),()()xA xxx 71818110可以解得：可以解得：()A xxx 1792 18110因此有因此有由于由于(),nnnnx 017 89 102.nnna117981022另解：另解：n-1位十进制数共有位十进制数共有910n-2个，要么含有奇个，要么含有奇数个数个5，要么含有偶数个，要么含有偶数个5。故有：。故有：,.nnnn

8、nnaabba 1121199 10因此有因此有,.nnnaaa 21189 108()A xaa xa x 2123()xA xa xa x 212888_()()()()x A xaaxaax 2213218888xx 2899 10 xxxx 98718110110因此有因此有(),nnnnx 017 89 102.nnna117981022(1)不出现不出现a1，这相当于从其他，这相当于从其他n-1个元素中取个元素中取r个做个做可重组合；可重组合；这样的组合可以分为两种情况：这样的组合可以分为两种情况：C n rC n rC nr (,)(,1)(1,).(2)出现出现a1，这相当于从

9、，这相当于从n个元素中取个元素中取r-1个做可重组个做可重组合再加上合再加上a1。因此有。因此有初始条件为初始条件为C nnC nn (,1),(1,1)1,因此还可以令因此还可以令例例2 从从n个不同的元素个不同的元素a1,a2,an中取中取r个做允许重复个做允许重复的组合，求不同的组合数的组合，求不同的组合数C n r(,)C n(,0)1.()(,)(,)(,)nGxC nC nxC nx2012()(,)(,)nxGxC nxC nx 201)()(,)(,)nGxC nC nx 11 01 1_()()()nnx GxGx 110注意到注意到()(,)(,)(,)GxCCxCx 21

10、1 01 11 2,xxx 2111递推关系递推关系 中有中有2个参个参数，对于固定的数，对于固定的n，的母函数为的母函数为Gn(x)，则，则C n rC n rC nr (,)(,1)(1,)C n r(,)因此有因此有()()()()nnnGxGxGxxx 1221111因此由二项式展开定理可知因此由二项式展开定理可知()()()(,)()!rnnnrC n rr 111-(),()()nnGxxx 111111()()!n nnrr 11(,).C nrr 12.Fibonacci数列数列Fibonacci数列是递推关系的又一个典型问题，数数列是递推关系的又一个典型问题，数列的本身有着许

11、多应用。列的本身有着许多应用。有雌雄兔子一对，假定过两月便可繁殖雌雄各一的有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了一对小兔。问过了n个月后共有多少对兔子？个月后共有多少对兔子？设满设满n个月时兔子对数为个月时兔子对数为Fn，其中当月新生兔数目，其中当月新生兔数目设为设为Nn 对，上个月留下的兔子数目设为对，上个月留下的兔子数目设为On对，则对，则.nnnFNO 但是注意到但是注意到 On=Fn-1，Nn=On-1=Fn-2，因此有，因此有,.nnnFFFFF 12121利用这个递推关系很容易可以得到：利用这个递推关系很容易可以得到：,FFFFFFFFF 3124235342

12、3325下面我们利用母函数来计算下面我们利用母函数来计算Fn的通项表达式。的通项表达式。设设Fn的母函数为的母函数为G(x)，则，则FFF321FFF432x3:x4:_()()()G xxxx G xxx G x 22+)()()xx G xx 21().xG xxx 21,151522方程方程1-x-x2=0的两个根设为：的两个根设为：则有则有().xABG xxxxx 2111利用待定系数法易有利用待定系数法易有,AB 1515因此有因此有()()()nnnnG xxx 0015()nnnnx 115即通项表达式为：即通项表达式为：().nnnF 15下面介绍一些关于下面介绍一些关于Fi

13、bonacci数列的结论。数列的结论。(1)任意正整数任意正整数N可以表示成可以表示成Fibonacci数列中的数的数列中的数的有限和，即有限和，即=2=niiiNs F,满足满足si=0或或1，且，且si si+1=0。(2)边长为边长为Fn的正方形可以分解为若干个边长为的正方形可以分解为若干个边长为Fi和和Fi+1的长方形。的长方形。参见课本图形。参见课本图形。();nnFFFF 12231FFF 132FFF 243)nnnFFF 21_nnnFFF 11nnFFFFF 1222.nF 21();nnFFFFF 1352124FF 12FFF 342)nnnFFF 21222_FFF 5

14、64.nnFFFFF 135212().nnnFFFF F 2221215FF F 2121()FF FFF FF F 222312321)()nnnnnnnnFF FFF FFF 21111_()FF FFF FF F 233423423.nnnFFFF F 222121下面介绍一个下面介绍一个Fibonacci数列在优化中的应用。数列在优化中的应用。问题：求单峰函数问题：求单峰函数f(x)在区间在区间a,b上的最大值。上的最大值。(),().kkkkkkkkabaaba 1233三分法：三分法：将第将第k步的区间步的区间ak,bk三等分，即三等分，即优点：优点：每次区间长度缩短每次区间长度

15、缩短1/3。数值方法迭代求解。首先令数值方法迭代求解。首先令a1=a，b1=b。若若 ，则取，则取()()kkff ,kkkkaab 11否则取否则取,.kkkkabb 11缺点：缺点：上一步中点的值在下一步没有用到。上一步中点的值在下一步没有用到。0.618方法：方法：将三分法中的将三分法中的2/3换成换成0.618。不妨假设区间为不妨假设区间为0,1，上一步的取值点为，上一步的取值点为x，1-x。为了充分利用上一步取值点的信息，因此要求为了充分利用上一步取值点的信息，因此要求x2=x(1-x)，解得，解得x约等于约等于0.618。为什么取为什么取0.618？假设保留的区间为假设保留的区间为

16、0,x，则下一步的取值点为，则下一步的取值点为x2，x(1-x)。这比三分法节省了大约这比三分法节省了大约一半一半的运算量。的运算量。Fibonacci方法：方法：在第在第k步令步令因此若要求最后区间长度不超过因此若要求最后区间长度不超过d d，则可由，则可由 (b-a)/Fn d d 解出解出Fn，即确定，即确定n。这样在这样在n步迭代后，步迭代后，bn-an=(b-a)/Fn。注意到注意到(),().n kn kkkkkkkkkn kn kFFabaabaFF 111lim.,nnnFF 1510 6182因此当因此当n趋于无穷时，趋于无穷时，Fibonacci方法与方法与0.618方法的方法的区间缩短率相同。区间缩短率相同。可以证明可以证明Fibonacci方法是一维极值问题的方法是一维极值问题的最优策略最优策略，而而0.618是近似最优的。是近似最优的。