• System Practice B Homepage

ハノイの塔の再帰プログラムの説明

何故そのプログラムが問題を解けるか：知能システム学の授業（問題分割法）で説明があった。

3本の棒に1,2,3の名前を付ける。最初1に n 個の円盤があり、3にすべての円盤を移動させるとすると、次のようにする。
 1.上から n - 1 個目までの円盤を再帰方法で1から2に移動する。
 2.残った1枚を1から3に移動する。
 3.2にある円盤を再帰方法で2から3に移動する。

dohanoi()関数の各行を実行し、それでまたdohanoi()という行があるから同処理を繰返す。ループのようにn=0まで関数の実行を行う。

dohanoi(n, to, frm, using) -> dohanoi(n-1, using, frm, to) -> dohanoi(n-2, using, frm, to) -> dohanoi(n-3, using, frm, to)

 -> moveit(frm, to,ここが何故n=1ですか？dohanoi(n-2=1, using, frm, to)のmoveit処理を実行することです) ->dohanoi(1-1, to, using, frm)次の行-> 

moveit(frm, to,nここが何故n=2ですか？dohanoi(n-1=2, using, frm, to)のmoveit処理を実行することです)->dohanoi(n-1=2, using, frm, to) 

-> dohanoi(2-1=1, using, frm, to) ->dohanoi(1-1=0, using, frm, to) -> ...

もっと詳しく表示すると、次の図に赤線を実行し、ピンク色の線を次に実行です。他の色は待機状態のです。