重建一座64层的汉诺塔至少需要多长时间（重建一座64层的汉诺塔至少需要多长时间）

我要

灰飞烟灭啦

前几天，超模君跟模友来分了一下酒（分酒问题传送门），然后又好几个模友都表示想起了汉诺塔问题。

于是，在周末的时候，超模君就下载了个汉诺塔的游戏来玩，刚开始第一关，没几秒超模君就完整将第一条杆上3个蓝蓝的小圈圈从大到小移到了第三条杆上，轻松获得了满分3星。

然而，随着轮胎数的增加，超模君发现，虽然原理都是一样的，但脑子有时真的有点转不过来，一不小心就game over了。。。

首先，当然要从汉诺塔的由来讲起，这源于印度的一个关于“世界末日”的传说。

相传，印度教主神梵天在创造这个世界的时候，在印度贝那勒斯城的一座寺庙里，做了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万数学精英都在关注！

,