斐波纳契数列的一次优化

斐波纳契数列（Fibonacci Sequence），又被称为波拿契数、斐波那契数列、费氏数列、黄金分割数列。指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：

因为数列构造并不复杂，用普通的初等代数就能够解题~但是今天Xushine研究院来用矩阵的方法处理斐波那契额数列，因为这样解题的效率会比较高O（logn），比初等代数方法还是优化了不少~

首先看一下我们一般的程序：
#include<iostream>
 #include<string>
 using namespace std;
 
 long Fibonacci(unsigned int n)
 {
     if(n == 0)
         return 0;
     else if(n == 1)
         return 1;
     else
         return Fibonacci(n-1) + Fibonacci(n-2);
 }
 
 int main()
 {
     cout<<“Enter an N:”<<endl;
     unsigned int number=0;
     cin>>number;
     cout<<Fibonacci(number)<<endl;
     return 0;
 }
上面的程序为最普通的写法，这个时候我们会发现在递归的过程中而计算重复值的数量随着N值而急剧增大，事实上该算法的时间复杂度随着n值呈指数增长。如果我们取N=100这个时候递程序基本上已经处于崩溃的边缘了~

下面我们来看看用Xushine研究院推荐的方法处理这个数列：
首先我们看下推导的过程：

我们先构建一个矩阵方程

然后我们用数学归纳法：

Step1: n=2时

Step2：设n=k时，公式成立，则有：

等式两边同乘以[1,1;1,0]矩阵可得：

左边=右边，所以当n=k+1时等式成立，所以假设成立。

由此可以知道该问题转化为计算右边矩阵的n-1幂问题。

我们直接用分治的算法思想可以求一个数A的幂。

这样我们就能写出优化后的代码了：
#include<iostream>
 #include<string>
 using namespace std;
 
 //定义2×2矩阵；
 struct Matrix2by2
 {
         Matrix2by2
     (
         long m_00,
         long m_01,
         long m_10,
         long m_11
     )
     :m00(m_00),m01(m_01),m10(m_10),m11(m_11)
     {
     }
 
     long m00;
     long m01;
     long m10;
     long m11;
 };
 
 //定义2×2矩阵的乘法运算
 Matrix2by2 MatrixMultiply(const Matrix2by2& matrix1,const Matrix2by2& matrix2)
 {
     Matrix2by2 matrix12(1,1,1,0);
     matrix12.m00 = matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10;
     matrix12.m01 = matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11;
     matrix12.m10 = matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10;
     matrix12.m11 = matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11;
     return matrix12;
 
 }
 
 
 //定义2×2矩阵的幂运算
 Matrix2by2 MatrixPower(unsigned int n)
 {
     Matrix2by2 matrix(1,1,1,0);
     if(n == 1)
     {
         matrix = Matrix2by2(1,1,1,0);
     }
     else if(n % 2 == 0)
     {
         matrix = MatrixPower(n / 2);
         matrix = MatrixMultiply(matrix, matrix);
     }
     else if(n % 2 == 1)
     {
         matrix = MatrixPower((n-1) / 2);
         matrix = MatrixMultiply(matrix, matrix);
         matrix = MatrixMultiply(matrix, Matrix2by2(1,1,1,0));
     }
     return matrix;
 }
 //计算Fibnacci的第n项
 long Fibonacci(unsigned int n)
 {
     if(n == 0)
         return 0;
     if(n == 1)
         return 1;
 
     Matrix2by2 fibMatrix = MatrixPower(n-1);
     return fibMatrix.m00;
    
 }
 
 int main()
 {
     cout<<“Enter A Number:”<<endl;
     unsigned int number;
     cin>>number;
     cout<<Fibonacci(number)<<endl;
     return 0;
 }