株式会社ヘキサドライブ | HEXADRIVE

こんにちは
ビッシーです

 

先月の社員研修旅行で四日市市をフィールドワークしていた際、
懐かしい雰囲気のおもちゃ屋さんを見かけたので立ち寄らせて頂きました

 

アレコレ懐かしのおもちゃが見つかり、
お宝の山をドキドキしながら眺めていたのですが・・・

 

 

懐かしのゲーム「ハノイの塔」を見つけました
(そして衝動買いしてしまいました…)

 

 

 

 

 

ハノイの塔は、
3本の柱と大きさの違う円盤の山があり、
円盤を全て隣の柱に動かすというシンプルなゲームです。

 

 

 

 

ただし、円盤を動かすにはルールがあります。

 

1. 必ず一度に一枚ずつ動かすこと

 

2. 自分より小さい円盤の上に大きい円盤を置かないこと

 

この2つのルールを守りながら、
最初にあった円盤の山を隣の柱に移動できたらゲームクリアです。

 

 

一見すると、たった8枚の円盤を隣に動かすだけなので
すぐに終わりそうに見えますが、
実は最低でも 255回 も円盤を動かさないとゲームクリア出来ないのです

 

 

さらにこの手数は円盤が増えれば増えるほど、

爆発的に増えていきます

 

 

64枚の円盤になると、
何と最低 18,446,744,073,709,551,615 回 も
円盤を動かさないとゲームクリアできません

 

(1枚1秒で動かせたとしても、とんでもない時間がかかります)

 

このハノイの塔は計算機科学的に楽しい特徴があるため、
計算機科学の基礎課程で、例題としてよく取り上げられます。

 

 

特徴①
　解き方が再帰的アルゴリズムになっている

 

 

N枚の円盤の山を「隣の柱」に動かすには、
まずN-1枚の円盤の山を「隣の隣の柱」に動かして、
一番大きな円盤を「隣の柱」に動かして、
「隣の隣の柱」にあるN-1枚の円盤の山を「隣の柱」に戻します。

 

N-1枚の円盤の山を「隣の柱」に動かすには、
まず、、、

 

と手順が入れ子のようになります。

 

 

 

特徴②
　入力サイズ(円盤の枚数)に応じて、
　計算量が指数関数的に増加する例題として分かりやすい

 

 

・円盤が1枚のときは、
　「隣の柱」に移動するだけなので手数は1で済みます
・円盤がN枚のときは、
　(「N-1枚の円盤を動かす手数」+ 1回 +「N-1枚の円盤を動かす手数」)回 だけ移動させる必要があります

 

「N枚の円盤を動かすための手数」をH(N)という漸化式で表すと、

 

　　 H(1) = 1
　　 H(n) = H(n-1) + 1 + H(n-1) (n > 1のとき)

 

と表せます。

 

両辺に1を足して、
　　 H(n) + 1 = 2 * (H(n-1) + 1) (n > 1のとき)

 

「H(n) + 1」が等比なので、
　　 H(n) + 1 = 2ⁿ

 

定数項を移動して、
　　 H(n) = 2ⁿ – 1

 

となり、
「N枚の円盤を動かすための手数」は「2のN乗引く1」だと判明します

 

 

 

 

プログラムを書く上でも計算量は大事な要素になります。

 

 

計算量が大きいアルゴリズムだと、

データ量が少ないうちは問題なく動いていたプログラムが、
いざ本番サイズのデータを入力してみると、
いつまで経っても終わらなかったり、
メモリが全く足りなくなってしまったりしてしまいます。

 

 

検索・マッチング・ソートなどプログラムを書く上で良く使うアルゴリズムには、
計算量がどうなのか必ず問題がついて回るので、
実際どの程度の計算量なのか計算することが重要です。

 

 

 

それでは