使用直接公式打印前 n 个斐波那契数

---

在本文中，我们将解决使用直接公式打印前 n 个斐波那契数的问题。

在数学中，斐波那契数通常用 Fn 表示（表示第 n 个斐波那契数），形成一个序列，其中每个数字都等于前两个数字的和。第 n 个斐波那契数可以表示如下：

$$\mathrm{Fn\:=\:F_{n-1}\:+\:F_{n-2}}$$

该序列以 0 和 1 开始。斐波那契数列的前几个值，从 0 和 1 开始是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

因此，在这个问题中，我们将得到一个数字 N，我们需要使用直接公式打印前 N 个斐波那契数。

示例

输入: 4

输出: 0 1 1 2

输入: 8

输出: 0 1 1 2 3 5 8 13

对于此问题，我们需要了解毕内公式的概念，该公式提供了获取第 n 个斐波那契数的直接公式，并在算法部分详细讨论。

算法

根据公式，$\mathrm{Fn\:=\:F_{n-1}\:+\:F_{n-2}}$ 我们需要 (n-1) 项和 (n-2) 项才能通过将它们相加得到第 n 项。由于在这个问题中，我们应该使用直接公式打印前 n 个斐波那契数来获取第 n 个斐波那契数。

要获得斐波那契数列中的第 n 个斐波那契数，可以使用称为**毕内公式**的显式公式。它是由数学家雅克·菲利普·玛丽·毕内创建的。

公式

如果 $\mathrm{Fn}$ 表示斐波那契数列中的第 n 个斐波那契数，则可以表示为

$$\mathrm{F_n\:=\:\frac{1}{\sqrt5}((\frac{1+{\sqrt5}}{2})^n\:-\:(\frac{1-{\sqrt5}}{2})^n)}$$

**注意** - 此公式给出从 1 和 1 开始的斐波那契数列。要获得从 0 和 1 开始的斐波那契数列，请使用 n-1 获取第 n 个斐波那契数。

我们可以使用二次方程的概念推导出这个公式。我们将使用此公式打印每个斐波那契数，直到第 n 个斐波那契数，以打印前 n 个斐波那契数。

方法

• 我们将使用 for 循环打印所有 N 个斐波那契数，从 0 到 n 迭代，因为我们正在考虑从 0 和 1 开始的斐波那契数列。

• 将一个变量初始化为 fibonacci，并在每次迭代中使用上述公式存储第 i 个斐波那契数，直到 i<N。

• 在每次迭代中继续打印 fibonacci，这将为我们提供前 N 个斐波那契数。

示例

以下是 C++ 中上述方法的实现：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void fibonacci(long long int N){ //function to print first N fibonacci numbers
   long long int fibonacci; //to store ith fibonacci number
   
   for(int i=0;i<N;i++) { //using for loop to print all N fibonacci numbers
      //using direct formula to print every fibonacci number until n
      fibonacci = 1/sqrt(5)*(pow((1+sqrt(5))/2,i) - (pow((1-sqrt(5))/2,i)));
      cout<<fibonacci<<" ";
   }
   cout<<endl;
}

//Driver Code
int main(){
   long long int N=10;
   fibonacci(N);
   N=6;
   fibonacci(N);
   return 0;
}

输出

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

**时间复杂度：O(n)，**因为 for 循环运行直到 i 小于 n。

**空间复杂度：O(1)，**因为它不使用额外的空间。

结论

在本文中，我们学习了如何使用直接公式而不是使用递归来打印前 N 个斐波那契数。我们还学习了毕内公式，以直接获取斐波那契数列中的第 n 个斐波那契数。

希望本文能帮助您解决所有关于该主题的概念。