1、2.2 递推关系与 Fibonacci数列1. 递推关系2. Fibonacci数列1. 递推关系Hanoi塔问题：这是组合数学中的一个著名问题。n个圆盘依其半径大小，从下而上套在 A柱上。每次只允许取一个移到柱 B或 C上，而且不允许大盘放在小盘上方。若要求把柱 A上的 n个盘移到 C柱上，请设计一种方法并估计要移动几个盘次。现在只有 A、 B、 C三根柱子可用。首先要设计算法，进而估计它的复杂性，即估计工作量。当 n=2时，第一步把 A柱的小圆盘移到 B柱；第二步把 A柱的大圆盘移到 C柱；A B C第三步把 B柱的小圆盘移到 C柱，即完成移动。假定 n-1个盘子的转移算法已经确定，对于一
2、般 n个圆盘的问题，A B C首先把 A柱上面的 n-1个圆盘移到 B柱；然后把 A柱最下面的圆盘移到 C柱；最后把 B柱的 n-1个圆盘移到 C柱，即完成移动。令 h(n)表示 n个圆盘所需要的转移盘次。因此有：从这个递推关系式可以逐项递推得到所有的 h(n)。根据算法先把前面 n-1个盘子转移到 B上；然后把第 n个盘子转到 C上；最后将 B的 n-1个盘子转移到 C上。下面我们利用母函数来得到 h(n)的通项表达式。假设序列 h(n)对应的母函数为 H(x)，即因此有或者利用x2:x3:x4:+)同样可以得到：假设下面我们用幂级数展开的方法得到 h(n).利用待定系数法容易得到 A=1， B=-1，即即对于一个 n位十进制数 p1 p2 pn-1 pn，则 p1 p2 pn-1 是 n-1位十进制数。例 1 求 n位十进制数中出现偶数个 5的数的个数。因此若令 an表示 n位十进制数中出现偶数个 5的数的个数， bn表示出现奇数个 5的数的个数，则有若它含有偶数个 5，则 pn必须取 5以外的九个数中的一个；若 p1 p2 pn-1含有奇数个 5，则 pn必须取成 5。a1=8， b1=1.设 an 的母函数为 A(x)， bn的母函数为 B(x)，则或者利用 x:x2:+)
