斐波那契數(shù)列，其最開始的幾項是0、1、1、2、3、5、8、13、21、34…… ，后面的每一項是前兩項之和，事實上，斐波那契在數(shù)學上有自己的嚴格遞歸定義。
f0 = 0
f1 = 1
f(n) = f(n-1) + f(n-2)
斐波那契數(shù)列其實有很多有趣的性質，比如你拿斐波那契里每項數(shù)為半徑繪制1/4圓弧，你就會得到著名的黃金螺旋線。
上圖只是繪制到了10多項，如果繼續(xù)繪制，會變成下面這樣。。
另外斐波那契數(shù)還有一個神奇的性質，f(n-1)/f(n)約等于黃金分割比例，n越大，其越接近黃金分割比0.6180339887…… 。
扯遠了，回到今天的正題，如何求斐波那契數(shù)列第n項，如果作為面試題的話，也可以考察候選人很多方面，比如遞歸、優(yōu)化、數(shù)學…… 當然現(xiàn)在大廠面試時很大可能也不會直接出斐波那契了，而是可能出現(xiàn)其變形，文末會給出幾個相關參考題。
求解斐波那契數(shù)列第n項有很多種方式
遞歸求解
根據(jù)其遞歸定義，我們很容易寫出以下遞歸函數(shù)來計算斐波那契第n項。
private static long fibonacci(int n) {
if (n == 0) {
return 0L;
}
if (n == 1) {
return 1L;
}
return fibonacci(n-1) + fibonacci(n-2);
}
雖然按其數(shù)學定義來看，代碼是沒問題，但這種實現(xiàn)效率非常低，存在著大量的重復計算，不信你用你自己電腦執(zhí)行下fibonacci(30) 試試！ 哦，對了，如果面試官讓你分析下上述代碼的時間復雜度，你會分析嗎？？
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
像上圖中，fib(3) fib(2) 被重復計算多次，實際上對于任意n，其n-2節(jié)點都會出現(xiàn)在其左右子樹中。大致看起來遞歸求斐波那契數(shù)列的時間復雜度為O(2^n)，這個也不是精確上界，精確證明見遞歸求解斐波那契數(shù)列的時間復雜度——幾種簡潔證明
當然遞歸版本也有有方法優(yōu)化的，我們之前打ACM的時候有種方法叫做記憶化搜索，其本質上就是把計算結果緩存下來，下次用的時候就直接取，而不是重復計算，這樣可以避免上述代碼中大量的重復計算，可以將其時間復雜度從O(2^n) 降至 O(n)。針對上面代碼的改動也很簡單，你可以自己試試（提示：就是加個全局數(shù)組保證下結果）。
遞推求解
我們在解決問題的時候，逆向思維也很重要，逆向思維往往能找到更高效直接的解決方案。上述遞歸的方式其實是從后往前計算，事實上我們可以從前往后計算。居然我們已知f0和f1，那我們就可以算出f2，緊接著算出f3 f4，一直到fn。
private static long fibonacci(int n) {
long[] fb = new long[n+1];
fb[1] = 1;
for (int i = 2; i <= n; i++) {
fb[i] = fb[i-1] + fb[i-2];
}
return fb[n];
}
不過上述代碼依舊有優(yōu)化空間。我們計算fb[i]只需要fb[i-1]和fb[i-2]兩項即可，是不是0到i-3都白存了！其實只需要保存長度為2的滑動窗口即可，優(yōu)化后代碼如下：
private static long fibonacci(int n) {
if (n < 2) {
return n;
}
long fa = 0L;
long fb = 1L;
long fc = fa + fb;
for (int i = 2; i < n; i++) {
fc = fa + fb;
fa = fb;
fb = fc;
}
return fc;
}
比內公式
其實斐波那契第n項是有計算公式的，稱為比內公式，如下：
在維基百科Fibonacci number上有嚴格的證明過程，有興趣可以參考下。但這個公式其實并不適合計算機來計算。首先，根號5是個無理浮點數(shù)，眾所周知當今的計算機在處理浮點數(shù)時是有精度損失的，另外計算機計算浮點數(shù)的速度也比較慢。當然，你也別惦記著把這個公式背下來，你面試過程中不一定能想起來這個，當然如果你是數(shù)學大牛的話，你可以參考下推導過程，直接在面試現(xiàn)場把結論推導出來，肯定能唬住大部分面試官的。
矩陣冪運算
上面已經(jīng)說了比內公式有低效和精度損失的問題，我這里當然有更牛x的方案了，那就是借助矩陣的運算來解決，借助如下公式，我們可以計算出斐波那契的第n項。
如果再進一步，公式可以化簡為：
具體推導過程見維基百科Fibonacci number，當然這里我直接用octave驗證過了，毫無問題。
>>fb = [1,1;1,0]
fb =
1 1
1 0
>>fb^10
ans =
89 55
55 34
>>fb^30
ans =
1346269 832040
832040 514229
小學三年級的時候我們學過求n次方的快速冪算法，可以把求n次方的時間復雜度從O(n)降低到O(log(n))，對于矩陣我們當然也可以用快速冪算法(不知道快速冪的同學可以去復習下了)。
// 快速求矩陣的n次方
private static long[][] pow(long[][] matrix, int n) {
if (n == 1) {
return matrix;
}
long[][] res = pow(matrix, n/2);
res = multi(res, res);
if (n%2 == 1) {
res = multi(res, matrix);
}
return res;
}
// 兩個矩陣相乘
private static long[][] multi(long[][] m1, long[][] m2) {
long[][] res = new long[2][2];
res[0][0] = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
res[0][1] = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
res[1][0] = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
res[1][1] = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];
return res;
}
public static void main(String[] args) {
long[][] fb = {{1,1},{1,0}};
long[][] res = pow(fb, 10);
System.out.println(res[0][1]);
}
上述幾種解法把時間復雜度從O(2^n)降低到了O(log(n))，實際上還有O(1)的解法。斐波那契數(shù)列其實是一個增長很快的數(shù)列，n用不了多大就會超過int甚至long所能表示的范圍(n大概幾十就會溢出)，所以可以直接存下來，用的時候直接取，用空間換時間，從而達到O(1)的時間復雜度。
面試題擴展
求斐波那契第n項雖然看起來很基礎，但它也有著很高級的解法，平凡中蘊藏著不凡。事實上，你現(xiàn)在出去面試，大概率不會遇到面試官直接問你斐波那契，而是其變形題或是和其他內容融合的題，比如：
- 你每次可以上1級臺階，或者2級臺階，問：上到第n級臺階總共有多少種不同的路徑？
- fib(i)對應的是斐波那契的第i項，找到所有第fin(i)個素數(shù)(i<=20)，比如fib(20)是6765，第6765個素數(shù)是67931。
歡迎關注我的面試專欄面試題精選，永久免費 持續(xù)更新，本專欄會收集我遇到的比較經(jīng)典面試題，除了提供詳盡的解法外還會從面試官的角度提供擴展題，希望能幫助大家找到更好的工作。另外，也征集面試題，如果你遇到了不會的題 私信告訴我，有價值的題我會給你出一篇博客。
本文來自https://blog.csdn.net/xindoo
