439a – 斐波那契数列

斐波那契数列是这样的一个数列:1,1,2,3,5,8,13,21⋯。

fn 表示斐波那契数列的第 n 项,则有:

f1=f2=1

fn=fn1+fn2(n>2)

输入一个 n,求出 fn

1000000007(109+7) 取模结果。

输入格式

输入一个整数 n(1≤n≤100000)。

输出格式

输出 fn mod 1000000007 的值。

样例输入

3

样例输出

2

代码实现

#include <iostream>

using namespace std;

int main()
{
    int n;
    int nV[100001];
    nV[1] = 1;
    nV[2] = 1;
    
    cin >> n;
    if(n > 2){
    	for(long int i = 3; i <= n; i++){
            nV[i] = (nV[i-1] + nV[i-2]) % 1000000007;
    	}
    }
    cout << nV[n] << endl;
	return 0;
}

欢迎提供建议,优化算法。

部分浏览器可能点击评论区空白处无法输入内容,请尝试点击评论空白处左上角的字进行评论…

标签:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注