Data Structures Algorithms 简明教程
Tower of Hanoi Using Recursion
Tower of Hanoi
河内塔是一个数学谜题，由三根塔（桩）和多个圆环组成，如下图所示 -
这些圆环大小不同，并且按升序堆叠，即较小的圆环放在较大的圆环上面。还有其他变种的谜题，其中磁盘的数量不断增加，但塔数保持不变。
Rules
任务是将所有磁盘移动到另一个塔，而不违反排列顺序。解决河内塔的几个规则如下 -
-
任何给定时间只能在塔之间移动一个磁盘。
-
只能移除“顶部”磁盘。
-
没有大磁盘可以放在小磁盘上。
以下是解决带有三个圆盘的河内塔谜题的动画表示。
带有 n 个磁盘的河内塔谜题可以在最少 2n−1 步中解决。此演示显示带有 3 个磁盘的谜题已经进行了 23 - 1 = 7 步。
Algorithm
要编写河内塔算法，首先我们需要学习如何解决圆盘更少的问题，例如 → 1 或 2。我们用 source 、 destination 和 aux 标记三个塔（仅帮助移动磁盘）。如果我们只有一个磁盘，则可以轻松地从源点移动到目标桩。
如果我们有 2 个磁盘 -
-
首先，我们将较小的（顶部）磁盘移动到辅助桩。
-
然后，我们将较大的（底部）磁盘移动到目标桩。
-
最后，我们将较小的磁盘从辅助桩移动到目标桩。
所以现在，我们有能力设计一个用于超过两个磁盘的河内塔算法。我们将磁盘堆栈分成两部分。最大的磁盘（第 n 个磁盘）在一部份中，所有其他 (n-1) 个磁盘在第二部分中。
我们的最终目的是将磁盘 n 从源点移动到目标点，然后将所有其他 (n1) 个磁盘放在它上面。我们可以想象以递归方式对所有给定的磁盘集应用相同的操作。
要遵循的步骤如下 -
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth 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