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)

2 番目の再帰呼び出しが途中で停止し、見落としていることを知りたいと思いました。

反復コードの方がはるかに理解しやすいことがわかり、反復アルゴリズムに基づいて再帰アルゴリズムを作成しました。

4

2 に答える 2

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,...,...) と next move(n-1,...,...) だけでなく、 move(n,...,...) 。

于 2013-06-15T06:58:40.497 に答える
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 に答える