这个游戏大家想必都不陌生：
当然，游戏是有规则的，否则把所有的圈圈们连根拔起，一下扔过去就结束了。。。
规则一：每次操作只能移动一个圈圈，把它从一个柱子移到另一个柱子上；
规则二：大圈圈不能架在小圈圈的上面。
今天咱们就来说说这个游戏。
游戏的名字，最通俗的叫法是汉诺塔，英文名Tower of Hanoi。
Hanoi在英文里是河内（越南首都）的意思，所以，其实还是叫河内塔更准确些。
神话故事
这是一个古印度的游戏，源自古印度神话：
印度教的主神梵天创造世界时，做了三根金刚石的柱子，并在其中的一根柱子上按照大小顺序依次放置了64个黄金圆盘。
梵天神告诉侍奉他的婆罗门（祭司），要借助一根柱子做中介，来把这64个圆盘一起移动到另一根柱子上；规则和上面说的一样，在三根柱子间一次只能移动一个圆盘，而且大圆盘不能放在小圆盘之上。
梵天大神说了，只要你们能实现最终的目标，世界就会在一个闪电中毁灭。
据说，这个婆罗门和他的后人从此就开始一刻不停的挪圆盘，以愚公移山的精神，为世界的最终毁灭贡献自己的力量。
让 他 们 先 挪 一 会 ！
解法概述
我们来看看解法。
对于河内塔游戏而言，无论是64个盘子，还是8个盘子，或是3个盘子，盘子的数量只会影响具体操作的复杂度，和方法本身关系不大。
要讲清楚解谜的方法，盘子数太多了没意义，太少了又不典型，因此咱们采用8个盘子为例，把这个问题说明白：
有ABC三根棒子，其中在A棒上有8个从大到小排列好的盘子。现在要以B棒为过渡和中转，把这8个盘子最终都移到C棒上。
学过计算机编程基础的小盆友们都知道，解决河内塔问题大体有两种思路：迭代和非迭代。
迭代的解法
迭代的方法非常简单，也很好玩。
记得那个经典的笑话吗：
把大象放进冰箱要几步？
分三步：
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亿年左右……
