特進コース2年生生の「情報の科学」で、コンピュータサイエンスアンプラグド(CSアンプラグド)の第2弾を行いました。

(コンピュータサイエンスアンプラグドは、コンピュータを使わずに情報科学を教えるための学習法です。カードなどを用いたゲームやグループ活動を通して、コンピュータの基本的なしくみを楽しく学ぶことができます。)

今回は数学の中でも有名なフィボナッチ数列の単元でよく目にする「ハノイの塔」というものを、情報の観点から見てみようということで、実際に体現してみました。

ハノイの塔は、次の図のようなものがあったとします。無題 簡単に説明すると3つの棒があって、円盤が上から小さい順に重ねられている。
これを次の条件のもと別の棒に全て移動させることができれば終了。条件:1.一回の移動に一枚しか移動できない。2.小さい円盤の上に大きい円盤をのせてはいけない。このルールで次の図のようにすると終了。無題2というもので、最小の回数で移動してみようというものです。

このハノイの塔はコンピュータのC言語プログラムの中でも、再帰アルゴリズムというもので表すことができるため、ゲームに取り組みながら法則を見つけて再帰アルゴリズムを理解しようというものでしたが、生徒たちは、簡単だけど難しいし、理論上で最小の回数を割り出しても、実際にやると出来そうで出来ないけど、やってて面白い。でも、疲れるといいながら、とても楽しそうにゲームに取り組んでいました。

(今回のハノイの塔のアルゴリズム解析はnigoblogスタートアップのCMOブログ。プログラマーは今こそアルゴリズムを書くべき!!2~再帰アルゴリズムでハノイの塔を解く~http://nigohiroki.hatenablog.com/entry/2012/09/19/234612を参考にさせて頂きました)