题目：
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
解决：
方法一：（得分30分）
使用递归求出Fibonacci，之后再求余于10007，改测评的结果显然是时间不在测评范围内，递归求Fibonacci数列的复杂度为O(2^n)
#include<stdio.h>
int fib(int n) {
if (n == 1 || n == 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
int main() {
int n;
scanf("%d", &n);
printf("%d
", fib(n) % 10007);
return 0;
}
方法二：（得分100分）
使用递归显然测试时间不在题目规定得范围内，因此为了降低算法得时间复杂度，因此需要消耗空间，用空间来降低算法的时间复杂度，和递归相对应的迭代算法，在时间复杂度上是（O(n)）,迭代算法采用数组存取，每求得一个数就将其存入到数组中，消耗系统空间以减少时间消耗
#include<stdio.h>
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a[1000000];//切记不能创建数组为a[n]，数组下标只能是一个常量
a[0] = 0, a[1] = 1;
//直接使用迭代这样的话时间复杂度为O(n)，这样的话不会超时，但是如果n大的话，空间复杂度会更大，以空间换时间
for (int i = 2; i <= n; i++) {
a[i] = (a[i - 2] + a[i - 1]) % 10007;
}
cout << a[n] << endl;
return 0;
}