关于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 13:53 编辑
浮点型转整型，有精度损失是必然的，这是他们的存储方式导致的，没有解决办法。
而且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;
}
页:
[1]