編程之美 裴波那楔數列

給出如下遞推式：

以上就是經典的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;
}

以上采用了循環的方法，時間復雜度加快了。