題目要求
求斐波那契數(shù)列的第n項。
題目解析
思路一：
- 分析
斐波那契數(shù)列的第n項的計算過程是一個標(biāo)準(zhǔn)的遞歸 。
- 代碼段
public static int getValue(int n) throws Exception {
if(n < 0) {
throw new Exception("輸入?yún)?shù)小于0 ，不合法的輸入") ;
}
if(n <= 1) {
return (n==1) ? 1: 0 ;
}
return getValue( n-1 ) + getValue( n-2 ) ;
}
思路二：
- 分析
斐波那契數(shù)列的第n項的計算過程是一個標(biāo)準(zhǔn)的遞歸 ， 但是由于遞歸對內(nèi)存的需求非常大，所以我們要進行以下優(yōu)化。新建一個數(shù)組對計算結(jié)果進行存儲，下次計算式，先在數(shù)組中進行查詢，若不存在再進行計算。
- 代碼段
public static int getValue1(int n) throws Exception {
if(n < 0) {
throw new Exception("輸入?yún)?shù)小于0 ，不合法的輸入") ;
}
if(n <= 1) {
return (n==1) ? 1: 0 ;
}
if(result.get(n)!=null) {
return result.get(n) ;
}else {
result.put(n, getValue( n-1 ) + getValue( n-2 )) ;
}
return result.get(n) ;
}
測試代碼
public static void main(String[] args) {
try {
System.out.println("未優(yōu)化");
long curTime = System.nanoTime() ;
System.out.println(getValue(5));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("優(yōu)化");
curTime = System.nanoTime() ;
System.out.println(getValue1(5));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("未優(yōu)化");
curTime = System.nanoTime() ;
System.out.println(getValue(30));
System.out.println(System.nanoTime() - curTime);
System.out.println("-----------------------------------");
System.out.println("優(yōu)化");
curTime = System.nanoTime() ;
System.out.println(getValue1(30));
System.out.println(System.nanoTime() - curTime);
System.out.println(getValue1(-1));
} catch (Exception e) {
e.printStackTrace();
}
}
運行結(jié)果
未優(yōu)化
5
51786
優(yōu)化
5
176816
未優(yōu)化
832040
10688252
優(yōu)化
832040
8065874
java.lang.Exception: 輸入?yún)?shù)小于0 ，不合法的輸入
at 斐波那契數(shù)列.Demo.getValue1(Demo.java:41)
at 斐波那契數(shù)列.Demo.main(Demo.java:91)
題目擴展：
青蛙跳臺階問題：
- 題目要求：
一只青蛙一次可以跳一個臺階，也可以跳兩個臺階，求該青蛙要跳上n跳臺階有多少種方法。 - 題目分析：
首先我們考慮最簡單的情況，當(dāng)只有一階臺階時，只有一種情況，有兩階臺階時，有兩種情況，第一次跳一階，第二次跳一階?；蛘咭淮翁鴥呻A。然后我們來看當(dāng)有n階臺階時，假設(shè)一共有f(n)種情況，那么第一次跳有兩種選擇，跳一階，那么剩下的臺階的情況數(shù)量則為f(n-1)種。如果第一次跳兩階，那么剩下的階數(shù)的情況就是f(n-2)。這個時候我們就可以簡單的看出它就是一個斐波那契數(shù)列問題。
擺方塊兒問題
有一個28的大方框和一個21的小方框，同樣的我們可以吧第一次放的條件分類。如果把第一塊橫著放，那么下面的那個也必須橫著放，也就是不確定的是剩下的26，如果第一塊豎著放，那么我們不能確定的就是剩下的27。并且當(dāng)只有21的方格時只有一種方法，只有22方格時，只有兩種方法。那我們可以將問題轉(zhuǎn)化為斐波那契數(shù)列，解決問題。
青蛙跳臺階問題再擴展
- 題目要求：
一只青蛙一次可以跳1-n個臺階。求該青蛙要跳上n跳臺階有多少種方法。 - 題目分析：
已知：當(dāng)如上題條件。那么f(n) = f(1) + f(2) + ...... + f(n-1) + 1;
且：
f(n) = f(1) + f(2) + ...... + f(n-1) + 1 ;
f(n - 1 ) = f(1) + f(2) + ...... + f(n-2) + 1 ;
f(n) = 2 f(n-1) ;
那么可以得出f(n) = 2^(n-1)
