【C言語】ハノイの塔の解法：再帰アルゴリズムの実装とステップ解説

この記事は、C言語でハノイの塔問題を再帰アルゴリズムを使って解決する方法を簡潔に解説します。

具体的なコード例を交えながら、再帰処理による動作の流れや各ステップの操作をわかりやすく説明します。

既に開発環境が整っている方向けに、実践的な実装手順を中心に紹介します。

ハノイの塔問題の基礎知識

問題の定義とルール

ハノイの塔は、3本の柱と複数の円盤を用いたパズルです。

最初に、円盤は大きいものから小さいものへと順に一つの柱に積まれており、目的はすべての円盤を別の柱に移動することです。

ただし、以下のルールに従って移動しなければなりません。

• 一度に1つの円盤しか動かせない
• 大きい円盤の上に小さい円盤を置くことはできない

これにより、アルゴリズムの設計は慎重な順序と条件チェックが必要になります。

塔の構造と移動条件

ハノイの塔では、柱を「開始柱」「補助柱」「目的柱」として扱います。

各柱は、円盤の重なり状況を管理するために、スタックや配列として実装されることが多いです。

移動条件は次のように整理できます。

• 移動前に移動元の柱に円盤が存在するかを確認する必要があります。
• 移動先の柱が空であるか、または先に置かれている円盤より小さい円盤であるかをチェックします。

これらのチェックを通じて、プログラムは正しい順序で円盤の移動を実現できます。

再帰アルゴリズムの基本

再帰処理の仕組み

再帰処理とは、関数が自分自身を呼び出すことで処理を進める手法です。

複雑な問題をより小さな部分問題に分割し、同じ関数で解決できるため、ハノイの塔のような再帰的な問題に非常に適しています。

再帰を用いる場合、問題を段階的に解くための明確なロジックが必要になるため、問題を「最小単位」にまで分解することを意識します。

ベースケースの設定

再帰関数では、無限ループに陥らないように必ず終端条件(ベースケース)を設定する必要があります。

ハノイの塔の場合、円盤が1枚だけの場合は直接移動することで処理が終了するため、これがベースケースとなります。

数学的には、円盤が1枚の場合の移動は以下のように表されます。

$$T(1)=1$$

再帰呼び出しの流れ

再帰的な解法では、まず円盤の最上部を除いた残りの円盤を別の柱へ移動し、その後最下部の円盤を目的の柱へ移動します。

その後、補助柱に移動しておいた円盤を目的の柱に重ねて移動するという手順となります。

この一連の流れは、円盤がn枚の場合に対して以下の式で表現されます。

$$T(n)=T(n-1)+1+T(n-1)$$

このような数式は、アルゴリズムの流れを視覚的に理解するのに役立ちます。

C言語における再帰実装

関数定義と呼び出し

C言語で再帰アルゴリズムを実装する際は、まず再帰関数を定義し、その中で自身を呼び出す形を取ります。

以下は、ハノイの塔の再帰関数のサンプルコードです。

#include <stdio.h>
// moveDisk: 円盤を1枚移動する処理(移動内容を表示)
void moveDisk(int disk, char fromPeg, char toPeg) {
    // 円盤の移動内容を表示する
    printf("Move disk %d from %c to %c\n", disk, fromPeg, toPeg);
}
// hanoi: 再帰的にハノイの塔の解法を実行する関数
void hanoi(int disks, char fromPeg, char auxPeg, char toPeg) {
    // 円盤が1枚の場合は直接移動
    if (disks == 1) {
        moveDisk(disks, fromPeg, toPeg);
        return;
    }
    // 残りの円盤を補助柱に移動
    hanoi(disks - 1, fromPeg, toPeg, auxPeg);
    // 一番大きな円盤を目的の柱に移動
    moveDisk(disks, fromPeg, toPeg);
    // 補助柱にある円盤を目的の柱に移動
    hanoi(disks - 1, auxPeg, fromPeg, toPeg);
}
int main(void) {
    int totalDisks = 3; // 円盤の枚数
    // ハノイの塔の解法を実行
    hanoi(totalDisks, 'A', 'B', 'C');
    return 0;
}

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

このサンプルコードでは、関数hanoiが再帰的に自身を呼び出しながら解法を進めています。

また、moveDisk関数により円盤ごとの移動内容が出力され、処理の流れが分かりやすくなっています。

メモリ管理の留意点

再帰呼び出しは呼び出しごとに関数の実行環境をメモリ(スタック)上に積むため、円盤の枚数が多くなるとスタック領域が不足する可能性があります。

そのため、実装時は以下の点に注意する必要があります。

• 円盤の枚数が非常に大きい場合のスタックオーバーフローを防ぐために、円盤の枚数に制限を設ける
• 再帰呼び出しの深さを考慮して、メモリ使用量を把握する

必要に応じて、再帰を使用せずにループなどで同じ処理を実現する手法も検討できます。

ハノイの塔解法の実装手順

プログラム設計と構成要素

ヘッダファイルと定数宣言

C言語でハノイの塔を実装する際は、まず必要なライブラリをインクルードし、プログラム内で使用する定数やマクロを宣言します。

たとえば、円盤の最大枚数や柱を表す文字を定数として定義することで、可読性が向上します。

• 標準入出力ライブラリstdio.hを使用して出力を行います。
• 円盤の枚数や柱の名前を定義することで、コード内のハードコーディングを避けます。

以下のサンプルコードは、ヘッダファイルの取り扱いと定数宣言の例となります。

#include <stdio.h>
#define MAX_DISKS 10  // ハノイの塔で扱う最大の円盤数
// プロトタイプ宣言
void moveDisk(int disk, char fromPeg, char toPeg);
void hanoi(int disks, char fromPeg, char auxPeg, char toPeg);

