图片发自简书App
问题描述
Fibonacci数列的递推公式为：F(n)=F(n-1)+F(n-2)，其中F(1)=F(2)=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
默认规定：
1<= n <=1000000
分析一
根据斐波那契递推公式可以写出递归函数，求出F(n)对10007取余即可。
int fibon(int n)
{
if(n<=2)
return 1;
else
return fibon(n-1) + fibon(n-2);
}
挺简单的，直接调用试一下：
int main()
{
int n;
scanf("%d", &n);
printf("%d", fibon(n)%10007);
return 0;
}
结果在快写代码中测试，在第四项以后都超时。。。
图片发自简书App
分析二
上面求斐波那契数列用的是递归，由于递归有重复操作可能耗时比较长，导致测试超时。
将递归修改成循环会不会不超时呢？
int fibon(int n)
{
int fn = 1, fn1 = 1, fn2 = 1;
if(n>2)
{
for(int i=2; i<n; i++)
{
fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
}
return fn;
}
主函数调用方法同上，不再重复，结果。。。测试项4之后未通过。。。
图片发自简书App
分析三
测试上面代码，再加上n的大小规定，猜想可能是int的范围不够大，所以将代码中int替换为double。
#include <stdio.h>
#include <math.h>
double fibon(int n)
{
double fn = 1, fn1 = 1, fn2 = 1;
if(n>2)
{
for(int i=2; i<n; i++)
{
fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
}
return fn;
}
int main()
{
int n;
scanf("%d", &n);
double sha = floor(fibon(n)/10007);
printf("%.0lf", fibon(n)-sha*10007);
return 0;
}
结果比上面好一点，不过还是有通不过的。。。
图片发自简书App
分析四
本题最终结果是求余数，fn的结果10007001和1是一样的，所以最终应该改造斐波那契数列的求值。
int fibon(int n, int yu)
{
int fn = 1, fn1 = 1, fn2 = 1;
if(n>2)
{
for(int i=2; i<n; i++)
{
fn = (fn1 + fn2)%yu;
fn2 = fn1;
fn1 = fn;
}
}
return fn;
}
调用也相对简单：
int main()
{
int n;
scanf("%d", &n);
printf("%d", fibon(n, 10007));
return 0;
}
结果自然是通过，100分！
图片发自简书App
总结
题目其实描述的挺清楚的：
fn比较大、n的取值范围比较大
其实可以猜测普通的暴力求解是解不出来的。
