斐波那契数列
编程实现费式数列中第 n 项的数值并返回。
费式数列:1 1 2 3 5 8 13 21
分析规律
- 第 1 项和第 2 项固定为 1。
- 从第 3 项起每一个数值是前两项的和。
递归实现
递归实现会影响程序的执行性能 不推荐使用
public int recursion(int n) { // int n = 5; int n = 4; int n = 3; int n = 2; n = 1;
// 当 n == 1 或 n == 2 时返回 1
if (n == 1 || n == 2) {
return 1;
}
// 否则是前两者的和
return recursion(n - 1) + recursion(n - 2);
// 分析执行
// recursion(5) => return recursion(4)+ recursion(3); => 5
// recursion(4) => return recursion(3)+ recursion(2); => 3
// recursion(3) => return recursion(2)+ recursion(1); => 2
// recursion(2) => return 1; => 1
// recursion(1) => return 1; => 1
}
public static void main(String[] args) {
MathSeries series = new MathSeries();
int num = series.seriesRecursion(40);
System.out.println(num);
}
递推实现
public int seriesFor(int n) {
// 当 n == 1 或 n == 2 时返回 1
if (n == 1 || n == 2) {
return 1;
}
int ia = 1; // 前 2 项
int ib = 1; // 前 1 项
// 从第 3 项开始计算
for (int i = 3; i <= n; i++) {
int result = ia + ib; // 前两者的和
ia = ib; // 将前第 1 项移至 2 项
ib = result; // 将第一项设为前两项的和
}
return ib;
}
public static void main(String[] args) {
MathSeries series = new MathSeries();
int num = series.seriesFor(10);
System.out.println(num);
}