算法

斐波那契数列

斐波那契数列解析

需求

  • 斐波那契数列 1、1、2、3、5、8、13、21、34、……

  • 算法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

package org.example;

public class fb1 {
    public static void main(String[] args) {
        System.out.println(test1(10));
    }

    public static int test1(int i) {
        if (i == 0) {
            return 0;
        }
        if (i == 1) {
            return 1;
        }
        return test1(i - 1) + test1(i - 2);
    }
}

  • 算法2：递归优化，增加一个空间
1
2
3
4
5
6
7
8
9
10
11
12
public static int test2(int[] arr, int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    if (arr[i - 1] != 0) return arr[i - 1];
    arr[i - 1] = test2(arr,i - 1) + test2(arr,i - 2);
    return arr[i - 1];
}

  • 算法3：双指针算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int test3(int i) {
    int pre = 0;
    int next = 1;
    int sum = 0;
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }

    for (int j = 2; j <= i; j++) {
        sum = pre + next;
        pre = next;
        next = sum;
    }
    return sum;

}