一、問題描述
要求輸入一個整數n,請你輸出斐波那契數列的第n項
二、算法分析
給出一系列斐波拉契數列:0 1 1 3 5 8 13 21 。。。
通過觀察,很容易發現:
1 n=0,1
f(n) = f(n-1)+f(n-2) n>1
三、算法設計
遞歸法:根據遞歸公式實作遞歸函數
缺點:遞歸過程中會包含很多重複的運算,是以效率不高
疊代法:疊代的思想就是不斷地用變量的舊值遞推新值的過程。疊代法相對于遞歸效率要高,因為節省了重複計算
四、編碼實作
(1)遞歸法
public int Fibonacci(int n) {
if(n<=1)
return n;
else
return Fibonacci(n-1)+Fibonacci(n-2);
}
(2)疊代法
public int Fibonacci1(int n){
int f0 = 0;
int f1 = 1;
int currentNum=0;
if(n<=1){
return n;
}
for(int i=2; i<=n;i++){
currentNum = f0 + f1;
f0 = f1;
f1 = currentNum;
}
return currentNum;
}