克罗克福德的河内职能(摘自"The Good Parts") [英] Crockford's hanoi function (from "The Good Parts")

问题描述

此刻，我正在阅读道格拉斯·克罗克福德(Douglas Crockford)的书，河内塔的功能让我有些头疼.即使将内容记录到控制台，我也无法真正理解正在发生的事情.这是我添加的功能:

At the moment I'm reading Douglas Crockford's book, and the towers of hanoi function is a bit over my head. Even with logging stuff to the console I wasn't able to really understand what's going on. Here's the function with my additions:

var hanoi = function (disc, src, aux, dst) {
  console.log(disc);
  console.log(src, dst);    
  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
    console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

结果如下:

3
Src Dst
2
Src辅助
1
Src Dst
0
Src辅助
将光盘1从Src移至Dst
0
辅助Dst
将光盘2从Src移至Aux
1
Dst Aux
0
Dst Src
将光盘1从Dst移至Aux
0
Src辅助
将光盘3从Src移至Dst
2
辅助Dst
1
辅助Src
0
辅助Dst
将光盘1从Aux移到Src
0
Dst Src
将光盘2从Aux移至Dst
1
Src Dst
0
Src辅助
将光盘1从Src移至Dst
0
辅助Dst

3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
Move disc 1 from Src to Dst
0
Aux Dst
Move disc 2 from Src to Aux
1
Dst Aux
0
Dst Src
Move disc 1 from Dst to Aux
0
Src Aux
Move disc 3 from Src to Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
Move disc 1 from Aux to Src
0
Dst Src
Move disc 2 from Aux to Dst
1
Src Dst
0
Src Aux
Move disc 1 from Src to Dst
0
Aux Dst

我很早就迷路了.在结果的第6行，它如何从Src Aux返回Src Dst?

And I'm lost at an early point. At line 6 of the results, how can it go back from Src Aux to Src Dst?

当函数仅使用"disc-1"进行调用时，光盘数量达到0后又如何增加?

And how can the number of discs go up again once it has reached 0, when the function is only calling itself using "disc - 1"?

推荐答案

之所以会出现混淆，是因为输出的文本表示形式不是理解递归的最佳方法.光盘的数量不是上升"，而是hanoi(1)一旦完成hanoi(0)就会继续运行.

The confusion arises because the text representation of the output isn't the best way to understand recursion. The number of discs isn't "going up", rather it's hanoi(1) that continues to run once hanoi(0) is done.

我在 JSBin 中创建了一个修改后的示例，该示例以(某种)更漂亮的方式打印输出与空格.只有动作"实际上会做任何事情，其余各行只是递归调用，以解决较小的子问题，以便稍后解决整个问题.

I've created a modified example at JSBin that prints the output in a (somewhat) prettier way with spaces. Only the "moves" actually do anything, the rest of the lines are just recursive calls to solve smaller sub-problems in order to tackle the entire problem later.

您可能还想看看这个 Java小程序以图形方式显示算法的工作原理-可能更容易理解.

You might also want to have a look at this Java applet that graphically shows how the algorithm works - this might be easier to understand.

这篇关于克罗克福德的河内职能(摘自"The Good Parts")的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！