博客

汉诺塔问题

规则简述：有三个塔座，在第一个塔座上有n个直径大小不同的，从小到大依次标号为1，2，3……，n的圆盘。要求将所有圆盘移动至第三个塔座且仍按同样顺序叠排。（每次只能移动一个圆盘且任何时候不能将一个较大圆盘压在较小圆盘之上。）

那我们该如分析这个问题呢？

无从下手之时，不妨我们先试着玩一下这个游戏。

我们将塔座分别编号为X （起始塔座），Y（辅助塔座），Z（目标塔座）。

当n=1时，问题极为简单，只要将编号为1的圆盘从X移至Z塔座即可。

现在我们加大难度，

当n=2时，我们需要

1：将编号为1的圆盘从X移至Y塔座

2：将编号为2的圆盘从X移至Z塔座

3：将编号为1的圆盘从Y移至Z塔座

当n=2时，我们无法将1直接移动至Z塔座（如果你这样做你将无法解决2号圆盘），

而需要将在1移至Z之前将2移至Z，

这时我们则需要Y来接纳1，

以此类比下去，当有n个圆盘时，我们需要用Y接纳n-1，将n圆盘移至Z，最后将n-1移动至Z。

此刻很明显一个递归的思想浮现了出来，让我们总结一下，其实就三个步骤周而复始，就可以一层一层地解决汉诺塔问题。

简而言之如下

1：将n-1从X移至Y （Z塔座作为辅助塔座）

2：将n 从X移动至Z

3：将n