1

我在维基百科中看到了这个解决河内塔的递归算法。有人可以向我解释我如何得到这个算法的递归方程吗？

递归解决方案

  • 标记钉子 A、B、C — 这些标签可能会以不同的步长移动
  • 设 n 为磁盘总数
  • 从 1（最小，最上面）到 n（最大，最下面）对圆盘进行编号

要将 n 个圆盘从桩 A 移动到桩 C：

  • 将 n-1 个圆盘从 A 移动到 B。这使得圆盘 n 单独留在钉子 A 上
  • 将圆盘 n 从 A 移动到 C
  • 将 n-1 个圆盘从 B 移动到 C，使它们坐在圆盘 n 上

以上是递归算法，要执行步骤 1 和 3，对 n-1 再次应用相同的算法。整个过程是有限数量的步骤，因为在某些时候，n = 1 时需要算法。这一步，将单个圆盘从钉 A 移动到钉 B，是微不足道的。

4

1 回答 1

2

前三步可以在一个线性时间内完成，后三步是递归的部分，那么，只需将纯文本格式的内容写成递归格式即可：

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

另一方面，因为标签并不重要并且 T(n,A,B) = T(n,B,C)=T(n,A,C)=...，我们可以去掉标签，所以方程将是？

于 2013-10-31T11:43:48.693 回答