チャレンジ課題 C1 ハノイの塔

チャレンジ課題は、腕試し用の問題です。チャレンジ課題を解かなくても単位取得はできますが、解いた場合は成績に加味します。

出典:wikipediaより

ハノイの塔を再帰を使って解くプログラム（つまり円盤をどのように移動するかを表示するプログラム）を作成せよ。円盤の枚数nはユーザーの入力で設定できるようにすること。

以下のルールに従って、すべての円盤を右端の杭に移動できれば完成。

• ハノイの塔は、3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に、小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤の移動を、n-1枚の円盤の移動を使って表すことを考える（再帰）。左端の棒から、棒1, 棒2, 棒3と呼ぶことにすると、以下の手順で円盤をすべて移動できる。

1. 棒3を一時的な退避場所として使い、n-1枚の円盤を棒1から棒2へ移す
2. 最後の円盤（一番大きなもの）を棒1から棒3へ移す
3. 棒1を一時的な退避場所として使い、n-1枚の円盤を棒2から棒3へ移す

ネットを調べれば解き方は簡単にわかりますが、自力で考え出す方が楽しいと思います。