汉诺塔的由来 汉诺塔 汉诺塔-由来及传说,汉诺塔-相关预言

汉诺塔是根据一个传说形成的一个问题。汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

汉诺塔_汉诺塔 -由来及传说

由来

法国数学家爱德华・卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片,移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时,

假如每秒钟一次,共需多长时间呢?一个平年365天有31536000 秒,闰年366天有31622400秒,平均每年31556952秒,计算一下:

18446744073709551615秒

这表明移完这些金片需要5845.54亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

印度传说

和汉诺塔故事相似的,还有另外一个印度传说:舍罕王打算奖赏国际象棋的发明人──宰相西萨・班・达依尔。国王问他想要什么,他对国王说:“陛下,请您在这张棋盘的第1个小格里赏给我一粒麦子,在第2个小格里给2粒,第3个小格给4粒,以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒,都赏给您的仆人吧!”国王觉得这个要求太容易满足了,就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时,国王才发现:就是把全印度甚至全世界的麦粒全拿来,也满足不了那位宰相的要求。

那么,宰相要求得到的麦粒到底有多少呢?总数为

1+2+2^2 + … +2^63=2^64-1

等于移完汉诺塔的步骤数――共3853步。我们已经知道这个数字有多么大了。人们估计,全世界两千年也难以生产这么多麦子!

汉诺塔_汉诺塔 -相关预言

有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。

汉诺塔_汉诺塔 -其他相关

与宇宙寿命

如果移动一个圆盘需要1秒钟的话,等到64个圆盘全部重新落在一起,宇宙被毁灭是什么时候呢?

让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次,2个的时候是3次,3个的时候就用了7次......这实在是太累了

因此让我们逻辑性的思考一下吧。

3个的时候能够移动最大的3盘时如图所示。


汉诺塔

到此为止用了7次。

汉诺塔的由来 汉诺塔 汉诺塔-由来及传说,汉诺塔-相关预言

接下来如右图,在上面再放上3个圆盘时还要用7次(把3个圆盘重新放在一起需要的次数)。

因此,4个的时候是

“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”

=2x“3个圆盘重新摞在一起的次数”+1次

=15次。

那么,n个的时候是

2x“(n-1)个圆盘重新摞在一起的次数”+1次。

由于1 个的时候是1次,结果n个的时候为(2的n次方减1)次。

1个圆盘的时候 2的1次方减1

2个圆盘的时候 2的2次方减1

3个圆盘的时候 2的3次方减1

4个圆盘的时候 2的4次方减1

5个圆盘的时候 2的5次方减1

........

n个圆盘的时候 2的n次方减1

也就是说,n=64的时候是(2的64次方减1)次。

因此,如果移动一个圆盘需要1秒的话,

宇宙的寿命=2的64次方减1(秒)

2的64次方减1到底有多大呢?动动计算器,答案是一个二十位的数字约是

1.84467440*10^19

用一年=60秒x60分x24小时x365天来算的话,大约有5800亿年吧。

太阳及其行星形成于50亿年前,其寿命约为100亿年。

汉诺塔问题在数学界有很高的研究价值,而且至今还在被一些数学家们所研究。

也是我们所喜欢玩的一种益智游戏,它可以帮助开发智力,激发我们的思维。

经典题目

有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动,设移动次数为H(n)。

首先我们肯定是把上面n-1个盘子移动到柱子C上,然后把最大的一块放在B上,最后把C上的所有盘子移动到B上,由此我们得出表达式:

H⑴ = 1

H(n) = 2*H(n-1)+1 (n>1)

那么我们很快就能得到H(n)的一般式:

H(n) = 2^n - 1 (n>0)

并且这种方法的确是最少次数的,证明非常简单,可以尝试从2个盘子的移动开始证,你可以试试。

进一步加深问题(解法原创*_*):

