求解斐波那契数的5种方法

一、暴力递归法

由于斐波那契数列的递归定义，我们很容易可以写出一个递归的算法，F(n)=F(n-1)+F(n-2)。

//朴素方法int Simple_Fibonacci(int n){if(n<=0){return 0;//避免非法输入}if(n==1){return 1;}else{return Simple_Fibonacci(n-1) + Simple_Fibonacci(n-2);}}

由于该算法是递归定义的，当n变大时，高昂的指数次时间复杂度无法在有生之年完成计算。为了避免对重复数据的重复递归运算，引入一个备忘录，存放之前曾计算过的内容。

二、带备忘录的自顶向下的动态规划算法

借助一个备忘录p，存放之前已经计算过的内容，避免重复递归，减少时间复杂度。

//带备忘录的自顶向下法//借助带备忘的自顶向下法可以同时求解出一个fibonaci序列int Memoized_Fibonacci_Aux(int n,int *p);int Memoized_Fibonacci(int n){int p[n+1];for(int i=0;i<=n;i++){p[i] = -INF;}p[0]=0;p[1]=1;//底//保证已经初始化int res = Memoized_Fibonacci_Aux(n,p);for(int i=0;i<=n;i++){printf("%d ",p[i]);}putc('\n',stdout);return res;}int Memoized_Fibonacci_Aux(int n,int *p){if(n<0){return 0;//避免非法输入}if(p[n]>=0){return p[n];}else{int res1 = Memoized_Fibonacci_Aux(n-1,p);p[n-1] = res1;int res2 = Memoized_Fibonacci_Aux(n-2,p);p[n-2] = res2;p[n] = res1+res2;//存储已经完成过的数据return res1+res2;}}

三、自底向上的动态规划算法

和自顶向下的带备忘的动态规划算法相比，自底向上这种反人类的思考方式更加快速，从小到大，从底向上，依次构造最终的完整解。

//自底向上法int Bottom_fibonacci(int n){int p[n];p[0]=0;p[1]=1;//基for(int i=2;i<=n;i++){p[i] = p[i-1] + p[i-2];}for(int i=0;i<=n;i++){printf("%d ",p[i]);}putc('\n',stdout);return p[n];}

四、辅助矩阵的 快速 次方 法

leetcode斐波那契数列中的一个解法，利用辅助矩阵的n次方直接构造第n个斐波那契数列，这种思想十分巧妙，笔者用手算了一下，如果看不懂直接跑去看leetcode。

typedef struct{int data[2][2];}Matrix;/** 利用矩阵乘法的关系 构造辅助矩阵 利用矩阵的次方快速计算fibonacci数列*/Matrix matrix_pow(Matrix *m1,Matrix *m2);Matrix multi_matrix(Matrix m1,int n);int Fibonacci_quick_matrix(int n){if(n<=0){return 0;}if(n==1){return 1;}Matrix m1 = {1,1,1,0};Matrix buf = multi_matrix(m1,n);for(int i=0;i<2;i++){for(int j=0;j<2;j++){printf("%d ",buf.data[i][j]);}putchar('\n');}return buf.data[0][1];}Matrix matrix_pow(Matrix *m1,Matrix *m2){Matrix buf;for(int i=0;i<2;i++){for(int j=0;j<2;j++){buf.data[i][j] = m1->data[i][0]*m2->data[0][j] + m1->data[i][1]*m2->data[1][j];}}return buf;}//计算矩阵的次方 存储到buf中Matrix multi_matrix(Matrix m1,int n){Matrix buf={1,0,0,1};while(n>0){//借助位运算符号判断奇偶性if(n %2==1){buf = matrix_pow(&buf,&m1);for(int i=0;i<2;i++){for(int j=0;j<2;j++){printf("%d ",buf.data[i][j]);}putchar('\n');}}Matrix temp = m1;m1 = matrix_pow(&temp,&m1);n >>= 1;//右移}return buf;}

五、通项公式法

