logo图片
数据结构与算法

汉诺塔

汉诺塔,是一个数学谜题,由三个塔(钉)和多个环组成,如图所示-
汉诺塔
这些戒指尺寸不同,并按升序堆叠,即较小的戒指位于较大的戒指之上。拼图还有其他变体,其中磁盘数量增加,但塔数保持不变。

规则

任务是将所有磁盘移动到另一个塔而不违反排列顺序。汉诺塔要遵循的一些规则是-
在任何给定时间,只能在塔之间移动一个磁盘。 只能移除"顶部"磁盘。 没有大磁盘可以放在小磁盘上。
以下是用三个圆盘解决汉诺塔谜题的动画演示。
汉诺塔
具有 n 个圆盘的汉诺塔谜题可以用最少 2n-1 个步骤解决。此演示文稿显示一个包含 3 个磁盘的拼图已执行 23-1 = 7 个步骤。

算法

要为汉诺塔编写算法,首先我们需要学习如何用更少的磁盘来解决这个问题,比如 → 1 或 2、我们用名称标记三个塔, sourcedestinationaux(仅用于帮助移动磁盘)。如果我们只有一个磁盘,那么它可以很容易地从源 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 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
要检查 C 编程中的实现,单击此处。

有用的视频课程

Azure Data Lake 在线培训
视频
Azure 数据湖在线培训
42 个讲座 1.5 小时
Ravi Kiran
更多详情
数据结构在线培训
视频
数据构建在线培训
141 场讲座 13 小时
Arnab Chakraborty
更多详情
Oracle Data Guard 在线培训
视频
Oracle Data Guard 在线培训
26 节课 8.5 小时
Parth Panjabi
更多详情
大数据 & Hadoop 在线培训
视频
大数据和 Hadoop 在线培训
65 节课 6 小时
Arnab Chakraborty
更多详情
汉诺塔,是一个数学谜题,由三个塔(钉)和多个环组成,如图所示-
汉诺塔
这些戒指尺寸不同,并按升序堆叠,即较小的戒指位于较大的戒指之上。拼图还有其他变体,其中磁盘数量增加,但塔数保持不变。

规则

任务是将所有磁盘移动到另一个塔而不违反排列顺序。汉诺塔要遵循的一些规则是-
在任何给定时间,只能在塔之间移动一个磁盘。 只能移除"顶部"磁盘。 没有大磁盘可以放在小磁盘上。
以下是用三个圆盘解决汉诺塔谜题的动画演示。
汉诺塔
具有 n 个圆盘的汉诺塔谜题可以用最少 2n-1 个步骤解决。此演示文稿显示一个包含 3 个磁盘的拼图已执行 23-1 = 7 个步骤。

算法

要为汉诺塔编写算法,首先我们需要学习如何用更少的磁盘来解决这个问题,比如 → 1 或 2、我们用名称标记三个塔, sourcedestinationaux(仅用于帮助移动磁盘)。如果我们只有一个磁盘,那么它可以很容易地从源 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 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
要检查 C 编程中的实现,单击此处。

有用的视频课程

Azure Data Lake 在线培训
视频
Azure 数据湖在线培训
42 个讲座 1.5 小时
Ravi Kiran
更多详情
数据结构在线培训
视频
数据构建在线培训
141 场讲座 13 小时
Arnab Chakraborty
更多详情
Oracle Data Guard 在线培训
视频
Oracle Data Guard 在线培训
26 节课 8.5 小时
Parth Panjabi
更多详情
大数据 & Hadoop 在线培训
视频
大数据和 Hadoop 在线培训
65 节课 6 小时
Arnab Chakraborty
更多详情
Python with Data Science
视频
Python与数据科学
畅销书
75 节课 13 小时
Eduonix 学习解决方案
更多详情
Mathematics for Data Science and Machine Learning using R
视频
使用 R 的数据科学和机器学习数学
64 节课 10.5 小时
Eduonix 学习解决方案
更多详情
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4