算法:河内塔算法

河内塔,是一个数学难题,由三个塔(钉)和多个环组成,如图所示 -

河内塔

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

 

规则

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

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

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

河内塔

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

 

算法

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

如果我们有2个磁盘 -

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

河内塔有两个盘的

所以现在,我们可以设计一个具有两个以上磁盘的Tower of Hanoi算法。我们将磁盘堆分成两部分。最大的磁盘(第 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**

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

Fibonacci系列通过添加两个先前的数字来生成后续数字。Fibonacci系列从两个数字开始 --F 0和F 1。F 0和F1的初始值可分别取0,1或1,1。斐波那契系列满足以下条件 -Fn = Fn- ...