解法:ハノイの塔 [C]

「ハノイの塔」の解法です。

n枚のハノイの塔の解法は再帰的に定義できます。

解法

  1. n = 1 の場合
    1. 移動元 (Source) の1枚を移動先 (Destination) に移動
  2. 1 < n の場合
    1. (n – 1)枚を移動元 (Source) から空き場所 (Temporary) に移動
    2. 移動元 (Source) の1枚を移動先 (Destination) に移動
    3. (n – 1)枚を空き場所 (Temporary) から移動先 (Destination) に移動

n枚のハノイの塔の移動手順を表示する関数

void hanoi(int n, char *src, char *tmp, char *dst)
{
    /* n = 1 の場合 */
    if (n == 1) {
        /* 移動元 (Source) の1枚を移動先 (Destination) に移動 */
        printf("%s -> %s\n", src, dst);
    }
    /* 1 < n の場合 */
    else {
        /* (n - 1)枚を移動元 (Source) から空き場所 (Temporary) に移動 */
        hanoi(n - 1, src, dst, tmp);

        /* 移動元 (Source) の1枚を移動先 (Destination) に移動 */
        printf("%s -> %s\n", src, dst);

        /* (n - 1)枚を空き場所 (Temporary) から移動先 (Destination) に移動 */
        hanoi(n - 1, tmp, src, dst);
    }
}

n枚のハノイの塔の移動手順を表示する関数(シンプル版)

void hanoi(int n, char *src, char *tmp, char *dst)
{
    /* 0 < n の場合 */
    if (0 < n) {
        /* (n - 1)枚を移動元 (Source) から空き場所 (Temporary) に移動 */
        hanoi(n - 1, src, dst, tmp);

        /* 移動元 (Source) の1枚を移動先 (Destination) に移動 */
        printf("%s -> %s\n", src, dst);

        /* (n - 1)枚を空き場所 (Temporary) から移動先 (Destination) に移動 */
        hanoi(n - 1, tmp, src, dst);
    }
}

サンプルコード

塔の名前を A・B・C とし、1〜3枚のハノイの塔の移動手順を順番に表示します。

hanoi.c

About TSUCHIDA Takuya

生まれ変わったら黒猫になりたいシステムアーキテクトです。僕への連絡は右下の MessageLeaf からお願いします。
This entry was posted in Solution and tagged , , . Bookmark the permalink.