面试题10- I.斐波那契数列

[wind-jyf]

斐波那契数列

一、题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

二、解题思路

1. 第一种，便是使用递归，很简单，不做赘述
2. 第二种，使用循环
3. 设置first，second，sum
4. sum为first+second
5. 当我们求第几个斐波那契数列为多少时，其实就是前面的那些数，进行两两相加
6. 每加一次，都需要将first和second后移
7. 最后返回sum

三、代码实现

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n<=1){
        return n;
    }
    let first = 0;
    let second = 1;
    for(let i = 0;i<n-1;i++){
        let sum = (first + second);
        first = second;
        second = sum;
    }
    return second;//此时second就等于sum
};

---