C++ でフィボナッチ数列をメモ化してみた

C++

そういえば書いたことがなかったかも？と思ったので C++ でフィボナッチ数列をメモ化してみました。 ポイントはメモ化したデータをグローバル領域に置きたくなかったので関数オブジェクト化してメモ化したデータはメンバ変数で保持するようにしました。

[コード]

#include <vector>
#include <iostream>

#define USE_OPTIONAL 0

#if USE_OPTIONAL
#  include <experimental/optional>
#endif


struct fibonacci{
    using value_type = std::size_t;

#if USE_OPTIONAL
    std::vector<std::experimental::optional<value_type>> memo = { 0, 1 };
#else
    // optional を使わない場合はこっち
    std::vector<value_type> memo = { 0, 1 };
#endif

    value_type
    operator ()(value_type value){
#if USE_OPTIONAL
        if( memo.size() > value && (memo[value]) ){
            return memo[value].value();
        }
        memo.resize(value + 1);
#else
        // optional を使わない場合はこっち
        if( memo.size() > value && (memo[value] || value == 0) ){
            return memo[value];
        }
        memo.resize(value + 1, 0);
#endif

        value_type result = (*this)(value - 2) + (*this)(value - 1);

        memo[value] = result;
        return result;
    }
};


int
main(){
    fibonacci fib;

    for(int i = 0 ; i < 40 ; ++i){
        std::cout << fib(i) << std::endl;
    }
    return 0;
}

[出力結果]

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229

『データが初期化されてるかどうか』を判定するために std::experimental::optional を使用してるのでちょっとコードが複雑になっていますが、実装自体はそんなに難しくないと思います。
まあ、std::vector に各数値の結果を保存しているだけですね。

[参照]