文档介绍：当n=2时，
第一步把A柱的小圆盘移到B柱；
第二步把A柱的大圆盘移到C柱；
A B C
第三步把B柱的小圆盘移到C柱，即完成移动。
第1页/共25页
假定n-1个盘子的转移算法已经确定，对于一般n个圆盘的问题，
A B C
首先把A柱上面的n-1个圆盘移到B柱；
然后把A柱最下面的圆盘移到C柱；
最后把B柱的n-1个圆盘移到C柱，即完成移动。
第2页/共25页
令h(n)表示n个圆盘所需要的转移盘次。
因此有：
从这个递推关系式可以逐项递推得到所有的h(n)。
根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后将B的n-1个盘子转移到C上。
下面我们利用母函数来得到h(n)的通项表达式。
假设序列h(n)对应的母函数为H(x)，即
第3页/共25页
因此有
第4页/共25页
或者利用
x2:
x3:
x4:
+)
同样可以得到：
第5页/共25页
假设
下面我们用幂级数展开的方法得到h(n).
利用待定系数法容易得到A=1，B=-1，即
即
第6页/共25页
对于一个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.
第7页/共25页
设 {an} 的母函数为A(x)，{bn}的母函数为B(x)，则
或者利用
x2:
x3:
+)
第8页/共25页
类似的还有
这样就得到了关于A(x)和B(x)的联立方程组：
可以解得：
第9页/共25页
因此有
由于
另解： n-1位十进制数共有9×10n-2个，要么含有奇数个5，要么含有偶数个5。故有：
因此有
第10页/共25页