ハノイの塔と再帰

イントロ

大きい問題を同じ小問題へ分ける

ハノイの塔で再帰を体験する

一見複雑なn枚の円盤移動も、最大の円盤を動かす前後にn−1枚の移動が必要だと見抜けば、同じ形の小さな問題二つと一手へ分解できます。手順と手数の理由を同時に説明できる分解です。

定義

教科書では: ある大きさの問題を、同じ種類で一段小さい問題を使って表し、最も小さい場合までたどる考え方です。
言いかえると: 最大円盤を出発棒から目的棒へ動かすには、上のn−1枚を補助棒へよける必要があります。最大円盤を一手で動かした後、同じn−1枚の問題をもう一度解いて目的棒へ重ねます。n=1なら一手で終わるという基準があるので、分解をいつ止めるかも決まります。

公式

n枚の最小手数をT(n)とすると、n−1枚の移動が前後に一回ずつ必要です。

再帰関係

T(n)=2T(n−1)+1

n−1枚を二回動かす手数に、最大円盤を動かす中央の一手を加えます。二回とも最小である必要があります。

使うときのコツ

最初の値はT(1)=1です。ここから順にT(2)、T(3)を作れます。

最小手数

T(n)=2ⁿ−1

枚数が1増えるたびに、手数は前の2倍より1多くなります。指数のnは円盤枚数です。

使うときのコツ

n=1、2、3で1、3、7になるか確かめます。

解くコツ

式だけを覚えず、「上をよける・最大を動かす・上を戻す」の三段階へ対応させます。小問題を一手と数えないことも重要です。

手順

例

場面: 3枚の円盤を最小何手で移せるか。
順に考えると: まず上の2枚を補助棒へ移すのにT(2)=3手、最大円盤を目的棒へ1手、2枚を目的棒へ重ねるのに再び3手です。合計3+1+3=7手です。式でもT(3)=2×T(2)+1=2×3+1=7となります。前半か後半を3手未満にできないため、全体も7手未満にはできません。
ここが結論: 3枚の最小手数は7手です。三段階は実行方法だけでなく、それより短くできない理由にもなっています。

比較

枚数n1

枚数n2

枚数n3

枚数n4

1、3、7、15と、前の値を2倍して1を加える規則が続きます。差ではなく、問題の分解から規則が導かれます。

注意

確認

Q1

4枚の最小手数T(4)をT(3)=7から求める式はどれですか。

まとめ