4.10.河内塔游戏

河内塔是由法国数学家爱德华·卢卡斯在 1883 年发明的。他的灵感来自一个传说，有一个印度教寺庙，将谜题交给年轻的牧师。在开始的时候，牧师们被给予三根杆和一堆 64 个金碟，每个盘比它下面一个小一点。他们的任务是将所有 64 个盘子从三个杆中一个转移到另一个，有两个重要的约束。它们一次只能移动一个盘子，并且它们不能在较小的盘子顶部上放置更大的盘子。牧师日夜不停每秒钟移动一块盘子。当他们完成工作时，传说，寺庙会变成灰尘，世界将消失。

虽然传说是有趣的，你不必担心世界不久的将来会消失。移动 64 个盘子的塔所需的步骤数是 2^64 -1 = 18,446,744,073,709,551,615264-1 = 18,446,744,073,709,551,615。以每秒一次的速度，即584,942,417,355584,942,417,355 年！。

Figure 1 展示了在从第一杆移动到第三杆的过程中的盘的示例。请注意，如规则指定，每个杆上的盘子都被堆叠起来，以使较小的盘子始终位于较大磁盘的顶部。如果你以前没有尝试过解决这个难题，你现在应该尝试下。你不需要花哨的盘子，一堆书或纸张都可以。

Figure 1

我们如何递归地解决这个问题？我们的基本情况是什么？让我们从下到上考虑这个问题。假设你有一个五个盘子的塔，在杆一上。如果你已经知道如何将四个盘子移动到杆二上，那么你可以轻松地将最底部的盘子移动到杆三，然后再将四个盘子从杆二移动到杆三。但是如果你不知道如何移动四个盘子怎么办？假设你知道如何移动三个盘子到杆三;那么很容易将第四个盘子移动到杆二，并将它们从杆三移动到它们的顶部。但是如果你不知道如何移动三个盘子呢？如何将两个盘子移动到杆二，然后将第三个盘子移动到杆三，然后移动两个盘子到它的顶部？但是如果你还不知道该怎么办呢？当然你会知道移动一个盘子到杆三足够容易。这听起来像是基本情况。

这里是如何使用中间杆将塔从起始杆移动到目标杆的概要：

1. 使用目标杆将 height-1 的塔移动到中间杆。

2. 将剩余的盘子移动到目标杆。

3. 使用起始杆将 height-1 的塔从中间杆移动到目标杆。

只要我们遵守规则，较大的盘子保留在栈的底部，我们可以使用递归的三个步骤，处理任何更大的盘子。上面概要中唯一缺失的是识别基本情况。最简单的河内塔是一个盘子的塔。在这种情况下，我们只需要将一个盘子移动到其最终目的地。 一个盘子的塔将是我们的基本情况。 此外，上述步骤通过在步骤1和3中减小塔的高度，使我们趋向基本情况。Listing 1 展示了解决河内塔的 Python 代码。

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)

Listing 1

请注意，Listing 1 中的代码与描述几乎相同。算法的简单性的关键在于我们进行两个不同的递归调用，一个在第 3 行上，另一个在第 5 行。在第 3 行上，我们将初始塔上的底部圆盘移动到中间。下一行简单地将底部盘移动到其最终的位置。然后在第 5 行上，我们将塔从中间杆移动到最大盘子的顶部。当塔高度为 0 时检测到基本情况; 在这种情况下不需要做什么，所以 moveTower 函数简单地返回。关于以这种方式处理基本情况的重点是，从 moveTower 简单地返回以使 moveDisk 函数被调用。

函数 moveDisk，如 Listing 2 所示，非常简单。它所做的就是打印出一个盘子从一杆移动到另一杆。 如果你输入并运行 moveTower 程序，你可以看到它给你一个非常有效的解决方案。

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

Listing 2

现在你已经看到了 moveTower 和 moveDisk 的代码，你可能会想知道为什么我们没有明确记录什么盘子在什么杆上的数据结构。这里有一个提示：如果你要明确地跟踪盘子，你会使用三个 Stack 对象，每个杆一个。 答案是 Python 提供了我们需要调用隐含的栈。