フィボナッチ数が黄金比に収束するかの確認

フィボナッチ数はプログラムの演習では多用されますが、実際の生活で役に立つようなことはないよなと思っていたら、その比が黄金比になるんですね。

フィボナッチ数が黄金比に収束するかの確認からですが、愚直にフィボナッチ数を計算するといつになったら終了するのか分かりませんから、ここではフィボナッチ数列で使ったようにメモ化してフィボナッチ数を求めます。 また、フィボナッチ数が黄金比に収束するかの確認にも書かれていますが、収束したかどうかを判断するのに絶対値の差が 0.000001 以下であるとして問題を解きます。

#! /usr/bin/gawk -f
# fibonacci_golden.awk

BEGIN {
    golden_rate = 1.618033;

    for (i = 1;; i++) {
        fibonacci_rate = fibonacci_memo(i + 1) / fibonacci_memo(i);
        if (abs(fibonacci_rate - golden_rate) > 1e-6) {
            print fibonacci_memo(i);
        } else {
            exit;
        }
    }
}

# fibonacci_mem()
function fibonacci_memo(n) {

    if (n <= 2) {

        return 1;
    } else if (memo[n] != 0) {

        return memo[n];
    } else {
        memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1);

        return memo[n];
    }
}

# abs()
function abs(num) {
    if (num >= 0) {
        return num;
    } else {
        return -num;
    }
}

実行してみます。

$ busybox awk -f fibonacci_golden.awk
1
1
2
3
5
8
13
21
34
55
89
144
233
377

ちょっとめずらしく Busybox の awk を使ってみました。 Busybox の awk は AwkFeatureComparison を見ても分かるように length() 関数で配列の要素数を取得できないことと asort() 関数が使えないことを除けば gawk と同様の機能が使えることが分かります。 まさに小さな巨人といったところでしょう。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png