C++でフィボナッチ数列を表示するプログラム【動的計画法・再帰の2つの方法】

フィボナッチ数列とは、各項が「直前の2つの項の和」となる規則性を持つ数列のことです。この規則に従うと、次のような整数列が得られます。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377……

フィボナッチ数を定義する漸化式は以下の通りです。

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

フィボナッチ数列を表示する2つの方法

C++でフィボナッチ数列を表示するには、大きく分けて動的計画法（DP）と再帰的プログラミングの2つのアプローチがあります。それぞれの特徴と実装例を詳しく見ていきましょう。

方法1：動的計画法を使った実装

サンプルコード

#include<iostream>
using namespace std;

void fib(int n) {
    int f[n];
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i < n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    for (i = 0; i < n; i++) {
        cout<<f[i]<<" ";
    }
}

int main() {
    int n = 10;
    fib(n);
    getchar();
    return 0;
}

実行結果

0 1 1 2 3 5 8 13 21 34

プログラムの仕組み

このプログラムでは、main()がドライバ関数として機能し、フィボナッチ数列を実際に生成する処理はfib()関数内にまとめられています。main()からfib()を呼び出すことで一連の処理が開始されます。

まず、フィボナッチ数列の最初のn項を格納するための配列f[n]を作成します。配列の先頭2つの要素は、それぞれ0と1で初期化されます。

f[0] = 0;
f[1] = 1;

その後、forループを使って、各要素を「直前の2つの要素の和」として順番に格納していきます。

for (i = 2; i < n; i++) {
    f[i] = f[i-1] + f[i-2];
}

最後に、完成したフィボナッチ数列を画面に表示します。

for (i = 0; i < n; i++) {
    cout<<f[i]<<" ";
}

動的計画法では一度計算した値を配列に保存して再利用するため、計算量はO(n)となり非常に効率的です。

方法2：再帰を使った実装

続いて、再帰呼び出しを利用してフィボナッチ数列を表示する方法を紹介します。

サンプルコード

#include<iostream>
using namespace std;

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

int main() {
    int n = 10, i;
    for(i=0; i<n; i++)
        cout<<fib(i)<<" ";
    return 0;
}

実行結果

0 1 1 2 3 5 8 13 21 34

プログラムの仕組み

このプログラムでは、forループの中で関数fib()を各項ごとに呼び出し、再帰によってフィボナッチ数列の各項を順に生成しています。

for(i=0; i<n; i++)
    cout<<fib(i)<<" ";

関数fib()は、引数nが0または1の場合にはそのまま0または1を返します。それ以外の場合は、直前の2項の和を求めるために自分自身を再帰的に呼び出し、正しい値が得られるまで計算を繰り返します。

if (n <= 1)
    return n;
return fib(n-1) + fib(n-2);

なお、再帰による実装はコードがシンプルで直感的というメリットがある一方、同じ値を何度も再計算するため項数が増えると処理時間が急激に伸びるというデメリットもあります。大量の項を扱う場合は、動的計画法による実装を選ぶのがおすすめです。