问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
时间限制：1.0s
内存限制：256.0MB
提示
答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单
思路
- 选择C++，输入输出选择scanf和printf语法；
- 想办法动态调用F1,F2,Fn，不要让这三个变量保存数据，即取即用；
- 初始化F1=F2=1，想办法在n大于2后，例如F3调用F1、F2的值，F4调用F3、F2的值；
- 得到F3后，F1就用不着了，就可以把F2的值给F1，然后把F3的值给F2。这样F4就能继续利用变量F1、F2调用F3和F4的值。之后类比。
- 用到循环，同时也要想想如何在n<3时都输出1。
- 可以用if语句判断一下n>2否，然后引进一个变量i 来记录初始值3，每算出一次都i++，循环与n比较，直到i > n结束循环，在结束之前一定要算好Fn。
- 输出Fn。
代码展示
#include<cstdio>
using namespace std;
int main() {
int n=0,f1=f2=1,f3=1;
scanf("%d",&n);
if(n>2)
for (int i = 3; i <= n; i++){
f3 = (f1+ f2) %10007;
f1 = f2;
f2 = f3;
}
printf("%d",f3);
return 0;
}
心得
一开始写这个题的时候觉得挺简单的，那时我还是个菜逼，觉得不就是递归嘛，于是写下来了这段代码
#include <iostream>
using namespace std;
int Fibonacci(int n) {
if (n == 1 || n == 2)
return 1;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main() {
int n;
cin >> n;
cout << Fibonacci(n) % 10007 << endl;
return 0;
}
得分：30
CPU使用：运行超时
内存占用：61.94MB
时隔多年，再次挑战。
1.首先要说明的是我选用的是C++；
2.cin和cout费时比scanf()和printf多的多；
3.在c++下用scanf和printf需要用到头文件<cstdio>/<stdio.h>；
4.不要在同一程序中同时使用到cin和scanf，还有cout和printf。可能出问题；
虽然cin、cout用时高，但主要问题还不是这个，这个递归有大量的重复计算，而且占用了不少内存。
我看了下动态规划方面的书，斐波那契数列还可以这样写
F[1] = 1;
F[2] = 1;
for (i = 3; i <= n; i++){
F[i] = (F[i - 1] + F[i - 2]);
}
太酷了……这样只用算一遍就能继续调用！
用数组F[1000000]，先令F[1]=1, F[2]=1，然后用F[i]=(F[i-1]+F[i-2])%10007来计算F[i]。然后却发现怎么都没办法用printf同时输出当n>2和n<2时的结果。【突然想到了把数组赋值给一个整型，然后输出整型。以后试试】
于是写下来了这个运行不了的程序。
#include<cstdio>
using namespace std;
int main() {
char F[1000000]={0};
int n = 1,i=1;
scanf("%d",&n);
if(n<2)
F[n] =F[i] = 1;
if(n>2)
F[1] = 1;
F[2] = 1;
for (i = 3; i <= n; i++){
F[i] = (F[i - 1] + F[i - 2])%10007;
}
printf("%s",F[i]);
return 0;
}
