Data Structures Algorithms 简明教程
Tower of Hanoi Using Recursion
Tower of Hanoi
河内塔是一个数学谜题，由三根塔（桩）和多个圆环组成，如下图所示 -
Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −
这些圆环大小不同，并且按升序堆叠，即较小的圆环放在较大的圆环上面。还有其他变种的谜题，其中磁盘的数量不断增加，但塔数保持不变。
These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.
Rules
任务是将所有磁盘移动到另一个塔，而不违反排列顺序。解决河内塔的几个规则如下 -
The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −
-
Only one disk can be moved among the towers at any given time.
-
Only the "top" disk can be removed.
-
No large disk can sit over a small disk.
以下是解决带有三个圆盘的河内塔谜题的动画表示。
Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.
带有 n 个磁盘的河内塔谜题可以在最少 2n−1 步中解决。此演示显示带有 3 个磁盘的谜题已经进行了 23 - 1 = 7 步。
Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.
Algorithm
要编写河内塔算法，首先我们需要学习如何解决圆盘更少的问题，例如 → 1 或 2。我们用 source 、 destination 和 aux 标记三个塔（仅帮助移动磁盘）。如果我们只有一个磁盘，则可以轻松地从源点移动到目标桩。
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.
如果我们有 2 个磁盘 -
If we have 2 disks −
-
First, we move the smaller (top) disk to aux peg.
-
Then, we move the larger (bottom) disk to destination peg.
-
And finally, we move the smaller disk from aux to destination peg.
所以现在，我们有能力设计一个用于超过两个磁盘的河内塔算法。我们将磁盘堆栈分成两部分。最大的磁盘（第 n 个磁盘）在一部份中，所有其他 (n-1) 个磁盘在第二部分中。
So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.
我们的最终目的是将磁盘 n 从源点移动到目标点，然后将所有其他 (n1) 个磁盘放在它上面。我们可以想象以递归方式对所有给定的磁盘集应用相同的操作。
Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.
要遵循的步骤如下 -
The steps to follow are −
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河内塔的递归算法可以驱动如下 -
A recursive algorithm for Tower of Hanoi can be driven as follows −
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