[已解决]关于C语言计算斐波那契数列

人中仙

原题：题目2：在斐波那契数列中，找出4百万以下的项中值为偶数的项之和

描述：在使用通项公式计算斐波那契第n项值的过程中要用到double型，但是斐波那契数列在20项以后会变得很大很大，这使得用浮点计算后的误差也变得很大很大，得不到精确的整数值。

问题：对于浮点数转化为整型有没有更准确的解决办法？该题中有没有时间开销比较小的算法？

代码片段如下，万分感谢。

通项公式法求第n项

1. //通项公式求数列第n项  a_n = (1/sqrt(5))*(pow((sqrt(5)+1)/2,n)+pow((sqrt(5)-1)/2,n))
   
2. #define F2_FIBONACCI_SWITCH
   
3. #ifdef F2_FIBONACCI_SWITCH
   
4. 
   
5. #include "math.h"
   
6. 
   
7. #define T_1 0.44721359549995f
   
8. #define T_2 1.61803398874989f   //浮点运算会带来误差
   
9. #define T_3 0.61803398874989f
   
10. 
    
11. unsigned long int Fibonacci(int n){
    
12.   double tmp = 0.0f;
    
13.   tmp = T_1*(pow(T_2,n)+pow(T_3,n));
    
14.   return (unsigned long int)(tmp);  //在整型转换过程中，大数计算误差很大，得错误值
    
15. }
    
16. 
    
17. #endif

复制代码

递推法求第n项

1. #define F1_FIBONACCI_SWITCH
   
2. #ifdef F1_FIBONACCI_SWITCH
   
3. unsigned long int Fibonacci(int n){
   
4.   unsigned long int f1=1,f2=1,temp;
   
5.   if (n<3) return 1;
   
6.   for (int i = 1; i < n; i++) {
   
7.     temp = f1;
   
8.     f1 = f2;
   
9.     f2 = temp +f1;
   
10.   }
    
11.   return f1;
    
12. }
    
13. #endif

复制代码

完整代码

1. /*
   
2. * 题目2：在斐波那契数列中，找出4百万以下的项中值为偶数的项之和
   
3. */
   
4. 
   
5. #include <stdio.h>
   
6. 
   
7. unsigned long int Fibonacci(int n);
   
8. int IsEven(unsigned long int n);
   
9. 
   
10. int main(){
    
11.     unsigned long int sum = 0;
    
12.     int k = 1;
    
13.   for (unsigned long int i = 1; i < 4000000;) {
    
14.     i=Fibonacci(k++);
    
15.     printf("%ld ",i);
    
16.     IsEven(i) && (sum+=i);
    
17.   }
    
18.   printf("\n%ld\n",sum);
    
19.   return 0;
    
20. }
    
21. 
    
22. #define F1_FIBONACCI_SWITCH
    
23. #ifdef F1_FIBONACCI_SWITCH
    
24. unsigned long int Fibonacci(int n){
    
25.   unsigned long int f1=1,f2=1,temp;
    
26.   if (n<3) return 1;
    
27.   for (int i = 1; i < n; i++) {
    
28.     temp = f1;
    
29.     f1 = f2;
    
30.     f2 = temp +f1;
    
31.   }
    
32.   return f1;
    
33. }
    
34. #endif
    
35. 
    
36. int IsEven(unsigned long int n){
    
37.   return n%2?0:1;
    
38. }
    
39. 
    
40. //通项公式求数列第n项  a_n = (1/sqrt(5))*(pow((sqrt(5)+1)/2,n)+pow((sqrt(5)-1)/2,n))
    
41. //#define F2_FIBONACCI_SWITCH
    
42. #ifdef F2_FIBONACCI_SWITCH
    
43. 
    
44. #include "math.h"
    
45. 
    
46. #define T_1 0.44721359549995f
    
47. #define T_2 1.61803398874989f   //浮点运算会带来误差
    
48. #define T_3 0.61803398874989f
    
49. 
    
50. unsigned long int Fibonacci(int n){
    
51.   double tmp = 0.0f;
    
52.   tmp = T_1*(pow(T_2,n)+pow(T_3,n));
    
53.   return (unsigned long int)(tmp);  //在整型转换过程中，大数计算误差很大，得错误值
    
54. }
    
55. 
    
56. #endif

复制代码

最佳答案

月排行榜 / 总排行榜

sunrise085

2021-2-2 11:51:59

浮点型转整型，有精度损失是必然的，这是他们的存储方式导致的，没有解决办法。
而且long本来就满足数据大小的要求了，何必非要去使用double来降低精度
斐波那契数列不要用通项公式求了。直接用基本方法累加就挺简单的啊

想找时间开销少的方法，直接写程序，不要花里胡哨的写好几个函数，能省去不少时间

1. #include <stdio.h>
   
2. int main(){
   
3.     unsigned long int sum = 0,i=1,temp1=1,temp2;
   
4.     int k = 1;
   
5.     for (; i < 4000000;) {
   
6.         if(i%2==0){
   
7.             printf("%d:%ld \n",k++,i);//若只是完成功能，则删掉这一行，printf特别消耗时间！！
   
8.             sum+=i;
   
9.         }
   
10.         temp2=i;
    
11.         i=temp1;
    
12.         temp1=i+temp2;
    
13.     }
    
14.     printf("\nsum=%ld\n",sum);
    
15.     return 0;
    
16. }

复制代码

跳转到最佳答案楼层

sunrise085

浮点型转整型，有精度损失是必然的，这是他们的存储方式导致的，没有解决办法。
而且long本来就满足数据大小的要求了，何必非要去使用double来降低精度
斐波那契数列不要用通项公式求了。直接用基本方法累加就挺简单的啊

想找时间开销少的方法，直接写程序，不要花里胡哨的写好几个函数，能省去不少时间

1. #include <stdio.h>
   
2. int main(){
   
3.     unsigned long int sum = 0,i=1,temp1=1,temp2;
   
4.     int k = 1;
   
5.     for (; i < 4000000;) {
   
6.         if(i%2==0){
   
7.             printf("%d:%ld \n",k++,i);//若只是完成功能，则删掉这一行，printf特别消耗时间！！
   
8.             sum+=i;
   
9.         }
   
10.         temp2=i;
    
11.         i=temp1;
    
12.         temp1=i+temp2;
    
13.     }
    
14.     printf("\nsum=%ld\n",sum);
    
15.     return 0;
    
16. }

复制代码