求解斐波那契数的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); //Perfect
printf("Res5:%d\n",res5);
return 0;
}谢谢大家指正！