文档介绍：:这是个组合数学中的著名问题。
N个圆盘依其半径大小,从下而上套在A柱上。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来,并估计要移动几个盘次。现在只有A、B、C三根柱子可用。
Hanoi塔
要求:
1)每次只能移动一个盘子;
2)盘子可以放到ABC任何一个塔座上;
3)任何时候,都不能将较大的盘子压在较小的圆盘之上;
Hanoi问题是个典型的问题,第一步要设计算法,进而估计它的复杂性,估计工作量。
算法:
N=2时
第一步先把最上面的一个圆盘套在B上

第二步把下面的一个圆盘移到C上

最后把B上的圆盘移到C上
到此转移完毕
A B C
对于一般n个圆盘的问题,
假定n-1个盘子的转移算法已经确定。
先把上面的n-1个圆盘经过C转移到B。
第二步把A下面一个圆盘移到C上
最后再把B上的n-1个圆盘经过A转移到C上
A B C
上述算法是递归的运用。n=2时已给出算法;n=3时,第一步便利用算法把上面两个盘移到B上,第二步再把第三个圆盘转移到柱C上;最后把柱B上两个圆盘转移到柱C上。N=4,5,…以此类推。
算法分析:令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后再一次将B上的n-1个盘子转移到C上。
算法复杂度为:
H(x)是序列的母函数。给定了序列,对应的母函数也确定了。反过来也一样,求得了母函数,对应的序列也就可得而知了。
令
如何从母函数得到序列?
下面介绍一种化为部分分数的算法。