Aritalab:Lecture/Algorithm/Towers of Hanoi
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
(New page: ==ハノイの塔== (E. リュカ, 1883) 台の上に３本の棒が固定されており、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとする。Ａにはn枚...) |
m |
||
| Line 6: | Line 6: | ||
;解 | ;解 | ||
| − | 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-1</sub> + 1 | * T<sub>n</sub> = 2 T<sub>n-1</sub> + 1 | ||
Revision as of 08:48, 28 February 2011
ハノイの塔
(E. リュカ, 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となる。
