递推关系与Fibonacci数列课件

2.2递推关系与Fibonacci数列

递推关系

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

B

C第三步把B柱的小圆盘移到C柱，即完成移动。令h(n)表示n个圆盘所需要的转移盘次。因此有：从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后将B的n-1个盘子转移到C上。下面我们利用母函数来得到h(n)的通项表达式。假设序列h(n)对应的母函数为H(x)，即因此有或者利用x2:x3:x4:+)同样可以得到：对于一个n位十进制数p1p2…pn-1pn，则p1

p2…pn-1是n-1位十进制数。例1求n位十进制数中出现偶数个5的数的个数。因此若令an表示n位十进制数中出现偶数个5的数的个数，bn表示出现奇数个5的数的个数，则有若它含有偶数个5，则pn必须取5以外的九个数中的一个；若p1p2…pn-1含有奇数个5，则pn必须取成5。a1=8，b1=1.设{an}的母函数为A(x)，{bn}的母函数为B(x)，则或者利用x2:x3:+)类似的还有这样就得到了关于A(x)和B(x)的联立方程组：可以解得：因此有(1)不出现a1，这相当于从其他n-1个元素中取r个做可重组合；这样的组合可以分为两种情况：(2)出现a1，这相当于从n个元素中取r-1个做可重组合再加上a1。因此有初始条件为因此还可以令例2从n个不同的元素a1,a2,…,an中取r个做允许重复的组合，求不同的组合数注意到递推关系

中有2个参数，对于固定的n，

的母函数为Gn(x)，则2.Fibonacci数列Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为Fn，其中当月新生兔数目设为Nn对，上个月留下的兔子数目设为On对，则但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有利用这个递推关系很容易可以得到：下面我们利用母函数来计算Fn的通项表达式。设Fn的母函数为G(x)，则x3:x4:+)方程1-x-x2=0的两个根设为：则有利用待定系数法易有因此有即通项表达式为：0.618方法：将三分法中的2/3换成0.618。不妨假设区间为[0,1]，上一步的取值点为x，1-x。为了充分利用上一步取值点的信息，因此要求x2=x(1-x)，解得x约等于0.618。为什么取0.618？假设保留的区间为[0,x]，则下一步的取值点为x2，x(1-x)。这比三分法节省了大约一半的运算量。Fibonacci方法：在第k步令因此若要求最后区间长度不超过d，则可由(b-a)/Fn<d解出Fn，即确定n。这样在n步迭代后，bn-an=(b-a