=n-1
(注：表示乙個矩陣。在矩陣中第一行第一列是f(n+1)，第一行第二列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)
有了這個公式，要求得f(n)，我們只需要求得矩陣的n-1次方，因為矩陣的n-1次方的結果的第一行第一列就是f(n)。這個數學公式用數學歸納法不難證明。感興趣的朋友不妨自己證明一下。
現在的問題轉換為求矩陣的乘方。如果簡單第從0開始迴圈，n次方將需要n次運算，並不比前面的方法要快。但我們可以考慮乘方的如下性質：
/ an/2*an/2 n為偶數時
an=\ a(n-1)/2*a(n-1)/2 n為奇數時
要求得n次方，我們先求得n/2次方，再把n/2的結果平方一下。如果把求n次方的問題看成乙個大問題，把求n/2看成乙個較小的問題。這種把大問題分解成乙個或多個小問題的思路我們稱之為分治法。
這樣求n次方就只需要logn次運算了。
實現這種方式時，首先需要定義乙個2×2的矩陣，並且定義好矩陣的乘法以及乘方運算。當這些運算定義好了之後，剩下的事情就變得非常簡單。完整的實現**如下所示。
#include
// a 2 by 2 matrix
struct matrix2by2
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};// multiply two matrices
// input: matrix1 - the first matrix
// matrix2 - the second matrix
//output: the production of two matrices
matrix2by2 matrixmultiply
(const matrix2by2& matrix1,
const matrix2by2& matrix2
)// the nth power of matrix
// 1 1
// 1 0
matrix2by2 matrixpower(unsigned int n)
else if(n % 2 == 0)
else if(n % 2 == 1)
return matrix;
}// calculate the nth item of fibonacci series using devide and conquer
long long fibonacci_solution3(unsigned int n)
;if(n < 2)
return result[n];
matrix2by2 powernminus2 = matrixpower(n - 1);
return}
月薪三萬的一道面試題
小明和小強都是張老師的學生，張老師的生日是m月n日，2人都知道張老師的生日 是下列10組中的一天，張老師把m值告訴了小明，把n值告訴了小強，張老師問他們知道他的生日是那一天嗎？3月4日 3月5日 3月8日 6月4日 6月7日 9月1日 9月5日 12月1日 12月2日 12月8日 小明說 如果我不知...
一道銀監會面試題
2010國家公 銀監會面試真題解析題目 你新參加工作，領導交給你一項任務，要求寫乙份關於銀行監管的規章制度，沒有範本，沒有依照，你怎麼做?解析 本題屬於情景處理兼壓力型試題，重在考查考生面對壓力情景的實際處理能力，同時本題也從側面考查了考生的計畫組織協調能力。解題思路 由於本題具有專業部門的針對性，...
一道終身受用的面試題
為什麼不說服醫生救治老人，自己帶著夢中情人離開？醫生沒有工具就像戰士沒有槍一樣啊。你認為在那種地方有救助這個老人的條件嗎？我覺得這是乙個很好的題目，開拓了我們的思維，也考驗了乙個人的品質。這道題很受用，但在美國汽車只是乙個代步的普及工具，遠沒有其他來得重要，比如夢中情人。在美國人的角度，可能較容易回...