不能让我的老师递归算法河内

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. 移动所有的光盘，但一到“空闲” PEG
2. 将最后一张光盘到目的地挂
3. 移动所有光盘，但一个（来自步骤1的那些）从备用挂钩到目标挂钩

因此，所有光盘已被移动到目标挂钩。

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

的一点是，步骤1和3将递归到更多的呼叫，以move，并且每个呼叫move为其k > 0打印恰好一个指令符合prinft。那么会发生什么呢是这个算法会打印出你需要采取的步骤来逐一移动光盘。

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