限制性斐波那契序列

Question

我想实现一个函数，从N到N+K生成斐波那契数列，并返回array[K]个元素，其中(0<=N<=370; 0<=N+K<=371; 0<=K<=255)。 当输入为n:370, k:1时，最后一个尝试n2超出了需要和范围。我想简化我的代码，而不是使用多个if语句。谢谢。

更新：

这是用于区块链的智能合约，其中int是256位，当N+K >= 369时，最后一个循环的n2会溢出。

function getFibSeq(n, k) {
  let  numbers = [];

  let n1 = 0;
  let n2 = 1;
  let i = 0;
  let j = (n + k);

  while (i < j){ if((i - n) >= 0){
      output.push(n1);
    }
    if((j - i - 1) > 0){
      let temp = n1;
      n1 = n2;
      if((j - i - 2) > 0) {
        n2 = temp + n2;
      }
    }

    i = i + 1;
  }

  return output;
}

Answer 1

有一个用于计算第n个斐波那契数的封闭公式，被称为Binet公式。这使您可以在O(1)的渐近时间复杂度内获得第n个数。

下面是一个示例，展示如何计算任意n的斐波那契数。

将此扩展以解决您的特定问题。我建议计算n-1和n的值。然后迭代k次以获得所需的值。在进行迭代时跟踪结果，您应该没问题。

function fibonacci(n) {
    const phi = (1 + Math.sqrt(5)) / 2;
    const psi = (1 - Math.sqrt(5)) / 2;  // phi的负倒数
    return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / Math.sqrt(5));
}

// 测试
console.log(fibonacci(10));  // 输出：55

注意：尽管此公式对于较小的n值给出精确结果，但由于JavaScript中浮点运算的限制，对于较大的值可能会失去精度。