【JavaScript】ハノイの塔を可視化 / プログラミング

JavaScript
スポンサーリンク

本記事ではハノイの塔についてのプログラムを紹介しています。

 

JavaScriptを使っています。

 

ハノイの塔とは、3本の棒の1つに突き刺された大小の円盤(板)を他の棒へと、ある規則に従って移し換えるパズルゲームのことを言います。

 

全部の板を移動させるのに最低何手必要なのかを求めます。

 

プログラミングにおいては、再帰的呼出しの例題としてよく紹介される有名なものです。

 

今回は解放にその再帰的アルゴリズムを含む「ハノイの塔」をアニメーションで再現、可視化したものを JavaScript で書きました。

 

YouTubeに動画もアップしてあるのでそちらもご覧ください↓

 

【6倍速】ハノイの塔をプログラミングで可視化 / JavaScript
スポンサーリンク

ハノイの塔を可視化するプログラム

DEMO

まずこちらが完成品。

 

まず、板の枚数を3~10の間の数で入力し、Enter ボタンを押します。

 

そして、「Start」ボタンを押すと移動が始まります。

その際、下の「Speed」 バーの値を変更することで、移動のスピードを速くしたり遅くすることができます。

 

画面右上には移動した回数が表示されています。

HTMLファイルの作成

 

html ファイルは以下のように書きました。


<input type=button“>でボタンの作成、<input type=”number”>で数字のインプット、 <input type=”range”>でバーの作成をしています。

JavaScript ファイルの作成

 

HTML ファイルの次に、JavaScript ファイルを作成します。

 

まず、html ファイルでした id をもとに、ボタンやスライドバーなどの特定の要素にアクセスするため Document の getElementById() メソッドを使っています。

 

14~19行目で、speed の値をスライダーバーから読み取ったものにし、また oninput というものを使用し、値が変更されたら新しい数字に更新しそれを画面に表示しています。(output.innerHTML)

 

50行目の drawBar() 関数では3本の白い棒の描画を行っています。

長方形を描画する際は、まず beginPath() でパスの初期化をし、ctx.rect() で長方形を描き、fill() メソッドでその棒を塗りつぶしています。

 

63行目の drawDisk(diskWidth,placeTower,level) 関数では、板の幅を決めるための変数(diskWidth)、どの棒に板を描画するかを決める変数(placeTowe)、そして板をどの何段目に描画するかを決める変数(level)を受け取り、板を指定の位置に描画しています。

 

(diskWidth,placeTower,level)のこの3つの数を変えることで指定の位置、指定の長さで板を描画しています。

 

73行目moveDisk(from,to) ではfrom という配列と to という移動先を示す配列を受け取ります。

 

pop() というメソッドを使用し、配列の最後の要素を取り除き、push() というメソッドを使い、配列の末尾に要素を追加しています。

 

例えば、 moveDisk(towerA,towerB)と書いた場合には、towerA の配列の末尾を削除し、towerB という配列のお尻にそれを追加するという動作が行われます。

 

87~106行目の drawTowerA() や drawTowerB()という関数では それぞれの tower にある板を描画しています。

 

sleep() 関数で指定された時間の処理を止めています。

 

114行目hanoiTower(n,from,to,remain) 関数はハノイの塔のアルゴリズムについて。

再帰的呼出しが行われています。

 

reset() 関数は色々なパラメータをリセットするためのもの。

 

gameLoop() 関数では描画についての処理を行っています。

requestAnimationFrame() というメソッドを使用しています。

 

そして、最後に、addEventListener() というメソッドを使用し、特定のボタンが押されたときの処理を決めています。

 

以上がハノイの塔を可視化するためのプログラムです。

 

参考資料・動画

 

 

 

 

コメント