假如现在每种大小的盘子都有两个,并且是相邻的,设盘子个数为2n,问:⑴假如不考虑相同大小盘子的上下要多少次移动,设移动次数为J(n);⑵只要保证到最后B上的相同大小盘子顺序与A上时相同,需要多少次移动,设移动次数为K(n)。

⑴中的移动相当于是把前一个问题中的每个盘子多移动一次,也就是:

J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2

在分析⑵之前

,我们来说明一个现象,假如A柱子上有两个大小相同的盘子,上面一个是黑色的,下面一个是白色的,我们把两个盘子移动到B上,需要两次,盘子顺序将变成黑的在下,白的在上,然后再把B上的盘子移动到C上,需要两次,盘子顺序将与A上时相同,由此我们归纳出当相邻两个盘子都移动偶数次时,盘子顺序将不变,否则上下颠倒。

现在回到最开始的问题,n个盘子移动,上方的n-1个盘子总移动次数为2*H(n-1),所以上方n-1个盘子的移动次数必定为偶数次,最后一个盘子移动次数为1次。

讨论问题⑵,

综上两点,可以得出,要把A上2n个盘子移动到B上,首先可以得出上方的2n-2个盘子必定移动偶数次,所以顺序不变,移动次数为:

J(n-1) = 2^n-2

然后再移动倒数第二个盘子,移动次数为2*J(n-1)+1 = 2^(n+1)-3,

最后移动最底下一个盘子,所以总的移动次数为:

K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5

开天辟地的神勃拉玛(和中国的盘古差不多的神吧)在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)大约是1.84467440*10^19,众僧们即便是耗尽毕生精力也不可能完成金片的移动了。

算法介绍

其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n

  

爱华网本文地址 » http://www.413yy.cn/a/8103420103/92918.html

更多阅读

三八妇女节的由来 三八妇女节的由来50字

三八妇女节的由来——简介 三八妇女节又称国际劳动妇女节。在国际上,妇女节的全称是“联合国妇女权益和国际和平日”,是世界各国妇女争取和平、平等、发展的节日。一个世纪以来,各国妇女为争取自身的权利做出了不懈的努力,成功地撑起世

解读八仙过海的由来与八个仙人的故事图文 问责条例图文解读

解读八仙过海的由来与八个仙人的故事(图文)八仙是神话传说中的八位仙人。即铁拐李(李铁拐)、汉钟离(钟离汉)、张果老、何仙姑、蓝采和、吕洞宾、韩湘子、曹国舅八人。八仙故事多见于唐、宋、元、明的记载和杂剧中,姓名不固定,至明吴元泰《八

“花和尚”绰号的由来——水浒拾遗 水浒绰号由来

“花和尚”绰号的由来——水浒拾遗在梁山一百单八将的排名中,鲁智深排第十三,号称是天孤星花和尚鲁智深。“花和尚”这个绰号是怎么产生的呢?在宋朝时,江湖好汉都要有一个绰号,这在当时是一种时尚。不独是一百单八将,其他好汉也有类似的

“一枝梨花压海棠”的由来 一枝梨花压海棠完整版

欲知“一枝梨花压海棠”的由来和寓意,就得从苏轼的一首七绝说起:全诗如下:十八新娘八十郎,苍苍白发对红妆。鸳鸯被里成双夜,一树梨花压海棠。“一枝梨花压海棠”的原文应该是“一树梨花压海棠”,只是在翻译用作lolita〈洛丽塔〉的电影

端午节吃粽子的来历介绍 端午节吃粽子的由来

端午节为什么要吃粽子?端午节吃粽子的来历是什么?端午节粽子的由来介绍:粽子是我国端午节的传统食品,据《续齐谐记》记载,人们最早是用竹筒贮米投水来祭祀屈原的,汉建武中,屈原白日显圣,说大家投入水中的祭物都被蛟龙抢去了,以后要用楝叶塞

声明:《汉诺塔的由来 汉诺塔 汉诺塔-由来及传说,汉诺塔-相关预言》为网友晃荡少年丶分享!如侵犯到您的合法权益请联系我们删除