河内塔:递归算法

Question

虽然我对理解递归没有任何问题,但我似乎无法绕过河内塔问题的递归解决方案.以下是维基百科的代码:

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;

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

Answer 1

实际上,您从中获取该代码的部分也提供了解释:

要将n个光盘从弦轴A移动到弦轴C:

1. 将n-1个光盘从A移动到B.这样就可以在光盘A上单独留下光盘#n
2. 将光盘#n从A移动到C.
3. 将n-1个光盘从B移到C,这样它们就位于光盘#n上

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

你的帖子中的代码有三个参数,除了光盘的数量:一个源挂钩,一个目标挂钩和一个临时挂钉,光盘可以存储在其间(每个大小为n - 1的光盘都适合).

递归实际上发生了两次,其中一次发生在一次之前writeln,一次发生之后.前的所述一个writeln将移动Ñ 1张光盘在临时栓,使用目的地栓的临时存储(在递归调用的参数在不同的次序) - .之后,剩余的光盘将被移动到目标钉,然后第二次递归通过将n -1塔从临时栓钉移动到光盘n上方的目标钉,推动整个塔的移动.

Answer 2

一年前,我有功能编程课程,并为该算法绘制此图.希望能帮助到你!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

3环问题已被分解为2个2环问题(1.x和3.x)

Answer 3

在http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html上对递归的河内实施有一个很好的解释.

总结一下,如果你想将底板从底座A移动到底座B,首先必须将顶部的所有较小的底板从A移动到C.然后第二个递归调用将你移动的底板移动到C在您的基础案例将单个大板从A移动到B之后返回到B.

Answer 4

当你第一次看到它时,我同意这个并不是立竿见影的,但是当你深入了解它时,它是相当简单的.

基本情况:你的塔的大小为1.所以你可以一步到位,从源头到目的地.

递归案例:您的塔的大小为n> 1.因此,您将大小为n-1的顶部塔架移动到额外的钉子(by),将尺寸为1的底部"塔"移动到目标钉,然后移动顶部塔从by到dest.

所以在一个简单的情况下,你有一个高度为2的塔:

 _|_    |     |
__|__   |     |
===== ===== =====

第一步:将顶部的2-1(= 1)塔移动到额外的钉子(中间的一个,让我们说).

  |     |     |
__|__  _|_    |
===== ===== =====

下一步:将底部光盘移动到目的地:

  |     |     |
  |    _|_  __|__
===== ===== =====

最后,将(2-1)= 1的顶部塔移动到目的地.

  |     |    _|_
  |     |   __|__
===== ===== =====

如果你考虑一下,即使塔是3或更多,总会有一个空的额外挂钉,或者所有较大圆盘的挂钉,用于在交换塔时使用的递归.