斐波那契数列的每一项f（n），计算出f（n）<int所能表示的最大值的n值为多少？
刚开到这道题，哇，太简单了吧，有个递归就可以搞定斐波那契数列啦，于是写了一个简单的递归实现的斐波那契数列算法：
int fib(int n)
{
if(n==1||n==2)
{
return 1;
}
else
{
return fib(n-1)+fib(n-2);
}
}
试着运行了一下，当n的值大于40时，运行速度就慢了很多了，试想一下距离int所能表示的最大值2^31-1还远着呢，看来用递归是不可行的。
接下来想了想，既然递归能够实现，那循环肯定也是实现斐波那契数列的啦~~
int f1(int n)
{
int a = 1;
int b = 1;
double k =double(n);
int j =ceil(k/2); //天花板函数，算出所要求的项的二分之一的上值
for(int i=1;i<= j-1;i++)
{
a += b;
b += a;
}
if(n%2==0)
return b;
else
return a;
}
果然不出所料，循环实现的这个算法比递归真的要快上N倍，而且n值能够取得最大值是依赖于int能够表示的范围的，超出了int表示范围就变成负数了。n=46时，是int能够表示的最大的斐波那契值了。
其实这道题用循环就可以解出来了，不过对于运行速度还是有要求的话，我们就可以直接用斐波那契数列的通项公式算出具体的某个值。通项为F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（√5表示根号5）
int f2(int n)
{
return (pow((1+sqrt(5.0))/2,n)-pow((1-sqrt(5.0))/2,n))/sqrt(5.0);
}
这个算法当然就更快了，都不用递归或循环，只要输入一个n值就可以直接算出来了，数学公式果然是强大的解题工具。
这道题的解题过程如下：
int f2(int n)
{
return (pow((1+sqrt(5.0))/2,n)-pow((1-sqrt(5.0))/2,n))/sqrt(5.0);
}
int main()
{
int n=1;
int max = pow(2,31)-1;
while(f2(n)<max&&f2(n)>0)
{
n++;
}
cout<<n-1<<endl;
return 0;
}
结果n=46
现在算一下这几个算法运行的时间长短：
在网上搜了个比较精确的计数器程序：
double getTime2() //使用高精度计时器
{
static LARGE_INTEGER s_freq;
LARGE_INTEGER performanceCount;
double t;
if (s_freq.QuadPart==0)
{
if ( !QueryPerformanceFrequency( &s_freq))
return 0;
}
QueryPerformanceCounter( &performanceCount );
t=(double)performanceCount.QuadPart / (double)s_freq.QuadPart;
return t;
}
测量程序如下：
int main()
{
double t1=getTime2();
fib(35); //再大的话程序就卡在那里了，所以选了个35，跟其他两个算法不一样
double t2=getTime2();
cout<<"fib(n)递归:"<<t2-t1<<endl;
double t3=getTime2();
f1(46);
double t4=getTime2();
cout<<"f1(n)循环:"<<t4-t3<<endl;
double t5=getTime2();
f2(46);
double t6=getTime2();
cout<<"f2(n)公式:"<<t6-t5<<endl;
return 0;
}
运行结果如下：
fib(n)递归:0.722634
f1(n)循环:7.82222e-006
f2(n)公式:3.35238e-006
从上面的运行时间可以看出来，递归实在是太慢了，公式法的速度优于循环，不过循环也比递归快很多了，都不是一个数量级的差别了~~