<< 递归基础斐波那契数列 >>

汉诺塔

汉诺塔，是一个数学谜题，由三个塔（钉）和多个环组成，如图所示-

这些戒指尺寸不同，并按升序堆叠，即较小的戒指位于较大的戒指之上。拼图还有其他变体，其中磁盘数量增加，但塔数保持不变。

规则

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

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

以下是用三个圆盘解决汉诺塔谜题的动画演示。

具有 n 个圆盘的汉诺塔谜题可以用最少 2ⁿ-1 个步骤解决。此演示文稿显示一个包含 3 个磁盘的拼图已执行 2³-1 = 7 个步骤。

算法

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

如果我们有 2 个磁盘-

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

所以现在，我们可以为具有两个以上磁盘的汉诺塔设计一种算法。我们将磁盘堆栈分为两部分。最大的磁盘 (n ^th 个磁盘) 在一个部分中，所有其他 (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

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

有用的视频课程

视频

Azure 数据湖在线培训

42 个讲座 1.5 小时

Ravi Kiran

更多详情

视频

数据构建在线培训

141 场讲座 13 小时

Arnab Chakraborty

更多详情

视频

Oracle Data Guard 在线培训

26 节课 8.5 小时

Parth Panjabi

更多详情

视频

大数据和 Hadoop 在线培训

65 节课 6 小时

Arnab Chakraborty

更多详情

汉诺塔，是一个数学谜题，由三个塔（钉）和多个环组成，如图所示-

这些戒指尺寸不同，并按升序堆叠，即较小的戒指位于较大的戒指之上。拼图还有其他变体，其中磁盘数量增加，但塔数保持不变。

规则

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

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

以下是用三个圆盘解决汉诺塔谜题的动画演示。

具有 n 个圆盘的汉诺塔谜题可以用最少 2ⁿ-1 个步骤解决。此演示文稿显示一个包含 3 个磁盘的拼图已执行 2³-1 = 7 个步骤。

算法

如果我们有 2 个磁盘-

我们的最终目标是将磁盘 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

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

有用的视频课程

视频

Azure 数据湖在线培训

42 个讲座 1.5 小时

Ravi Kiran

更多详情

视频

数据构建在线培训

141 场讲座 13 小时

Arnab Chakraborty

更多详情

视频

Oracle Data Guard 在线培训

26 节课 8.5 小时

Parth Panjabi

更多详情

视频

大数据和 Hadoop 在线培训

65 节课 6 小时

Arnab Chakraborty

更多详情

视频

Python与数据科学

畅销书

75 节课 13 小时

Eduonix 学习解决方案

更多详情

Mathematics for Data Science and Machine Learning using R

视频

使用 R 的数据科学和机器学习数学

64 节课 10.5 小时

Eduonix 学习解决方案

更多详情

<< Python 语法 Python 变量 >>

找工作要求35岁以下，35岁以上的程序员都干什么去了？

长久以来，一直有一个问题困扰着技术人——如何打破“程序员的35岁职业魔咒”，这一天迟早会到来，或早或晚。

或许是选错了行业，程序员薪水虽高，但光鲜的外表下，背后的苦衷只有自己知道。三十多岁本该是一个人事业的黄金期，但技术变化日新月异，行业竞争异常残酷，对一个企业来说，永远有比你更年轻、劳动成本更低的人可以选择，这让你的中年危机提前到来。破局的智慧可以看看这本书！>>

<< 递归基础斐波那契数列 >>

昵称：邮箱：