フィボナッチ数列を生成する方法｜動的計画法によるC++実装を解説

フィボナッチ数列とは

フィボナッチ数列は、以下のように各項が直前の2つの項の和となる数列です。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,……

この数列では、第n項が(n-1)番目の項と(n-2)番目の項の合計として定義されます。

フィボナッチ数列の生成には再帰的なアプローチも利用できますが、動的計画法（DP）を使えば手順はさらにシンプルになります。計算済みのフィボナッチ数をすべて表（配列）に格納しておき、その表を参照することで、以降の項を効率よく求められるのがポイントです。

入力と出力

入力：
項数を入力として受け取る。例：10

出力：
Enter number of terms: 10
10th Fibonacci Terms: 55

アルゴリズム

genFiboSeries(n)

入力： 最大項数 n

出力： 第n項のフィボナッチ数

Begin
    define array named fibo of size n+2
    fibo[0] := 0
    fibo[1] := 1

    for i := 2 to n, do
        fibo[i] := fibo[i-1] + fibo[i-2]
    done
    return fibo[n]
End

C++による実装例

#include<iostream>
using namespace std;

int genFibonacci(int n) {
    int fibo[n+2];          // フィボナッチ数を格納する配列

    // 数列の0番目と1番目はそれぞれ0と1
    fibo[0] = 0;
    fibo[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];     // 直前の2項からi番目の項を生成
    }
    return fibo[n];
}

int main () {
    int n;
    cout << "Enter number of terms: "; cin >>n;
    cout << n<<" th Fibonacci Terms: "<<genFibonacci(n)<<endl;
}

実行結果

Enter number of terms: 10
10th Fibonacci Terms: 55

計算量について

この動的計画法によるアプローチでは、各項を一度だけ計算するため時間計算量はO(n)、結果を格納する配列が必要なため空間計算量もO(n)となります。同じ項を何度も再計算してしまう単純な再帰実装（指数時間かかる）と比較すると、大幅に高速に動作します。