【ETOJ P1046】斐波那契数列题解（数学+动态规划）

本文主要是介绍【ETOJ P1046】斐波那契数列题解（数学+动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个整数 $T$ ，表示样例数。

对于每个样例，给定一个整数 $n$ ，求斐波那契数列的第 $n$ 项。

斐波那契数列定义为 $f (1) = f (2) = 1$ ， $f (n) = f (n - 1) + f (n - 2)$ 。

结果对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $T$ 。（ $1 \leq T \leq 100$ ）

对于每个样例，一个整数 $n$ 。（ $1 \leq n \leq 100$ ）

输出格式

对于每个样例，输出一个整数表示答案。

样例输入1

2
3
5

样例输出1

2
5

思路

斐波那契数列是一个非常经典的递归序列，其定义为：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2) (n>=2)。

首先定义了一个数组f，用于存储斐波那契数列的值。然后先将斐波那契数列的前两项设为1，这是斐波那契数列的定义。接下来，通过一个循环，计算出斐波那契数列的前100项。在计算每一项的时候，都用前两项的和对一个大数（1e9+7）取模，防止数值过大导致的溢出。

在计算完斐波那契数列的前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;
}