1. WIKI教程
2. 数据结构和算法
3. DSA - 河内塔(Tower of Hanoi)

DSA - 河内塔(Tower of Hanoi)

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

这些环具有不同的尺寸并以升序堆叠，即较小的环位于较大的环上。 这个拼图还有其他变化，其中磁盘数量增加，但塔数仍然相同。

规则 (Rules)

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

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

以下是用三个磁盘解决河内塔拼图的动画表示。

可以用最少2 ⁿ −1步骤解决具有n个盘的河内塔拼图。 此演示文稿显示具有3个磁盘的拼图已经采取2 ³ - 1 = 7步。

算法 (Algorithm)

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

如果我们有2个磁盘 -

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

所以现在，我们可以设计一个具有两个以上磁盘的Tower of Hanoi算法。 我们将磁盘堆分成两部分。 最大的磁盘（ ^第 n ^个磁盘）在一个部分中，所有其他（n-1个）磁盘在第二部分中。

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

要遵循的步骤是 -

<b class="notranslate">Step 1</b> − Move n-1 disks from <code><b class="notranslate">source</b></code> to <code><b class="notranslate">aux</b></code>
<b class="notranslate">Step 2</b> − Move n<sup>th</sup> disk from <code><b class="notranslate">source</b></code> to <code><b class="notranslate">dest</b></code>
<b class="notranslate">Step 3</b> − Move n-1 disks from <code><b class="notranslate">aux</b></code> to <code><b class="notranslate">dest</b></code>

River of Hanoi的递归算法可以如下驱动 -

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

要检查C编程中的实现， 请单击此处 。