斐波拉契数列
目录
斐波拉契数列
题目描述
给定正整数n，求斐波那契数列的第n项F(n)。
令F(n)表示斐波那契数列的第n项，它的定义是：
当n=1时，F(n)=1；
当n=2时，F(n)=1；
当n>2时，F(n)=F(n−1)+F(n−2)。
大数据版：
输入描述
一个正整数n（1≤n≤104）。
输出描述
斐波那契数列的第n项F(n)。
由于结果可能很大，因此将结果对10007取模后输出。
样例1
输入
1
输出
1
解释
边界定义：F(1)=1
样例2
输入
3
输出
2
解释
F(3)=F(2)+F(1)=1+1=2
样例3
输入
5
输出
5
题解：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> f(n+1, 0); //如果是f(n, 0)就会错误
f[1] = f[2] = 1;
for(int i=3;i<=n;i++){
f[i] = (f[i-1] + f[i-2]) % 10007;
}
cout<<f[n];
return 0;
}#include <cstdio>
const int MOD = 10007;
const int MAXN = 10000 + 1;
int fib[MAXN];
int main() {
int n;
scanf("%d", &n);
fib[1] = fib[2] = 1;
for (int i = 3; i <= n; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
printf("%d", fib[n]);
return 0;
}