JavaScript中的斐波那契數列

---

給定的問題陳述要求我們利用JavaScript的功能建立一個類似斐波那契數列的序列。在JavaScript中，我們可以透過遞迴或使用for迴圈來解決這個問題。

什麼是斐波那契數列？

讓我們瞭解一下JavaScript中斐波那契數列的工作原理。

我們知道，斐波那契數列是一個數列，其中每個數字都是前兩個數字之和。該數列從0和1開始。數列中的下一個數字是1（0 + 1），然後是2（1 + 1），3（1 + 2）……以此類推。

上述問題的邏輯

實現斐波那契數列最簡單的方法是使用遞迴方法。

因此，讓我們瞭解給定問題的邏輯。JavaScript中斐波那契數列的遞迴方法將問題分解成更小的子問題。它首先檢查輸入數字是否小於或等於1。如果等於1，則返回該數字，否則則不返回。然後，它將透過遞迴呼叫已定義的函式，並將n-1和n-2作為引數，並將結果相加來計算第n個斐波那契數。

演算法

步驟1 - 宣告一個數字，直到獲得斐波那契數列或生成n項序列。這裡我們將看到兩種實現。

步驟2 - 將n1和n2數字分別宣告為0和1。並將nextDigit數字定義為空。這裡nextDigit將是兩個數字n1和n2的和。

步驟3 - 此步驟將計算並確定我們對兩種程式碼都使用的方 法。如果我們想獲得直到某個數字的輸出，我們將使用while迴圈，該迴圈將執行直到條件nextDigit小於或等於該數字，列印序列。如果我們想要直到n項的輸出，我們將使用for迴圈來迭代給定輸入數字的長度。

步驟4 - 現在轉向步驟三，根據需要列印斐波那契數列。

示例

// code to generate fibonacci sequence up to a certain number
const number = 13;
let n1 = 0, n2 = 1, nextDigit;

console.log('Fibonacci Series is as follows:');
// print 0 and 1 initially
console.log(n1);
console.log(n2);

//adding two consecutive digits
nextDigit = n1 + n2;

while (nextDigit <= number) {

    // print the next digit
    console.log(nextDigit);

    n1 = n2;
    n2 = nextDigit;
    nextDigit = n1 + n2;
}

輸出

Fibonacci Sequence is as follows:
0
1
1
2
3
5
8
13

示例

// code to generate fibonacci series up to n terms
const number = 8;
let n1 = 0, n2 = 1, nextDigit;

console.log('Fibonacci Sequence is as follows:');

//initialize a for loop
for (let i = 1; i <= number; i++) {
    console.log(n1);
    nextDigit = n1 + n2;
    n1 = n2;
    n2 = nextDigit;
}

輸出

Fibonacci Sequence i as follows:
0
1
1
2
3

時間複雜度

生成到某個數字的時間複雜度為O(log n)。因為程式碼使用while迴圈來獲得直到給定數字的序列。該迴圈將持續進行，直到nextDigit大於輸入數字，此時while迴圈將終止。由於while迴圈迭代log以2為底n次，因此這段程式碼的複雜度為O(log n)。第一段程式碼的空間複雜度為O(1)，因為所需空間不依賴於輸入大小。

第二種方法的時間複雜度為O(n)，n是序列中項的數量。這段程式碼使用for迴圈迭代1到輸入數字的所有範圍。由於迴圈執行到n次，因此複雜度為O(n)。

第二種方法的空間複雜度也是O(n)，因為它為迴圈的每一步都儲存值n1和n2。由於這些數字所需的記憶體是恆定的，並且不依賴於輸入大小。因此，在這種情況下，我們忽略空間複雜度的分析。

結論

在這段程式碼中，我們實現了兩種程式碼或演算法。第一段程式碼給出輸出以列印直到某個數字的斐波那契數列。第二段程式碼返回n項的輸出。我們得出的結論是，第一種和第二種方法的時間複雜度分別為O(log n)和O(n)。兩種程式碼的空間複雜度都是O(1)。