剑指offer 10 斐波那契 &大数余数

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

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

斐波那契难度不大, 不用写了, 关键是如何处理a和b反复相加的过程中变得越来越大的问题
原来我想得到真正的a和真正的b之后再做取余运算, 但是这样依旧超出了long的容量.

后来我在结果处调用循环,使得a -=(1e9+7), 但是会超时

最终的解决方法是: 在每一次得到a或者b的时候就进行取余运算. 或许我不能知道100次的时候真正的ab到底是多少, 但是这样避免了出现超大整数.

一个小问题是, 别忘了给1e9+7转换成(long), 否则编译器会认为是double

int fib(int n){
    long a = 0, b = 1;
    if(n < 1) return 0;
    if(n == 1) return 1;
    int flag = 0;
    for(int i = 2; i<=n; i++)
    {
        if(!flag)
        {
            a +=b;
            a %=(long)(1e9+7);
        }
        else
        {
            b += a;
            b %=(long)(1e9+7);
        }
        flag = !flag;
    }
    if(flag)//最终结果在a
        return a;
    else
        return b;
}