バイナリ値を使ってハノイの塔の問題を解くC++プログラム

ハノイの塔は、3本の杭と複数の円盤を使った古典的なパズルです。本記事では、2進数（バイナリ値）を活用してハノイの塔の移動手順を出力するC++プログラムを紹介します。再帰呼び出しを使わず、ビット演算だけで解を導ける点が大きな特徴です。

バイナリ値による解法の考え方

この手法では、各円盤に1桁の2進数（ビット）を対応させます。n枚の円盤がある場合、全体の状態はn桁のビット列で表現できます。

• 最上位ビットが最大の円盤を表します。値が 0 なら最大の円盤は初期の杭にあり、1 なら最終の杭にあることを意味します。
• ビット列は左から右へ読み進め、各ビットから対応する円盤の位置を特定できます。
• あるビットが直前のビットと同じ値であれば、その円盤は同じ杭上で前の円盤の上に積まれています。
• 値が異なる場合は、その円盤は前の円盤の左または右隣の杭にあることを示します。

なお、n枚の円盤を移動するには最少で 2^n − 1 回の手順が必要となるため、プログラムでは 1 から (1<<n) − 1 までのカウンタを用いてすべての手順を列挙します。

アルゴリズム

Begin
    円盤の枚数 n を入力として受け取る。
    変数 n と a を宣言する。
    a = 1 から (1<<n) − 1 まで繰り返すforループを作る。
    //
    ここで、(a & a−1) は a と a−1 のビットごとのAND演算。
    (a | a−1) は a と a−1 のビットごとのOR演算。
    % は剰余（モジュロ）演算子を表す。
    //
    杭番号 (a & a−1) % 3 から 杭番号 ((a | a−1) + 1) % 3 へ円盤を移動する旨を出力する。
End

サンプルコード

#include<iostream>
using namespace std;
int main() {
    int n, a;
    cout<<"\nEnter the no of Disks: ";
    cin>>n;
    for (a = 1; a < (1 << n); a++) {
        cout<<"\nDisk Move from Peg "<<(a&a-1)%3<<" to Peg "<<((a|a-1)+1)%3;
    }
    cout<<"\n";
}

実行結果

Enter the no of Disks: 3
Disk Move from Peg 0 to Peg 2
Disk Move from Peg 0 to Peg 1
Disk Move from Peg 2 to Peg 1
Disk Move from Peg 0 to Peg 2
Disk Move from Peg 1 to Peg 0
Disk Move from Peg 1 to Peg 2
Disk Move from Peg 0 to Peg 2

まとめ

このプログラムは、ビット演算 (a & a−1) と (a | a−1) を組み合わせることで、移動元と移動先の杭を簡単に算出しています。3で剰余を取ることで杭番号（0〜2）に変換できるのがポイントです。再帰関数を定義せずに済むため、スタックオーバーフローの心配がなく、シンプルで効率的な実装方法として覚えておくと役立ちます。