自助建站系统源源码,wordpress改mip,网页制作,网站建设客户需要提供什么科目题目描述
给定一个整数 T T T#xff0c;表示样例数。
对于每个样例#xff0c;给定一个整数 n n n#xff0c;求斐波那契数列的第 n n n 项。
斐波那契数列定义为 f ( 1 ) f ( 2 ) 1 f(1) f(2) 1 f(1)f(2)1#xff0c; f ( n ) f ( n − 1 ) f ( n − 2 ) f(…题目描述
给定一个整数 T T T表示样例数。
对于每个样例给定一个整数 n n n求斐波那契数列的第 n n n 项。
斐波那契数列定义为 f ( 1 ) f ( 2 ) 1 f(1) f(2) 1 f(1)f(2)1 f ( n ) f ( n − 1 ) f ( n − 2 ) f(n) f(n−1) f(n−2) f(n)f(n−1)f(n−2)。
结果对 1 0 9 7 10^9 7 1097 取模。
输入格式
第一行一个整数 T T T。 1 ≤ T ≤ 100 1 ≤ T ≤ 100 1≤T≤100
对于每个样例一个整数 n n n。 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100
输出格式
对于每个样例输出一个整数表示答案。
样例输入1
2
3
5样例输出1
2
5思路
斐波那契数列是一个非常经典的递归序列其定义为F(0)0F(1)1F(n)F(n-1)F(n-2) (n2)。
首先定义了一个数组f用于存储斐波那契数列的值。然后先将斐波那契数列的前两项设为1这是斐波那契数列的定义。接下来通过一个循环计算出斐波那契数列的前100项。在计算每一项的时候都用前两项的和对一个大数1e97取模防止数值过大导致的溢出。
在计算完斐波那契数列的前100项之后程序进入一个循环每次从输入中读取一个数n然后输出斐波那契数列的第n项。这个循环会一直进行直到没有更多的输入。 AC代码
#include iostream
#define ll long long
#define AUTHOR HEX9CF
using namespace std;const int N 1e2 7;
const int MOD 1e9 7;ll f[N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);f[1] f[2] 1;for (int i 3; i 100; i) {f[i] (f[i - 1] f[i - 2]) % MOD;}int t;cin t;while (t--) {int n;cin n;cout f[n] endl;}return 0;
}
