[趣题分享]汉诺塔 Hanoi Tower

elimqiu

汉诺塔 Hanoi Tower
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
我们现在要问，如果从头开始，按每秒完成一片金片的搬动计算，世界末日离我们多远？

技术员

这是个天文数字!

申一言

   一张报纸叠32层，问有多高？（一层为0.2mm)

awei

[color=#0000FF]
摘自百度：
2^64-1=18446744073709551615 秒
假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下， 　　18446744073709551615/31556952=584554049253.855年
这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
动听的不只是这个传说，而是传说背后人类对于自己的深思，称赞自己文明的同时不得不感叹自己的渺小，呵呵！

申一言

  h= (2ˇ32)*0.2mm[br][br]-=-=-=-=- 以下内容由 申一言 在 时添加 -=-=-=-=-
4294967696*0.2mm=8589934m

elimqiu

搞数学的人有时候是有一点癫狂。这个问题已经不好一下子回答，竟有人还要用更虚无缥缈的函数来表达：
假定金片的数目不是64而是n, 那么游戏规则确定了这种从针x到针y的搬运的最捷工作量f(n). 考虑这样的情形：金片起初都在宝石针0处，经过若干次搬动，宝石针0上面n-1片金片都搬到宝石针1处（按照规定的大小上下秩序），宝石针0剩下最大最后的一片金片。宝石针2依然独身一柱撑天。按照f的定义，我们需要 f(n-1)次搬动来达到这个状态。现在我们把最大最后的那片金片套入宝石针2，然后我们再需要另外f(n-1)次搬动才能把宝石针1处的金片移至宝石针2。这个手续是必要的，又是充分（足够达到目的）的。所以我们得到一个关系式
f(n) = 2f(n-1)+1 即  f(n)+1 = 2(f(n-1)+1)
令 a(n) = f(n)+1 得到 a(n) = 2a(n-1) 即 a(n) = 2^(n-1)a(1)  (n ≥ 1)
注意f(1)=1, a(1)=2. 上面的式子表明 a(n)=2^n  即 f(n) = 2^n-1
所以原问题的答案是我们还有 2^(64)-1 秒。这表明移完这些金片需要5845亿年以上。

elimqiu

我盼望大家对上面的解有一点思考。这个问题我小时候就隐约知道，不知道汉诺之名。有一天送儿子上学时想起，就在车上这么解得了这个一般的公式。回来靠计算机才算出年数。想到要贴在这里，才非了一番周折查出‘汉诺’之名。
数学地解决一个问题的第一步是什么？ 就是把问题数学地表达出来么。一个问题的好的陈述方式就是离解答近，就是有工具可用的陈述。在这里，抽象的思考很重要，而抽象的思考是需要平时的锤炼的。如果一开始就拒绝抽象，那么就难了。拒绝函数，映射，序列的概念，数学能走多远？

申一言

   给人以启迪的问题！
   皇帝与农民下棋，打赌，皇帝赢了杀农民的头；农民则笑着说俺赢了，只要你第一个棋盘的格子里给一粒粮食，剩下每格倍增就可以了，结果皇帝输了，全国的粮食也不够给农民的？
     狠毒的皇帝输给了机智善良的农民。

elimqiu

下面引用由申一言在 2010/10/23 09:05am 发表的内容：
   给人以启迪的问题！
   皇帝与农民下棋，打赌，皇帝赢了杀农民的头；农民则笑着说俺赢了，只要你第一个棋盘的格子里给一粒粮食，剩下每格倍增就可以了，结果皇帝输了，全国的粮食也不够给农民的？
     狠毒　...

不要相信这种故事。皇帝拿不出这么多粮食，还是会杀人的头的。最好不要让人做皇帝。

elimqiu

网上有一些汉诺塔游戏的程序。什么时候搞下来玩一玩。