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
に各数値の結果を保存しているだけですね。