剑指 Offer 10- I. 斐波那契数列

一、题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

二、示例

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

三、题目分析 & 解题思路

斐波那契数列 是指这样一串数列：
0 1 1 2 3 5 8 13 21 34 55 89… 这样 一串数字
该串数字的规律可以总结为
相邻 的 三 个 数字 ，第 二个 + 第 一个 = 第三个
原始的数字 为 0 和 1 0 + 1 等于 1 ，依次往后

因此我们可以用三个变量来表示这一规律
first、second、third
third = first + second
计算出第三个结果之后我们只需要 将 third 赋值给 second,原来的 second 赋值给 first 即可,需要计算出 n(n>=2） 个 斐波那契数 循环 n - 2 次即可
即：

third = first + second;
first = second;
second = third;
1
2
3

同样可以使用递归的解决方法，但是由于其复杂度过高，本题 ACE 不过，因此不在此阐述

代码实现

class Solution {
public:
    int fib(int n) {
        int first = 0;
        int second = 1;
        int third = 0;
        if(n <2)
        {	
        	// 0,1
            return n;
        }
        else
        {
            for(int i = 2; i <=n ; i++)
            {
            	//注意这里是每次对结果取模(%)
                third = (first + second) % 1000000007;
                first = second;
                second = third; 
            }
        }
        return third;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25