C++でフィボナッチ数列の2乗の総和を求める方法

フィボナッチ数列とは

フィボナッチ数列とは、0から始まり「直前の2つの数の和が次の数になる」という規則に従う数学的な数列です。たとえば、最初の数が0、2番目の数が1であれば、その和である1が3番目の数となります。

F0=0, F1=1

これを漸化式で表すと次のようになります。

Fn = Fn-1 + Fn-2
F2 = F0 + F1 = 0 + 1 = 1

さらに、1と1を足すと次の数は2になります。

F1=1, F2=1
F3 = F1 + F2 = 1 + 1 = 2

したがって、フィボナッチ数列は以下のように続いていきます。

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

フィボナッチ数の2乗の総和を求める

今回の課題は、N番目までのフィボナッチ数をそれぞれ2乗し、その合計値を求めることです。

入力：4
出力：15
説明：0² + 1² + 1² + 2² + 3² = 15

解き方の手順はシンプルです。まずN番目までのフィボナッチ数を順に求め、各項を2乗しながら合計に加算していきます。

C++による実装例

#include <iostream>
using namespace std;
int main(){
    int n = 4, c;
    int first = 0, second = 1, next;
    int sum = 0;
    for ( c = 0 ; c < n+1 ; c++ ){
        if ( c <= 1 )
            next = c;
        else{
            next = first + second;
            first = second;
            second = next;
        }
        sum += next * next;
    }
    printf("%d", sum);
    return 0;
}

出力結果

15

コードの解説

このプログラムでは、変数 first と second を使って直前の2つのフィボナッチ数を保持しています。ループ内では、インデックス c が1以下の場合はそのまま c の値（0または1）を次の項とし、それ以外の場合は直前の2項の和を新しい項として計算します。

各反復処理で得られたフィボナッチ数を next * next によって2乗し、変数 sum に加算することで、最終的にN番目までのフィボナッチ数の2乗の総和が求まります。計算量はO(N)であり、非常に効率的なアルゴリズムです。