汉诺塔问题

来自计算思维百科
跳转至: 导航搜索

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

 7.4.2.png

                                          图1 汉诺塔的初始位置

不管这个传说的可信度有多大,如果仅考虑把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时,f(64)=2^64-1=18446744073709551615次。

如果每秒钟移动一次,共需多长时间呢?一年有31536000秒,则

18446744073709551615/31536000=584942417355年

这表明移完这些金片需要5849亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。因此,这个示例理论上是可计算的问题,实际上并不一定能行,这属于算法的时间复杂性问题。