您的位置: 首页  >  IT文章  >  编程之美之斐波那契数列

编程之美之斐波那契数列

分类: IT文章 • 2023-03-11 19:17:39

【背景】

编程之美之斐波那契数列

编程之美之斐波那契数列

【思路1-递归】

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. int Fibonacci(int n){  
  2.         if(n <= 2){  
  3.             return n;  
  4.         }  
  5.         return Fibonacci(n - 1) + Fibonacci(n - 2);  
  6.     }  


进一步优化：

当n增大到一定数值，Fibonacci数列值会溢出，并且花费时间很长。

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. long long Fibonacci(int n){  
  2.         if(n <= 2){  
  3.             return n;  
  4.         }  
  5.         return Fibonacci(n - 1) + Fibonacci(n - 2);  
  6.     }  


编程之美之斐波那契数列

编程之美之斐波那契数列

【思路2-递推关系式的优化】

编程之美之斐波那契数列

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. long long Fibonacci(int n){  
  2.         long long* Fibonacci = (long long*)malloc(sizeof(long long)*(n+1));  
  3.         Fibonacci[0] = 0;  
  4.         Fibonacci[1] = 1;  
  5.         for(int i = 2;i <= n;i++){  
  6.             Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];  
  7.         }  
  8.         return Fibonacci[n];  
  9.     }  


该思路的另一种实现方法：

编程之美之斐波那契数列

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. long long  Fibonacci(int n){  
  2.         int i;  
  3.         long long fibonacciA = 0;  
  4.         long long fibonacciB = 1;  
  5.         long long fibonacciC;  
  6.         if(n == 0){  
  7.             return 0;  
  8.         }  
  9.         else if(n == 1){  
  10.             return 1;  
  11.         }  
  12.         for(i = 2;i <= n;i++){  
  13.             fibonacciC = fibonacciA + fibonacciB;  
  14.             fibonacciA = fibonacciB;  
  15.             fibonacciB = fibonacciC;  
  16.         }  
  17.         return fibonacciC;  
  18.     }  

【思路3-求解通项公式】

编程之美之斐波那契数列

编程之美之斐波那契数列

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. int Fibonacci(int n) {  
  2.         double s = sqrt(5);  
  3.         // floor 返回小于或者等于指定表达式的最大整数  
  4.         return floor((pow((1+s)/2, n) - pow((1-s)/2, n))/s + 0.5);  
  5.     }  


当n增大到一定数值，Fibonacci数列值会溢出。因为floor返回小于或者等于指定表达式的最大整数

【思路4-分支策略】

编程之美之斐波那契数列

编程之美之斐波那契数列

[cpp] view plaincopy编程之美之斐波那契数列编程之美之斐波那契数列
 
  1. #include <iostream>  
  2. #include <malloc.h>  
  3. #include <stdio.h>  
  4. using namespace std;  
  5. //矩阵乘法  
  6. void MatrixMulti(long long matrix[2][2],long long matrix2[2][2]){  
  7.     long long a = matrix[0][0] * matrix2[0][0] +  matrix[0][1] * matrix2[1][0];  
  8.     long long b = matrix[0][0] * matrix2[0][1] +  matrix[0][1] * matrix2[1][1];  
  9.     long long c = matrix[1][0] * matrix2[0][0] +  matrix[1][1] * matrix2[1][0];  
  10.     long long d = matrix[1][0] * matrix2[0][1] +  matrix[1][1] * matrix2[1][1];  
  11.     matrix[0][0] = a;  
  12.     matrix[0][1] = b;  
  13.     matrix[1][0] = c;  
  14.     matrix[1][1] = d;  
  15. }  
  16. //Fibonacci数列  
  17. long long Fibonacci(int value){  
  18.     if(value == 0){  
  19.         return 0;  
  20.     }  
  21.     long long A[2][2] = {1,1,1,0};  
  22.     //初试为单位矩阵  
  23.     long long Matrix[2][2] = {1,0,1,0};  
  24.     int n = value - 1;  
  25.     for(; n ;n >>= 1){  
  26.         //奇偶  
  27.         if(n&1){  
  28.             MatrixMulti(Matrix,A);  
  29.         }//if  
  30.         MatrixMulti(A,A);  
  31.     }//for  
  32.     return Matrix[0][0];  
  33. }  
  34.   
  35. int main() {  
  36.     int i,n,height;  
  37.     while(scanf("%d",&n) != EOF){  
  38.         long long result;  
  39.         for(i = 0;i <= n;i++){  
  40.             result = Fibonacci(i);  
  41.             printf("%lld ",result);  
  42.         }//for  
  43.     }//while  
  44.     return 0;  
  45. }  

该思路另一种解析：

编程之美之斐波那契数列

编程之美之斐波那契数列

编程之美之斐波那契数列

编程之美之斐波那契数列

编程之美之斐波那契数列

相关推荐