Restricted Fibonacci sequence
P粉463811100
2023-08-16 19:46:31
<p>I want to implement a function that generates the Fibonacci sequence from <code>N</code> to <code>N K</code> and returns <code>array[K]< /code> elements, of which <code>(0<=N<=370; 0<=N K<=371; 0<=K<=255)</code>.
When the input was <code>n:370, k:1</code>, the last attempt, <code>n2</code>, was beyond the need and scope. I want to simplify my code and not use multiple <code>if</code> statements. Thanks. </p><p><strong>Update: </strong></p><p>This is a smart contract for blockchain where <code>int</code> It is 256 bits. When <code>N K >= 369</code>, the last loop of <code>n2</code> will overflow. </p>
<pre class="brush:js;toolbar:false;">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;
}
</pre>
<p><br /></p>
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
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-1andn. 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)); // 输出：55Note: Although this formula gives accurate results for smaller
nvalues, precision may be lost for larger values due to limitations of floating point operations in JavaScript .