河内塔只有懒惰的人才没有写过关于哈布雷的著名游戏《爱德华·卢克》。 似乎所有的封面都被撕掉了，关于该算法的其他内容不再可能添加。 但是，不，此主题隐藏了资源。 今天，特别是今天，我们将重做用于完全解决该难题的算法。 （为什么？只是为了好玩。可能在星期五。）
这篇文章致力于纪念真正的编程大师Andrei Mrrl Astrelin，他曾经向我简单，清楚地解释了这种算法。 下面的伪代码是其著作的文本。
在经典拼图中，最初订购了第一杆上的碟片。 但是我们将允许它们以任何顺序串起来。
另外，假定磁盘大小是唯一的。 我们不会坚持这种限制，并允许重复。
如果只允许这两个自由，那么难题的初始条件可以解释为一个数组（磁盘是数字），任务归结为需要对该数组进行排序的事实。
我们（几乎）不会改变的其余条件：
- 我们有两个辅助极点（一对空数组）。
- 我们可以一次转移一张光盘。
- 仅将较小的磁盘放置到较大的磁盘中（由于我们允许使用相同大小的磁盘，因此您也可以将移动的磁盘放在顶部的相同大小的磁盘上）。
- 我们有权将便携式磁盘与仅顶部磁盘（即，所有3个阵列都是堆栈）进行比较。
我们的任务：采用经典的递归拼图算法...
def hanoi(n, source, helper, target): if n > 0: hanoi(n - 1, source, target, helper) if source: target.append(source.pop()) hanoi(n - 1, helper, source, target)
...并将其转换为排序！
实际上，从我们允许磁盘大小的初始混乱和重复这一事实出发，从根本上没有改变。 基本上，该问题以相同的经典递归方式解决。 要了解的最重要的一点是，所有磁盘移动都分为几个阶段，每个阶段都是一个经典的微型河内。
也就是说，在每个阶段，我们不会考虑所有可用磁盘，而只会考虑满足旧条件的所有磁盘。 通过经典对这一小集合进行排序后，我们将使系统的总体状态更接近经典难题。 然后，我们再次获取与经典磁盘对应的磁盘集，并再次应用众所周知的算法。 并且此集合将比上一步更大！ 因此，我们重复进行直到所有极上的所有磁盘突然变得不同于经典状态。
最初违反的系统（由于磁盘未按输入顺序排序）在每次迭代中都可以自我修复。
至于重复的解决，这根本没有关系。 因为连续的相同磁盘，我们只是作为一个磁盘移动。
演算法
我们称列
A ，
B ，
C （开头的
A为非空）。
我们介绍操作：
A- >
C （）-将一个磁盘从
A移到
C。top（A） ，
top（C） -上部磁盘
A或
C的大小
。 如果该
列为空，则此大小=
MaxInt 。
B- >
C （
K ）-将所有大小小于
K的磁盘从
B移到
C （如果上部磁盘
A和
C不小于
K，则可以这样做）。
swap （）-重新排列
B和
C列（或重命名它们-我们不在乎磁盘在哪里）。
while （
A ）-循环直到
A为空。
然后，以下算法起作用：
©
Mrrl难点
在最坏的情况下，对于传统算法，排序往往会增加时间复杂度，尽管简单而优雅，但同时效率却最高。 至于最佳和平均水平，我觉得很难假设。
至于内存，可以说如果使用递归，那么成本将是相对应的。
实作
我没有用Python编写自己的版本（我将在以后做）。 但是，在下面的“链接”部分中，我发布了一些链接，您可以在其中看到不同语言的实现。 Java中特别有趣的选项。 作者没有将解决难题的众所周知的递归方法作为基础，而是建立了最短的路径树。 如果您以“河内之塔”的形式编写排序，则大概是最有效的解决方案。
算法特征
参考文献
河内塔实现：
C ，
Java，C ++，Python ，
Python 。
系列文章：
在AlgoLab应用程序中，此排序现在可用。 尽管它属于按插入排序的类别，但由于算法的浪费，它位于“其他排序”部分。 还有一个限制-排序数组中的数字只能是1到5（由于磁盘渲染困难）。 其他数字仍将被这些数字代替。
数组的大小也有限制-不得超过20个元素。 这样做完全是出于您自己的利益-如果您选择的数组太大，则可能必须将其分类到很老的年龄。
本文是在EDISON Software（一家专业开发智慧城市照明并维护Python网站的公司）的支持下撰写的。