ハノイの塔

ハノイの塔とは、3本の棒と大きさの異なる複数の円盤を使って、円盤をすべて別の棒に移動させる数学パズルです。再帰的な処理を説明するための古典的な教材として知られています。

このパズルは、円盤の数を増やすと移動回数が指数関数的に増加するという特徴があります。計算機科学においては、複雑な問題を小さな問題に分割して解く再帰アルゴリズムの挙動を示す際によく用いられます。

G検定の文脈では、直接の計算問題が出ることは稀ですが、指数関数的な計算量の増加や、再帰的アルゴリズムの考え方を理解するための具体例として頻出します。計算の複雑さとアルゴリズムの設計思想を学ぶ上で重要です。