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

人中仙

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

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

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

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

通项公式法求第n项

//通项公式求数列第n项  a_n = (1/sqrt(5))*(pow((sqrt(5)+1)/2,n)+pow((sqrt(5)-1)/2,n))
#define F2_FIBONACCI_SWITCH
#ifdef F2_FIBONACCI_SWITCH

#include "math.h"

#define T_1 0.44721359549995f
#define T_2 1.61803398874989f   //浮点运算会带来误差
#define T_3 0.61803398874989f

unsigned long int Fibonacci(int n){
  double tmp = 0.0f;
  tmp = T_1*(pow(T_2,n)+pow(T_3,n));
  return (unsigned long int)(tmp);  //在整型转换过程中，大数计算误差很大，得错误值
}

#endif

递推法求第n项

#define F1_FIBONACCI_SWITCH
#ifdef F1_FIBONACCI_SWITCH
unsigned long int Fibonacci(int n){
  unsigned long int f1=1,f2=1,temp;
  if (n<3) return 1;
  for (int i = 1; i < n; i++) {
    temp = f1;
    f1 = f2;
    f2 = temp +f1;
  }
  return f1;
}
#endif

完整代码

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

#include <stdio.h>

unsigned long int Fibonacci(int n);
int IsEven(unsigned long int n);

int main(){
    unsigned long int sum = 0;
    int k = 1;
  for (unsigned long int i = 1; i < 4000000;) {
    i=Fibonacci(k++);
    printf("%ld ",i);
    IsEven(i) && (sum+=i);
  }
  printf("\n%ld\n",sum);
  return 0;
}

#define F1_FIBONACCI_SWITCH
#ifdef F1_FIBONACCI_SWITCH
unsigned long int Fibonacci(int n){
  unsigned long int f1=1,f2=1,temp;
  if (n<3) return 1;
  for (int i = 1; i < n; i++) {
    temp = f1;
    f1 = f2;
    f2 = temp +f1;
  }
  return f1;
}
#endif

int IsEven(unsigned long int n){
  return n%2?0:1;
}

//通项公式求数列第n项  a_n = (1/sqrt(5))*(pow((sqrt(5)+1)/2,n)+pow((sqrt(5)-1)/2,n))
//#define F2_FIBONACCI_SWITCH
#ifdef F2_FIBONACCI_SWITCH

#include "math.h"

#define T_1 0.44721359549995f
#define T_2 1.61803398874989f   //浮点运算会带来误差
#define T_3 0.61803398874989f

unsigned long int Fibonacci(int n){
  double tmp = 0.0f;
  tmp = T_1*(pow(T_2,n)+pow(T_3,n));
  return (unsigned long int)(tmp);  //在整型转换过程中，大数计算误差很大，得错误值
}

#endif

最佳答案

月排行榜 / 总排行榜

sunrise085

2021-2-2 11:51:59

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

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

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

跳转到最佳答案楼层

sunrise085

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

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

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