Question

斐波那契数列:c语言

以下给出计算斐波那契数列的两种不同方法：
（1）递推计算
f0=0,f1=1;
fi=f(i-1)+f(i-2), (i>1)

（2）公式计算
fi=(int)(c^i/sqrt(5)+0.5)

c=(1.0+sqrt(5)/2.0)

试编写程序找出以上两种计算方法求得的fi不相等的i

Answer 1

你公式计算的公式不对 如果按照这个公式计算，只有0 和1的时候是一样的 剩下的都不一样
程序这样做
#include <stdio.h>
#include <math.h>
int f1(int i)
{
if(i == 0) return 0;
if(i == 1) return 1;
return f1(i - 1) + f1(i - 2);
}

int f2(int i)
{
#if 1
int ret;
double c;

c = (1.0+sqrt(5)/2.0);
ret =(int)(pow(c,i)/sqrt(5)+0.5);
#else
int ret;
double c, c1;

c = (1.0+sqrt(5))/2.0;
c1 = (1.0-sqrt(5))/2.0;
ret =(int)((pow(c,i) - pow(c1, i))/sqrt(5)+0.5);

#endif
return ret;
}

main()
{
int i = 0;
int r1, r2;
while(1)
{
r1 = f1(i);
r2 = f2(i);
if(r1 != r2)
printf("diff at %d, %d %d\n", i, r1, r2);
i ++;
}
}

在f2里面有一个#if 1 这时是用你的公式
改成#if 0后用的是正确的公式