課題

C

ハノイの塔の問題

１．ハノイの塔とは

　n枚のドーナツ形の円盤を大きい物順に重ねたA塔があります。このA塔の全ての円盤を塔Bに次のルールに従って移動するのがハノイの塔の問題です。

• 塔はA,B,Cの３本あり、どの塔を作業移動用に利用してもよい。
• 円盤は一度に１枚ずつしか移動できない。
• 小さな円盤の上に大きな円盤を置くことはできない。

２．ハノイ移動の例

　今回はこの移動過程を画面表示するのですが、便宜上このような移動を「ハノイ移動」と呼ぶことにします。
　まずは３枚のハノイ移動をするには次のような流れになり、この中の１から７までの移動手順をプログラムで求めることになります。

• 1の円盤をAからBに移動する
• 2の円盤をAからCに移動する
• 1の円盤をBからCに移動する
• 3の円盤をAからBに移動する
• 1の円盤をCからAに移動する
• 2の円盤をCからBに移動する
• 1の円盤をAからBに移動する