《劍指offer》里面的這道題對fibonacci的常見計算方法進行了改進

#include<iostream> using namespace std;long long Fibonacci_Solution1(unsigned int n) {if (n <= 0)return 0;if (n == 1)return 1;return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2); }// ====================方法2：循環==================== long long Fibonacci_Solution2(unsigned n) {int result[2] = { 0, 1 };if (n < 2)return result[n];long long fibNMinusOne = 1;long long fibNMinusTwo = 0;long long fibN = 0;for (unsigned int i = 2; i <= n; ++i){fibN = fibNMinusOne + fibNMinusTwo;//an=a(n-1)+a(n-2)fibNMinusTwo = fibNMinusOne;//注意這里的兩句之所以看起來有些奇怪，是因為我們手算的時候都是一輪計算兩個數，而這里的循環中一輪只計算1個數//這一句是an-1//fibNMinusOne = fibN;//an//以上兩句是為了下一輪計算a(n+1)來作準備的}return fibN; }// ====================方法3：基于矩陣乘法==================== #include <cassert>struct Matrix2By2 {Matrix2By2(long long m00 = 0,long long m01 = 0,long long m10 = 0,long long m11 = 0):m_00(m00), m_01(m01), m_10(m10), m_11(m11){}long long m_00;long long m_01;long long m_10;long long m_11; };Matrix2By2 MatrixMultiply (const Matrix2By2& matrix1,const Matrix2By2& matrix2 ) {return Matrix2By2(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); }Matrix2By2 MatrixPower(unsigned int n) {assert(n > 0);Matrix2By2 matrix;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; }long long Fibonacci_Solution3(unsigned int n) {int result[2] = { 0, 1 };if (n < 2)return result[n];Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);return PowerNMinus2.m_00; }// ====================測試代碼==================== void Test(int n, int expected) {if (Fibonacci_Solution1(n) == expected)printf("Test for %d in solution1 passed.\n", n);elseprintf("Test for %d in solution1 failed.\n", n);if (Fibonacci_Solution2(n) == expected)printf("Test for %d in solution2 passed.\n", n);elseprintf("Test for %d in solution2 failed.\n", n);if (Fibonacci_Solution3(n) == expected)printf("Test for %d in solution3 passed.\n", n);elseprintf("Test for %d in solution3 failed.\n", n); }int main() {Test(0, 0);Test(1, 1);Test(2, 1);Test(3, 2);Test(4, 3);Test(5, 5);Test(6, 8);Test(7, 13);Test(8, 21);Test(9, 34);Test(10, 55);Test(40, 102334155);return 0; }

總結

以上是生活随笔為你收集整理的09_Fibonacci的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。