ハノイの塔実行プログラム

記事の初出、2005/09/25の日記

コンピュータ科学の本にC言語で書かれたハノイの塔の実行プログラムがあったので、JavaScriptに移植。

ハノイの塔とは、例えば3本の棒があり、左端の棒に下から大きい順で円盤が重ねられている。この円盤をそっくり右端の棒に移動させればいいのだが、これには決まりがある。

1. 円盤は1枚ずつしか動かせない
2. 小さい円盤の上に大きい円盤を重ねることはできない
3. 途中で真中の棒を利用しても良い

以上の約束を守って円盤を移動させる。JavaScriptプログラムは以下の通り。なお、ハノイの塔は現在のコンピュータの能力では有限時間以内に計算終了が確定できても、計算に莫大な時間のかかるNP問題に属する。このプログラムも円盤の数が20個程度でも事実上計算不可能に陥る。

<script type="text/javascript">
<!--
document.writeln("<pre>");
cnt=1;
r_c = function(n,x,y,z){
        if(n>0){
                r_c(n-1,x,z,y);
                document.writeln("円盤",n,"を",x,"から",y,"に移動(",cnt,")");
                cnt++;
                r_c(n-1,z,y,x);
        }
}
while(true){
        Saucer = prompt("円盤の個数を入力","5");
        if(isNaN(Saucer)||1>eval(Saucer)){
                alert("error");
                continue;
        }else{
                S = eval(Saucer);
                conf = confirm("予想計算ステップは"+(Math.pow(2,S)-1)+"ですがよろしいですか？");
                if(!conf)continue;
                else break;
        }
}
r_c(S,"X","Z","Y");
document.writeln("移動回数:",cnt-1,"</pre>");
//-->
</script>

このソースコードを空のHTMLファイルにコピーペーストしてブラウザで開けば、あとは指示に従って数字を入力するだけで自動実行される。円盤は小さい順に1,2,3...、棒は右からX,Y,Z。

• プログラム実行ページ