汉诺塔
汉诺塔问题由法国数学家爱德华·卢卡斯于1883年提出。他的灵感是一个与印度寺庙有关的传说,相传这座寺庙里的年轻修行者试图解决这个难题。起初,修行者有3根柱子和64个依次叠好的金盘子,下面的盘子大,上面的盘子小。修行者的任务是将64个叠好的盘子从一根柱子移动到另一根柱子,同时有两个重要的限制条件:每次只能移动一个盘子,并且大盘子不能放在小盘子之上。修行者夜以继日地移动盘子(每一秒移动一个盘子),试图完成任务。根据传说,如果他们完成这项任务,整座寺庙将倒塌,整个世界也将消失。
尽管这个传说非常有意思,但是并不需要担心世界会因此而毁灭。要正确移动64个盘子,所需的步数是
。根据每秒移动一次的速度,整个过程大约需要584 942 417 355年!显然,这个谜题并不像听上去那么简单。
下图展示了一个例子,这是在将所有盘子从第一根柱子移到第三根柱子的过程中的一个中间状态。注意,根据前面说明的规则,每一根柱子上的盘子都是从下往上由大到小依次叠起来的。如果你之前从未求解过这个问题,不妨现在就试一下。不需要精致的盘子和柱子,一堆书或者一叠纸就足够了。
image.png
def moveTower(height,fromPole, toPole, withPole):
if height >= 1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)
def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)
moveTower(2,"A","B","C")
参考资料
网友评论