C言語 ハノイの塔の説明

Question

#include <stdio.h>

int count = 0;
void move(int no, int x, int y){
    if (no > 1)
        move(no - 1, x, 6 - x - y);

    printf("[%d]を%d軸から%d軸へ移動\n", no, x, y);
    count++;

    if (no > 1)
        move(no - 1, 6 - x - y, y);
}

int main(void) {
    int n;
    printf("円盤の枚数:");
    scanf("%d", &n);

    move(n, 1, 3);

    printf("%d回移動しました。\n", count);
    return 0;
}

上のコードはハノイの塔なのですが、この再帰を理解することができません。
本には「最も大きい円盤以外の円盤をグループとみなせば、円盤の枚数とは無関係に、まったく同じ手続きを実現できます。」と書いてありますが、漠然としていてよくわかりません。

どのように理解すればよいでしょうか？
よろしくお願いいたします。

Answer 1

「最も大きい円盤以外の円盤をグループとみなせば、円盤の枚数とは無関係に、まったく同じ手続きを実現できます。」

「n枚の円盤が積みあがったピラミッド」 を
「n-1枚の円盤が積みあがったピラミッド」が「最大円盤」の上に乗ったもの とみなせば、

「n枚の円盤が積みあがったピラミッド」を x から y に移すには
・「n-1枚の円盤が積みあがったピラミッド」を x から 6-x-y に移す
・「最大円盤」を x から y　に移す
・「n-1枚の円盤が積みあがったピラミッド」を 6-x-y から y に移す

をやればいい。この手順を素直に実装すると

void move(int no, int x, int y){

    // 「n-1枚の円盤が積みあがったピラミッド」を x から 6-x-y に移す
    if (no > 1)
        move(no - 1, x, 6 - x - y);

    // 「最大円盤」を x から y　に移す
    printf("[%d]を%d軸から%d軸へ移動\n", no, x, y);
    count++;

    // 「n-1枚の円盤が積みあがったピラミッド」を 6-x-y から y に移す
    if (no > 1)
        move(no - 1, 6 - x - y, y);
}

Comments

[hogeee]

なるほど、printの部分を最大円盤をｘからｙに移すと考えればよいのですね！
その視点で考えていませんでした！
ありがとうございます！

[episteme]

で、どこが「漠然としていて」よくわからなかったのでしょう?

[hogeee]

関数内の処理をパーツとして考えたときに
パーツ① move(no - 1, x, 6 - x - y);
パーツ② printf("[%d]を%d軸から%d軸へ移動\n", no, x, y);
パーツ③ move(no - 1, 6 - x - y, y);

をなぜこの順番で組むとハノイの塔の関数が完成するのか。もっと言うとなぜパーツ①とパーツ②はこのように再帰させるのかがわかりません。

[episteme]

え? わからないのにベストアンサーつけたんですか?

[hogeee]

あと、このハノイの問題を自分で実装するときに、どういう思考回路でこの関数をくみ上げればよいのかまったくイメージできません。そこが一番悩んでいます。
「最も大きい円盤以外の円盤をグループとみなせば、円盤の枚数とは無関係に、まったく同じ手続きを実現できます。」の考え方はわかるのですが、いざコードに書こうとするとどこから書いていいのか、、、

再帰を使った実装というのが本当に難しいです。自分で処理を考えきれないという感じです。

[hogeee]

＞え? わからないのにベストアンサーつけたんですか?

例えると迷路の答えがわかった感じです。なのでベストアンサーをつけさせていただきました。
しかし、迷路の自力での解き方がわからないという感じです。

Answer 2

書いてのとおりです。複数枚重なっている場合でも、いちばん下の1枚だけ別に考えれば、動かし方は以下のようになります。

1. いちばん下の1枚以外を、動かしたい棒と別の棒に移動させる
2. いちばん下の1枚を、目的の棒まで動かす
3. いちばん下の1枚以外を、動かしたいちばん下の1枚の上に戻す