Fibonacci数列 求余数问题求助

黑框眼镜和卷毛

问题：

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

我的代码：

#include<stdio.h>
int main()
{
        long F1,F2,F3,i,n;
        
        F1=F2=1;
        
        printf("please enter a number(n)!");
        scanf("%ld",&n);
        
        if(n==1||n==2){
                printf("%ld",1%10007);
        }
        else
        {
                for(i=1;i<=n-2;i++)
                {
                        F3=F2+F1;
                        F1=F2;
                        F2=F3;        
                }
                printf("%ld",F3%10007);
        }        
        return 0;
 } 

我在一个在线答题网站上提交这段代码，评测结果是错误。
我是编程新手，我想问一下各位大神，代码错在哪儿？
谢谢各位。

黑框眼镜和卷毛

这个试题好诡异。
我把上面的代码中的  printf("please enter a number(n)!"); 去掉了。
评测分数从之前的0分变成了30分

黑框眼镜和卷毛

我已经知道为什么错了....
虽然还没有人回复我。
这个代码的问题在于，当输入特别大的数时会不满足条件，例如“999999”
个人见解，如有错误，欢迎指出。

黑框眼镜和卷毛

黑框眼镜和卷毛 发表于 2017-1-25 20:21
这个试题好诡异。
我把上面的代码中的  printf("please enter a number(n)!"); 去掉了。
评测分数从之前 ...

这个大概是因为题目对于代码的格式规定吧

超凡天赐

一开始溢出了。代码评测网站对算法要求比较高，超出时间是一分不给，输入时只有数据，其他不能显示。我也时是新手，暂时帮你改到这了。

#include<stdio.h>
int main()
{
    long long F1,F2,F3 = 0;
    int n,i;
    F1=F2=1;
    scanf("%d",&n);
    
    if(n==1||n==2){
        printf("%d",1%10007);
    }
    else
    {
        for(i=1;i<=n-2;i++)
        {
            F3=F2+F1;
            F1=F2;
            F2=F3;
        }
        printf("%lld",F3%10007);
    }
    return 0;
}

fc1735

是什么答题网站阿，有网址吗

fc1735

写得有点复杂，效率还可以

#include<stdio.h>
#include<math.h>
#define div 10007  

int main()
{
        int F1=1,F2=1,t,t_2,i;
        long long int n;
        t=log(div)/log((sqrt(5)+1)/2);
        t+=t&1;
        t_2=t>>1;

        scanf("%lld",&n);

        for(;;)
        {
                if ((n-=2)<=0) break;
                for(;;)
                {
                        if (n<t)break;
                        for(i=0;i<t_2;i++)
                        {
                                F1+=F2;
                                F2+=F1;
                        }
                        n-=t;
                        F1%=div;
                        F2%=div;
                }
                if(!n)break; 
                for(;n;n--)
                {
                        F2+=F1;
                        F1=F2-F1;
                }
                F2%=div;
                break;

        }


        printf("%d",F2);

        return 0;
}

代码农民

用unsigned，反正取余要的是数的后几位，并且10007< 65535(2个字节）。

#include <stdio.h>

int
main( void )
{
    unsigned a = 0, b = 1, sum;       // A[ 0 ] = 0, A[ 1 ] = 1, A[ 2 ] = 1, A[ 3 ] = 2,....
    unsigned i, n;                   //n为下标

    scanf( "%u", &n );
    for( i = 2; i < n; ++i )          //从A[ 3 ]开始到A[ n - 1 ], 不满足就忽略该循环
        sum = a + b, a = b, b = sum;  
     
    sum = a + b;                     // A[ n ] = A[ n - 1 ] + A[ n - 2 ]
    printf( "%u", sum % 10007 );    

    return 0;
}

黑框眼镜和卷毛

fc1735 发表于 2017-1-27 12:37
是什么答题网站阿，有网址吗

蓝桥杯大赛的练习系统