【公式】プログラミングでも使う再帰・漸化式の解き方【ハノイの塔】

こんにちは。iQeda [@iQeeeda] です。

プログラムでは「再帰処理」といって「関数の中でその関数をまた呼び出す」ことがあります。
これによって、欲しい答えを導くための「依存する値」を同時に求めることができます。

ハノイの塔

3 本の細い柱 A, B, C が立っています。
柱 A には穴の開いた円盤が 6 枚積み重なっています。

円盤のサイズは全て異なり、
一番下の円盤が最も大きく、一番上の円盤が最も小さい円盤です。

その 6 枚の円盤を柱 B に移そうと思います。
ただし以下の条件を守ってください。

1 枚の円盤をある柱からある柱へ動かすことを 1 手と考えると、
6 枚の円盤すべてを A から B に移すためには最低何手かかるでしょうか。

少ない円盤で考える

3 枚の円盤で考える

最初から 6 枚で考えるのは大変なので、まず 3 枚の場合で考えます。
上記の画像を見てください。円盤を動かすフェーズは 3 つに別れています。

この「 2 枚の円盤を別の柱に移す」行為は 、2 枚の円盤で考えるときの条件と一緒です。

6 枚の円盤で考える

円盤が 6 枚の場合でも、先ほどと同じように考えることができます。

この「 5 枚の円盤を別の柱に移す」行為も 、5 枚の円盤で考えるときの条件と一緒です。

再帰的な構造

もし問題がこういった構造なのであれば、
0 枚の円盤の答えを使って 1 枚から 6 枚までの答えは「再帰的に」計算できそうです。

n 枚の円盤で考える

柱 A, B, C ではなく x, y, z という値で問題を捉えなおします。

円盤を動かすフェーズで「出発地」「目的地」「経由地点」の見方が変わるからです。
改めて「 n 枚の円盤を、柱 z を利用して柱 x から 柱 y へ移す」とはどういうことか整理します。

n 枚の答えを導くには、やはり n - 1 枚の答えを再利用できそうです。
これを「再帰を使った表現」といいます。

漸化式とは

ここで、手数 H(n) という表現で式を立てることにします。

H(n) における H(n - 1) との関係式のことは「漸化式」といいます。

答え

H(0) の手数がわかり、 H(n - 1) から H(n) を作る方法がわかったので、
残る H(1) から H(6) まで順番に計算していけば 6 枚のときの手数がわかります。

閉じた式とは

H(0) から H(6) の答えに規則性があれば、H(n) の答えも一般化できます。

H(n) は 2^n - 1 という式で表現できそうです。
H(n) を n だけで表現する式のことは「 H(n) の閉じた式」といいます。

この閉じた式が正しいかどうかは「数学的帰納法」を使って証明できます。

数学的帰納法について

0 以上のすべての整数 n について証明することを「数学的帰納法」といいます。
数学的帰納法については以下の記事で詳しく解説しています。

ハノイの塔を解くプログラム

実際に動かした手数を表示する C 言語のプログラムは以下のとおりです。
hanoi という関数の中で hanoi をまた呼び出すという「再帰処理」をしています。

# include <stdio.h>
# include <stdlib.h>

void hanoi (int n, char x, char y, char z);

void hanoi (int n, char x, char y, char z) {
    if (n == 0) {
        // 何もしない
    } else {
        // 再帰処理
        hanoi(n - 1, x, z, y);
        printf("%c->%c, ", x, y);
        hanoi(n - 1, z, y, x);
    }
}

int main (void) {
    hanoi(6, 'A', 'B', 'C');
    return EXIT_SUCCESS;
}

再帰的な構造を見つけだす

ハノイの塔のまとめになります。

大きい数字になると複雑化して問題が解けなくなってしまうことはよくありますが、
今回のように「大きい問題は、一回り小さい問題を使って表現できないか」考えてみてください。

これが「再帰」の基本的な考え方になります。

あわよくば、一発で答えを出せる「閉じた式」が得られると便利ですが、
漸化式だけでも地道に計算すれば具体的な答えが出せますし、問題の性質の把握に繋がります。

CS シリーズ

次回

前回