DSA-河内塔

河内塔是一个数学难题，由三座塔（钉子）和不止一个环组成，如图所示 -

这些环的大小不同，并按升序堆叠，即较小的环位于较大的环上。这个谜题还有其他变体，其中磁盘数量增加，但塔数保持不变。

规则

任务是在不违反排列顺序的情况下将所有磁盘移动到另一个塔上。河内塔要遵循的一些规则是 -

在任何给定时间，塔之间只能移动一个磁盘。
只能删除“顶部”磁盘。
没有大磁盘可以放在小磁盘上。

以下是用三个圆盘解决河内塔谜题的动画表示。

带有 n 个圆盘的河内塔谜题至少可以在 2 个 n−1^个步骤内解决。此演示文稿显示，一个有 3 个圆盘的谜题需要 2^{3 -} 1 = 7 个步骤。

算法

要为河内塔编写算法，首先我们需要学习如何使用较少数量的磁盘（例如 1 或 2）来解决此问题→。我们用名称、源、目的地和辅助标记三座塔（仅用于帮助移动磁盘）。如果我们只有一个磁盘，那么它可以很容易地从源移动到目标挂钩。

如果我们有 2 个磁盘 -

首先，我们将较小的（顶部）磁盘移动到辅助挂钩。
然后，我们将较大的（底部）磁盘移动到目标挂钩。
最后，我们将较小的磁盘从辅助磁盘移动到目标挂钩。

所以现在，我们可以为河内塔设计一个有两个以上磁盘的算法。我们将磁盘堆栈分为两部分。最大的磁盘（第 n 个磁盘）位于一个部分中，所有其他（n-1）^个磁盘位于第二部分中。

我们的最终目标是将磁盘 n 从源移动到目标，然后将所有其他（n1）磁盘放在上面。我们可以想象以递归方式对所有给定的磁盘集应用相同的内容。

要遵循的步骤是 -

Step 1 − Move n-1 disks from source to aux Step 2 − Move n^th disk from source to dest Step 3 − Move n-1 disks from aux to dest

河内塔的递归算法可以驱动如下：

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP