public class Main {
/* 0 1 2 3 4 5
* 0 1 1 2 3 5 8 13 ...
* *
*/
public static int fib1(int n) {
// 方法一:递归法
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
public static int fib2(int n) {
// 方法二: 记忆化搜索
int[] memo = new int[n+1]; // 自定义数组的默认值都为0
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// 当数组的值为0时,才进行迭代
if (memo[n] == 0) {
memo[n] = fib1(n-1) + fib1(n-2);
}
return memo[n];
}
public static int fib3(int n) {
// 方法三: 数组自下而上的思考方式
int[] memo = new int[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
memo[i] = memo[i - 2] + memo[i - 1];
}
return memo[n];
}
public static int fib4(int n) {
// 方法四:自下而上法
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
public static void main(String[] args) {
System.out.println("四种实现斐波那契数列的方法");
System.out.println(fib1(5));
System.out.println(fib2(5));
System.out.println(fib3(5));
System.out.println(fib4(5));
}
}
网友评论