フィボナッチ数列 (その 2)

22歳事務員の悩みを見ながら、プログラマになるのはそんなに魅力的なのかな? と考えていました。 鶏口牛後という言葉がありますが、周りがプログラマだとその中で認められるのは大変なことですが、事務職や製造業のようなところで頭角を現すというのも悪くないと思うんですけどね。 製造業でも e-Manufactureing と言う言葉があり、IT 化 (というよりも昔の AI のような位置づけに近いかな) の波は押し寄せています。 そういうものの導入の際にプログラミングの知識を生かすのも面白いのではないでしょうか?

さて、今回はまたフィボナッチ数列です。 どなたかプログラミングが得意な方、お願いします!(お礼はコイン50枚!) ...というタイトルが付いていますが、要するに宿題です。 既に書いたフィボナッチ数列では再帰を使った方法とさらにメモ化を使った方法を用いていますが、宿題であれば「○○を習った後に出された宿題です」と言わないと、どういう方法で解けばいいのか迷ってしまいます。 回答が再帰ではない方法で書かれていますので、同じアルゴリズムで awk で記述してみます。

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

BEGIN {

    # 初期化
    n  = 1;
    fn  = 0;
    fn2 = fn = 1;

    # デフォルトで 30 回ループ
    while (n < 30) {
        n++;
        fn = fn1 + fn2;
        printf("n = %d, fn = %d\n", n, fn);
        fn1 = fn2;
        fn2 = fn;
    }
}

ここでは前のフィボナッチ数列に合わせて 30 回のループにしています。 実行してみましょう。

$ time gawk -f fibonacci_norecursive.awk
n = 2, fn = 1
n = 3, fn = 2
n = 4, fn = 3
n = 5, fn = 5
n = 6, fn = 8
<snip>
gawk -f fibonacci_norecursive.awk  0.00s user 0.00s system 45% cpu 0.002 total

フィボナッチ数列の際に用いた PC と同じなので、かなり高速に処理できていることが分かります。 決して再帰が悪いアルゴリズムであるという意味ではなく、可能であれば解析的に解く手法で解いた方が効率が良いということです。 再帰はフィボナッチ数の定義をほぼそのまま忠実に定義できるので間違いが少なく、プログラムに必要とする脳力を節約できるでしょう。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png