[C++] フィボナッチ数列をメモ化再帰でn=93までを高速で出力する

フィボナッチ数列の出力をメモ化再帰を用いて高速に出力しました。

c++のunsigned long long型を用いて$n=93$までを出力できるようにしました。

$n=94$以降はunsigned long long型の最大値$18446744073709551615$を超えてオーバーフローしてしまいます。

また、フィボナッチ数列とは次の漸化式を満たす正の整数列です。

$n$を正の整数として、

A(0) = 0,\ \ \ A(1) = 1 \\

A(n) = A(n-1) + A(n-2)\ \ \ \ \ \ \ \ \ (n>=2)

つまり、

A = \{ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ ... \}

となる数列である。

実装 [C++]

再帰のみで実装

単純に実装すると、次のようになります。

# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull fibonacci(ull a);

int main() {
    ull n;
    cin >> n;

    ull ans = fibonacci(n);

    cout << ans << endl;

    return 0;
}

ull fibonacci(ull a) {
    if (a == 0 || a == 1) {
        return a;
    } else {  
        return fibonacci(a-1) + fibonacci(a-2);
    }
}

C++で実装する際に、いくらC++が高速な言語であっても愚直に再帰で解こうとすると計算複雑性は$O(2^n)$となるので$n=50$程度で計算時間が数秒ではなくなってしまいます。

メモ化再帰を利用する

そこで、すでに計算されたフィボナッチ数を記録しておき、それぞれのフィボナッチ数を求める前にすでに計算されいているか確認するようにしました。

もし、すでに計算されていれば、その値を参照するようにします。

次のようになります。

# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull fibonacci(ull a);

map<ull, ull> fibomap;

int main() {
    ull n;
    cin >> n;

    fibomap[0] = 0;
    fibomap[1] = 1;

    ull ans = fibonacci(n);

    cout << ans << endl;

    return 0;
}

ull fibonacci(ull a) {
    if (a == 0 || a == 1) {
        return a;
    } else {
        if (fibomap.find(a-1) != fibomap.end()) {
            if (fibomap.find(a-2) != fibomap.end()) {
                return fibomap[a-1] + fibomap[a-2];
            } else {
                fibomap[a-2] = fibonacci(a-2);
                return fibomap[a-1] + fibomap[a-2];
            }
        } else {
            if (fibomap.find(a-2) != fibomap.end()) {
                fibomap[a-1] = fibonacci(a-1);
                return fibomap[a-1] + fibomap[a-2];
            } else {
                fibomap[a-1] = fibonacci(a-1);
                fibomap[a-2] = fibonacci(a-2);
                return fibomap[a-1] + fibomap[a-2];
            }
        }
    }
}

メモ化再帰することで計算複雑性は$O(n)$になり高速で計算できます。

しかし、今回はC++のunsigned long long型を使用しているので$n=94$でオーバーフローしてしまいました。

もし、$n=94$以降も高速で求められる方法がありましたら、ぜひコメントで教えてください。