递归算法如何适用于河内塔？

Question

这是我解释递归的书中的代码.问题是我不明白该计划采取的步骤:

var hanoi = function(disc,src,aux,dst) {
    if (disc > 0) {
        hanoi(disc - 1,src,dst,aux);
        document.write("Move disc " + disc + " from " + src + " to " + dst + "<br />");
        hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

这是输出的读取方式:

Move disc 1 from src to dst
Move disc 2 from src to aux
Move disc 1 from dst to aux
Move disc 3 from src to dst
Move disc 1 from aux to src
Move disc 2 from aux to dst
Move disc 1 from src to dst

有人可以一步一步地解决这个问题吗？这对我很有帮助.

Answer 1

对于河内塔来说,最简单的解决方案可能是这样的:

要将x光盘从弦轴A 移动到弦轴C,请使用弦轴B作为"辅助"弦轴:

1. x-1使用挂钩C作为辅助挂钩将圆盘从挂钉A 移动到挂钉B.
2. 将第x's光盘从弦轴A移动到弦轴C(不需要辅助弦轴,因为您只移动一张光盘).
3. x-1使用挂钉A作为辅助挂钩将光盘从挂钉B 移动到挂钉C.

请注意,要移动x光盘,您必须移动x-1光盘.您可以使用相同的功能来移动这些x-1光盘,只需切换哪个挂钩是源,目标和辅助挂钩.这就是使河内之塔成为递归的常见例子的原因,这就是你需要在问题中看到的那种模式,以便让递归适合你.它x-1当然不一定是"移动光盘"......它可能就像"列出这个子文件夹".树(如带有子文件夹的目录等)是递归闪耀的另一个地方.和其他工作一样,为了对项目执行任务,您可能需要对子项目执行相同的工作.

现在,为了获得有用的递归,您需要一个"基本情况" - 递归将停止的条件.如果不这样做,代码将永远运行(或至少直到内存耗尽或溢出调用堆栈).这里的基本情况发生在x == 0(因为移动0盘意味着你什么也不做,因为if功能的周围).它也可能是x == 1因为那时你不必递归,但if每次hanoi调用之前的额外增加会产生一些噪音(递归解决方案的主要好处是它的简单性).无论如何,当x == 0函数返回时没有做任何事情.调用它的函数(有x == 1)现在可以继续执行它的操作 - 在这种情况下,说"将光盘1从src移动到dest",然后hanoi在args切换的情况下再次调用该函数.

流程有点像这样:

hanoi(3, src, aux, dest)
  hanoi(2, src, dest, aux)
    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "Move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

    print "Move 2 from src to aux"

    hanoi(1, dest, src, aux)
      hanoi(0, dest, aux, src)        // no op
      print "move 1 from dest to aux"
      hanoi(0, src, dest, aux)        // no op

  print "move 3 from src to dest"

  hanoi(2, aux, src, dest)
    hanoi(1, aux, dest, src)
      hanoi(0, aux, src, dest)        // no op
      print "Move 1 from aux to src"
      hanoi(0, dest, aux, src)        // no op

    print "Move 2 from aux to dest"

    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op