- O(n)复杂度方法
- O(logn)复杂度方法
计算矩阵的n次方,可以先求矩阵的n/2次方,然后再平方即可。
1 #include <cassert> 2 3 struct Matrix2By2 4 { 5 Matrix2By2 6 ( 7 long long m00 = 0, 8 long long m01 = 0, 9 long long m10 = 0, 10 long long m11 = 0 11 ) 12 :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 13 { 14 } 15 16 long long m_00; 17 long long m_01; 18 long long m_10; 19 long long m_11; 20 }; 21 22 Matrix2By2 MatrixMultiply 23 ( 24 const Matrix2By2& matrix1, 25 const Matrix2By2& matrix2 26 ) 27 { 28 return Matrix2By2( 29 matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10, 30 matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11, 31 matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10, 32 matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11); 33 } 34 35 Matrix2By2 MatrixPower(unsigned int n) 36 { 37 assert(n > 0); 38 39 Matrix2By2 matrix; 40 if (n == 1) 41 { 42 matrix = Matrix2By2(1, 1, 1, 0); 43 } 44 else if (n % 2 == 0) 45 { 46 matrix = MatrixPower(n / 2); 47 matrix = MatrixMultiply(matrix, matrix); 48 } 49 else if (n % 2 == 1) 50 { 51 matrix = MatrixPower((n - 1) / 2); 52 matrix = MatrixMultiply(matrix, matrix); 53 matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0)); 54 } 55 56 return matrix; 57 } 58 59 long long Fibonacci_Solution3(unsigned int n) 60 { 61 int result[2] = { 0, 1 }; 62 if (n < 2) 63 return result[n]; 64 65 Matrix2By2 PowerNMinus2 = MatrixPower(n - 1); 66 return PowerNMinus2.m_00; 67 }View Code