C/C++面試之算法系列－－菲波拉契數列的遞歸與非遞歸算法

  ××××××××××××××××××××××××××××××××× 菲波拉契數列的遞歸與非遞歸算法 Sailor_forever [email protected] 轉載請注明 http://blog.csdn.net/sailor_8318/archive/2007/09/27/1802355.aspx ××××××××××××××××××××××××××××××××× Fibonacci 數列有如下特點：其第 1 ， 2 項均為 1 ， 1 。從第 3 個數開始，該數是其前兩個數之和 . 即 : F1=1 (n=1) F2=1 (n=2) Fn=Fn-1+Fn-2 (n>=3) 請你編寫一個函數 fun ，它的功能是：對于一個給定的數（ N ）， 求不大于 N 的最大 Fibonacci 數。 要儲存兩個連續的序列值，目前數大于且上一個小于時，即為所求值，非遞歸比較容易實作   1     1     2     3     5     8     13。。。。。。。。。。。。 ××××××××××××××××××××××××××××××××× 遞歸算法：   1. 最普通算法    long   fib(long  n)    {          // if (n ==0 || n == 1)               if (n <= 0) // 因為上面的參數n是有符号的，要考慮容錯性能，否則參數錯誤時将造成死循環了                      return   0 ;               if ( n == 1)                return   1 ;           else                 return   fib(n - 1) + fib(n - 2);    }   2.    指針疊代，每次可算倆個值 fib(int n,int *s)   {          int f1,f2;   // 每次遞歸都有申請兩個變量，遞歸深度太大時可能導緻堆棧溢出哦        if(n==1||n==2)                   *s=1; 傳回        else          {                 fib(n-1,&f1);   // 指針傳遞，這裡隻是将上面的一個式子分解了下而已               fib(n-2,&f2);                 *s=f1+f2;          }   }   3. 引用疊代，減少了傳回值臨時變量的申請 fib(int n,int &s)   {          int f1,f2;          if(n==1||n==2)                   s=1; 傳回        else          {                 fib(n-1, f1);   // 引用傳遞               fib(n-2, f2);                 s=f1+f2;          }   } ××××××××××××××××××××××××××××××××× 非遞歸算法 1.    數組疊代 void   F(long*f, int n)   {          int   i;          f[0]=f[1]=1;        if(n <= 2)               return;        for(i=2;i<n;i++)                  f[i]=f[i-1]+f[i-2];   } 2.    變量替換，又額外申請了變量f0,f1,f2，不好；但每次更新相加的數，思想不錯，邏輯清楚 void   F(long *f, int n)   {   int   f0,f1,f2;          f0=f1=1;        for(i=2;i<=n;++i){         f2=f0+f1;         f0=f1;         f1=f2;          }        printf("f[%d]=%d/n",n,f2); }   3.    此法比較難以想到 對于任意第n項    int   Fx(int   n)    {    p1   =   pow((1+sqrt(5))/2,n);    p2   =   pow((1-sqrt(5))/2,n);    return   (p1-p2)/sqrt(5);    }   4.    效率最高，一次循環可以算出兩個值，每個值隻需一條語句，沒有交換過程，是通過改變輸出的變量來實作的 void   fibonacci(int   n)   // 1 2 3 …..  {   a   =   1;    b   =   1;    if(n <= 2)  { cout   <<   1   <<   endl; return; }    for(i = 1;   i   <  n/2;   i++)    {             a   +=   b;   // a儲存了奇數         cout   <<   a   <<   endl;                   If（(n > 3) && (n %2 == 0)）// 每次的偶數部分 {           b   +=   a;   // b儲存了偶數           cout   <<   a   <<   endl; }  }   }   ××××××××××××××××××××××××××××××××× 給定n，找到小于此數的最大fibonacci數   1.    變量替換，終止條件是目前數大于給定的數，上一個數就是求的臨界值，c即為所求 void   fibonacci(int   n)    {             int   a   =   1;             int   b   =   1;             printf("...",a,b);              while(b<n）             {                     int   c=b;                     b   =   a+b;                     printf("...",b);                     a   =   c;             }    }   2.    此法非常精妙，比上面少申請了一個中間變量c，通過加減來實作循環指派的 #include   <iostream.h> void   fibonacci(int   n)    {            int   low   =   1,high   =   1;             while(high   <   n)             {             cout   <<   high   <<   endl;             high   =   low   +   high;             low   =   high   -   low;            }        }