ハノイの塔 (1回目)

2024/12/4(水)
ハノイの塔 (1回目)
 
再帰を使った手順(hanoi)
 
■ 定義
▼ 前提
3本(A,B,C)の棒とn枚の円盤(小さい順に1～nとする)がある
Aに1～nの円盤が上から順に積まれている
 
▼ 目標
1～nの円盤全てをCに移動させる
 
▼ ルール
小さい円盤の上に大きい円盤は置けない
1度に動かせる円盤は1枚のみ
 
■ 例
▼ 定義
円盤1をAからCに移動する事を1:A->C
棒を0
円盤を1 222 33333 …
と書く事にする
 
▼ n = 1の時
A B C A B C
1 0 0 0 0 1
1:A->C 1回移動
 
▼ n = 2の時
 A   B   C   A   B   C   A   B   C   A   B   C
 1   0   0   0   0   0   0   0   0   0   0   1
222  0   0  222  1   0   0   1  222  0   0  222
1:A->B 2:A->C 1:B->C 3回移動
 
▼ n = 3の時
  A    B    C   A    B    C   A    B    C
  1    0    0   0    0    0   0    0    0
 222   0    0  222   0    0   0    0    0
33333  0    0 33333  0    1 33333 222   1
1:A->C 2:A->B 1:C->B
 
  A    B    C
  0    0    0
  0    1    0
33333 222   0
3:A->C
 
A    B    C    A    B    C    A    B    C
0    0    0    0    0    0    0    0    0
0    1    0    0    0    0    0    0   222
0   222 33333  1   222 33333  1    0  33333
1:B->A 2:B->C 1:A->C
 
A    B    C
0    0    1
0    0   222
0    0  33333
7回移動
 
■ 考察
▼ n = 3の時の手順
  A    B    C   A    B    C    A    B    C

  1    0    0   0    0    0    0    0    0
 222   0    0   0    1    0    0    1    0
33333  0    0 33333 222   0    0   222 33333
1～2:A->B 3:A->C 1～2:B->C
 
▼ nの時の手順
1～n-1の円盤をA->B
nの円盤をA->C
1～n-1の円盤をB->C
 
以上の手順で完成する
 
▼ 移動回数N(n)
n = 1 ⇒ N(1) = 1回
n = 2 ⇒ N(2) = N(1)+1+N(1) = 2N(1)+1 = 2¹+2⁰ = 2²-1 = 3回
n = 3 ⇒ N(3) = 2N(2)+1 = 2(2+1)+1 = 2²+2¹+2⁰ = 2³-1 = 7回
…
N(n) = N(n-1) + 1 + N(n-1) = 2N(n-1) + 1
= 2(…2(2+1)+1…)+1 = 2^n-1 + … + 2⁰ = 2ⁿ - 1 回
 
補足
2²+2¹+2⁰ = 111(2進数) = 1000(2進数) - 1 = 2³ - 1
 
▼ n = 64の移動時間
n = 64のハノイの塔を1回/秒で移動させて完成するまでの
時間が宇宙の寿命というお話(神話?)があります
 
N(64) = 2⁶⁴ - 1 = 18,446,744,073,709,551,615回
 
グレゴリオ暦(現在の使用されている暦)の1年は
365 + 1/4 - 1/100 + 1/400 = 365 + 0.25 - 0.01 + 0.0025 = 365.2425日/年
(春分点を基準とした太陽年は約362.24219日)
3600×24×365.2425 = 31,556,952秒/年(グレゴリオ暦)
 
18,446,744,073,709,551,615回 × 1回/秒 / 31,556,952秒/年
= 584,554,049,253.855429859005…
≒ 5846億年
 
n = 64のハノイの塔を1回/秒で移動させて完成するまでの時間は
約5846億年
 
宇宙の余命は1400億年以上、宇宙の年齢は137億年といわれているので
宇宙の寿命は約1537億年以上という事になる
 
実際とはずいぶん誤差がありますが
作り話にしては近い値なのではないかと思います
 
 
■ 結果
▼ nの時の手順
1～n-1の円盤をA->B
nの円盤をA->C
1～n-1の円盤をB->C
の手順で完成する
 
▼ 移動回数N(n)
N(n) = 2ⁿ - 1 回
 
▼ n = 64の移動時間
1回/秒として
N(64) = 2⁶⁴ - 1 = 18,446,744,073,709,551,615回
3600×24×365.2425 = 31,556,952秒/年(グレゴリオ暦)
 
18,446,744,073,709,551,615回 × 1回/秒 / 31,556,952秒/年
≒ 5846億年(宇宙の寿命というお話がある)
 
宇宙の寿命は約1537億年以上なので
作り話にしては近い値なのではないかと思います