1.0 问题描述

实现斐波那契数列，求第N项的值

2.0 问题分析

1. 斐波那契数列最简单的方法是使用递归，递归和查表法同时使用，可以降低复杂度。
2. 根据数列特点，同时进行计算的数值其实只有3个，所以可以使用3个变量循环递进计算结果。
3. 3个变量可以简化为2个变量。

3.0 代码实现

3.1使用swift实现

func fbnq(_ n: Int) -> UInt64{
    if n < 0 || n > 92 {
        return 0;
    }
    var p: UInt64 = 0, c: UInt64 = 1;
    for _ in 0 ..< n {
        c = c + p;
        p = c - p;
    }
    return c;
}

3.2使用js实现

function fb(n){
    let p = 0, c = 1;
    for(let i = 0; i < n; i++){
        c = p + c;
        p = c - p;
    }
    return c;
}

4.0 复杂度分析

复杂度为 O(n)