シルギア

ハノイの塔とは

読み:はのいのとう

大きさの違う円盤を、ルールに従って別の棒へ移すパズル。最少手数は2のn乗−1回。

ハノイの塔は、3本の棒と、大きさの違う何枚かの円盤を使うパズルです。最初はすべての円盤が1本の棒に大きい順に積まれていて、「一度に動かせるのは1枚だけ」「小さい円盤の上に大きい円盤を置いてはいけない」というルールで、全部を別の棒へ移します。1883年にフランスの数学者エドゥアール・リュカが発表しました。

円盤がn枚のときの最少手数は、2のn乗−1回です。3枚なら7回、4枚なら15回、10枚なら1023回と、1枚増えるごとにほぼ2倍に増えます。「上のn−1枚をよけて、いちばん下を移し、またn−1枚を戻す」という考え方は、プログラミングの再帰の例題としてもよく使われます。

64枚の円盤をすべて移し終えたとき世界が終わる、という伝説が添えられることもあります。1秒に1枚動かしても約5800億年かかる計算で、指数的に増える量の大きさを実感できる例として知られています。

関連する無料ツール

関連する用語

ほかの用語

← 用語集一覧へ / すべてのツール