使用直接公式列印前 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)th 將它們相加得到第n 項。因為在這個問題中我們應該使用直接公式列印前 n 個斐波那契數來得到第 n 個斐波那契數。

要得到斐波那契序列中的第 n 個斐波那契數，可以應用稱為比奈公式的顯式公式。它是由數學家 Jacques Philippe Marie Binet 創建的。

公式

如果$\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 迴圈來列印從 0 到 n 迭代的所有 N 個斐波那契數，因為我們正在考慮從 0 和 1 開始的斐波那契數列。

• 將變數初始化為斐波那契數，並在每次迭代時使用上述公式儲存第 i 個斐波那契數，直到 i

• 在每次迭代中繼續列印斐波那契數，這將為我們提供前 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個斐波那契數。

我希望這篇文章可以幫助您理清有關該主題的所有概念。

以上是使用直接公式列印前 n 個斐波那契數的詳細內容。更多資訊請關注PHP中文網其他相關文章！