蓝桥杯练习（入门二）Fibonacci数列

入门训练4 Fibonacci数列

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

Fibonacci数列的递推公式为：F_n=F_n-1+F_n-2，其中F₁=F₂=1。

当n比较大时，F_n也非常大，现在我们想知道，F_n除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示F_n除以10007的余数。

说明：在本题中，答案是要求F_n除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出F_n的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入

样例输出

样例输入

样例输出

7704

数据规模与约定

1 <= n <= 1,000,000。

 1 #include<iostream>
 2 using namespace std;
 3 long Fibonaci(long day){
 4     if(day == 1 || day == 2){
 5         return 1;
 6     } 
 7     else
 8     {
 9         long f1, f2, f3;
10         f1 = 1;
11         f2 = 1;
12         for(int i=3; i<=day; ++i){
13             f3 = (f1 + f2)%10007;
14             f1 = f2%10007;
15             f2 = f3%10007;
16         }
17         return f3;
18     }
19     
20 }
21 int main(){
22     long day;
23     cin >> day;
24     cout << Fibonaci(day);
25 }

个人总结：

　　第一次做的时候用的递归，一直报运行超时，没有注意到数据很大，单纯用函数递归算出结果然后再取余10007计算量很大，用所以改用迭代的方法在每次求得比10007大的值之后便取余，减少运行时间。