ニコニコ動画でハノイの塔の動画を見に行く
- ほめる
(15) - 掲示板を見る
(60) - その他
|
この記事は第359回今週のオススメ記事（2015/5/5）に選ばれました！ よりニコニコできるような記事に編集していきましょう。 |
ハノイの塔とは、パズルゲームの一種である。
概要
3本の棒と、中心に穴のあいた何枚かの異なる大きさの円盤がある。ゲームスタート時は一番左の棒に下から大きい順に円盤が積み重ねられており、所定のルールに従って全ての円盤を一番右の棒に移動させていく。
単純で理解しやすいゲームであり、小学校や中学校で算数・数学の教材に使われることもある。
ルール
最短手数
上記のルールに従ってn枚の円盤を一番左の棒から一番右の棒へと動かす場合、最少でも2n-1の手数が必要となることが知られている。たとえば、3枚の場合なら23-1=7となり7手必要である。また、最短手数の場合、奇数の手（1手目、3手目、5手目…）は一番小さい円盤を動かす手であり、その次の偶数の手（2手目、4手目、6手目…）は1通りしかない。
最短手数についての解説
このゲームを最短手数で終わらせる際、次のような手順で解いていくことになる。
さて、ここで気になるのは「何らかの方法」なのだが、これは全体の円盤の枚数より1枚少ない状態でゲームをするのに等しい。例えば、5枚の円盤でゲームをする場合、「4枚の円盤でのゲーム」を2回行っていることになる。これを1枚の円盤で行うゲームから順に適用していくと、次のようになる。
- 1枚：円盤を右に動かす……1手
- 2枚：1枚の円盤を真ん中に（1手）→一番大きい円盤を右に（1手）→1枚の円盤を右に（1手）……3手
- 3枚：2枚の円盤を真ん中に（3手）→一番大きい円盤を右に（1手）→2枚の円盤を右に（3手）……7手
- 4枚：3枚の円盤を真ん中に（7手）→一番大きい円盤を右に（1手）→3枚の円盤を右に（7手）……15手
- 5枚：4枚の円盤を真ん中に（15手）→一番大きい円盤を右に（1手）→4枚の円盤を右に（15手）……31手
- 6枚：5枚の円盤を真ん中に（31手）→一番大きい円盤を右に（1手）→5枚の円盤を右に（31手）……63手
- 7枚：6枚の円盤を真ん中に（63手）→一番大きい円盤を右に（1手）→6枚の円盤を右に（63手）……127手
以上のように回数は増加していき、円盤の枚数がn枚のとき、最短手数は2n-1回であることが確認できる。より厳密に証明したい場合は数学的帰納法か漸化式を用いれば証明することができる。
伝説
「一番左の棒に64枚の円盤を積み、それら全てを一番右の棒に移し終わったとき世界は滅亡する」という旨の伝説があるが、これは考案者の創作であると考えられている。
前述したとおり、n枚の円盤を移し終えるには最少でも2n-1の手数が必要であるため、円盤が64枚の場合に必要な手数は途轍もない数となる。仮に一度も間違えることなく1秒に1回のペースで円盤を動かし続けるとすると264-1秒（1844京6744兆0737億0955万1616秒）、約5845億年の時間が掛かることになる。移し終える前に人類は滅亡してしまうだろう。
ちなみに関連動画ではTASさんの力をもってしても127手に0.43秒かかっているので、単純計算で一手あたり約0.0033秒（300分の1秒）であり64段には約19億年かかる計算になる。だいぶマシになったがそれでも長い。
関連動画
関連リンク
- ハノイの塔100段のゴールまでの最短時間を計算してみた
- 3枚から8枚まで遊べる。解答あり。
関連項目
掲示板
-
58 ななしのよっしん
2023/02/10(金) 00:36:10 ID: hxlpM2KHY9
64段って結構高いな。記事の画像の感じ一段2cmでも1m超える
-
👍0👎0
-
59 ななしのよっしん
2024/10/26(土) 14:59:10 ID: 8t+JKhJWFP
>>51 氏
大体その認識で間違いじゃないと思います。
但し、1手目で
「始まりの針(※)」にある山になっている円盤の枚数が、
「終わりの針」すなわち移したい先に全部置くためには
「始まりの針」にある枚数が奇数・偶数のどちらかで
「終わりの針」か「途中の針」に置くべきか決まる
ということになりそうです。
(省略しています。全て読むにはこのリンクをクリック！) -
👍0👎0
-
60 ななしのよっしん
2024/12/12(木) 19:45:51 ID: 8VHAj0DKCg
既に書かれてるのと同じ事だけど
最終的に動かしたい一番大きな円盤を右に動かしたいなら、
それより一つ上の円盤は真ん中、さらに一つ上は右・・・って交互に考えるようにしたら
最短手順を間違えないようになった -
👍0👎0
おすすめトレンド
ニコニ広告で宣伝された記事
急上昇ワード改
- 1
- 33
- 112
- 61
- 308
最終更新：2025/07/12(土) 22:00
- 102
- 76
- 24
- 174
- 133
最終更新：2025/07/12(土) 22:00
ウォッチリストに追加しました！
すでにウォッチリストに
入っています。
追加に失敗しました。
ほめた！
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。