偶数のフィボナッチ数 復習

C Project Euler

これは以前に書いた 偶数のフィボナッチ数 (Dec 10, 2011) の補足です.

開発の経験はまったくないし, 今後も経験する可能性のきわめて低い高齢者の身ですが, 最近ふとバージョン管理システムというものに興味を持ちまして, 自分の Windows PC に msysGit をインストールし, そして GitHub にもアカウント登録をしました.

何かソースコードを書いてアップしてみたいなと思い, Hello World レベルのものをちょこちょこ push してみたりして遊んでいましたが, そういえばそうそう, 以前ちょっとやりかけて挫折した Project Euler をネタにしてもいいんじゃないかなという気がしてきました. ふだん Twitter でフォローさせていただいている @sano66 さんも GitHub に Project Euler の練習風景をアップしていらっしゃったなあと思い出しまして, わたしもやってみようかなと考えました.

で, せっかくなので, Project Euler にもアカウント登録をして, また取り組んでみようかなという思いが沸き起こっているのが現状です. (たぶんこの土日で熱が冷める可能性大ですが...)

さて, 本日 Problem 2 (Oct 19, 2001) をやりなおした際に, 前回は気づかなかった小さなことを知ることができましたので, ものを書くというリハビリも兼ねて, 久しぶりにこのはてな日記を書いています.

出題内容

出題内容を再掲します.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

フィボナッチ数の数列が 1 と 2 からスタートするという条件において, 4,000,000 未満のフィボナッチ数のうち偶数であるものすべての合計はいくつですか, という問題です.

初歩的な解法

初歩的な解法は, フィボナッチ数をひとつずつ求め, それが偶数かどうかを判定し, 偶数であれば合計に加算していきます. フィボナッチ数を求める際に再帰的な方法を使うのは, スタック領域が徐々に食いつぶされるのが悩ましいような気がするので, あまり好きではありません. そこで, 次のようなコードにしました.

int solution0() {
    int f0 = 1, f1 = 2, f2;
    int sum = 2;
    while ((f2 = f0 + f1) < 4000000) {
        if (f2 % 2 == 0)
            sum += f2;
        f0 = f1;
        f1 = f2;
    }
    return sum;
}

多少は考えたつもりの解法

フィボナッチ数の数列においては, 3 項ごとに偶数があらわれます. F1 が偶数なら, 次の偶数は F4 だということです. そこで, Fn と Fn+1 から Fn+3 と Fn+4 を求めることを繰り返していけば, ループの回数は 3 分の 1 で済むんじゃないかと考えました.

int solution1() {
    int f0 = 1, f1 = 2, sum = 0;
    while (f1 < 4000000) {
        sum += f1;
        int f3 = f0 + 2 * f1;
        int f4 = 2 * f0 + 3 * f1;
        f0 = f3;
        f1 = f4;
    }
    return sum;
}

もうちょい工夫すれば得られたはずの解法

以上の 2 とおりの解法は, 以前の日記にも書いたとおりです. (ソースコードの書き方自体は, ちょっと変わりましたが, 考え方は同じだと思います.) 今回も, ここまででいったん満足し, Project Euler にログインして解答を送信し, 正解を得ることができました.

ところで, Project Euler にアカウント登録すると, 正解するたびに, 問題を解説した PDF 文書を閲覧することができるという特典がつくのですね. 今回は, それを読んで, ささやかなアハ体験がありました.

先ほど, Fn と Fn+1 から Fn+3 と Fn+4 を求めると書きました. 自分では, これが精一杯と思い込んでいたのですね. ところが, 解説を読んで, しまったと思いました. 要するに, Fn と Fn+3 から Fn+6 を求めるようにすれば, 余計な補助的な変数を増やさなくても済むのですね.

指摘されてみると, たしかに簡単な式変形で, できるのですね. 高校生のときなら, たぶん自力で見つけたかもしれませんが, 老化というのは恐ろしいものです.

int solution2() {
    int f0 = 2, f1 = 8, f2 = 34, sum = f0 + f1;
    while (f2 < 4000000) {
        sum += f2;
        f0 = f1;
        f1 = f2;
        f2 = 4 * f1 + f0;
    }
    return sum;
}

比較

ここで少し話は脱線します. C 言語の勉強は, 基本的には プログラミング言語C 第2版 ANSI規格準拠 (共立出版 ©1989 ISBN4-320-02692-6) を読むことしかしていませんでした. 俗に K&R と呼ばれている書籍の邦訳です. そのため, 文法は多少理解したとしても, 実際にどのようにビルドするのかがまださっぱりわかっていません.

そこで, 今回はじめて自分で Makefile を書いてみました.

main: *.c

これは, プログラミングを趣味や職業とされている方々から見れば非常に小さな一歩に過ぎないと思いますが, わたしにとって非常に大きな飛躍の一歩であります.

まあ, そんなことはどうでもいいや. (誰だって最初はこんなものでしょう?)

前述の各解法を solution0.c, solution1.c, solution2.c という感じのファイルにし, 次のコードを main.c というファイルにします.

#include <stdio.h>
#include <time.h>

extern int solution0();
extern int solution1();
extern int solution2();

int main(int argc, char *argv[]) {
    clock_t t0, t1;
    int (*solutions[])() = { solution0, solution1, solution2 };
    int i, j, answer;
    for (i = 0; i < sizeof(solutions) / sizeof(solutions[i]); i++) {
        t0 = clock();
        for (j = 0; j <= 65535; j++)
            answer = solutions[i]();
        t1 = clock();
        printf("Solution #%d: %d (%ums)\n", i, solutions[i](), t1 - t0);
    }
    return 0;
}

make して, main.exe を実行します.

Solution #0: 4613732 (12ms)
Solution #1: 4613732 (5ms)
Solution #2: 4613732 (4ms)

まとめ

つまり, そういうわけです. おしまい.