ACM 斐波那切数列#include int fun(int n) { if(n==1) return 11; if(n=2; num

ACM 斐波那切数列#include int fun(int n) { if(n==1) return 11; if(n=2; num
ACM 斐波那切数列
#include
int fun(int n)
{
if(n==1)
return 11;
if(n=2;
num

ACM 斐波那切数列#include int fun(int n) { if(n==1) return 11; if(n=2; num
自己看咯

你的程序肯定是有问题的，Fibonacci数列是以指数增长的，即使使用VC中_int64存储最多也只能算到n=92，并且你的算法效率奇低，为最差的指数级别T(n)=T(0)*((√5+1)/2)^n=T(0)*1.618^n
这道题要考虑两点,一是数据溢出,二是运行效率
采用普通递归的方式求Fibonacci数列的时间函数是T(n)=T(n-1)+T(n-2),从而T(n)=T(0...

全部展开

你的程序肯定是有问题的，Fibonacci数列是以指数增长的，即使使用VC中_int64存储最多也只能算到n=92，并且你的算法效率奇低，为最差的指数级别T(n)=T(0)*((√5+1)/2)^n=T(0)*1.618^n
这道题要考虑两点,一是数据溢出,二是运行效率
采用普通递归的方式求Fibonacci数列的时间函数是T(n)=T(n-1)+T(n-2),从而T(n)=T(0)*((√5+1)/2)^n=T(0)*1.618^n
通过实际测试得出T(30)=0.2515 sec,那么T(0)=1.353*10^(-7)
T(90)=1.353*10^(-7)*1.618^90=8.7×10^11 sec=27577 year
也就是说你永远也得不到结果,普通递推之所以慢,是因为其中有很多重复的计算,因此要采用数组保存中间结果,防止重复计算.
下面是我改进后的递归算法:
#include "stdio.h"
#include "windows.h"
#define NUM 92
__int64 fib[NUM];
int flag=-1;//用于标记fib数列中还未计算的项
__int64 Fib(int n)
{
if(fib[n]!=flag)
return fib[n];
// return Fib(n-1)+Fib(n-2);//普通递归
return fib[n]=Fib(n-1)+Fib(n-2);//改进递归
}
void main()
{
int i;
LARGE_INTEGER t1,t2,frq;
for(i=0;i fib[i]=flag;
fib[0]=fib[1]=1;
QueryPerformanceFrequency(&frq);//获取计时器频率
QueryPerformanceCounter(&t1);//获得起始时间
for(i=0;i {
printf("fib[%d]=%I64d\t",i,Fib(i));
QueryPerformanceCounter(&t2);
printf("time=%f sec\n",(double)(t2.QuadPart-t1.QuadPart)/frq.QuadPart);
}
}
尤其要注意递归部分注释掉的和下面的区别,前92项只需0.09秒即全部算出.

收起