无法理解我的讲师递归算法的河内塔

Question

算法如下:

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线在做什么似乎对整个功能至关重要.

Answer 1

递归算法分为三个步骤:

1. 将所有光盘移动到"备用"挂钩上
2. 将最后一张光盘移动到目标挂钩
3. 将所有光盘从备用挂钩移动到目标挂钩,但将其中一个(步骤1中的那些)移动到目标挂钩

因此,所有光盘都已移动到目标挂钩.

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

这里的关键是,步骤1和3将递归到更多的调用move,并且每次调用move针对k > 0打印一条指令符合prinft.因此,该算法将打印出您需要采取的逐步移动光盘的步骤.

实际上,该伪代码没有实现用于移动钉的算法; 它是一种向人类提供指令的算法,如果你愿意的话.