河内之塔 - 汉诺塔

说明

河内之塔(Towersof Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时 北越的首都，即现在的胡志明市;1883年法国数学家 EdouardLucas曾提及这个故事，据说创世 纪时Benares有一座波罗教塔，是由三支钻石棒(Pag)所支撑，开始时神在第一根棒上放置64 个由上至下依由小至大排列的金盘(Disc) ，并命令僧侣将所有的金盘从第一根石棒移至第根三 石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬 运完毕之时，此塔将毁损，而也就是世界末日来临之时。

解法

A上有n个盘子。
一、如果n=1，则将圆盘从A直接移动到C。
二、如果n=2，则：
1）将A上的n-1（等于1）个圆盘移到B上；
2）再将A上的一个圆盘移到C上；
3）最后将B上的n-1（等于1）个圆盘移到C上。

如果n=3，则：
将A上的n-1（等于2，令其为n'）个圆盘移到B（借助于C），步骤如下：
1）将A上的n'-1（等于1）个圆盘移到C上。
2）将A上的一个圆盘移到B。
3）将C上的n'-1（等于1）个圆盘移到B。

B将A上的一个圆盘移到C。

C将B上的n-1（等于2，令其为n'）个圆盘移到C（借助A），步骤如下：
1）将B上的n'-1（等于1）个圆盘移到A。
2）将B上的一个盘子移到C。
3）将A上的n'-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。

从上面分析可以看出

1、当n=1时，将A移到C上

2、当n大于等于2时， 移动的过程可分解为三个步骤：

第一步：把A上的n-1个圆盘移到B上；

第二步：把A上的一个圆盘移到C上；

第三步：把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n'-1个圆盘从一个针移到另一个针上，这里的n'=n-1。

image.png