C语言之不一样的斐波那契数列

C语言之不一样的斐波那契数列

问题描述

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;
}

结果在快写代码中测试，在第四项以后都超时。。。

C语言之不一样的斐波那契数列

分析二

上面求斐波那契数列用的是递归，由于递归有重复操作可能耗时比较长，导致测试超时。
将递归修改成循环会不会不超时呢？

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之后未通过。。。

C语言之不一样的斐波那契数列

分析三

测试上面代码，再加上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;
}

结果比上面好一点，不过还是有通不过的。。。

C语言之不一样的斐波那契数列

分析四

本题最终结果是求余数，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分！

C语言之不一样的斐波那契数列

总结

题目其实描述的挺清楚的：
fn比较大、n的取值范围比较大

其实可以猜测普通的暴力求解是解不出来的。

工具分享

快写代码：安卓手机上的编程软件，随时随地写代码。