4

算法如下：

Algorithm move(k, from, to, spare)
if k >0 then
move(k−1, from, spare, to)
printf (”move top disc from %d to %d\n”,
from, to)
move(k−1, spare, to, from)

k 是磁盘的数量（http://en.wikipedia.org/wiki/Tower_of_Hanoi）。我了解递归，我只是不明白这是如何工作的，任何人都可以理解这一点吗？

抱歉在这里的描述含糊不清，只是我对正在发生的事情的理解也很模糊-我不知道 printf 行在做什么，这似乎对整个功能至关重要。

4

1 回答 1

5

递归算法分为三个步骤：

  1. 将除一张以外的所有光盘移至“备用”挂钩
  2. 将最后一张光盘移动到目标挂钩
  3. 将除一张以外的所有光盘（步骤 1 中的光盘）从备用钉移动到目标钉

因此，所有圆盘都已移动到目标挂钩。

步骤 1 和 3 是伪代码中的两个递归move(k-1, ...)调用。步骤 2 由printf.

这里的要点是，第 1 步和第 3 步将递归到对 的更多调用move，并且每次调用都move将k > 0打印一个带有prinft. 所以将会发生的是，这个算法将打印出你需要采取的步骤来最终详细地移动光盘，一个接一个。

实际上，这个伪代码没有实现移动钉子的算法。如果您愿意，它是一种向人类提供指令的算法。

于 2011-04-11T18:50:58.693 回答