编程之美 裴波那楔数列

给出如下递推式：

以上就是经典的Fibonacci数列，下面给出递推的解法：

int Fibonacci(int n) 
{ 
   if(n<=0) 
       return 0; 
   else if(n==1) 
        return 1; 
   else 
       return Fibonacci(n-1)+Fibonacci(n-2); 
 
} 

int Fibonacci(int n)
{
   if(n<=0)
    return 0;
   else if(n==1)
        return 1;
   else
    return Fibonacci(n-1)+Fibonacci(n-2);

}

 

我们知道 ，以上的解法每个F(n)计算了2次，我们能不能只计算一次，做一个缓存，当然是可以的。如下：

int tmp1=1;//临时变量，保存中间结果  
int tmp2=0; 
int tmp; 
 
int Fibonacci(int n) 
{ 
  int F; 
  
  for(int i=2;i<=n;++i) 
  { 
 
     tmp=tmp1+tmp2;      
     tmp2=tmp1; 
     tmp1=tmp; 
  } 
  return tmp; 
} 

int tmp1=1;//临时变量，保存中间结果
int tmp2=0;
int tmp;

int Fibonacci(int n)
{
  int F;
 
  for(int i=2;i<=n;++i)
  {

     tmp=tmp1+tmp2;    
  tmp2=tmp1;
     tmp1=tmp;
  }
  return tmp;
}

以上采用了循环的方法，时间复杂度加快了。