JavaScript 斐波那契数列

在给定的问题陈述中，我们被要求使用JavaScript功能创建一个类似斐波那契数列的序列。在JavaScript中，我们可以通过递归或使用for循环来解决这个问题。

什么是斐波那契数列

让我们了解一下在JavaScript中斐波那契数列的工作原理。

我们知道，斐波那契数列是一个序列，其中每个数字都是前两个数字的和。序列从0和1开始。序列中的下一个数字是1（0 + 1），然后是2（1 + 1），3（1 + 2）…以此类推。

上述问题的逻辑

实现斐波那契数列的最简单方法是使用递归方法。

让我们了解给定问题的逻辑。JavaScript中的斐波那契数列的递归方法将问题分解为更小的子问题。它首先检查输入数字是否小于或等于1。如果等于1，则返回该数字；否则，继续计算第n个斐波那契数，通过以n-1和n−2作为参数递归调用定义的函数，并将结果相加。

步骤

步骤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循环来获取给定数字之前的数列。这个循环会一直执行，直到下一个数字大于输入的数字，此时while循环会终止。由于while循环迭代log以2为底的n次，所以此代码的复杂度为O(log n)。第一个代码的空间复杂度为O(1)，因为所需空间不取决于输入的大小。

第二个方法的时间复杂度为O(n)，其中n是数列中的项数。这段代码使用for循环遍历从1到输入数字的所有数值范围。由于此循环运行n次，所以复杂度为O(n)。

第二个方法的空间复杂度也为O(n)，因为它为循环的每一步存储了n1和n2的值。由于存储这些数字所需的内存是恒定的，且不取决于输入的大小。因此，在这种情况下，我们忽略分析空间复杂度。