Cで記述されたハノイの塔のプログラムをJavaScriptに移植しただけの代物。参考までに。
記事の初出、2005/09/25の日記
コンピュータ科学の本にC言語で書かれたハノイの塔の実行プログラムがあったので、JavaScriptに移植。
ハノイの塔とは、例えば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。