限制性斐波那契序列

Question

我想實作一個函數，從N到N K產生斐波那契數列，並回傳array[K]< /code>個元素，其中(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中浮點運算的限制，對於較大的值可能會失去精度。