Aritalab:Lecture/Algorithm/Towers of Hanoi
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
m (→ハノイの塔) |
m |
||
| Line 1: | Line 1: | ||
==ハノイの塔== | ==ハノイの塔== | ||
| − | ( | + | (フランスの数学者 エドゥアール リュカ によるパズル, 1883) |
| − | + | [[Image:TowersOfHanoi.jpg|thumb]] | |
| + | |||
| + | 台の上に３本の棒が固定されていて、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとします。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっています。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるでしょうか。 | ||
# 一回に一枚の円盤しか動かしてはいけない。 | # 一回に一枚の円盤しか動かしてはいけない。 | ||
# 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。） | # 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。） | ||
;解 | ;解 | ||
| − | n (>0) 枚の円盤を移動する手数をT<sub>n</sub> | + | 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-1</sub> + 1 | * T<sub>n</sub> = 2 T<sub>n-1</sub> + 1 | ||
| − | ここで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-1</sub> + 2<sup>-n</sup> (n > 0) | * S<sub>n</sub> = S<sub>n-1</sub> + 2<sup>-n</sup> (n > 0) | ||
| + | |||
この漸化式を解くと | この漸化式を解くと | ||
| + | |||
: 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> = 1 - 2<sup>-n</sup> | ||
| − | 従って T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>- | + | 従って T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>-1となります。例えば 8 枚の円盤が棒にささっている場合、最短の手数で移動させても 2<sup>8</sup> - 1 = 255 手が必要だということです。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようですが、枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうです。 |
Revision as of 18:11, 28 December 2011
ハノイの塔
(フランスの数学者 エドゥアール リュカ によるパズル, 1883)
台の上に３本の棒が固定されていて、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとします。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっています。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるでしょうか。
- 一回に一枚の円盤しか動かしてはいけない。
- 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
- 解
n (>0) 枚の円盤を移動する手数をTnと書きます。上からn-1枚の円盤をまずBの棒に移し、一番大きい円盤をCに移してから、Bにあるn-1枚をもう一度全てCに移せばよいので、以下の漸化式を得ます。
- T0 = 0
- Tn = 2 Tn-1 + 1
ここでSn = Tn/2nとおきます。
- S0 = 0
- Sn = Sn-1 + 2-n (n > 0)
この漸化式を解くと
- Sn = 2-1 + 2-2 + ... 2-n = 1 - 2-n
従って Tn = 2nSn = 2n-1となります。例えば 8 枚の円盤が棒にささっている場合、最短の手数で移動させても 28 - 1 = 255 手が必要だということです。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようですが、枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうです。
