汉诺塔游戏总结发言（干货汉诺塔游戏解法完整版）

这个游戏大家想必都不陌生：

当然，游戏是有规则的，否则把所有的圈圈们连根拔起，一下扔过去就结束了。。。

规则一：每次操作只能移动一个圈圈，把它从一个柱子移到另一个柱子上；

规则二：大圈圈不能架在小圈圈的上面。

今天咱们就来说说这个游戏。

游戏的名字，最通俗的叫法是汉诺塔，英文名Tower of Hanoi。

Hanoi在英文里是河内（越南首都）的意思，所以，其实还是叫河内塔更准确些。

神话故事

这是一个古印度的游戏，源自古印度神话：

学过计算机编程基础的小盆友们都知道，解决河内塔问题大体有两种思路：迭代和非迭代。

迭代的解法

迭代的方法非常简单，也很好玩。

记得那个经典的笑话吗：

把大象放进冰箱要几步？

分三步：

1、把冰箱门打开；

2、把大象塞进去；

3、把冰箱门关上。

嗯，跟这个笑话类似：

你不是想要找一个办法把8个盘子都移到C棒吗？

分三步：

1、假设有了一个办法，把前7个盘子一起都移到B棒。

2、把最大的盘子移到C棒。

3、再用想象中的办法，把B棒上那7个盘子都移到C棒那个最大的盘子上。

问题就解决了。

图中深黄色的盘子可视为任意数量：对任何N个盘子的情况，都可以简化为将N-1个盘子先移到中转棒，将最大的盘子移到目标棒，再将N-1个盘子移到目标棒

那么如何完成第一步和第三步里，把7个盘子整体移动呢？

继续迭代：先把前6个盘子都移到C棒，再把最大的那个移到B棒，再把C棒上那6个盘子移回B棒上来。

每一次迭代，都使得需要移动的盘子数减少了1；一直迭代下去，直到最原始的情况：把一个盘子移到另一根棒子上。

这个原始情况解决了，那么依次倒回去，所有的问题都解决了。

仍然用大象和冰箱的例子作比，那就是：

中间的第二步，如何把大象塞进去呢？

先把大象头塞进去；

再把大象身体塞进去；

再把大象腿和尾巴塞进去。

大象的头如何塞进去呢？

先把鼻子塞进去；

再把脸塞进去；

再把后脑勺一股脑塞进去。

大象鼻子怎么塞进去呢？

先把第一段鼻子塞进去；

再把第二段鼻子塞进去；

……

迭代法，就是这么简（bao）单（li）而且易（liu）行（mang）！

正因为如此，这个方法也成为大学里教授计算机编程思想的必修内容之一：几乎所有的计算机专业的大学生都遇到过这个问题和解法。

程序是解决了，但这其实并不是一个正常人类能看懂和操作的方法；你能写出这样的程序让计算机给出答案，可是当你实际遇到8个盘子叠起来时，还是一样抓瞎没辙，并没有实际的指导意义。

有没有直观的、操作性强的统一解法呢？

当然有。

这就是所谓非迭代的解法。

---

以下慎入，因为当你看完后，你会发现此游戏的所有乐趣都被剥夺殆尽，只剩下了极其简单和无聊的解谜过程

---

非迭代的解法

同样以8个盘子为例：

A棒上的8个盘子要全部移到目标C棒，

所以：

最大的8号盘的目标是C棒。

次大的7号盘的目标就应该是B棒。

以此类推，6号盘的目标又是C棒。

5号盘的目标是B棒。

4号盘的目标是C棒。

3号盘的目标是B棒。

2号盘的目标是C棒。

最小的1号盘，目标是B棒。

总而言之：

1、3、5、7号盘的目标是中转棒B；

2、4、6、8号盘的目标是目标棒C。

这8个目标把整个问题分成了8步，而且和刚刚迭代法那不负责任的3步比起来，这8步的指导意义是很强的：

第一个目标，就是将最小的1号盘移到中转棒B棒上。——这个目标当然一步就能实现：

然后将2号盘移到目标棒C棒上。——也是一步就可以实现：

下一个目标，就是把3号盘移到B棒。这时由于1号盘占上了B棒的坑位，所以要先把它挪到C棒，腾出B棒的位置，再把3号盘移过来：

下面类似：1号移回A，2号移上B，1号移上B，4号移到C：

后面的思路都一样，不再赘述：总之，8个目标是分别让1、2、3、4、5、6、7、8号盘依次就位：

当8号盘在C棒就位以后，下面就是要让7号去C棒。

要实现这一点，6号要去A，5号去C，4号去A，3号去C，2号去A，1号去C。

也就是说，接下来的一步是让1号盘移到C棒。

再重复一下问题的关键：对于8个盘的情况，其实盘子们分别要去的目标是唯一的——

1、3、5、7号盘去中转棒B，

2、4、6、8号盘去目标棒C。

不仅如此！

在操作中的每一步，你想要移动的目标盘和你实际移动的盘之间，保持间隔始终为偶数，就一定没问题。

举例来说，在某一个中间状态，12345号盘一起堆在C棒上，你想把它们一起弄到B棒；这时1、3、5号盘的目标就是B棒，2、4号盘的目标是A棒。所以此时要做的第一步就是把1号盘移到B棒。

嗯，你已经获得了这个游戏的精髓。

这么一来，这个游戏还有什么乐趣可言呢？？

没有了。

即使是64个盘子，我们也能一下得到所有的中间状态：把所有盘子从小到大编号，所有的奇数号盘子（1，3，5，7，...）一律去中转棒，所有的偶数号盘子（2，4，6，8，...）一律去目标棒；当第64个盘子就位以后，再将所有的奇数号盘子的目标定为目标棒，把剩下的偶数号盘子的目标定为中转棒，直至第63个盘子就位；然后再继续重复这一过程，直至所有盘子就位。

好枯燥，好简单，好无聊！

复杂度

那么我们来看看这个话题里最后一个有点意思的内容：

操作开销和时间开销。

要实现64个盘子移位的终极目标，要做多少次有效的移动？

——所谓有效移动是指，假设这些婆罗门和后代们把其中的算法和过程都研究得很清楚，奇偶数的盘子都没有数错，老眼昏花、头昏脑胀，移的过程乱七八糟等等，所有这些意外统统不出现：

那么一共至少要多少步呢？

很好算。

1个盘子就位需要1步，

2个盘子都就位需要3步，

从3个盘子开始，就需要先用3步使前2个盘子都移到中转棒，再来1步使第三个盘子就位，再来3步使前2个盘子都移到目标棒，一共就是3 1 3=7步。

4个盘子全部就位，需要7 1 7=15步。

按照归纳法进行简单的计算，容易知道：

n个盘子全部就位，需要总步数为：2的n次方-1。

也就是说，对于梵天神64个盘子的完整版，婆罗门和后人们一共只需要移动2的64次方-1步，就可以就位啦！

这个过程其实很快的，只要他们能做到并且维持每秒移动1个盘子的速度，那么一共只要2的64次方-1秒，合5800亿年，就能把64个盘子正确就位，使得宇宙在闪电中毁灭！

不过，据科学家分析，宇宙的寿命也就在150亿年左右……

好吧梵天还是你赢了！！~

,