C++でN番目の偶数フィボナッチ数を求めるプログラム

この問題では、整数値Nが与えられ、N番目の偶数フィボナッチ数を求めることが課題となります。

フィボナッチ数列は、直前の2つの数を加えることで次の数を生成していく数列です。数列はF0とF1という2つの初期値から始まり、初期値には (0, 1) または (1, 1) が用いられます。

問題の確認

まず、具体例を使って問題を理解しましょう。

入力 : N = 4
出力 : 144

解法アプローチ

この問題を解くためのシンプルな方法は、「フィボナッチ数列において3つごとの数が必ず偶数になる」という性質を利用することです。さらに、偶数のみを並べた数列も漸化式に従うという点がポイントです。

偶数フィボナッチ数列の漸化式は次のとおりです。

Ef(n) = 4Ef(n-1) + Ef(n-2)（ただし Ef(0)=0、Ef(1)=2）

フィボナッチ数列の3つごとの数が偶数であることから、f(n-3) と f(n-6) も必ず偶数になります。そこで、f(n) をk番目の要素として Ef(k) と表すと、f(n-3) は直前の偶数である Ef(k-1) に対応し、f(n-6) はそのさらに前の Ef(k-2) に対応します。

したがって、次の関係式が成り立ちます。

f(n) = 4f(n-3) + f(n-6)
すなわち、Ef(k) = 4Ef(k-1) + Ef(k-2)

プログラム例

この解法の動作を示すC++プログラムは以下のとおりです。

#include<iostream>
using namespace std;
int findNthEvenFiboNum(int n){
    if (n < 1)
        return n;
    if (n == 1)
        return 2;
    return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n-2));
}
int main (){
    int n = 5;
    cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n);
    return 0;
}

出力

5th even fibonacci number is 610