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

この問題では、整数値Nが与えられます。私たちのタスクは、C++プログラムを使用してN番目の非フィボナッチ数を見つけることです 。

フィボナッチ数列は、前の2つの数値を加算することにより、後続の数値を生成します。フィボナッチ数列は、F0とF1の2つの数字から始まります。 F0とF1の初期値は、それぞれ0、1、または1、1にすることができます。

問題を理解するために例を見てみましょう

入力

N = 5

出力

10

ソリューションアプローチ

この問題の簡単な解決策は、フィボナッチ数を見つけて、フィボナッチ数に存在しない最初のn個の数を出力することです。

別の解決策は、フィボナッチ数の式を使用してから、2つのフィボナッチ数の間にギャップを連続して追加し続けることです。最後に、すべてのギャップの合計の値は、目的の出力になります。ここでは、クラッキングに賢明なアイデアを使用します。

アルゴリズム

• 現在の要素、前の要素、前の要素を追跡する3つの変数を作成します。

• 非フィボナッチ数は負ではありませんが、フィボナッチ数の簡単な式を使用します-Fib（n）=Fib（n-1）+ Fib（n-2）。

• 式n=n +（curr-prev-1）を使用して非フィボナッチ数の数を取得するには

• 
  

• ここで、n番目の非フィボナッチ数を取得するには、nから前の数を減算します。

例

ソリューションの動作を説明するプログラム

#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