大家都知道斐波那契數列，現在要求輸入一個整數 n，請你輸出斐波那契數列的第 n 項（從 0 開始，第 0 項為 0，第 1 項是 1）
首先給出斐波那契數列的定義
F(1) = 1，F(2) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 3，n ∈ N*）
解法一：遞回解法
不建議使用，如果出現大規模的測驗用例，會導致堆疊溢位
public class Solution {
public int Fibonacci(int n) {
if(n == 0) {
return 0;
}
if(n == 1 || n == 2) {
return 1;
}
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
}
解法二：非遞回解法
public class Solution {
public int Fibonacci(int n) {
// f(1) = 1
int preNum = 1;
// f(2) = 0
int prePreNum = 0;
// 保存每次運算的結果
int result = 0;
if(n == 0) {
return 0;
}
if(n == 1) {
return 1;
}
for(int i = 2; i <= n; i++) {
result = preNum + prePreNum;
prePreNum = preNum;
preNum = result;
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127912.html
標籤：其他
上一篇：python協程(yield、asyncio標準庫、gevent第三方)、異步的實作
下一篇：跳臺階