Guajara in other languages: Spanish, Deutsch, English, French, Italian ...



ハノイの塔

ハノイの塔(はのいのとう)はパズルのひとつ。

Table of contents
1 ルール
2 解き方
3 由来

ルール

3本の立棒と、順々に大きくなる中央に穴の開いた円盤形の複数の盤から構成される。
最初はすべての盤が中央の立棒に小さいものが上になるように順に積み重ねられている。
盤は一度に一枚づつ立棒のどれかに移動させることができるが、小さな盤の上に大きな盤を乗せることは出来ない。
上記のルールに従ってすべての盤を左右どちらかの立棒に順序正しく移動させられれば完成。

すべての盤を移動させるのにはかかる。

解法に再帰的アルゴリズムが使用可能な問題として有名であり、再帰的呼び出しを記述可能なプログラミング言語の記述例としてもよく用いられる。

解き方

3本の棒にA,B,Cの名前を付ける。最初Aにn個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。
  1. 上からn-1個目までの円盤を何らかの方法でAからBに移動する。
  2. 残った1枚をAからCに移動する。
  3. Bにある円盤を何らかの方法でBからCに移動する。

ここで、1は最初Aにn-1個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。そこで、次のようにする。
  1. 上からn-1個目までの円盤を何らかの方法でAからCに移動する。
  2. 残った1枚をAからBに移動する。
  3. Cにある円盤を何らかの方法でCからBに移動する。

3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける。

由来

ハノイの塔は、フランスの数学者E・リュカ(Edouard Lucas)が1883年に考えたものである。リュカは、インドに次のような伝説があると説明している。

インドのガンジス河の畔のベナレス(ヴァラナシ)に世界の中心を表すという聖堂がある。そこには3本の大理石の柱(ダイヤモンドの針との説もあり)が立てられており、そのうちの1本には、当初64枚の黄金の円盤が大きい円盤から順に重ねられていたという。バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。

もちろんこれはリュカの作り話であるが、1枚移動させるのに1秒かかったとして、64枚の円盤を移動させるには、最短でも約5,850億年かかる。




Wikipedia - All text is available under the terms of the GNU Free Documentation License.

Tagoror dot com  -  Legal Information  -  Contact us