查找第 N 个非斐波那契数的 C++ 程序

在这个问题中，我们得到一个整数值 N。我们的任务是使用C++ 程序找到第 N 个非斐波那契数。

斐波那契数列通过添加两个先前的数字来生成后续数字。斐波那契数列从两个数字开始 - F0 和 F1。F0 和 F1 的初始值可以分别取 0, 1 或 1, 1。

让我们举个例子来理解这个问题，

输入

N = 5

输出

10

解决方法

该问题的一个简单解决方案是找到斐波那契数，然后打印斐波那契数中不存在的前 n 个数。

另一种解决方案是使用斐波那契数公式，然后连续添加两个斐波那契数之间的差距。最后，所有间隙之和的值将产生所需的输出。在这里，我们将使用明智的想法进行破解。

算法

• 创建三个变量，它们将跟踪当前元素、前一个元素和前一个元素。

• 虽然非斐波那契数是非负数，但使用斐波那契数的简单公式 - 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<<"第 N 个非斐波那契数是 "<<findNthNonFiboNumber(n);
   return 0;
}

第 N 个非斐波那契数是 12