ハノイの塔単語

ハノイノトウ
  • 13
  • 0pt
掲示板へ
今週のおすすめ この記事は第359今週のオススメ記事2015年5月5日)に選ばれました!
よりニコニコできるような記事に編集していきましょう。

ハノイの塔とは、パズルゲームの一種である。

概要

3本の棒と、中心にのあいた何枚かの異なる大きさの円盤がある。ゲームスタート時は一番左の棒に下から大きい順に円盤が積み重ねられており、所定のルールに従って全ての円盤を一番右の棒に移動させていく。

単純で理解しやすいゲームであり、小学校中学校算数数学の教材に使われることもある。

ルール

  • 一手につき1枚しか円盤を動かすことはできない。
  • ある円盤の上に、それより大きい円盤を積むことはできない。
  • 棒以外のところに円盤を移動させることはできない。

最短手数

上記のルールに従ってn枚の円盤を一番左の棒から一番右の棒へと動かす場合、最少でも2n-1の手数が必要となることが知られている。たとえば、3枚の場合なら23-1=7となり7手必要である。また、最短手数の場合、奇数の手(1手、3手、5手…)は一番小さい円盤を動かす手であり、その次の偶数の手(2手、4手、6手…)は1通りしかない。

3段
1手
2手
3手
4手
5手
6手
7手
4段
1手
2手
3手
4手
5手
6手
7手
8手
9手
10手
11手
12手
13手
14手
15手
5段
1手
2手
3手
4手
5手
6手
7手
8手
9手
10手
11手
12手
13手
14手
15手
16手
17
18手
19手
20
21
22
23
24手
25
26手
27手
28
29手
30
31
盤の枚数を変える

最短手数についての解説

このゲームを最短手数で終わらせる際、次のような手順で解いていくことになる。

  1. 左の棒に積み重なっている円盤のうち、一番下以外の円盤何らかの方法でん中の棒に移す
  2. 左の棒に残っている一番大きい円盤を右の棒に移す
  3. ん中の棒に残っている円盤をすべて何らかの方法で右の棒に移す

さて、ここで気になるのは「何らかの方法」なのだが、これは全体の円盤の枚数より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、約5845億年の時間が掛かることになる。移し終える前に人類は滅亡してしまうだろう。

関連動画

関連商品

関連ゲーム

関連項目

外部リンク

【スポンサーリンク】

  • 13
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

ハノイの塔

40 ななしのよっしん
2015/04/08(水) 09:48:40 ID: mLYqBoXNdT
リュカが考えた伝説はこのパズル自体と同じくらい価値があると思う
「設定かくあるべし」の見本のような、シンプルシャープで印的な設定
41 ななしのよっしん
2015/04/09(木) 00:47:50 ID: Qof+6AmPHb
>>39
編集です
42 ななしのよっしん
2015/04/09(木) 05:41:34 ID: k57vocWutL
m段のハノイの塔について、最短手数のとき、上からn番円盤を2^(m-n)回動かすことになる。
64段のハノイの塔は一番上の円盤を2^63回(約920回)動かすことになる。
円盤が木製で厚さ1cm程度なら、移し終える前に擦り減ってくなりそう。
43 ななしのよっしん
2015/04/13(月) 23:22:12 ID: 1jMB+TP+My
クリックで進むのすごいなのだよ
64段のやつを作ってほしいなのだよ
44 ななしのよっしん
2015/05/07(木) 02:34:21 ID: 1QyAypt7FO
この伝説マジでそんなに時間掛かるのかよ?なんかを二十数回折ると富士山と同じ位の高さに成るっての彷彿させるな。
45 ななしのよっしん
2015/05/08(金) 23:51:01 ID: XwtP9dF5u/
倍々になってくからな
40数回でに届いて100回くらいで宇宙の直径になるらしい
46 nの3乗
2016/09/06(火) 22:39:52 ID: 619sTLgUew
64段を全て移動するには2^64 -1(18,446,744,073,709,551,615)回円盤を動かす必要があり、
TAS動画(毎300回)でも19億年以上かかるからね
47 ななしのよっしん
2016/12/03(土) 14:49:39 ID: LHxG8TjtoY
プログラミングにおいては再帰処理の例題によく出されるね
48 ななしのよっしん
2018/01/27(土) 10:38:15 ID: V5bMTX2cbQ
スーパーコンピュータなら一間に1回の計算ができるから
ハノイの塔64段は5時間で解けるらしい
49 ななしのよっしん
2019/03/20(水) 02:40:44 ID: 7Ua1Zk6flM
の束をふたつ折りにするには、の大きさがその束の厚さよりも大きくないと
「ふたつ折りにした」と言える状態じゃないような気もするw

【鋭利な物で束をふたつに切断する→重ねる】…A
という形式なら、幾分か現実味がある
…まあどのみち、Aの動作を40回も100回も実際にやるのは不可能だろうから
現実味もクソいのかも知れんけどw

急上昇ワード