Fibonacci数列 C语言

问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入格式
输入包含一个整数n。

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

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

样例输入

10
样例输出

55
样例输入

22
样例输出

7704
数据规模与约定

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

首先，看到这个题目，笔者第一个想到的是递归法，但由于笔者学艺不精，时间长了具体怎么写给忘光了，于是看了蓝桥杯官网的锦囊
锦囊给的提示是
在这里插入图片描述
用数组保存？看起来是个办法，但仔细一想其实问题很多：
首先，题目中给的数据规模是 n<=1,000,000 如果用数组保存，那就得申请1000000这么大的数组空间，这无疑是一种空间上的浪费。
当然，也可以根据用户输入的n的值来申请空间

int n;
scanf("%d",&n);
int a[n];

但是，由题目可知，我们只需要打印出最后的结果就行了，也就是说，最终我们只会用到数组最后一个空间中的值，前面的空间依然是一种浪费。

So，这个方法Pass…

于是，笔者老老实实地用草稿纸将递归法回忆了起来（因为懒，不想翻课本），写下以下这段超级简单地代码：

#include <stdio.h>
int Fibonacci(int n)
{
    if(n==1||n==2)
        return 1;
    else
        return (Fibonacci(n-1)+Fibonacci(n-2))%10007;
}
int main(void)
{
    int n;
    while(n<1||n>1000000)
        scanf("%d",&n);
    printf("%d",Fibonacci(n));    
}

编译运行毫无问题，于是信心满满地粘贴到了蓝桥杯评测系统…

结果。。。

0分！

0分！！

0分！！！

我寻思着，这** 不对啊！难道是评测系统智障吗！？？？
很显然，这只可能是笔者这只菜鸟的问题，评测系统总是有它的道理的~~
但是，我确实是找不出什么问题。。。于是上网找度娘，于是乎，找到了一下这段代码：

#include <stdio.h>
int main()
{
    unsigned long s=0,f1=1,f2=1,f3=1,n=0;
    scanf("%d",&n);
     if(n>2)
    for(s=3;s<=n;s++)
    {
         f3=(f2+f1)%10007;
         f1=f2;
         f2=f3;
     }
     printf("%d",f3);
     return 0;
 }