Fibonacci数列 求余数问题求助

黑框眼镜和卷毛

问题：

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

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

我的代码：

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.         long F1,F2,F3,i,n;
   
5.        
   
6.         F1=F2=1;
   
7.        
   
8.         printf("please enter a number(n)!");
   
9.         scanf("%ld",&n);
   
10.        
    
11.         if(n==1||n==2){
    
12.                 printf("%ld",1%10007);
    
13.         }
    
14.         else
    
15.         {
    
16.                 for(i=1;i<=n-2;i++)
    
17.                 {
    
18.                         F3=F2+F1;
    
19.                         F1=F2;
    
20.                         F2=F3;       
    
21.                 }
    
22.                 printf("%ld",F3%10007);
    
23.         }       
    
24.         return 0;
    
25. }

复制代码

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

黑框眼镜和卷毛

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

黑框眼镜和卷毛

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

黑框眼镜和卷毛

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

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

超凡天赐

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

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.     long long F1,F2,F3 = 0;
   
5.     int n,i;
   
6.     F1=F2=1;
   
7.     scanf("%d",&n);
   
8.    
   
9.     if(n==1||n==2){
   
10.         printf("%d",1%10007);
    
11.     }
    
12.     else
    
13.     {
    
14.         for(i=1;i<=n-2;i++)
    
15.         {
    
16.             F3=F2+F1;
    
17.             F1=F2;
    
18.             F2=F3;
    
19.         }
    
20.         printf("%lld",F3%10007);
    
21.     }
    
22.     return 0;
    
23. }

复制代码

fc1735

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

fc1735

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

1. #include<stdio.h>
   
2. #include<math.h>
   
3. #define div 10007  
   
4. 
   
5. int main()
   
6. {
   
7.         int F1=1,F2=1,t,t_2,i;
   
8.         long long int n;
   
9.         t=log(div)/log((sqrt(5)+1)/2);
   
10.         t+=t&1;
    
11.         t_2=t>>1;
    
12. 
    
13.         scanf("%lld",&n);
    
14. 
    
15.         for(;;)
    
16.         {
    
17.                 if ((n-=2)<=0) break;
    
18.                 for(;;)
    
19.                 {
    
20.                         if (n<t)break;
    
21.                         for(i=0;i<t_2;i++)
    
22.                         {
    
23.                                 F1+=F2;
    
24.                                 F2+=F1;
    
25.                         }
    
26.                         n-=t;
    
27.                         F1%=div;
    
28.                         F2%=div;
    
29.                 }
    
30.                 if(!n)break;
    
31.                 for(;n;n--)
    
32.                 {
    
33.                         F2+=F1;
    
34.                         F1=F2-F1;
    
35.                 }
    
36.                 F2%=div;
    
37.                 break;
    
38. 
    
39.         }
    
40. 
    
41. 
    
42.         printf("%d",F2);
    
43. 
    
44.         return 0;
    
45. }
    

复制代码

代码农民

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

1. #include <stdio.h>
   
2. 
   
3. int
   
4. main( void )
   
5. {
   
6.     unsigned a = 0, b = 1, sum;       // A[ 0 ] = 0, A[ 1 ] = 1, A[ 2 ] = 1, A[ 3 ] = 2,....
   
7.     unsigned i, n;                   //n为下标
   
8. 
   
9.     scanf( "%u", &n );
   
10.     for( i = 2; i < n; ++i )          //从A[ 3 ]开始到A[ n - 1 ], 不满足就忽略该循环
    
11.         sum = a + b, a = b, b = sum;  
    
12.      
    
13.     sum = a + b;                     // A[ n ] = A[ n - 1 ] + A[ n - 2 ]
    
14.     printf( "%u", sum % 10007 );   
    
15. 
    
16.     return 0;
    
17. }
    

复制代码

黑框眼镜和卷毛

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

蓝桥杯大赛的练习系统