ハノイの塔と再帰的な考え
ゾウ先生1枚少ない場合さえわかれば、あとは同じ手順をくり返すだけで何枚でも解けるよ。
30秒でつかむ
- ハノイの塔は、3本の棒の間で円盤を1枚ずつ、小さい円盤の上に大きい円盤を乗せないという規則で移し替えるパズルである。
- n枚の円盤をすべて移すのに必要な最少回数は、n−1枚を移す回数の2倍に1を足した数になり、2ⁿ−1回で表せる。
- 自分より1つ小さい場合の答えを使って答えを組み立てる、この考え方を再帰的な考えという。
詳しく
公式
ハノイの塔は、3本の棒A・B・Cの1本に大きさの異なる円盤がすべて重ねてあるパズルだ。1回に1枚ずつ、どの棒でも小さい円盤の上に大きい円盤を乗せないという規則で、すべての円盤を別の棒に移す。
円盤がn枚のとき、すべて移すのに必要な最少回数をとする。という関係が成り立つ。上のn−1枚をいったん空いている棒に移し、いちばん大きい1枚を目的の棒に移す。最後にn−1枚を目的の棒に移す手順でよいからだ。
円盤が1枚なら移すのに1回で済むので、になる。
例題
例題：円盤が3枚のとき、最少回数を求めよう。
なので、。。
実際に動かすと、小さい2枚をいったん別の棒へ逃がし(3手)、いちばん大きい1枚を移す(1手)。逃がした2枚を目的の棒へ戻す(3手)と合わせて、手になる。
なぜそうなるか
という関係から、一般の式を導こう。両辺に1を足すととなる。とおくとになる。
から始まって2倍ずつ増えていく。だから、つまりになる。1枚少ない場合の答えから、同じ形のまま1段上の答えを組み立てられるのが、この再帰的な考えのよさである。
江戸時代の「塵劫記」の油分け算や、すべての行・列・対角線の和を等しくする魔方陣などがある。これらも同じように規則を見つけて手順を組み立てるパズルで、数学と遊びの関わりを示す例だ。
確認問題
確認問題（解答用紙）
スマホやタブレットで読み取ると、この問題をその場で解けます。
https://manazoo.com/math/tower-of-hanoi/?from=print#quiz
円盤が4枚のとき、ハノイの塔を解くのに必要な最少回数を求めよ。
答え：＿＿＿＿＿＿＿＿＿＿＿＿
正解：15
a(n)＝2ⁿ−1より、a(4)＝2⁴−1＝16−1＝15。円盤が5枚のとき、ハノイの塔を解くのに必要な最少回数を求めよ。
答え：＿＿＿＿＿＿＿＿＿＿＿＿
正解：31
a(n)＝2ⁿ−1より、a(5)＝2⁵−1＝32−1＝31。次のうち、ハノイの塔と同じように規則を見つけて手順を組み立てる数学的なパズルはどれか。
- ◯ 油分け算
- ◯ 度数分布表
- ◯ 二次方程式
- ◯ 三角比
正解：油分け算
「塵劫記」の油分け算も、決められた枡で油を分ける規則を見つけて手順を組み立てるパズルだ。ハノイの塔と同じ数学的な考え方を使う。n枚の円盤をすべて移すのに必要な最少回数を表す式はどれか。
- ◯ 2n−1
- ◯ 2ⁿ−1
- ◯ n！−1
- ◯ n²−1
正解：2ⁿ−1
a(n)＝2×a(n−1)＋1という関係を解くと、a(n)＝2ⁿ−1になる。
単元のポイント
- ハノイの塔 3本の棒の間で円盤を1枚ずつ、小さい円盤の上に大きい円盤を乗せずに移し替えるパズル
- 再帰的な考え 同じ種類で規模が1つ小さい問題の答えを使って、もとの問題の答えを組み立てる考え方
- 2ⁿ−1 n枚の円盤を移すのに必要な最少回数