斐波那契数列的推导详情见《算法导论》，如下图所示：

/** 同时 fibonacci还可以使用通项公式求取*/int fib(int n) {double sqrt5 = sqrt(5);double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);return round(fibN / sqrt5);}

六、总结

总的C语言代码如下，直接运行即可。

#include <stdio.h>#include <math.h>#define INF 1000//求解fibonacci数列//朴素方法int Simple_Fibonacci(int n){if(n<=0){return 0;//避免非法输入}if(n==1){return 1;}else{return Simple_Fibonacci(n-1) + Simple_Fibonacci(n-2);}}//带备忘录的自顶向下法//借助带备忘的自顶向下法可以同时求解出一个fibonaci序列int Memoized_Fibonacci_Aux(int n,int *p);int Memoized_Fibonacci(int n){int p[n+1];for(int i=0;i<=n;i++){p[i] = -INF;}p[0]=0;p[1]=1;//底//保证已经初始化int res = Memoized_Fibonacci_Aux(n,p);for(int i=0;i<=n;i++){printf("%d ",p[i]);}putc('\n',stdout);return res;}int Memoized_Fibonacci_Aux(int n,int *p){if(n<0){return 0;//避免非法输入}if(p[n]>=0){return p[n];}else{int res1 = Memoized_Fibonacci_Aux(n-1,p);p[n-1] = res1;int res2 = Memoized_Fibonacci_Aux(n-2,p);p[n-2] = res2;p[n] = res1+res2;//存储已经完成过的数据return res1+res2;}}//自底向上法int Bottom_fibonacci(int n){int p[n];p[0]=0;p[1]=1;//基for(int i=2;i<=n;i++){p[i] = p[i-1] + p[i-2];}for(int i=0;i<=n;i++){printf("%d ",p[i]);}putc('\n',stdout);return p[n];}typedef struct{int data[2][2];}Matrix;/** 利用矩阵乘法的关系 构造辅助矩阵 利用矩阵的次方快速计算fibonacci数列*/Matrix matrix_pow(Matrix *m1,Matrix *m2);Matrix multi_matrix(Matrix m1,int n);int Fibonacci_quick_matrix(int n){if(n<=0){return 0;}if(n==1){return 1;}Matrix m1 = {1,1,1,0};Matrix buf = multi_matrix(m1,n);for(int i=0;i<2;i++){for(int j=0;j<2;j++){printf("%d ",buf.data[i][j]);}putchar('\n');}return buf.data[0][1];}Matrix matrix_pow(Matrix *m1,Matrix *m2){Matrix buf;for(int i=0;i<2;i++){for(int j=0;j<2;j++){buf.data[i][j] = m1->data[i][0]*m2->data[0][j] + m1->data[i][1]*m2->data[1][j];}}return buf;}//计算矩阵的次方 存储到buf中Matrix multi_matrix(Matrix m1,int n){Matrix buf={1,0,0,1};while(n>0){//借助位运算符号判断奇偶性if(n %2==1){buf = matrix_pow(&buf,&m1);for(int i=0;i<2;i++){for(int j=0;j<2;j++){printf("%d ",buf.data[i][j]);}putchar('\n');}}Matrix temp = m1;m1 = matrix_pow(&temp,&m1);n >>= 1;//右移}return buf;}/** 同时 fibonacci还可以使用通项公式求取*/int fib(int n) {double sqrt5 = sqrt(5);double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);return round(fibN / sqrt5);}int main(int argc, char *argv[]) {//数列是从0开始的int i = 10;int res = Memoized_Fibonacci(i);int res2 = Bottom_fibonacci(i);int res3 = Simple_Fibonacci(i);int res4 = Fibonacci_quick_matrix(i);int res5 = fib(i);printf("Res1:%d\n",res);printf("Res2:%d\n",res2);printf("Res3:%d\n",res3);printf("Res4:%d\n",res4); //Perfectprintf("Res5:%d\n",res5);return 0;}

谢谢大家指正！