用 Python 解决河内塔问题

Manav Narula 2023年10月10日
用 Python 解决河内塔问题

河内塔问题是一个基本的数学难题,一开始就介绍给新程序员,以扩大他们解决问题的测验。

问题很简单,涉及三个杆。一根杆包含几个按递减顺序排列的圆盘,最大的圆盘在底部,最小的圆盘在顶部。我们必须使用第二个杆将其从第一杆转移到第三杆。

我们必须牢记某些规则。我们只能同时移动一个圆盘,并且必须在杆的顶部取出圆盘。此外,我们不能将较大的磁盘放在较小的磁盘之上。
记住所有这些,我们必须解决这个问题并计算解决它所采取的行动总数。

在本教程中,我们将介绍如何解决这个问题。我们将使用递归方法在 Python 中解决河内塔问题。

此方法将创建一个函数,该函数将根据某些条件递归调用自身以解决河内塔问题。
我们在下面的代码中实现了这个逻辑。

def ToH(n, A, B, C):
    if n == 1:
        print("Disk 1 from", A, "to", B)
        return
    ToH(n - 1, A, C, B)
    print("Disk", n, "from", A, "to", B)
    ToH(n - 1, C, B, A)


ToH(3, "A", "B", "C")

输出:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

在上面的例子中,我们使用杆 C 将三个圆盘从杆 A 移动到杆 B。

如你所见,上例中的总移动次数为 7。对于 n 个磁盘,使用此方法进行的总移动次数始终等于 2^n -1。

随着时间的推移,出现了一些其他解决方案来使用堆栈解决河内塔问题。尽管如此,还是不​​建议使用它们,因为这些方法在时间和速度方面效率很低。

作者: Manav Narula
Manav Narula avatar Manav Narula avatar

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.

LinkedIn