1.0 问题描述
实现斐波那契数列，求第N项的值
2.0 问题分析
- 斐波那契数列最简单的方法是使用递归，递归和查表法同时使用，可以降低复杂度。
- 根据数列特点，同时进行计算的数值其实只有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)
