写一个函数,输入 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;
同样可以使用递归的解决方法,但是由于其复杂度过高,本题 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;
}
};