了解河内塔的递归规则

Question

我是数据结构和算法的初学者，最近遇到了河内算法的塔。我看到一场冲突我无法在河内塔规则（递归方法）和冲突的标准方式之间找到冲突：

根据标准规则：

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

但根据递归方法：

1. 将N-1磁盘从源移到AUX。
2. 将nth磁盘从源转移到目的地。
3. 将N-1磁盘从AUX移动到目的地。

您可以看到，这两种方法的第一和第二规则之间存在区别。

Answer 1

帮助您了解第二种方法的含义，当它说将N-1磁盘从源到AUX移动时，这意味着要从源N-1次的顶部移动，然后移动顶部磁盘为AUX。因此，一个磁盘一次仍在移动，并且每次都会删除顶部磁盘。然后，nth磁盘现在是顶部，因此可以将其移至目的地。现在您可以重复步骤3。