斐波那契数列

  1 //计算斐波那契数列 f(n) 
  2 
  3 #include <iostream>
  4 #include <cmath> 
  5 using namespace std;
  6 
  7 long fib1(int n){
  8     /*递归程序1：这种是最原始的想法，这样的做法会重复调用，做很多无用的工作。下面是优化的几种方法 */
  9           if (n <= 2){
 10               return 1;
 11           }
 12           else{
 13               return fib1(n-1) + fib1(n-2);
 14           }
 15 }
 16 
 17 long fib(int n, long a, long b, int count){
 18      if (count == n)
 19          return b;
 20      return fib(n, b, a+b, ++count);
 21 }
 22  
 23 long fib2(int n){
 24     /* 递归程序2：这种递归的写法比fib1进步了不少，它略过了很多fib1中重复计算的部分。
 25     但是递归写法，时间复杂度依然很高，近似为线性时间O(n)，但比起下面的迭代循环仍然没有优势 */ 
 26      return fib(n, 0, 1, 1);
 27 }
 28 
 29 
 30 long fib3 (int n){
 31     /* 迭代解法：这里算法复杂度显然为O(n) ，
 32     这个解法目前来看是最好的解法，算法既不复杂，而且在时间复杂度和空间复杂度上都有保证  */ 
 33      long x = 0, y = 1;
 34      for (int j = 1; j < n; j++){
 35          y = x + y;
 36          x = y - x;
 37      }
 38      return y;
 39 }
 40 
 41 /* 这里也可以将每次计算的结果存储下来，这就是大名鼎鼎的以“空间换时间”，下面就是用空间换时间的程序   
 42 
 43 long fib3(int n){
 44     if(n==0) return 0;
 45     long data[n];
 46     data[0]=0,data[1]=1;
 47     for(int i=2;i<=n;i++){
 48         data[i]=data[i-1]+data[i-2];
 49     }
 50     return data[n];
 51 }
 52 
 53 */
 54 
 55 class Matrix{
 56 public:
 57        long matr[2][2];
 58        Matrix(const Matrix&rhs);
 59        Matrix(long a, long b, long c, long d);
 60        Matrix& operator=(const Matrix&);
 61        
 62        friend Matrix operator*(const Matrix& lhs, const Matrix& rhs){
 63               Matrix ret(0,0,0,0);
 64               ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];
 65               ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];
 66               ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];
 67               ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];
 68               return ret;
 69        }
 70 };
 71 
 72 Matrix::Matrix(long a, long b, long c, long d){
 73        this->matr[0][0] = a;
 74        this->matr[0][1] = b;
 75        this->matr[1][0] = c;
 76        this->matr[1][1] = d;
 77 }
 78 
 79 Matrix::Matrix(const Matrix &rhs){
 80        this->matr[0][0] = rhs.matr[0][0];
 81        this->matr[0][1] = rhs.matr[0][1];
 82        this->matr[1][0] = rhs.matr[1][0];
 83        this->matr[1][1] = rhs.matr[1][1];
 84 }
 85 
 86 Matrix& Matrix::operator =(const Matrix &rhs){
 87        this->matr[0][0] = rhs.matr[0][0];
 88        this->matr[0][1] = rhs.matr[0][1];
 89        this->matr[1][0] = rhs.matr[1][0];
 90        this->matr[1][1] = rhs.matr[1][1];
 91        return *this;
 92 }
 93  
 94 Matrix power(const Matrix& m, int n){
 95        if (n == 1)
 96               return m;
 97        if (n%2 == 0)
 98               return power(m*m, n/2);
 99        else
100               return power(m*m, n/2) * m;
101 }
102 
103 long fib4 (int n){
104     /* 矩阵乘法：二分法进一步优化程序，时间复杂度为O(log(n))   */ 
105        Matrix matrix0(1, 1, 1, 0);
106        matrix0 = power(matrix0, n-1);
107        return matrix0.matr[0][0];
108 }
109 
110 long fib5(int n){
111     /* 公式法：终极必杀，直接套用表达式求解，时间复杂度为O(1).
112     不过有瑕疵的一点就是受制于库函数实现开方和乘方的效率,具体时间复杂度上考虑到上一点，估计也是 O(log(n)) */
113      double z = sqrt(5.0);
114      double x = (1 + z)/2;
115      double y = (1 - z)/2;
116      return (pow(x, n) - pow(y, n))/z + 0.5;
117 }
118 
119 int main(){
120      cout << fib1(45) << endl;
121      cout << fib2(45) << endl;
122      cout << fib3(45) << endl;
123      cout << fib4(45) << endl;
124      cout << fib5(45) << endl;
125      return 0;
126 }