斐波那契數列，其最開始的幾項是0、1、1、2、3、5、8、13、21、34…… ，后面的每一項是前兩項之和，事實上，斐波那契在數學上有自己的嚴格遞回定義，
f0 = 0
f1 = 1
f(n) = f(n-1) + f(n-2)
斐波那契數列其實有很多有趣的性質，比如你拿斐波那契里每項數為半徑繪制1/4圓弧，你就會得到著名的黃金螺旋線，
上圖只是繪制到了10多項，如果繼續繪制，會變成下面這樣，，
另外斐波那契數還有一個神奇的性質，f(n-1)/f(n)約等于黃金分割比例，n越大，其越接近黃金分割比0.6180339887…… ，
扯遠了，回到今天的正題，如何求斐波那契數列第n項，如果作為面試題的話，也可以考察候選人很多方面，比如遞回、優化、數學…… 當然現在大廠面試時很大可能也不會直接出斐波那契了，而是可能出現其變形，文末會給出幾個相關參考題，
求解斐波那契數列第n項有很多種方式
遞回求解
根據其遞回定義，我們很容易寫出以下遞回函式來計算斐波那契第n項，
private static long fibonacci(int n) {
if (n == 0) {
return 0L;
}
if (n == 1) {
return 1L;
}
return fibonacci(n-1) + fibonacci(n-2);
}
雖然按其數學定義來看，代碼是沒問題，但這種實作效率非常低，存在著大量的重復計算，不信你用你自己電腦執行下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節點都會出現在其左右子樹中，大致看起來遞回求斐波那契數列的時間復雜度為O(2^n)，這個也不是精確上界，精確證明見遞回求解斐波那契數列的時間復雜度——幾種簡潔證明
當然遞回版本也有有方法優化的，我們之前打ACM的時候有種方法叫做記憶化搜索，其本質上就是把計算結果快取下來，下次用的時候就直接取，而不是重復計算，這樣可以避免上述代碼中大量的重復計算，可以將其時間復雜度從O(2^n) 降至 O(n)，針對上面代碼的改動也很簡單，你可以自己試試（提示：就是加個全域陣列保證下結果），
遞推求解
我們在解決問題的時候，逆向思維也很重要，逆向思維往往能找到更高效直接的解決方案，上述遞回的方式其實是從后往前計算，事實上我們可以從前往后計算，居然我們已知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];
}
不過上述代碼依舊有優化空間，我們計算fb[i]只需要fb[i-1]和fb[i-2]兩項即可，是不是0到i-3都白存了！其實只需要保存長度為2的滑動視窗即可，優化后代碼如下：
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是個無理浮點數，眾所周知當今的計算機在處理浮點數時是有精度損失的，另外計算機計算浮點數的速度也比較慢，當然，你也別惦記著把這個公式背下來，你面試程序中不一定能想起來這個，當然如果你是數學大牛的話，你可以參考下推導程序，直接在面試現場把結論推匯出來，肯定能唬住大部分面試官的，
矩陣冪運算
上面已經說了比內公式有低效和精度損失的問題，我這里當然有更牛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)的解法，斐波那契數列其實是一個增長很快的數列，n用不了多大就會超過int甚至long所能表示的范圍(n大概幾十就會溢位)，所以可以直接存下來，用的時候直接取，用空間換時間，從而達到O(1)的時間復雜度，
面試題擴展
求斐波那契第n項雖然看起來很基礎，但它也有著很高級的解法，平凡中蘊藏著不凡，事實上，你現在出去面試，大概率不會遇到面試官直接問你斐波那契，而是其變形題或是和其他內容融合的題，比如：
- 你每次可以上1級臺階，或者2級臺階，問：上到第n級臺階總共有多少種不同的路徑？
- fib(i)對應的是斐波那契的第i項，找到所有第fin(i)個素數(i<=20)，比如fib(20)是6765，第6765個素數是67931，
歡迎關注我的面試專欄面試題精選，永久免費 持續更新，本專欄會收集我遇到的比較經典面試題，除了提供詳盡的解法外還會從面試官的角度提供擴展題，希望能幫助大家找到更好的作業，另外，也征集面試題，如果你遇到了不會的題 私信告訴我，有價值的題我會給你出一篇博客，
本文來自https://blog.csdn.net/xindoo
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/224921.html
標籤：Java
下一篇：Java 列印Excel作業表