Aritalab:Lecture/Algorithm/Towers of Hanoi
m (→ハノイの塔) |
|||
| Line 7: | Line 7: | ||
* 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。） | * 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。） | ||
| + | この問題を解くには漸化式（ぜんかしき）を使います。 | ||
;解 | ;解 | ||
| − | n (>0) | + | n (>0) 枚の円盤を移動する手数を T<sub>n</sub> と書きます。上から n-1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n-1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。 |
* T<sub>0</sub> = 0 | * T<sub>0</sub> = 0 | ||
| − | * T<sub>n</sub> = 2 T<sub>n | + | * T<sub>n+1</sub> = 2 T<sub>n</sub> + 1 (n > 0) |
| + | 実際に | ||
| + | * 1 枚の円盤があるとき T<sub>1</sub> = 1 回、 | ||
| + | * 2 枚の円盤があるとき T<sub>2</sub> = 2 + 1 = 3 回、 | ||
| + | * 3 枚の円盤があるとき T<sub>3</sub> = 3 * 2 + 1 = 7 回 | ||
| + | の移動が必要なことを確認しましょう。 | ||
ここでS<sub>n</sub> = T<sub>n</sub>/2<sup>n</sup>とおきます。 | ここでS<sub>n</sub> = T<sub>n</sub>/2<sup>n</sup>とおきます。 | ||
* S<sub>0</sub> = 0 | * S<sub>0</sub> = 0 | ||
| − | * S<sub>n</sub> = S<sub>n | + | * S<sub>n+1</sub> = S<sub>n</sub> + 2<sup>-(n+1)</sup> (n > 0) |
| − | + | この式は | |
| + | * 1 枚の円盤があるとき S<sub>1</sub> = 1 / 2 | ||
| + | * 2 枚の円盤があるとき S<sub>2</sub> = 3 / 2<sup>2</sup> = 3/4 | ||
| + | * 3 枚の円盤があるとき S<sub>3</sub> = 7 / 2<sup>3</sup> = 7/8 | ||
| + | となっています。分母が分子よりも常に大きいので 1 より少し小さい数になっています。続けていくと、規則性がわかるでしょう。 | ||
| + | * 4 枚の円盤があるとき S<sub>4</sub> = 15 / 2<sup>4</sup> = 15/16 | ||
| + | * 5 枚の円盤があるとき S<sub>5</sub> = 31 / 2<sup>5</sup> = 31/32 | ||
| + | 分子は分母の数よりちょうど 1 だけ小さい数ですね。これを数学的に解くには等比数列の和の公式を利用します。 | ||
| − | : S<sub>n</sub> = 2<sup>-1</sup> + 2<sup>-2</sup> + ... 2<sup>-n</sup> = 1 - 2<sup>-n</sup> | + | : S<sub>n</sub> = 2<sup>-1</sup> + 2<sup>-2</sup> + ... 2<sup>-n</sup> |
| − | 従って T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>- | + | :: = 2<sup>-1</sup>(1 + 1/2 + 1/4 + 1/8 ... 2<sup>-(n-1)</sup>) |
| + | :: = 2<sup>-1</sup>(1 - 2<sup>-n</sup>) / ( 1 - 1/2 ) = 1 - 2<sup>-n</sup> | ||
| + | |||
| + | 従って T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>-1 となります。 | ||
| + | 上の円盤の動かし方をよくみても、これが円盤を動かすのに最低限必要な手数であることがわかります。 | ||
| + | つまりこの数より少ない回数で円盤を動かすことはできません。 | ||
| + | |||
| + | まとめると、 n 枚の円盤を動かすのに最低限必要な手数は 2<sup>n</sup>-1 、つまり n に対して指数的に増加していくことがわかりました。問題のサイズ (つまり n ) が大きくなると、かかる時間は急速に増えていきます。 | ||
| + | |||
| + | 例えば 8 枚の円盤が棒にささっている場合、最短の手数で移動させても 2<sup>8</sup> - 1 = 255 手が必要だということです。面白半分に 20 枚の円盤が棒にささっているパズルを作ったら、最短の手数でも 1048576 手、1 秒に一枚動かしても 12 日以上かかります。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようです。枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうですね。 | ||
Revision as of 10:06, 25 July 2013
ハノイの塔
(フランスの数学者 エドゥアール リュカ によるパズル, 1883)
台の上に３本の棒が固定されていて、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとします。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっています。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるでしょうか。
- 一回に一枚の円盤しか動かしてはいけない。
- 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
この問題を解くには漸化式（ぜんかしき）を使います。
- 解
n (>0) 枚の円盤を移動する手数を Tn と書きます。上から n-1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n-1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。
- T0 = 0
- Tn+1 = 2 Tn + 1 (n > 0)
実際に
- 1 枚の円盤があるとき T1 = 1 回、
- 2 枚の円盤があるとき T2 = 2 + 1 = 3 回、
- 3 枚の円盤があるとき T3 = 3 * 2 + 1 = 7 回
の移動が必要なことを確認しましょう。 ここでSn = Tn/2nとおきます。
- S0 = 0
- Sn+1 = Sn + 2-(n+1) (n > 0)
この式は
- 1 枚の円盤があるとき S1 = 1 / 2
- 2 枚の円盤があるとき S2 = 3 / 22 = 3/4
- 3 枚の円盤があるとき S3 = 7 / 23 = 7/8
となっています。分母が分子よりも常に大きいので 1 より少し小さい数になっています。続けていくと、規則性がわかるでしょう。
- 4 枚の円盤があるとき S4 = 15 / 24 = 15/16
- 5 枚の円盤があるとき S5 = 31 / 25 = 31/32
分子は分母の数よりちょうど 1 だけ小さい数ですね。これを数学的に解くには等比数列の和の公式を利用します。
- Sn = 2-1 + 2-2 + ... 2-n
- = 2-1(1 + 1/2 + 1/4 + 1/8 ... 2-(n-1))
- = 2-1(1 - 2-n) / ( 1 - 1/2 ) = 1 - 2-n
従って Tn = 2nSn = 2n-1 となります。 上の円盤の動かし方をよくみても、これが円盤を動かすのに最低限必要な手数であることがわかります。 つまりこの数より少ない回数で円盤を動かすことはできません。
まとめると、 n 枚の円盤を動かすのに最低限必要な手数は 2n-1 、つまり n に対して指数的に増加していくことがわかりました。問題のサイズ (つまり n ) が大きくなると、かかる時間は急速に増えていきます。
例えば 8 枚の円盤が棒にささっている場合、最短の手数で移動させても 28 - 1 = 255 手が必要だということです。面白半分に 20 枚の円盤が棒にささっているパズルを作ったら、最短の手数でも 1048576 手、1 秒に一枚動かしても 12 日以上かかります。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようです。枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうですね。
