斐波那契数列公式

斐波那契数列：
$f（n）=n，n⩽1$
$f（n）=f（n-1）+f（n-2）,n\ge 2$

常用的迭代编程算法

#include <stdio.h>
#include <stdlib.h>
unsigned long fibo(unsigned long int n)
{
    if(n <= 1)
        return n;
    else 
        return fibo(n-1) + fibo(n-2);
}
int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu",n,fiboNum);
    return 0;
}

以计算F（5）为例进行递归分析：

                   F(2)  F(1)
           F(3)          F(0)
                   F(1)
      F(4)   
           F(2)    F(1)
                   F(0)
F(5)      
           F(2)    F(1)
      F(3)         F(0)
           F(1)

可以观察出F（1）被计算五次 等等。时间复杂度很大。
其次可能会导致栈溢出。（默认栈空间大小为8M）

递归改进版

#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列，避免重复计算版本*/
unsigned long fiboProcess(unsigned long *array,unsigned long n)
{
   if(n < 2)
       return n;
   else
   {
       /*递归保存值*/
       array[n] = fiboProcess(array,n-1) + array[n-2];
       return array[n];
   }
}

unsigned long  fibo(unsigned long  n)
{
   if(n <= 1)
       return n;
   unsigned long ret = 0;
   /*申请数组用于保存已经计算过的内容*/
   unsigned long *array = (unsigned long*)calloc(n+1,sizeof(unsigned long));
   if(NULL == array)
   {
       return -1;
   }
   array[1] = 1;
   ret = fiboProcess(array,n);
   free(array);
   array = NULL;
   return ret;
}
int main(int argc,char *argv[])
{
   if(1 >= argc)
   {
      printf("usage:./fibo num");
      return -1;
   }
   unsigned long  n = atoi(argv[1]);
   unsigned long  fiboNum = fibo(n);
   printf("the %lu result is %lu",n,fiboNum);
   return 0;
}

时间复杂度为O（n）。

迭代解法

#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列迭代版*/
unsigned long  fibo(unsigned long  n)
{
    unsigned long  preVal = 1;
    unsigned long  prePreVal = 0;
    if(n <= 2)
        return n;
    unsigned long  loop = 1;
    unsigned long  returnVal = 0;
    while(loop < n)
    {
        returnVal = preVal +prePreVal;
        /*更新记录结果*/
        prePreVal = preVal;
        preVal = returnVal;
        loop++;
    }
    return returnVal;
}
int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu",n,fiboNum);
    return 0;
}

时间复杂度为O（n）

尾递归解法

#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列尾递归版*/
unsigned long fiboProcess(unsigned long n,unsigned long  prePreVal,unsigned long  preVal,unsigned long begin)
{
    /*如果已经计算到我们需要计算的，则返回*/
    if(n == begin)
        return preVal+prePreVal;
    else
    {
        begin++;
        return fiboProcess(n,preVal,prePreVal+preVal,begin);
    }
}

unsigned long  fibo(unsigned long  n)
{
    if(n <= 1)
        return n;
    else 
        return fiboProcess(n,0,1,2);
}
int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu",n,fiboNum);
    return 0;
}

尾递归在函数返回之前的最后一个操作仍然是递归调用。尾递归的好处是，进入下一个函数之前，已经获得了当前函数的结果，因此不需要保留当前函数的环境，内存占用自然也是比最开始提到的递归要小。时间复杂度为O(n)。

矩阵快速幂解法

推导如下：

假设有2*2的矩阵A满足下面的等式：
$A\ast \left[\begin{array}{c}f（n-1）\\ f（n-2）\end{array}\right]=\left[\begin{array}{c}f（n）\\ f（n-1）\end{array}\right]=\left[\begin{array}{c}f（n-1）+f（n-2）\\ f（n-1）\end{array}\right]$

可以得到矩阵A
$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$
即可以得到下面的矩阵等式
$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\ast \left[\begin{array}{c}f（n-1）\\ f（n-2）\end{array}\right]=\left[\begin{array}{c}f（n）\\ f（n-1）\end{array}\right]$
再进行变换：
$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\ast \left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\ast \left[\begin{array}{c}f（n-2）\\ f（n-3）\end{array}\right]=\left[\begin{array}{c}f（n）\\ f（n-1）\end{array}\right]$
即
${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\ast \left[\begin{array}{c}f（1）\\ f（0）\end{array}\right]=\left[\begin{array}{c}f（n）\\ f（n-1）\end{array}\right]$

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COL 2
#define MAX_ROW 2
typedef unsigned long MatrixType;
/*计算2*2矩阵乘法，这里没有写成通用形式，有兴趣的可以自己实现通用矩阵乘法*/
int matrixDot(MatrixType A[MAX_ROW][MAX_COL],MatrixType B[MAX_ROW][MAX_COL],MatrixType C[MAX_ROW][MAX_COL])
{
   /*C为返回结果，由于A可能和C相同，因此使用临时矩阵存储*/
    MatrixType tempMa[MAX_ROW][MAX_COL] ;
    memset(tempMa,0,sizeof(tempMa));
    /*这里简便处理*/
    tempMa[0][0] = A[0][0] * B[0][0] + A[0][1] * B [1][0];
    tempMa[0][1] = A[0][0] * B[0][1] + A[0][1] * B [1][1];
    tempMa[1][0] = A[1][0] * B[0][0] + A[1][1] * B [1][0];
    tempMa[1][1] = A[1][0] * B[0][1] + A[1][1] * B [1][1];
    memcpy(C,tempMa,sizeof(tempMa));

    return 0;
}
MatrixType fibo(int n)
{
    if(n <= 1)
        return n;
    MatrixType result[][MAX_COL] = {1,0,0,1};
    MatrixType A[][2] = {1,1,1,0};
    while (n > 0) 
    {
        /*判断最后一位是否为1，即可知奇偶*/
        if (n&1) 
        {
            matrixDot(result,A,result);

        }
        n /= 2;
        matrixDot(A,A,A);
    }
    return result[0][1];
}

int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu",n,fiboNum);
    return 0;
}

可以看到，计算次数类似与二分查找次数，其时间复杂度为O(logn)

通项公式解法

通项公式为：
$f（n）=\frac{（\frac{1+\sqrt{5}}{2}{）}^n-（\frac{1-\sqrt{5}}{2}{）}^n}{\sqrt{5}}$

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
unsigned long fibo(unsigned long n)
{
    if(n <=1 )
        return n;
    return (unsigned long)((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
}
int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu",n,fiboNum);
    return 0;
}

列表法

如果需要求解的斐波那契数列的第n个在有限范围内，那么完全可以将已知的斐波那契数列存储起来，在需要的时候读取即可，时间复杂度可以为O(1)。