以下很多参考Acwing：https://www.acwing.com/blog/content/25/
解法1
代码语言：javascript复制// 解法1：递归
/**
这是最容易想到的，但求解大数也是最有问题的。
存在大量重复计算。
一秒内大约能算到第三四十项。
**/
int f1(int n) {
const int MOD = 1000000007;
if (n == 0)
{
return 0;
}
if (n == 1 | n == 2)
{
return 1;
} else {
return (f1(n - 1) f1(n - 2))% MOD;
}
}解法2
代码语言：javascript复制// 解法2：
/**
因为我们求的是第n项，
所以也没必要把所有项求出来，
直接利用循环，把第n项求出来即可。
**/
int f2(int n)
{
const int MOD = 1000000007;
// 得先把0排除
if (n == 0)
{
return 0;
}
int x,y,z;
x = y = z = 1;
for (int i=3;i<=n;i )
{
z = (x y)%MOD;
x = y;
y = z;
}
return z;
}
int main()
{
int n;
cin >> n;
// 测试。所以，当输入-1结束。
while(n != -1)
{
int result = f1(n);
cout << result << endl;
cin >> n;
}
return 0;
}解法3
代码语言：javascript复制// 解法3：记忆化搜索。
/**
开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 nn 个状态，计算每个状态的复杂度是 O(1)O(1)，所以时间复杂度是 O(n)O(n)。
一秒内算 n=107n=107 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 n=105n=105 级别。
**/
const int N = 100000, MOD = 1000000007;
int a[N];
int f3(int n) {
if (n == 0) return 0;
if (a[n]) return a[n];
if (n <= 1) return 1;
a[n] = f3(n - 1) f3(n-2);
a[n] %= MOD;
return a[n];
}
int main() {
int n;
cin >> n;
// 测试。所以，当输入-1结束。
while(n != -1) {
// int result = f1(n);
// int result = f2(n);
int result = f3(n);
cout << result << endl;
cin >> n;
}
return 0;
}解法4
代码语言：javascript复制// 解法4：递推。
/**
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 nn 个状态，所以时间复杂度是 O(n)O(n)。
但需要开一个长度是 nn 的数组，内存将成为瓶颈，当 n=10^8时
需要的内存是381M。
**/
const int N = 100000000, MOD = 1000000007;
int a[N];
int f4(int n) {
if (n == 0) return 0;
a[1] = a[2] = 1;// 这里得注意以下，数组下标从0开始，我们抛弃0，从1开始
for (int i=3; i<=n; i )
{
a[i] = a[i - 1] a[i - 2];
a[i] %= MOD;
}
return a[n];
}
int main() {
int n;
cin >> n;
// 测试。所以，当输入-1结束。
while(n != -1) {
// int result = f1(n);
// int result = f2(n);
// int result = f3(n);
int result = f4(n);
cout << result << endl;
cin >> n;
}
return 0;
}解法5
代码语言：javascript复制// 解法5：矩阵运算 快速幂。
/**
至今，未理解到。这里先只保存一下代码：
**/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
void mul(int a[][2], int b[][2], int c[][2])
{
int temp[][2] = {{0, 0}, {0, 0}};
for (int i = 0; i < 2; i )
for (int j = 0; j < 2; j )
for (int k = 0; k < 2; k )
{
long long x = temp[i][j] (long long)a[i][k] * b[k][j];
temp[i][j] = x % MOD;
}
for (int i = 0; i < 2; i )
for (int j = 0; j < 2; j )
c[i][j] = temp[i][j];
}
int f_final(long long n)
{
int x[2] = {1, 1};
int a[2][2] = {{1, 1}, {1, 0}};
int res[][2] = {{1, 0}, {0, 1}};
int t[][2] = {{1, 1}, {1, 0}};
long long k = n - 1;
while (k)
{
if (k&1) mul(res, t, res);
mul(t, t, t);
k >>= 1;
}
int c[2] = {0, 0};
for (int i = 0; i < 2; i )
for (int j = 0; j < 2; j )
{
long long r = c[i] (long long)x[j] * res[i][j];
c[i] = r % MOD;
}
return c[0];
}
int main()
{
long long n ;
cin >> n;
cout << f_final(n) << endl;
return 0;
}解法6
代码语言：javascript复制// 解法6：利用数组。
/**
看代码吧，技术不到位，不好解释。
**/
int f6(int n)
{
// 定义临时数组
if (n < 1) {
return 0;
}
long double tmp;
long double *a = new long double[n 1];
a[1] = a[2] = 1;
for (int i = 3; i <= n; i) {
a[i] = a[i - 1] a[i - 2];
}
tmp = a[n];
delete[]a;
return tmp;
}
int main()
{
long long n ;
cin >> n;
cout << f6(n) << endl;
return 0;
}总结： 其实除了解法5和递归解法，其余解法均差不多是利用数组和循环。
