汉诺塔

李崇冲

点击：1534 时间：2014-09-12 16:18

　　汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着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秒钟的话，等到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 – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
　　若n为奇数，按顺时针方向依次摆放 A C B。
　　⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。

　　⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。

　　⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。
　　所以结果非常简单，就是按照移动规则向一个方向移动金片：
　　如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C
　　汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。aa

城市：

称呼：

面积：

手机：

户型：

小区：

装修开工必须吉利！10秒测算您的装修吉日！

汉诺塔

相关文章

最新分享

相关问题

2018年4月26日

三月十一

装修报价

免费设计

公司加盟