C++ でのハノイの塔

1. ハノイの塔
2. ハノイの塔問題の解決
3. ハノイの塔問題の C++ プログラム

この記事では、ハノイの塔問題とその C++ での再帰的な解決策について簡単に説明します。

ハノイの塔

ハノイの塔は、3 本の棒と棒の周りを移動できる複数の円盤を含む数学的パズルです。 ディスクは、サイズが小さい順に上から下に配置され、スタックを形成します。

目標は、目的の (最後の) ロッド内のすべてのディスクを移動することです。順序は同じですが、いくつかの規則に従います。

1. 一度に移動できるディスクは 1つだけです。
2. ディスクは、それ自体より小さいディスクには配置できません。

これらの規則に従って、ディスクを最初のロッドまたはペグから最後のロッドに移動する必要があります。 このタスクを達成するために必要な移動の最小数は、2^n -1 です。ここで、n はディスクの数です。

これを下の図に示します。

Peg B の助けを借りて、Peg A のこれら 3つのディスクを移動先の Peg C に移動する必要があります。

ハノイの塔問題の解決

この問題には反復的な解決策と再帰的な解決策の両方が考えられますが、反復はディスクの数に依存するため、ここでは再帰的な解決策について説明します。 再帰的な解決策として、Peg A に m 個のディスクがあるとします。

1. m-1 ディスクを Peg A から Peg B に移すのに、同じ基本的な方法が使用されます。 ルールに違反しないと仮定すると、ディスク m が Peg A の一番上のディスクになります。
2. ディスク m を ペグ A から目的のペグ、つまり ペグ C に移動します。これは簡単な手順であり、一般的な規則に従います。
3. 同じ方法を使用して、先ほど Peg B に取り付けた m-1 ディスクを Peg B から目的のペグ、つまり Peg C に移動します。 制限を破ることなくディスクm。
4. 終了ケースに到達するまで、これらの手順を繰り返します。
5. 終了ケースは、0 個のディスクを移動することです。つまり、すべてのディスクが移動先のペグにあります。

ハノイの塔問題の C++ プログラム

この問題を解決する C++ プログラムを以下に示します。

void TowerOfHanoi(int m, string first, string middle, string last) {
  cout << "Current iteration " << m << endl;
  if (m == 1) {
    cout << "Moving Disc from " << first << " to " << last << endl;
  } else {
    TowerOfHanoi(m - 1, first, last, middle);
    cout << "Moving disc " << m << " from " << first << " to " << last << endl;
    TowerOfHanoi(m - 1, middle, first, last);
  }
}
int main() {
  int di = 3;
  TowerOfHanoi(di, "PegA", "PegB", "PegC");
}

これにより、次の出力が得られます。

関数 TowerOfHanoi では、反復ごとに関数を 2 回呼び出すことに注意してください。 まず、最初のペグから中央に移動し、次に中央から最後に移動します。

これにより、次のツリーが作成されます。

main
  |--> TowerOfHanoi(3, ...)
  |      |
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |<-----|
  |