蓝桥杯 Fibonacci数列求余数 C语言版本
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
数据规模与约定
1 <= n <= 1,000,000。
首先，看到题目Fibonacci数列，余数，只要系统学过C语言的读者应该都知道这两个名词，当然余数是我们大家小学就学习的东西。当然，题目也给出了Fibonacci数列是一个什么样的数列，就是Fn=Fn-1+Fn-2，即当前的这个数等于前两个数之和，写一小段：1，1，2，3，5，8，13。
余数，当然也就是余数指整数除法中被除数未被除尽部分，且余数的取值范围为0到除数之间（不包括除数）的整数。这是百度百科的解释。C语言中求余使用‘%’来算，比如，求7除以3的余数就是7%3。
本题中求Fn%10007，就是算Fn除10007后所生剩下的数，也就是Fn减去10007的多少多少倍后剩下的数（这很重要）。
我看到这道题第一反应想的是采用先把当前的Fn算出来，再去用Fn直接求余数，但n的范围过大，肯定会超出整数数的范围，咱们来看看。
这是C语言中整数类型的范围：
unsigned int 0～4294967295
int -2147483648～2147483647
unsigned long 0～4294967295
long -2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615
__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615
我们来看当n为89,90左右时,Fn的值为61305790721611591,7540113804746346429 ，题目要求为 1 <= n <= 1,000,000，必定会超出整型的范围，所以是不能用以下的暴力办法求：
#include<stdio.h>
long long int Fibonacci(int n)
{
int i=0;
long long int f1,f2,fn;
fn=f1=f2=1;
while(i<n-2)
{
fn=f1+f2;
f1=f2;
f2=fn;
i++;
if(i%9==0)
printf("\n");
printf("%lld ",fn);
}
return fn;
}
int main()
{
int n;
long long int fn;
scanf("%d",&n);
fn=Fibonacci(n);
printf("%lld",fn%10007);
return 0;
}
所以来考虑简便方法：
我从网上看了很多人对这个简便方法的解释，不过可能是我找的不多的原因，没有找到比较详细的解答，下面就介绍我对这道题目的理解，如有解释不当，请见谅，可在下方共同讨论。
（可以先看代码，再看下面的苹果解答）
由于是要求余数，就从余数下手。我来形象的解释下这道题目，就把fn看成一堆苹果，那么f1就是1个苹果，f2是，f3是，f4是，…，fn就是n个苹果。现在要求fn%10007,也就是fn/10007剩下的部分。我们根据Fibonacci数列的式子可知Fn=Fn-1+Fn-2，所以第fn堆苹果是由前面的苹果加起来的，第一种求fn%10007，就是整个把fn整堆苹果/10007求剩下的苹果数，（也就是上面的代码）。第二种是在求之前每堆苹果数时先把能除10007的先除掉，因为是加法，所以除不掉的苹果数是可以加起来的，加到10007时，还是可以除掉的。所以可以用以下代码求解。
#include<stdio.h>
int main()
{
int n,f1,f2,fn,i=0;
f1=f2=fn=1;
while(i<n)
{
fn=(f1+f2)%10007;
f1=f2;
f2=fn;
i++;
}
return 0;
}
文章评论