Aritalab:Lecture/Algorithm/Towers of Hanoi - Revision history

Adm at 08:18, 21 August 2016

2016-08-21T08:18:29Z

Adm at 03:52, 6 August 2015

2015-08-06T03:52:38Z

Adm at 01:06, 25 July 2013

2013-07-25T01:06:31Z

Adm: /* ハノイの塔 */

2011-12-28T09:12:06Z

‎ハノイの塔

Adm at 09:11, 28 December 2011

2011-12-28T09:11:46Z

Adm: /* ハノイの塔 */

2011-12-19T06:23:57Z

‎ハノイの塔

Adm: moved Aritalab:Lecture/Basic/Towers of Hanoi to Aritalab:Lecture/Algorithm/Towers of Hanoi

2011-06-01T15:28:04Z

moved Aritalab:Lecture/Basic/Towers of Hanoi to Aritalab:Lecture/Algorithm/Towers of Hanoi

Adm at 23:48, 27 February 2011

2011-02-27T23:48:48Z

Adm: New page: ==ハノイの塔== (E. リュカ, 1883) 台の上に３本の棒が固定されており、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとする。Ａにはn枚...

2010-10-18T02:23:51Z

New page: ==ハノイの塔== (E. リュカ, 1883) 台の上に３本の棒が固定されており、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとする。Ａにはn枚...

New page

==ハノイの塔==
(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となる。

@@ Line 7: / Line 7: @@
 * 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
-===必要手数の解===
+===必要な手数===
 この問題を解くには漸化式（ぜんかしき）を使います。
 ;解
@@ Line 18: / Line 18: @@
 * 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>0</sub> = 0
@@ Line 31: / Line 37: @@
 * 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 だけ小さい数ですね。これを数学的に解くには等比数列の和の公式を利用します。
+分子は分母の数よりちょうど 1 だけ小さい数です。これを数学的に解くには等比数列の和の公式を利用します。
 : S<sub>n</sub> = 2<sup>-1</sup> + 2<sup>-2</sup> + ... 2<sup>-n</sup>

@@ Line 7: / Line 7: @@
 * 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
 この問題を解くには漸化式（ぜんかしき）を使います。
 ;解
-n (>0) 枚の円盤を移動する手数を T<sub>n</sub> と書きます。上から n-1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n-1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。
+n (>0) 枚の円盤を移動する手数を T<sub>n</sub> と書きます。上から n - 1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n - 1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。
 * T<sub>0</sub> = 0
 * T<sub>n+1</sub> = 2 T<sub>n</sub> + 1 (n > 0)
@@ Line 18: / Line 19: @@
 * 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
@@ Line 27: / Line 28: @@
 * 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 より少し小さい数になっています。続けていくと、規則性がわかるでしょう。
+となっています。分母が分子よりも常に大きいので 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
@@ Line 36: / Line 37: @@
 :: = 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 となります。
+元々の漸化式との関係を使うと T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>-1 となります。
 上の円盤の動かし方をよくみても、これが円盤を動かすのに最低限必要な手数であることがわかります。
 つまりこの数より少ない回数で円盤を動かすことはできません。
@@ Line 42: / Line 43: @@
 まとめると、 n 枚の円盤を動かすのに最低限必要な手数は 2<sup>n</sup>-1 、つまり n に対して指数的に増加していくことがわかりました。問題のサイズ (つまり n ) が大きくなると、かかる時間は急速に増えていきます。
-例えば 8 枚の円盤が棒にささっている場合、最短の手数で移動させても 2<sup>8</sup> - 1 = 255 手が必要だということです。面白半分に 20 枚の円盤が棒にささっているパズルを作ったら、最短の手数でも 1048576 手、1 秒に一枚動かしても 12 日以上かかります。ウェブ上で画像を検索すると、多くのパズルは7枚か8枚の円盤があるようです。枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうですね。
+===教訓===

@@ Line 7: / Line 7: @@
 * 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
 ;解
-n (>0) 枚の円盤を移動する手数をT<sub>n</sub>と書きます。上からn-1枚の円盤をまずBの棒に移し、一番大きい円盤をCに移してから、Bにあるn-1枚をもう一度全てCに移せばよいので、以下の漸化式を得ます。
+n (>0) 枚の円盤を移動する手数を T<sub>n</sub> と書きます。上から n-1 枚の円盤をまず B の棒に移し、一番大きい円盤を C に移してから、B にある n-1 枚をもう一度全て C に移せばよいので、以下の漸化式を得ます。
 * T<sub>0</sub> = 0
-* T<sub>n</sub> = 2 T<sub>n-1</sub> + 1
+* T<sub>n+1</sub> = 2 T<sub>n</sub> + 1 (n > 0)
 ここでS<sub>n</sub> = T<sub>n</sub>/2<sup>n</sup>とおきます。
 * S<sub>0</sub> = 0
-* S<sub>n</sub> = S<sub>n-1</sub> + 2<sup>-n</sup> (n > 0)
+* S<sub>n+1</sub> = S<sub>n</sub> + 2<sup>-(n+1)</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>
-従って 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枚の円盤があるようですが、枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうです。
+:: = 2<sup>-1</sup>(1 + 1/2 + 1/4 + 1/8 ... 2<sup>-(n-1)</sup>)

@@ Line 4: / Line 4: @@
 台の上に３本の棒が固定されていて、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとします。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっています。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるでしょうか。
-# 一回に一枚の円盤しか動かしてはいけない。
+* 一回に一枚の円盤しか動かしてはいけない。
-# 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
+* 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
 ;解

@@ Line 1: / Line 1: @@
 ==ハノイの塔==
-(E. リュカ, 1883)
+(フランスの数学者 エドゥアール リュカ によるパズル, 1883)
-台の上に３本の棒が固定されており、一番左の棒をＡ、真ん中の棒をＢ、一番右の棒をＣとする。Ａにはn枚の円盤がはまっており、円盤は下へいくほど半径が大きくなっている。次のルールに従い、棒Ｂを利用して全ての円盤をＡからＣに移すとき、何回の移動が必要になるか。
+[[Image:TowersOfHanoi.jpg|thumb]]
 # 一回に一枚の円盤しか動かしてはいけない。
 # 常に大きい方の円盤が下になるようにする。（移動の途中で円盤の大小を逆に積んではいけない。）
 ;解
-n (>0) 枚の円盤を移動する手数をT<sub>n</sub>と書く。上からn-1枚の円盤をまずBの棒に移し、一番大きい円盤をCに移してから、Bにあるn-1枚をもう一度全てCに移せばよいので、以下の漸化式を得る。
+n (>0) 枚の円盤を移動する手数をT<sub>n</sub>と書きます。上からn-1枚の円盤をまずBの棒に移し、一番大きい円盤をCに移してから、Bにあるn-1枚をもう一度全てCに移せばよいので、以下の漸化式を得ます。
 * T<sub>0</sub> = 0
 * 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>0</sub> = 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>
-従って T<sub>n</sub> = 2<sup>n</sup>S<sub>n</sub> = 2<sup>n</sup>-1となる。
+従って 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枚の円盤があるようですが、枚数がこれ以上の場合挑戦しないほうが時間を有効に使えそうです。