汉诺塔与数学递归法

橘子网 4,580 1

相信很多家长给孩子买过汉诺塔玩,其实他还是有一定难度,想要玩好汉诺塔,不得不讲讲“汉诺塔与数学递归法”。

汉诺塔与数学递归法

汉诺塔(Tower of Hanoi,又称河内塔)问题是一个源于印度古老传说的益智玩具。

汉诺塔与数学递归法

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

接下来,我们来研究一下汉诺塔问题到底有什么规律!当然,64片黄金圆盘不是一个好的出发点,数量太大了,没移动几次就晕头转向了。我们从简单的出发,比如三个圆盘的“三层汉诺塔”。

汉诺塔与数学递归法

经过尝试,我们发现,最少7次可以解决三层汉诺塔的问题。如下图所示:

第一步:

汉诺塔与数学递归法

第二步:

汉诺塔与数学递归法

第三步:

汉诺塔与数学递归法

第四步:

汉诺塔与数学递归法

第五步:

汉诺塔与数学递归法

第六步:

汉诺塔与数学递归法

第七步:

汉诺塔与数学递归法

我们仔细回顾整个过程,会发现似乎有些步骤是在重复相似的事情。如果你有这种直觉,恭喜你,你快要发现真理了!

我们经过比较发现:

第一个步骤至第三个步骤,移动三次,将两个较小的圆盘从第一根柱子移到了第二根柱子;

第五个步骤至第七个步骤,移动三次,将两个较小的圆盘从第二根柱子移到了第三根柱子。

虽然移动的目标柱子不同,但动作是非常相似的。而这种“移动两个圆盘”的动作,其实就是“两层汉诺塔”的解法。

我们再看“六层汉诺塔”。六层的汉诺塔可以通过下面三个步骤得到:

第一步:将五个较小的圆盘从第一根柱子移到第二根柱子。

汉诺塔与数学递归法

第二步:将六个圆盘中最大的那个从第一根柱子移到第三根柱子。

汉诺塔与数学递归法

第三步:将五个较小的圆盘从第二根柱子移到第三根柱子。

汉诺塔与数学递归法

聪明的你估计已经想到问题的关键了。第一个步骤和第三个步骤其实无非就是“五层汉诺塔”的解法。为了解决“六层汉诺塔”,只要解决“五层汉诺塔”就可以了。而且,这就是移动此书最少的解法。因为要把最大的圆盘从第一根柱子移到第三根柱子上(第二个步骤),就必须将上面较小的五个圆盘都先移到第二根柱子上。

同样的思路,我们可以解决“五层汉诺塔”。

第一步:将四个较小的圆盘从第一根柱子移到第二根柱子。

第二步:将五个圆盘中最大的那个从第一根柱子移到第三根柱子。

第三步:将四个较小的圆盘从第二根柱子移到第三根柱子。

“四层汉诺塔”、“三层汉诺塔”……都是相类似的解法。

通过以上的尝试和归纳,我们可以总结出“n层汉诺塔”的解法。我们假设“n层汉诺塔”所需的最少移动次数为H(n)。我们可以得到:

汉诺塔与数学递归法

我们计算一下“六层汉诺塔”的移动次数,看看可以发现什么?

汉诺塔与数学递归法

数感足够好的读者朋友应该已经察觉到数字的规律了,即:

汉诺塔与数学递归法

哇,一个非常漂亮的式子!

我们回头看印度的传说,64层汉诺塔,这个结果就是264-1。大部分人可能对这个数字没什么概念。

假如每秒钟移动一次,完成这个64层的汉诺塔最少需多长时间呢?一个平年365天有31536000秒,闰年366天有31622400秒,平均每年31556952秒,计算一下:18446744073709551615秒。这表明,移动完这些黄金盘片需要5845.54亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为137亿年。假如真的过了5845.54亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

总结一下整个思考过程:我们在解决汉诺塔问题时,先找了最简单的“三层汉诺塔”,发现某些动作是“重复”的;再扩展到“六层汉诺塔”,发现六层汉诺塔的问题可以反推到五层汉诺塔,进而反推到四层、三层问题;然后总结得到一般性的规律;最后进一步简化我们发现的规律,得到一个极为简单的解析式。这就是将数学递归法(recursion)应用到汉诺塔中,将复杂的问题简单化,非常开发孩子数学思维的训练。

上一篇:

下一篇:

相关阅读

分享