Restricted Fibonacci sequence

Question

I want to implement a function that generates the Fibonacci sequence from N to N K and returns array[K]< /code> elements, of which (0<=N<=370; 0<=N K<=371; 0<=K<=255). When the input was n:370, k:1, the last attempt, n2, was beyond the need and scope. I want to simplify my code and not use multiple if statements. Thanks.

Update:

This is a smart contract for blockchain where int It is 256 bits. When N K >= 369, the last loop of n2 will overflow.

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

There is a closed formula for calculating the nth Fibonacci number, called the Binet formula. This allows you to get the nth number in asymptotic time complexity of O(1).

Here is an example showing how to calculate the Fibonacci number for any n.

Extend this to solve your specific problem. I suggest calculating the values ​​of n-1 and n. Then iterate k times to get the desired value. Keep track of the results as you iterate and you should be fine.

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

Note: Although this formula gives accurate results for smaller n values, precision may be lost for larger values ​​due to limitations of floating point operations in JavaScript .