フィボナッチ数列-JavaScript
826 ワード
1、テーマの説明
関数を書いて、nを入力して、フィボナッチの数列の第n項を求めます.フィボナッチの数列の定義は以下の通りです.
答えは金型1 e 9+7(100000万07)を取ります.初期結果を計算すると、100000万08となります.1を返してください.
注意:テストデータはjs中の整数範囲に溢れますので、大きな数のタイプを使ってください.
本題と LeetCode.509.フィボナッチ数 同じです
2、考え方を解く
数学による定義:
関数を書いて、nを入力して、フィボナッチの数列の第n項を求めます.フィボナッチの数列の定義は以下の通りです.
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), N > 1.
フィボナッチの数列は0と1から始まり、その後のフィボナッチの数は前の2つの数で加算されます.答えは金型1 e 9+7(100000万07)を取ります.初期結果を計算すると、100000万08となります.1を返してください.
注意:テストデータはjs中の整数範囲に溢れますので、大きな数のタイプを使ってください.
本題と LeetCode.509.フィボナッチ数 同じです
2、考え方を解く
数学による定義:
f(n) = f(n - 1) + f(n - 2)
.最初の状況は f(0) = 0
和 f(1) = 1
そのため直接ループアップすればいいです.時間複雑度O(N),空間複雑度O(1)./**
* @param {number} n
* @return {number}
*/
function Fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
let a = 0,
b = 1;
for (let i = 2; i < n; ++i) {
let c = a + b;
a = b;
b = c;
}
return (a + b) % 1000000007;
};