蓝桥杯入门训练Fibonacci数列 C语言

青旅半醒 2022-04-12 13:13 292阅读 0赞

# 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。

首先，看到这个题目，笔者第一个想到的是递归法，但由于笔者学艺不精，时间长了具体怎么写给忘光了，于是看了蓝桥杯官网的锦囊  
锦囊给的提示是  
![在这里插入图片描述][20181203145532985.png]  
用数组保存？看起来是个办法，但仔细一想其实问题很多：  
首先，题目中给的数据规模是 **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;
     }

看上去，感觉确实厉害了不少 ，简洁精悍，于是我尝试将它粘贴上去。。。果然正确了。。。

然而身为小白的我百思不得其姐啊，怎么我的代码就不行嘞~~  
纠结了好久之后，我发现了这个：  
![在这里插入图片描述][20181203160213241.png]  
![在这里插入图片描述][20181203160151279.png]  
我的代码CPU占用率和内存使用远远大于正确的代码！仔细一想，递归其实和数组一样，确实占用了不少内存空间，而且也加大了计算量。

不过，本小（da）白也不知道是不是这个理，如果有大神看到这篇文章，欢迎指正！

[20181203145532985.png]: /images/20220412/f71faab98f3c4e64814a7ee8c7dee685.png
[20181203160213241.png]: /images/20220412/33f75d110a3e455b8eb73020ac6bfa28.png
[20181203160151279.png]: /images/20220412/21071dbe9e55446abe7704e292c55123.png