鱼C论坛

 找回密码
 立即注册
查看: 3547|回复: 8

Fibonacci数列 求余数问题求助

[复制链接]
发表于 2017-1-25 19:51:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
问题:

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

我在一个在线答题网站上提交这段代码,评测结果是错误。
我是编程新手,我想问一下各位大神,代码错在哪儿?
谢谢各位。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-1-25 20:21:31 | 显示全部楼层
这个试题好诡异。
我把上面的代码中的  printf("please enter a number(n)!"); 去掉了。
评测分数从之前的0分变成了30分
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-1-25 21:13:24 | 显示全部楼层
我已经知道为什么错了....
虽然还没有人回复我。
这个代码的问题在于,当输入特别大的数时会不满足条件,例如“999999”
个人见解,如有错误,欢迎指出。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

这个大概是因为题目对于代码的格式规定吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-25 21:37:26 | 显示全部楼层
一开始溢出了。代码评测网站对算法要求比较高,超出时间是一分不给,输入时只有数据,其他不能显示。我也时是新手,暂时帮你改到这了。
#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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-27 12:37:39 | 显示全部楼层
是什么答题网站阿,有网址吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-27 14:11:24 | 显示全部楼层
写得有点复杂,效率还可以
#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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-27 21:49:16 | 显示全部楼层
本帖最后由 代码农民 于 2017-1-27 23:16 编辑

用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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-1-29 18:56:38 | 显示全部楼层
fc1735 发表于 2017-1-27 12:37
是什么答题网站阿,有网址吗

蓝桥杯大赛的练习系统
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-27 19:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表