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

問題概要

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

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

入出力例

入力:

N = 5

出力:

10

解法アプローチ

最もシンプルな解法は、まずフィボナッチ数をすべて求めておき、フィボナッチ数に含まれない数を先頭から順に数えていく方法です。

もう一つの効率的な解法として、フィボナッチ数の性質を利用し、隣り合うフィボナッチ数同士の「間隔(ギャップ)」を順次加算していく方法があります。ギャップの合計を追跡することで、最終的に目的の値が導かれます。本記事では、この効率的なアイデアを採用して解説します。

アルゴリズム

• 現在の要素・直前の要素・前々回の要素を追跡するための3つの変数を用意します。
• 非フィボナッチ数のカウントが残っている間、フィボナッチ数の漸化式 Fib(n) = Fib(n-1) + Fib(n-2) を使って計算を進めます。
• n = n + (curr − prev − 1) という式で、各間隔に含まれる非フィボナッチ数の個数を更新します。
• 最後に、n の値をもとに直前のフィボナッチ数との位置関係を調整することで、N 番目の非フィボナッチ数を求めます。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

#include<iostream>
using namespace std;
int findNthNonFiboNumber(int n){
    int lastLastVal = 1, lastVal = 2, currVal = 3;
    while (n > 0){
        lastLastVal = lastVal;
        lastVal = currVal;
        currVal = lastLastVal + lastVal;
        n = n - (currVal - lastVal - 1);
    }
    n = n + (currVal - lastVal - 1);
    return (lastVal + n);
}
int main(){
    int n = 7;
    cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n);
    return 0;
}

出力結果

Nth non fibonacci number is 12

コードの解説

変数 lastLastVal、lastVal、currVal は、連続する3つのフィボナッチ数を保持しています。ループ内では、lastVal と currVal の間に存在する非フィボナッチ数の個数(currVal - lastVal - 1)を n から差し引いていきます。

n が負になった時点で、求める N 番目の非フィボナッチ数は lastVal と currVal の間にあることが確定します。ループを抜けた後、引きすぎた分を戻し(n + (currVal - lastVal - 1))、それを lastVal に加算することで答えが得られます。

フィボナッチ数は指数関数的に増加するため、このアルゴリズムの反復回数は非常に少なく、高速に動作する点も大きなメリットです。