10

これは私が再帰を説明している本のコードです。問題は、プログラムが実行する手順がわからないことです。

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

誰かがこれを段階的に分解できますか？それは私にとって非常に役に立ちます。

4

2 に答える 2

14

おそらく、ハノイの塔の最も簡単な解決策は次のように機能します。

xペグ B を「補助」ペグとして使用して、ディスクをペグ A からペグ C に移動するには:

  1. x-1ペグ C を補助ペグとして使用して、ディスクをペグ A からペグ B に移動します。
  2. 1 番目のディスクをペグ A からペグ C に移動xします (ディスクを 1 つだけ移動するため、補助ペグは必要ありません)。
  3. x-1ペグ A を補助ペグとして使用して、ディスクをペグ B からペグ C に移動します。

xディスクを移動するには、ディスクを移動する必要があることに注意してくださいx-1。同じ機能を使用してこれらのx-1ディスクを移動し、どのペグがソース、宛先、および補助ペグであるかを切り替えるだけです。これが、ハノイの塔が再帰の一般的な例である理由であり、再帰を機能させるために問題で確認する必要のある種類のパターンです。もちろん、「ディスクを移動する」である必要はありませんx-1...「このサブフォルダーをリストする」のようなものである可能性があります。ツリー (サブフォルダーを含むディレクトリなど) は、再帰が役立つもう 1 つの場所です。他のジョブと同様に、アイテムに対してジョブを実行するために、サブアイテムに対して同じジョブを実行する必要がある場合があります。

さて、有用な再帰を行うには、「基本ケース」、つまり再帰が停止する条件が必要です。そうしないと、コードは永久に実行されます (または、少なくともメモリが不足するか、コール スタックがオーバーフローするまで)。ここでの基本的なケースは、次の場合に発生します(0 個のディスクを移動することは、関数の肉の周りにあるx == 0ため、何もしないことを意味するため)。ifまたx == 1、再帰する必要がない場合もありますが、if各hanoi呼び出しの前に余分なものがあると、少しノイズが追加されます (再帰ソリューションの主な利点はその単純さです)。とにかく、 の場合x == 0、関数は何もせずに戻ります。それを呼び出した関数 ( を持っていたx == 1) は、その処理を続行します。この場合、「ディスク 1 を src から dest に移動する」と言ってから、hanoi引数を切り替えて再び機能します。

流れは次のようになります。

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
于 2011-08-06T01:50:11.690 に答える
4

私はそれを理解しました。分解すると、コードは次のように実行されます。

var write = function(string) {
document.write(string);
}

var i = 0;

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

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

/*
hanoi(3,"src","aux","dst");
    if (disc > 0) {
    hanoi(2,'src','dst','aux');
        if (disc > 0) {
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'dst','src','aux');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    write("Move disc " + 3 + " from " + src + " to " + dst + "<br />");
    hanoi(2,'aux','src','dst');
        if (disc > 0) {
        hanoi(1,'aux','dst','src');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    }
*/

これについて最も混乱した部分は、最初の再帰ループのENDを視覚化することでした。disc == 0の場合にのみ、disc==3のステートメントが最終的に書き込まれます。

于 2011-08-05T06:20:26.120 に答える