使用直接公式列印前 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 個斐波那契數。

希望本文能幫助您解決所有關於該主題的概念。