河内塔:递归算法 [英] Tower of Hanoi: Recursive Algorithm

问题描述

尽管我对递归的理解没有任何问题，但我似乎无法围绕河内塔问题的递归解决方案.这是维基百科的代码:

Although I have no problem whatsoever understanding recursion, I can't seem to wrap my head around the recursive solution to the Tower of Hanoi problem. Here is the code from Wikipedia:

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

我理解基本情况和将问题分解成小块直到您能够移动单个磁盘的概念.但是，我无法弄清楚非基本情况下的两个递归调用如何协同工作.也许有人可以帮助我?谢谢.

I understand the base case and the concept of breaking the problem into smaller pieces until you are able to move a single disk. However, I can't figure out how the two recursive calls in the non-base case work together. Perhaps someone can help me out? Thanks.

推荐答案

实际上，部分来自哪里你拿了那个代码也提供了一个解释:

Actually, the section from where you took that code offers an explanation as well:

将 n 个圆盘从挂钉 A 移动到挂钉 C:

To move n discs from peg A to peg C:

1. 将 n−1 个圆盘从 A 移到 B.这将圆盘 #n 单独留在挂钉 A 上
2. 将光盘 #n 从 A 移到 C
3. 将 n-1 个圆盘从 B 移到 C，使它们位于圆盘 #n 上

很明显，您首先必须移除 n − 1 张光盘才能访问 n 的光盘.并且您必须先将它们移动到另一个钉子上，而不是您希望整个塔出现的位置.

It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. And that you have to move them first to another peg than where you want the full tower to appear.

您帖子中的代码除了光盘数量外还有三个参数:源挂钩、目的地挂钩和临时挂钩之间可以存储哪些光盘(每个大小为 n - 1 的光盘都适合).

The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).

递归实际上发生了两次，一次在 writeln 之前，一次在之后.writeln 之前的那个会将 n − 1 个磁盘移动到临时挂钉上，使用目标挂钉作为临时存储(递归调用中的参数顺序不同).之后，剩余的圆盘将被移动到目标桩，然后第二次递归强制整个塔的移动，通过将 n - 1 个塔从临时桩移动到目标桩，上面光盘 n.

The recursion happens actually twice, there, once before the writeln, once after. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.

这篇关于河内塔:递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！