我要
灰飞烟灭啦
前几天，超模君跟模友来分了一下酒（分酒问题传送门），然后又好几个模友都表示想起了汉诺塔问题。
于是，在周末的时候，超模君就下载了个汉诺塔的游戏来玩，刚开始第一关，没几秒超模君就完整将第一条杆上3个蓝蓝的小圈圈从大到小移到了第三条杆上，轻松获得了满分3星。
然而，随着轮胎数的增加，超模君发现，虽然原理都是一样的，但脑子有时真的有点转不过来，一不小心就game over了。。。
不过，超模君表示不能轻易放弃，决定还是得彻底搞清楚汉诺塔（Tower of Hanoi）的玩法。
首先，当然要从汉诺塔的由来讲起，这源于印度的一个关于“世界末日”的传说。
相传，印度教主神梵天在创造这个世界的时候，在印度贝那勒斯城的一座寺庙里，做了3根宝石针，安放在一块黄铜板上。
并且，在其中一根宝石针上，自下而上，从大到小，堆放了64块黄金圆盘，所谓的汉诺塔就这样出来了。
接着，梵天大神便吩咐庙里的教徒，每天都按照规则去移动汉诺塔上的圆盘，借助中间那根宝石针作为中介，将这64个圆盘移到第三根宝石针上，重建一个新塔。
规则很简单：圆盘只能在3根宝石针之间移动，每次只能移动一个圆盘，小圆盘必须放在大圆盘上面。
梵天大神还说了，只要你们完成任务，这个世界就会在一瞬间毁灭。
于是，教徒开始不分昼夜去搬圆盘，为的就是能够看到世界毁灭，但是，连着教徒的后人都搬了好几代了，还是没能够完成梵天大神的任务。
暂且不论这个传说有几分真实，让我们先来算一笔账。
1个圆盘时需要移动1次，2个圆盘时需要移动3次，3个圆盘时需要移动7次，4个圆盘时移动的次数便增加到了15次。
n=3
n=4
如果是5个圆盘的话……
图片来源：http://blog.csdn.net/yuxiboh/article/details/44859873?locationNum=1&fps=1
上面那个动图估计大家看着都有点晕，现在超模君就再来展现一下自己的画功。
其实，汉诺塔问题永远只需要3步！
大家是否记得之前超模君推送过的“把大象装进冰箱的N种方法！”呢？虽然里面都是一本正经地胡说八道，但这都源于一个经典笑话。
把大象放进冰箱要几步？
分三步：1、把冰箱门打开；2、把大象塞进去；3、把冰箱门关上。
而这个笑话就是汉诺塔问题的解法啦。
就是这么简单粗暴！
只不过，随着圆盘数n的增加，就意味着“大象”被“分割”成更多个部分。
要想将“大象”装进冰箱，就要先把“大象的头”塞进去，然后再把“大象的身体”塞进去，最后把“大象的腿和尾巴”塞进去。
那我们第一轮的目标就是“大象的头”。要想将“大象的头”塞进冰箱，那就得先将“大象的鼻子”塞进去，然后再把“大象的脸”塞进去，最后把“大象的后脑勺”塞进去。
接着，我们的目标就变成了“大象的鼻子”。要想将“大象的鼻子”塞进冰箱，就得先把“大象的第一段鼻子”塞进去，再把“大象的第二段鼻子”塞进去，……把“最后一段鼻子”塞进去。
之后，我们的目标变成“大象的第一段鼻子”。要想将“大象的第一段鼻子”塞进冰箱，就要先把“大象的第一个鼻孔”塞进去，再“第二个鼻孔”。
。。。。。。
如此迭代，最后大象就会全部被塞进冰箱，也就是汉诺塔重建成功！
前方高能！看完之后估计你就会失去对这个游戏的兴趣了。。。
比如我们现在有5个圆盘，我们的最终目标是将A上的5个圆盘按顺序移到C上。
那么，最大的圆盘5目标位置就是C，这样的话，圆盘4的就得先去B，圆盘3要去C，圆盘2要去B，圆盘1就去C。
一句话就是，圆盘1,3,5的目标位置是C，圆盘2,4是去中转站B。
如果是6个圆盘，那最大的圆盘6的目标位置是C，那么，圆盘5就得先去B，圆盘4去C，圆盘3去B，圆盘2去C，圆盘1去B。
即系，圆盘2,4,6的目标就是C，而圆盘1,3,5要先去中转站B。
这样下去的话，就算是64个圆盘，也可以轻松知道每一个圆盘的每一步该怎么走：
这时需要将所有的奇数号圆盘移去中转站（B），所有偶数号圆盘移去目标站（C）；
当圆盘64到达目标站之后，此时就变成63个圆盘的移动问题了，需要将所有奇数号圆盘移到目标站（C），所有偶数号圆盘移到中转站（A），直到圆盘63就位C；
之后，就会变成62个圆盘的问题，再变成61,60,59……个圆盘的问题，继续重复这个过程，直到所有的圆盘都移到最终目标位置C。
是不是很简单？！是不是很刺激！？汉诺塔就这样被我玩完了！
最后，超模君再回头讲一下那个传说，重建一座64层的汉诺塔至少需要多少次移动呢？需要多长时间呢？
根据万能的数学归纳法，易得当有n个圆盘时，需要移动的次数Hn=2^n-1。
所以，当n=64时，Hn=2^64-1=18,446,744,073,709,551,615≈1.8446744*10^19。
有人算过，如果我们严格按照最便捷的方式移动，即是每一个圆盘的每一次移动的位置我们都记得清清楚楚，过程中的头昏脑涨完全不存在，每一秒我们都可以精准地移动一个圆盘的话，重建64层汉诺塔需要（一年按照365天共31536000秒计算）：
Tn=1.8446744*10^19÷31536000≈584,942,417,355≈5849亿年
也就是说，只需要搬5849亿年就可以迎来世界末日啦！
哦，不对，等等，好像地球至今也才45亿岁，而太阳系的寿命也不过200亿年左右。。。
本文系网易新闻·网易号“各有态度”特色内容
部分资料来源于网络
转载请在公众号中，回复“转载”
-----这里是数学思维的聚集地------
“超级数学建模”（微信号supermodeling），每天学一点小知识，轻松了解各种思维，做个好玩的理性派。50万数学精英都在关注！
