如何在JavaScript中计算斐波那契数列
斐波那契数列是以下模式中包含整数的数字序列。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..
从数学角度来看,计算斐波那契数列的一般公式是
fn = fn-1 + fn-2 ,其中n ≥ 2
在这里, **f 0 = 0 ** 和 **f 1 = 1 ** 。
我们需要计算给定整数 n 的 n 个斐波那契数,其中n≥0。
例子:
输入:n = 5
输出:[0, 1, 1, 2, 3]
输入:n = 10
输出:[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
可以使用JavaScript中的 for循环 和 while循环 实现此逻辑。
使用for循环: 由于系列的前两个值是固定的,我们从i = 2开始循环,循环到i < n,因为数组索引从0开始,所以,n = 1在数组的情况下实际上意味着i = 0。
<script>
const n = 10;
// 创建长度为'n'的新数组
var series = new Array(n);
// 填充数组中的所有位置为0
series.fill(0);
// 第一个元素的初始值
series[0] = 0;
// 第二个元素的初始值
series[1] = 1;
for(let i = 2; i < n; i++) {
// 应用基本的斐波那契公式
series[i] = series[i-1] + series[i-2];
}
// 打印数列
console.log(series);
</script>
输出:
打印出了斐波那契数列的前10个元素
使用while循环:
<script>
const n = 10;
// 创建大小为'n'的新数组
var series = new Array(n);
// 用0填充数组的所有位置
series.fill(0);
// 第一个元素种子值
series[0] = 0;
// 第二个元素种子值
series[1] = 1;
// 初始化条件变量
let i = 2;
while(i < n) {
// 应用基本的斐波那契数列公式
series[i] = series[i-1] + series[i-2];
// 递增条件变量
i++;
}
// 打印数列
console.log(series);
</script>
输出:
打印出前10个斐波那契数列的元素
使用递归: 不推荐使用递归方法来打印整个斐波那契数列,因为递归算法本身在时间和复杂性方面是昂贵的,而且除了从特定位置获取斐波那契数列的值之外,我们还需要将它们存储在一个数组中,这会多次调用递归函数,即 n 次!
以下是在JavaScript中应用递归方法的示例。
<script>
function fibonacci(n){
if(n == 1) return 0; // n=1时的返回值
if(n == 2) return 1; // n=2时的返回值
// 递归调用
return fibonacci(n-1) + fibonacci(n-2);
}
const n = 10;
// 创建大小为'n'的新数组
var series = new Array(n);
// 用0填充数组的所有位置
series.fill(0);
for(let i = 1; i <= n; i++) {
// 存储第'i'个斐波那契数
series[i-1] = fibonacci(i);
}
// 打印数列
console.log(series);
</script>
输出:
打印出前10个斐波那契数列的元素
阅读更多:JavaScript 教程