JavaScript 如何计算Fibonacci数列

Fibonacci数列是一个包含整数的数列，并按照以下模式排列。

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

在数学上，计算斐波那契数列的通用公式是

fn = fn-1 + fn-2 , where n &#x2265 2

这里，f0= 0 ，f1= 1。

我们需要计算任意给定整数n 的n 个斐波那契数，其中n ≥ 0 。

示例：

Input   : n = 5  
Output  : [0, 1, 1, 2, 3]  
Input   : n = 10  
Output  : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

在本文中，我们将专注于两种计算斐波那契数列的主要方法。

• 使用for循环和while循环
• 使用递归

使用循环

使用这种方法计算斐波那契数列的方法相比递归方法更好。这种方法利用动态规划 ，通过保存已生成的数字，然后在进一步的计算中使用它。

由于n=1 和n=2 的数字是固定的，即0 和1 ，因此可以通过以下逻辑计算出数列中的其余数字：

f3 = f2 + f1  
f4 = f3 + f2  
f5 = f4 + f3  
...  
fn = fn-1 + fn-2

这个逻辑可以用for 循环和while 循环在JavaScript中实现。

使用for循环

由于数列的前两个值是固定的，我们从i = 2开始循环，直到i < n为止，因为数组的索引从0开始，所以当n = 1时，实际上意味着i = 0。

Javascript

const n = 10;
 
// Create a new array of size 'n'
let series = new Array(n);
 
// Fills all places in array with 0
series.fill(0);
 
// Seed value for 1st element
series[0] = 0;
 
// Seed value for 2nd element
series[1] = 1;
 
for (let i = 2; i < n; i++) {
 
    // Apply basic Fibonacci formulae
    series[i] = series[i - 1] + series[i - 2];
}
 
// Print the series
console.log(series);

输出

[
  0, 1,  1,  2,  3,
  5, 8, 13, 21, 34
]

使用 While 循环

Javascript

const n = 10;
 
// Create a new array of size 'n'
let series = new Array(n);
 
// Fills all places in array with 0
series.fill(0);
 
// Seed value for 1st element
series[0] = 0;
 
// Seed value for 2nd element
series[1] = 1;
 
// Initialize the conditional variable
let i = 2;
while (i < n) {
 
    // Apply basic Fibonacci formulae
    series[i] = series[i - 1] + series[i - 2];
 
    // Increment the conditional variable
    i++;
}
 
// Print the series
console.log(series);

输出

[
  0, 1,  1,  2,  3,
  5, 8, 13, 21, 34
]

使用递归

不推荐使用递归方法打印整个斐波那契数列，因为递归算法本身在时间和复杂性方面是代价高昂的，并且除了在某个位置获取一个斐波那契数列数之外，我们还需要将它们存储在数组中，并且对于每个元素，不断地调用递归函数，即n 次！

可以将递归方法应用于JavaScript中。

Javascript

function fibonacci(n) {
 
    // Return value for n = 1
    if (n == 1) return 0;
 
    // Return value for n = 2
    if (n == 2) return 1;
 
    // Recursive call
    return fibonacci(n - 1) + fibonacci(n - 2);
}
 
const n = 10;
 
// Create a new array of size 'n'
let series = new Array(n);
 
// Fills all places in array with 0
series.fill(0);
 
for (let i = 1; i <= n; i++) {
 
    // Store i-th Fibonacci number
    series[i - 1] = fibonacci(i);
}
 
// Print the series
console.log(series);

输出

[
  0, 1,  1,  2,  3,
  5, 8, 13, 21, 34
]