2

注意：我了解递归解决方案；但我看不到代码是如何实现的，因为我无法按照代码执行的逐步进行。

我很难理解河内塔的递归循环。我已经评论并尝试了各种策略来查看程序是如何运行的，但我似乎无法掌握循环是如何运行的以及环是如何被引导的。

  def move(rings, from, destination, other)
    if rings == 1
      ring = from.pop
      p "Move ring #{ring} from #{from} to #{destination}"
      destination.push ring
    else
      move(rings-1, from, other, destination)
      move(1, from, destination, other)
      move(rings-1, other, destination, from)
    end
  end

这是输出：

"Move ring 1 from a to c"
"Move ring 2 from a to b"
"Move ring 1 from c to b"
"Move ring 3 from a to c"
"Move ring 1 from b to a"
"Move ring 2 from b to c"
"Move ring 1 from a to c"

我查看了各种解释，但是，我没有看到解释循环是如何执行的。例如，我不明白为什么在环是偶数的情况下，第一步将环 1 从 a 放置到 b，而对于所有奇数环，它是从 a 到 c，如上所示。

我理解解决方案背后的逻辑，为了在使用辅助挂钩时将 n 个环移动到目的地，需要您首先将 n-1 个环移动到辅助挂钩，然后将第 n 个环移动到目的地并重复第一个程序，再次。但是，我不确定放置方向是如何变化的，例如，当上面对 move 方法的调用似乎没有提到 c 到 b 时，我看不到块是如何从 c 到 b 的。

提前感谢您的时间和帮助。

此外，如果您对帮助跟踪 Ruby 中的代码执行过程有任何建议，请告诉我。我很想听听您对如何解决不确定事情如何执行的实例的一些见解。

渴望听到你的答案:)

4

1 回答 1

6

河内塔是分治算法的一个很好的例子。您有一种算法，它理所当然地认为它可以将所有元素从源移动到目标，方法是将除最后一个之外的所有元素移动到备用，然后将最后一个从源移动到目标，因此将所有元素从备用移动到目标。

每个不是基本情况的 move 调用都会以指数方式再分成 2 个调用，直到达到基本情况。你3盘游戏的痕迹，只考虑第一部分（移动中间元素之前）是：

move(3, source, dest, spare)
move(2, source, spare, dest)
move(1, source, dest, spare)

它在哪里输出“将环 1 从源移动到备用”

这里的技巧是传递的参数（堆栈）对于不同的级别具有不同的角色。对于 2. 级别，目的地是 3. 级别备用。当突然从备用移动到目的地时，源被用作备用，但该功能并不关心这一点。它只是洗牌，直到达到基本情况。n 盘有 2^n-1 次移动（基本情况命中）。

递归在返回之前完成第二层，然后第 3 层开始另一个 2 层，在移动它的中间之后，从备用移动到目标。

提示：您应该添加一个跟踪文本，例如在开头添加“entering 3, a, c, b”，在末尾添加“exiting 3, a, c, b”。这应该让您很好地了解完成了多少次递归以及它是如何完成的。

于 2013-08-21T22:26:41.913 回答