[C]「いくつかの言語でフィボナッチ数生成」を考える。

[awk,Ruby,C#,Java]いくつかの言語でフィボナッチ数生成はいくつかの言語でフィボナッチ数を生成したけど、なんだか必要以上に複雑になってしまった。
こんなんじゃダメなんだろうか？

fib1.c

#include <stdio.h>

int main(void) {
    int f = 1, fn = 1;
    for (int i = 0; i < 10; i++) {
        printf("%d\n", f);
        fn += f;
        f = fn - f;
    }

    return 0;
}

なんの問題もない。これでいい。
じゃあ、なんで前回みたいなやり方が出てくるんだろう。

fib1.cだと、ループの中で今回の値の出力と次の項の値の生成の処理が一緒になってしまっている。これは分けた方が良さそうだ。

fib2.c

#include <stdio.h>

static int* fib(int list[], size_t n) {
    int f = 1, fn = 1;
    for (size_t i = 0; i < n; i++) {
        list[i] = f;
        fn += f;
        f = fn - f;
    }

    return list;
}

int main(void) {
    int f[10];
    fib(f, 10);

    for (int i = 0; i < 10; i++) {
        printf("%d\n", f[i]);
    }

    return 0;
}

さて、これで数列の生成処理と出力処理が分離できた。

でもちょっと待ってほしい。
これだと、生成した項数分の配列領域が必要になってしまう。
リストがほしいのならいいけど、fib1.cでは覚えておかなければいけない項数分しか記憶領域を消費していなかったはずだ。

fib3.c

#include <stdio.h>

static int* fib_init(int fib[2]) {
    fib[0] = fib[1] = 1;
    return fib;
}

static int fib_next(int fib[]) {
    int f = fib[0];
    fib[0] = fib[1];
    fib[1] += f;

    return f;
}

int main(void) {
    int fib[2];
    fib_init(fib);

    for (int i = 0; i < 10; i++) {
        printf("%d\n", fib_next(fib));
    }

    return 0;
}

※Cでは配列引数に要素数を書いても意味はないけど、要素数2の配列を要求しているよ、ってことを明示するためにfib_init(int fib[2])としているよ。
初項の数分だけ領域を使って、次の項を求めるようにしたのがfib3.cだ。
これはint[2]の配列を状態を覚えておくためのハンドルとして使っているような感じになっている。

ちょっと、Enumerationぽくなってきただろうか。
さらに漸化式部分を一般化してみよう。

fib4.c

#include <stdio.h>

static int sequence_next(int term[], size_t n, int f(int*)) {
    int s = term[0];

    int next = f(term);
    for (size_t i = 0; i < n - 1; i++) {
        term[i] = term[i + 1];
    }
    term[n - 1] = next;

    return s;
}

static int fibonacci(int term[]) {
    return term[0] + term[1];
}

int main(void) {
    int fib[2] = { 1, 1 };

    for (int i = 0; i < 10; i++) {
        printf("%d\n", sequence_next(fib, 2, fibonacci));
    }

    return 0;
}

これで初項と漸化式を与えれば、数列を生成してくれるようになったね。
渡す初項と漸化式を表す関数を変えれば、別の数列にもなるよ。

// 公比3の等比数列
static int geom3(int term[]) {
    return term[0] * 3;
}

int main(void) {
    int a[1] = { 1 };

    for (int i = 0; i < 10; i++) {
        printf("%d\n", sequence_next(a, 1, geom3));
    }

    return 0;
}

以上をまとめるとこんな感じだろうか。

1. リストの列挙処理と消費処理を分離する。
2. 項目数分の領域を消費しない。
3. 具体的な生成方法は外から与える。

でも、実のところfib1.cのようなやり方の方がシンプルでいい場合だって多くある。
その場だけででなく、同じ列挙生成をいくつかの場面で使うのであれば、fib4.cのような方法がいいかもしれない。