アルゴリズム入門編: 「ハノイの塔」を学ぶ

このレッスンでは、アルゴリズムの定番問題である「ハノイの塔」について学習します。 「ハノイの塔」は、paizaスキルチェックのAランク相当の問題です。

ここでは、ハノイの塔のプログラムを作るために、データ構造を考えます。そして、プログラムの初期化部分と、それを表示させる部分を作成しましょう。

ここでは、ハノイの塔で、円盤を1枚移動するメソッドを作成します。先ほどのチャプターでは、このようにハノイの塔を初期化するメソッドと、それを出力するメソッドを作成しました。今回は、この初期化したデータから、1枚の円盤を動かします。

ここでは、円盤の枚数を増やした時に、どのように移動させるのか、いろいろ試してみたいと思います。円盤が1枚や2枚なら簡単ですが、3枚以上の時、どんな手順になるのか、プログラムで記述してみましょう。

ここでは、ハノイの塔をプログラムで実現するため、一般的な解法の手順を考えます。 先ほどのチャプタでは、1枚・2枚・3枚の円盤を動かす手順を、手動でやってみました。ここから、再帰呼び出しで円盤を動かす手順を見つけ出しましょう。

ここでは、ハノイの塔で円盤を動かす手順を、再帰呼び出しで実装します。 大きな問題を解くために、より小さな問題の答えを使っていく 場合、再帰呼び出しで実装できます。

ここからは、応用編として、ハノイの塔プログラムを効率よく実行する方法を考えます。ここでは、移動する円盤の枚数が増えた時、移動回数がどうなるか調べましょう。そのために、円盤の移動回数を表示するカウント変数を追加します。

ここでは、追加したカウント変数を利用して、円盤の枚数が変化した時、その移動回数を調べます。

ここでは、円盤の枚数と回数を指定したとき、その時の円盤の状態を出力するプログラムを作ります。先ほど、追加したカウント変数を利用して、指定回数になった時に、その状態を表示させます。

ここでは、ハノイの塔のプログラムで、再帰処理の回数を減らして、円盤の枚数が多くなっても、状態を出力できるようにプログラムを改良します。