再帰的呼び出しーハノイの塔を例に
はじめに¶
この教材では、ハノイの塔シミュレータを用いて、 ハノイの塔のパズルを解くための命令列を生成するプログラムを作成する課題に取り組む。
この教材では、シミュレータの操作方法や画面の見方については説明しない。 それらについては、すでに用意されている解説動画を参照されたい。
この課題の目的は、 ハノイの塔の「解き方」を覚えることではない。 どのように考えれば、 大量の手順をプログラムで生成できるかを考えることが目的である。
Figure 47:ハノイの塔シミュレータの画面例
関連資料・リンク¶
この課題では、以下の資料・ツールを使用する。
ハノイの塔シミュレータ¶
ディスク3枚を動かすコードを記入済みなので、まずは開いて動かしてみてほしい。
解説動画（YouTube）¶
1年次の「情報処理演習」用に作成した動画教材のため、動画中ではVBAの文法で説明しているが、考え方はPythonや他の言語でも同じである。
問題設定¶
円板は7枚～10枚とする。枚数が多いほど高評価とする。
初期状態では、すべての円板が柱Aに積まれている
目標は、すべての円板を柱Bに移動することである
ハノイの塔のルールは、通常のものと同じである。
1回に動かせる円板は1枚だけ
小さい円板の上に、大きい円板を置くことはできない
あなたが行うこと¶
あなたの課題は、次の3点である。
ハノイの塔を解くための命令列を生成するプログラムを書くこと
生成された命令列をハノイの塔シミュレータに入力し、動作を確認すること
すべての円板が移動できたことを、スクリーンショットで確認すること
命令は、次の形式で表す。
A,B：柱Aの一番上の円板を、柱Bに移動B,C：柱Bの一番上の円板を、柱Cに移動
1行につき1命令とする。
詳細はビデオ教材「ハノイの塔シミュレータ（Web版）の使い方」で説明している。
プログラムについて¶
使用する環境¶
Python（JupyterLab上で作成・実行）
命令列を出力するプログラムを書くこと
この課題では、 画面描画やGUIを作る必要はない。 出力はすべてテキストで構わない。
アルゴリズムについて¶
どのように命令列を生成するかは、各自に委ねる。
ただし、 なぜその順序で命令が生成されるのか を説明できることを求める。
命令列そのものを手で書いただけの提出は不可とする。 必ず「命令列を生成するプログラム」を作成すること。
なお、この課題で重視しているのは 再帰という書き方そのものではなく、 問題を同じ形の小さな問題に分けて考える視点である。 その考え方が説明できていれば、 プログラム上で再帰呼び出しを用いているかどうかは問わない。
生成AIの利用について¶
ChatGPTやGeminiなどの生成AIを、 実装の補助として使っても構わない。
ただし、
どのような考え方で命令列を生成しようとしたのか
その考え方が、プログラムの構造にどのように表れているか
は、必ず自分の言葉で説明すること。
生成AIを使った場合は、
どの部分で使ったか
どのように修正・調整したか
をレポート内に明記すること。
提出物¶
提出はKU-LMSから行うこと。 提出方法および提出期限はKU-LMSにて確認すること。
提出物は次の2点である。
1. プログラム＋レポート文書¶
JupyterLabで作成したPythonプログラム
ハノイの塔の命令列を自動生成するもの
同じノートブックに以下を記述すること。
プログラムの考え方
再帰（または別の方法）で何をしているか
生成AIを使った場合、その使い方
2. スクリーンショット¶
ハノイの塔シミュレータ上で、
すべての円板が目的の柱に移動していること が分かる画面
実行途中ではなく、完了状態の画面を提出すること
評価の観点¶
この課題では、命令列の長さや美しさは評価しない。
評価の対象は、次の点である。
問題をどのように分解して考えたか
なぜそのプログラムで解けるのかを説明できているか
自分のプログラムの動作を理解しているか
正しく解けたスクリーンショットは必要条件であるが、 それだけで十分条件ではない。
最後に¶
この課題の目的は、
ハノイの塔を解くこと
ではなく、問題を小さな同種の問題に分け、
その手順を体系的に生成する考え方を理解すること
である。
その考え方は、典型的には「再帰的」と呼ばれるが、 プログラム中で必ず再帰呼び出しを書かなければならない、 という意味ではない。
大切なのは、
どのように問題を分解して考えたか
その考え方が、プログラムの構造にどう表れているか である。
シミュレータは、 あなたの考えたプログラムが正しく動いているかを 確かめるための道具にすぎない。
自分のプログラムが、 どのような手順を生み出しているのかを、 ぜひ言葉にしてみてほしい。