概要
概要
ハノイの塔は再帰の教材として定番です。大きい円盤を動かす前後に、小さい円盤の塔を丸ごと移す発想が見えます。
動的計画法・再帰 / Tower of Hanoi（ハノイの塔）
ハノイの塔は再帰の教材として定番です。大きい円盤を動かす前後に、小さい円盤の塔を丸ごと移す発想が見えます。
目次
このページでわかること
概要
ハノイの塔は再帰の教材として定番です。大きい円盤を動かす前後に、小さい円盤の塔を丸ごと移す発想が見えます。
考え方
move(n-1, source, spare)
move largest disc
move(n-1, spare, target)要点
2^n - 1
再帰構造
大きい円盤を小さい円盤の上に置けない
高い
補足
n-1 枚を退避、最大を移動、n-1 枚を戻す、の 3 段構成です。
塔の図がそのまま再帰の構造になります。
手数が指数的に増える例としても使えます。
動きで確認
ここでは「状態が何か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。