程序員面試題-求Fibonacci數列[算法]
題目:定義Fibonacci數列如下:
/0n=0
f(n)= 1n=1
f(n-1)+f(n-2)n=2
輸入n,用最快的方法求該數列的第n項。
分析:在很多C語言教科書中講到遞歸函數的時候,都會用Fibonacci作為例子。因此很多程序員對這道題的遞歸解法非常熟悉,看到題目就能寫出如下的遞歸求解的代碼。
///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series recursively
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution1(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}
但是,教科書上反覆用這個題目來講解遞歸函數,並不能説明遞歸解法最適合這道題目。我們以求解f(10)作為例子來分析遞歸求解的過程。要求得f(10),需要求得f(9)和f(8)。同樣,要求得f(9),要先求得f(8)和f(7)……我們用樹形結構來表示這種依賴關係
f(10)
/
f(9)f(8)
//
f(8) f(7)f(7)f(6)
/ /
f(7) f(6)f(6) f(5)
我們不難發現在這棵樹中有很多結點會重複的,而且重複的結點數會隨着n的增大而急劇增加。這意味這計算量會隨着n的增大而急劇增大。事實上,用遞歸方法計算的時間複雜度是以n的指數的方式遞增的。大家可以求Fibonacci的第100項試試,感受一下這樣遞歸會慢到什麼程度。在我的'機器上,連續運行了一個多小時也沒有出來結果。
其實改進的方法並不複雜。上述方法之所以慢是因為重複的計算太多,只要避免重複計算就行了。比如我們可以把已經得到的數列中間項保存起來,如果下次需要計算的時候我們先查找一下,如果前面已經計算過了就不用再次計算了。
更簡單的辦法是從下往上計算,首先根據f(0)和f(1)算出f(2),在根據f(1)和f(2)算出f(3)……依此類推就可以算出第n項了。很容易理解,這種思路的時間複雜度是O(n)。
///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series iteratively
///////////////////////////////////////////////////////////////////////
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;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
這還不是最快的方法。下面介紹一種時間複雜度是O(logn)的方法。在介紹這種方法之前,先介紹一個數學公式:
{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1
(注:{f(n+1), f(n), f(n), f(n-1)}表示一個矩陣。在矩陣中第一行第一列是f(n+1),第一行第二列是f(n),第二行第一列是f(n),第二行第二列是f(n-1)。)
有了這個公式,要求得f(n),我們只需要求得矩陣{1, 1, 1,0}的n-1次方,因為矩陣{1, 1, 1,0}的n-1次方的結果的第一行第一列就是f(n)。這個數學公式用數學歸納法不難證明。感興趣的朋友不妨自己證明一下。
現在的問題轉換為求矩陣{1, 1, 1, 0}的乘方。如果簡單第從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
{
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;
};
///////////////////////////////////////////////////////////////////////
// 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
)
{
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);
}
///////////////////////////////////////////////////////////////////////
// The nth power of matrix
// 1 1
// 1 0
///////////////////////////////////////////////////////////////////////
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;
}
///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series using devide and conquer
///////////////////////////////////////////////////////////////////////
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;
}
相關文章
-
英語面試基本問答:Technical Qualifications
Technical QualificationsI: What certificates of technical qualifications have you received(obtained)?C: I've received an Accountant's Qualification Certificate. / I've received a Computer -
面試英語:Technical Qualifications 篇
Technical QualificationsI: What certificates of technical qualifications have you received(obtained)?C: I've received an Accountant's Qualification Certificate. / I've received a Computer -
Excel專家教你countif函數的使用方法-countif函數教程
導語:小編為幫助讓大家更好地瞭解、掌握Countif函數便用方法,現羅列一些實例如下,希望能夠幫助大家更好地使用Countif函數。一、求各種類型單元格的個數(1) 求真空單元格單個數: =COUNTIF(data,"=")(2) 真空+假空單元格 -
Jason Mraz & Colbie Caillat的Lucky樂評
Jason Mraz & Colbie Caillat演唱的歌曲《Lucky》,以輕快柔美的旋律和兩位演唱者動聽的聲音征服了嚴格的格萊美評委們,獲得了2010年第52屆格萊美最佳流行合作歌曲。下面就讓我們來看看相關樂評吧。Jason Mraz & -
酒店英語:抱怨服務Complaining about the Service
Why is my order taking so long?我點的菜為何這麼久?I’ll see if the chef has begun to cook the meal.我去看看廚師是不是已經幫你做了。I believe that there is an error on my bill.我的賬單有誤。Look what yo -
六年級《Chinatown in America》説課設計
教材分析:通過Daming給媽媽發送E-mail,介紹他在美國紐約的唐人街所看到的情景並能用There is a Chinatown in New York. We saw Chinese dancing. We ate in a Chinese restaurant.進行描述。學情分析:學生在之前的英語 -
英語面試問答:Reasons for Application
Reasons for ApplicationI: Why are you interested in workng with this company? / Why do you have(or take,feel)interest in applying to our firm? / Why are you desirous to get this job(post,position)?C: I& -
cappuccino什麼意思-釋義-雙語例句- cappuccino百科
cappuccino【釋義】英 [,kp'tin] 美 [,kpu'tino]n. 熱牛奶咖啡;(意)卡普齊諾咖啡n. (Cappuccino)人名;(意)卡普奇諾[ 複數 cappuccinos ]【短語】Lavender Cappuccino 熏衣草卡布奇諾 ; 薰衣草卡布奇諾Cappuc -
Unit 6 I like music that I can dance to評課稿範文
趙老師上的新目標英語9年級Unit 6 I like music that I can dance to SectionA 3a-4. Period 2公開課,聽了趙老師這節課,收穫頗多。趙老師老師這堂英語課,清晰實在、紮實系統、動靜結合,以新課程理念為指導,充分考慮了學生 -
面試英語:Reasons for Application
Reasons for ApplicationI: Why are you interested in workng with this company? / Why do you have(or take,feel)interest in applying to our firm? / Why are you desirous to get this job(post,position)?C: I&