汉诺塔与递归

IamZS 141 0

汉诺塔

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a smaller disk.

根据维基百科的定义,汉诺塔是一个数学游戏。它包括三根杆子和大小不一的圆盘,这些圆盘中间打孔使得可以将其摆放在任何一根杆子上。游戏的初始化状态为:将这些圆盘按照大的在下、小的在上依次摆放在其中一根杆子上,形成锥状。游戏的目标就是将这根杆子上的所有圆盘移到另一根杆子上,但必须遵循以下条件:一、一次只能移动一个圆盘;二、每次只能移动最上方的圆盘(也就是不能从下面抽),可以将其放置在另一堆圆盘上或者空的杆子上;三、任何时候都不允许大的圆盘放在小的圆盘上。

汉诺塔与递归

这游戏是由一位法国数学家在 1883 年发明的。与之相关的是印度的一个古老传说,在某个神庙中也有三根柱子,其中一根柱子上从上往下按照大小摞着 64 个金色圆盘,从创世之日起按照上述规则移动圆盘。据说,当这些圆盘被全部移到另一根柱子上时,世界将会毁灭。而根据规律,最少需要移动 264 - 1 次,假设每秒移动一次需要 5850 亿年,这是当今宇宙存在时间的 42 倍。

那么,将其进行抽象,如何用递归的算法来实现呢?

无论盘子数量有多少,都可以将其看成上面的(n - 1)个盘子和最底下的 1 个盘子这两个盘子。

首先:把 (n - 1) 移到缓冲区;

然后:把 1 移到终点;

最后:把缓冲区的 (n - 1) 移到终点。

用 Python 来实现就是:

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b)
        move(1, a, b, c)
        move(n-1, b, a, c)

汉诺塔与递归

图:知乎用户 @moqiuhen

发表评论
表情 图片 链接 代码