Honoi の塔の問題の解き方 (2)

分析 : N=3 の場合
高さ 3 の塔を、棒 1 から、棒 2 に移動するには...
a) 〜 c) : 高さ 2 の塔を 1 から 3 に動かしている (棚上げ)
d) : 円盤 (3) を 1 から 2 に移動している (目的の円盤の移動)
e) 〜 g) : 高さ 2 の塔を 3 から 2 に動かしている (棚下し)
ポイント (一般化)
高さ N の塔を動かすには、円盤 (N) を移動する必要がある
円盤 (N) を動かすには、上の N-1 の塔を退かす必要がある(棚上げ)
円盤 (N) を動かした後は、上に N-1 の塔を載せる必要がある(棚下し)
再起を利用した、一般の N の解法
高さ N の塔を、棒 i から、棒 j に、棒 k を棚にして移動するには
高さ N-1 の塔を、棒 i から 棒 k に、棒 j を棚にして移動 (再起)
大きさ N の円盤を 棒 i から 棒 j に移動 (単体作業)
高さ N-1 の塔を、棒 k から 棒 j に、棒 i を棚にして移動 (再起)
高さが 0 の塔は(円盤がないのだから)何もしなくてよい
再起の終了