斐波那契数列的优化算法C++

#includeiostream#includecmathusingnamespacestd;/////////////////////////////////////////////////////////////////////////A2by2matrix///////////////////////////////////////////////////////////////////////structMatrix2By2{Matrix2By2(longlongm00=0,longlongm01=0,longlongm10=0,longlongm11=0):m_00(m00),m_01(m01),m_10(m10),m_11(m11){}longlongm_00;longlongm_01;longlongm_10;longlongm_11;};/////////////////////////////////////////////////////////////////////////Multiplytwomatrices//Input:matrix1-thefirstmatrix//matrix2-thesecondmatrix//Output:theproductionoftwomatrices///////////////////////////////////////////////////////////////////////Matrix2By2MatrixMultiply(constMatrix2By2&matrix1,constMatrix2By2&matrix2){returnMatrix2By2(matrix1.m_00*matrix2.m_00+matrix1.m_01*matrix2.m_10,matrix1.m_00*matrix2.m_01+matrix1.m_01*matrix2.m_11,matrix1.m_10*matrix2.m_00+matrix1.m_11*matrix2.m_10,matrix1.m_10*matrix2.m_01+matrix1.m_11*matrix2.m_11);}/////////////////////////////////////////////////////////////////////////Thenthpowerofmatrix//11//10///////////////////////////////////////////////////////////////////////Matrix2By2MatrixPower(unsignedintn){assert(n0);Matrix2By2matrix;if(n==1){matrix=Matrix2By2(1,1,1,0);}elseif(n%2==0){matrix=MatrixPower(n/2);matrix=MatrixMultiply(matrix,matrix);}elseif(n%2==1){matrix=MatrixPower((n-1)/2);matrix=MatrixMultiply(matrix,matrix);matrix=MatrixMultiply(matrix,Matrix2By2(1,1,1,0));}returnmatrix;}/////////////////////////////////////////////////////////////////////////CalculatethenthitemofFibonacciSeriesusingdevideandconquer///////////////////////////////////////////////////////////////////////longlongFibonacci_Solution3(unsignedintn){intresult[2]={0,1};if(n2)returnresult[n];Matrix2By2PowerNMinus2=MatrixPower(n-1);returnPowerNMinus2.m_00;}