c - 河内塔迭代与 n > 3 钉

Question

3 个钉子（或杆，或任何你称它们的名称）的迭代算法是重复以下两点：
1. 将最小的圆盘向右/向左移动（如果奇数/偶数）
2. 在不触及最小圆盘的情况下向左移动一次

我的问题是 - 对于 n > 3 钉有类似的算法吗？

我在互联网上找不到这个（至少是迭代的）。我一个人什么都想不出来。上面的算法不起作用——它无限地移动磁盘。

我知道我之前曾发布过 2 种相关问题，但您不太欢迎它们，所以在您投反对票之前 - 只需在评论中写下我，以便我自己研究更多信息，我将删除此线程。

Answer 1

具有 n > 1 个磁盘的 3-peg Hanoi 问题的一般递归算法（n==1 的情况很简单）是：

1. 将 n-1 个磁盘从源 peg 移动到第三个 peg（不是源或目标的那个）
2. 将最大的磁盘移动到目标挂钩。
3. 将 n-1 个磁盘从第三个钉子移到目标钉子上。

超过 3 个钉子时，算法是相同的。只需将“第三个挂钩”替换为“任何未使用的挂钩”即可。

请注意，该算法不使用“左移”或“右移”之类的术语。

正如@nhahtdh 在评论中指出的那样，任何递归算法都可以通过标准方式转换为迭代算法。

Answer 2

来自维基百科关于河内塔的文章的回答：没有非暴力算法可以找到可证明的最优解，尽管有一种算法可能是最优的。

尽管三钉版本具有如上所述的简单递归解决方案，但对于具有四钉的河内塔问题（称为雷夫之谜）的最优解，更不用说更多钉，仍然是一个悬而未决的问题。这是一个很好的例子，说明如何通过稍微放松其中一个问题约束，使一个简单的、可解决的问题变得更加困难。