大家都知道斐波那契数列，现在要求输入一个整数 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;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
