0

很抱歉问这个问题，但我没有发现任何其他现有线程有用。我不得不说我很难理解复杂的话题，也许我只是愚蠢。我对此深感抱歉。无论如何，我试图解析以下内容，但有些不对劲。

   public class tower {
  public static void move(int n, int startPole, int endPole) {
    if (n== 0){
      return;
    }
    int intermediatePole = 6 - startPole - endPole;
    move(n-1, startPole, intermediatePole);
    System.out.println("Move " +n + " from " + startPole + " to " +endPole);
    move(n-1, intermediatePole, endPole);
  }

  public static void main(String[] args) {
    move(2, 1, 3);
  }
}

我草草写了一些笔记来帮助自己解析代码：

move(2,1,3)
move(1,1,2)
n==0

--------going back up

n==0
move(1,1,2)
Move 1 from 1 to 2
move(2,1,3)
Move 2 from 1 to 3

move(2,1,3)
move(1,2,3)
n==0

-------going back up

n==0
move(1,2,3)
Move 1 from 2 to 3
move(2,1,3)
?????????? (step is missing)

第二个递归调用过早停止，我想知道我忽略了什么。

我发现迭代代码更容易理解，我写了一个基于迭代算法的递归算法。

4

2 回答 2

0 
move(2,1,3)
+--move(1,1,2)
|  +--move(0,1,3)
|  |  '--(do nothing)
|  +--print "move from 1 to 2"
|  '--move(0,3,2)
|     '--(do nothing)
+--print "move from 1 to 3"
'--move(1,2,3)
   +--move(0,2,1)
   |  '--(do nothing)
   +--print "move from 2 to 3"
   '--move(0,1,3)
      '--(do nothing)

要将n 个圆盘从a塔移动到b塔，您需要

  1. 使用塔c将顶部的n - 1 个圆盘移开。
  2. 将底部圆盘移至b塔。
  3. 将顶部移回前一个圆盘的顶部，在塔b上。

第 1 步和第 3 步是递归完成的。

/** Moves n discs from startPole to endPole */
public static void move(int n, int startPole, int endPole) {
    if (n == 0) {
        // Base case: No disk to move. Do nothing.
        return;
    }

    // Calculate the pole that is not startPole and not endPole.
    // 1 + 2 + 3 = 6
    // 6 - 1 - 2 = 3
    // 6 - 1 - 3 = 2
    // 6 - 2 - 3 = 1
    int intermediatePole = 6 - startPole - endPole;

    // Step 1: Move n-1 discs out of the way, to the intermediate pole.
    move(n-1, startPole, intermediatePole);

    // Step 2: Move the bottom disc to the destination, the end pole.
    System.out.println("Move " + n + " from " + startPole + " to " + endPole);

    // Step 3: Move the n-1 discs back on top of the previous disc, on the end pole.
    move(n-1, intermediatePole, endPole);
}
于 2013-06-15T11:07:32.837 回答
0

我怀疑你的笔记是否正确，它看起来很混乱。

当您的代码执行时，它会像这样运行：

移动（2,1,3）

转向

移动（1,1,2）

（输出）“将 2 从 1 移到 3”

移动（1,2,3）

尽管

移动（1,1,2）

转向

move(0,1,3) // 什么都不做

（输出）“将 1 从 1 移到 2”

move(0,3,2) //什么都不做

和

移动（1,2,3）

转向

move(0,2,1) // 什么都不做

（输出）“将 1 从 2 移到 3”

move(0,1,3) // 什么都不做

所以它的输出：

“将 1 从 1 移到 2”

“将 2 从 1 移到 3”

“将 1 从 2 移到 3”

令人费解的事情可能是输出中的 n。它在它的 move() 中很重要，并且只是描述了将在这个 move(n-1,...,...) 中移动的元素的总和，move( n,...,...) 和下一步移动(n-1,...,...)，不仅仅是一个移动(n,...,...) 。

于 2013-06-15T06:58:40.497 回答