斐波那契数列是一组数字，除了第一个和第二个数字外，其他数字都是前两个数字之和：
0，1，1，2，3，5，8，13，21...
第一个斐波那契数的值是0，第四个斐波那契数的值是2。因此，要得到后续数列中任一斐波那契数n的值，可以使用下面的公式：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
一、递归
// 使用递归 int fib1(int n) { if (n < 2) { return n; } return fib1(n - 1) + fib1(n - 2); } //使用map记录 static Map<Integer, Integer> memo = new HashMap<>(Map.of(0, 0, 1, 1)); private static int fib2(int n) { if (!memo.containsKey(n)) { memo.put(n, fib2(n - 1) + fib2(n - 2)); } return memo.get(n); }
二、迭代
//使用迭代 // 递归是反向求解，而迭代是正向求解。有时递归是解决问题最直观的方法 // 然而，直观的递归解决方案也会带来巨大的性能成本。请记住，任何可以使用递归解决的问题也可以使用迭代来解决。 private static int fib3(int n) { int last = 0, next = 1; for (int i = 0; i < n; i++) { int oldLast = last; last = next; next = oldLast + next; } return last; }
三、流输入全部数列
// 使用流 private int last=0,next=1; public IntStream stream(){ return IntStream.generate(()->{ int oldLast = last; last = next; next = oldLast + next; return oldLast; }); }
四、测试
class AlgorithmEssenceApplicationTests { @Test // 0，1，1，2，3，5，8，13，21... void testFib() { System.out.println(fib1(5)); System.out.println(fib1(10)); System.out.println("---------"); System.out.println(fib2(5)); System.out.println(fib2(10)); System.out.println("---------"); System.out.println(fib3(5)); System.out.println(fib3(10)); System.out.println("---------"); new AlgorithmEssenceApplicationTests().stream().limit(5+1).forEachOrdered(System.out::println); System.out.println("---------"); new AlgorithmEssenceApplicationTests().stream().limit(10+1).forEachOrdered(System.out::println); } // 使用递归 int fib1(int n) { if (n < 2) { return n; } return fib1(n - 1) + fib1(n - 2); } //使用map记录 static Map<Integer, Integer> memo = new HashMap<>(Map.of(0, 0, 1, 1)); private static int fib2(int n) { if (!memo.containsKey(n)) { memo.put(n, fib2(n - 1) + fib2(n - 2)); } return memo.get(n); } //使用迭代 // 递归是反向求解，而迭代是正向求解。有时递归是解决问题最直观的方法 // 然而，直观的递归解决方案也会带来巨大的性能成本。请记住，任何可以使用递归解决的问题也可以使用迭代来解决。 private static int fib3(int n) { int last = 0, next = 1; for (int i = 0; i < n; i++) { int oldLast = last; last = next; next = oldLast + next; } return last; } // 使用流 private int last=0,next=1; public IntStream stream(){ return IntStream.generate(()->{ int oldLast = last; last = next; next = oldLast + next; return oldLast; }); } }
5 55 --------- 5 55 --------- 5 55 --------- 0 1 1 2 3 5 --------- 0 1 1 2 3 5 8 13 21 34 55