関数分割の方針

プログラム全体を見やすく保つために、主要な処理を複数の関数に分割する方針を採用します。

具体的には、以下のような分割が考えられます。

• main関数：プログラムのエントリーポイント。ハノイの塔の解法を呼び出す
• hanoi関数：再帰的なアルゴリズムを実装し、円盤の移動を制御する
• moveDisk関数：実際の円盤移動処理(移動内容を出力)を担当する

このように関数を分割することで、各関数の役割が明確になり、プログラムの保守性が向上します。

再帰アルゴリズムによる移動処理

各ステップの再帰処理

再帰アルゴリズムによる解法は、円盤の枚数を減らしながら問題を再帰的に解いていく手法です。

以下の手順で処理が進みます。

1. 円盤が1枚の場合は、直接目的の柱へ移動する
2. 円盤が複数ある場合、まず一番上の円盤以外を補助柱へ移動する
3. 次に、一番下の円盤を目的の柱へ移動する
4. 最後に、補助柱へ移動した円盤群を目的の柱へ再配置する

この手順は、再帰的に同じ処理を繰り返すことで、最終的な解法に至ります。

各呼び出しごとに移動処理の流れが追跡でき、デバッグも容易になります。

具体的な移動例の説明

たとえば、3枚の円盤の場合、以下のような移動が実行されます。

• まず、最小の円盤1を開始柱Aから目的柱Cに移動します。
• 次に、円盤2をAから補助柱Bに移動します。
• 円盤1をCからBに移動して、円盤2の上に乗せます。
• 円盤3(最大の円盤)をAからCに移動します。
• 残りの円盤群として、円盤1と円盤2を補助柱BからCに移動します。

この具体例は、再帰関数の呼び出しでどのようにアルゴリズムが進んでいくのかを直感的に示しています。

リストや表を用いて動作を視覚化すると、次のように整理できます。

円盤が3枚の場合の移動例

• Move disk 1: A → C
• Move disk 2: A → B
• Move disk 1: C → B
• Move disk 3: A → C
• Move disk 1: B → A
• Move disk 2: B → C
• Move disk 1: A → C

これにより、各ステップが順を追って理解できるようになります。

出力結果の確認と実行手順

実装したコードの正しさは、出力結果で確認することができます。

サンプルコード実行時には、各円盤の移動内容が標準出力に表示されるため、どのような順序で移動が実施されたかを確認できます。

具体的な手順は以下の通りです。

1. コンパイル時に、標準入出力ライブラリが正しくリンクされることを確認する
2. プログラムを実行して、各移動が画面に表示されることを確認する
3. 表示される移動順序がアルゴリズムの想定通りであれば、実装が正しいと判断できる

以下は、前述のハノイの塔解法のサンプルコードを用いた実行例です。

#include <stdio.h>
void moveDisk(int disk, char fromPeg, char toPeg) {
    // 円盤の移動内容を出力する
    printf("Move disk %d from %c to %c\n", disk, fromPeg, toPeg);
}
void hanoi(int disks, char fromPeg, char auxPeg, char toPeg) {
    if (disks == 1) {  // ベースケース：円盤が1枚の場合
        moveDisk(disks, fromPeg, toPeg);
        return;
    }
    // 円盤n-1枚を補助柱に移動
    hanoi(disks - 1, fromPeg, toPeg, auxPeg);
    // 一番大きな円盤を目的の柱に移動
    moveDisk(disks, fromPeg, toPeg);
    // 補助柱にある円盤を目的の柱に移動
    hanoi(disks - 1, auxPeg, fromPeg, toPeg);
}
int main(void) {
    int totalDisks = 3;  // 円盤の枚数を指定
    hanoi(totalDisks, 'A', 'B', 'C');  // ハノイの塔の解法を実行する
    return 0;
}

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

このサンプルでは、実際の実行結果と移動手順が一致していることが確認でき、正しくハノイの塔の解法が機能していることが分かります。

実装時の注意点

コードの可読性向上策

コードの可読性を高めるため、以下の点に注意しています。

• 変数名・関数名は英語で記述し、役割が明確になるよう努めます。たとえば、hanoi関数やmoveDisk関数など、役割を端的に表現しています。
• コメントを適切に記述し、各処理の意図や再帰呼び出しの流れが誰にでも理解しやすくなるよう配慮します。
• インデントや空行を活用し、ソースコード全体のレイアウトを整えることで、視覚的な整理も行います。

これにより、将来的なメンテナンスや他の開発者との協働時にも、コードの理解や改変が行いやすくなります。

デバッグと最適化のポイント

再帰アルゴリズムを実装する際に注意するポイントは以下の通りです。

• 再帰の深さを検証し、意図しない無限再帰が起きていないか確認します。
• 特に円盤の枚数が多くなるとスタック領域の消費が激しくなるため、実行時のメモリ使用量をモニタリングする必要があります。
• デバッグ時は、各関数呼び出し部に簡単な出力を入れることで、処理の流れを追いやすくする手法が有用です。
• コンパイラの最適化オプションを利用し、不要な再帰呼び出しが最適化されるよう設定することで、実行速度の向上も期待できます。

これらのポイントを意識することで、再帰アルゴリズムを用いた実装でもトラブルシューティングがしやすく、安定したプログラムの提供が可能になります。

まとめ

この記事では、C言語を用いてハノイの塔の問題の基礎知識、再帰アルゴリズムの仕組み、実装手順および注意点について詳しく解説しましたでした。

記事を通して、再帰処理の基本原理や関数分割、デバッグや最適化の具体的なアプローチがシンプルに理解できる内容となっています。

ぜひサンプルコードを実際に実装し、再帰アルゴリズムの有効性を体験してみてください。