Java 斐波那契数列的编程实现

发表于 更新于 分类于 阅读次数： 本文字数： 301 阅读时长 ≈ 1 分钟

斐波那契数列

编程实现费式数列中第 n 项的数值并返回。
费式数列：1 1 2 3 5 8 13 21

分析规律

  1. 第 1 项和第 2 项固定为 1。
  2. 从第 3 项起每一个数值是前两项的和。

递归实现

递归实现会影响程序的执行性能 不推荐使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}

递推实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 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);
   }