フィボナッチ数列-JavaScript

826 ワード

1、テーマの説明
関数を書いて、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;
};