数据结构和算法 - 汉诺塔

数据结构和算法汉诺塔 - 使用c，C ++和Java学习数据结构和算法，从简单和简单的步骤开始，从基本到高级概念，包括概述，环境设置，算法，渐近分析，贪婪算法，分而治之，动态编程，数据结构，数组，链表，双链表，循环列表，堆栈，解析表达式，队列，优先级队列，线性，二进制，插值搜索，树，树遍历，二叉搜索树，B +，AVL，跨越，河内塔，哈希表，堆，图，深度，广度第一遍历，搜索技术，排序技术，排序算法，泡沫，合并排序算法，插入，选择，壳，快速排序，递归，斐波那契系列。

河内之塔，是一个数学难题，由三个塔(钉)和多个环组成，如描绘 :

河内塔

这些戒指的大小不同，并按升序排列，即较小的戒指位于较大的戒指上.还有其他变化的谜题，其中磁盘数量增加，但塔数仍然相同.

规则

任务是移动所有磁盘到另一个塔而不违反排列顺序.河内塔的一些规则是 :

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

以下是用三个磁盘解决河内塔之谜的动画表示.

Tower Of Hanoi

有n个磁盘的河内之塔拼图可以在最小 2 ⁿ : 1 步骤中解决.此演示文稿显示具有3个磁盘的拼图已经 2 ³ - 1 = 7 步骤.

算法

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

如果我们有2个磁盘去;

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

有两个磁盘的河内塔

现在，我们可以设计一个具有两个以上磁盘的Tower of Hanoi算法.我们将磁盘堆分成两部分.最大的磁盘(n ^th磁盘)是一部分，所有其他(n-1)磁盘都在第二部分.

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

要遵循的步骤是 :

 第1步 : 将n-1个磁盘从 源 移至  aux   第2步 : 将 th 磁盘从 来源 移至  dest   第3步 : 将n-1个磁盘从  aux  移至  dest

Tower of Hanoi的递归算法可以按以下方式驱动;

STARTProcedure 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 ProcedureSTOP