本次程序可以获取斐波那契数列任意位置上的数字。
要怎样实现呢？用递归就可以了。
先上代码：
1 package com.hw.list0710; 2 3 import java.util.Scanner; 4 5 public class Fibonacci { 6 private int calculate(int num){ 7 if(num == 0){ 8 return 0; 9 }else if(num == 1){ 10 return 1; 11 }else{ 12 int a = calculate(num-1); 13 int b = calculate(num-2); 14 return a+b; 15 } 16 } 17 18 public static void main(String[] args) { 19 Fibonacci fib = new Fibonacci(); 20 System.out.println("输入你想要在斐波那契数列中查找的位置索引:"); 21 Scanner s = new Scanner(System.in); 22 int index = s.nextInt(); 23 s.close(); 24 int res = fib.calculate(index); 25 System.out.println(res); 26 } 27 }
具体的递归代码在calculate函数里，思路很简单。
不过仔细一想会发现其实这有个问题，那就是，有很多数其实重复计算了。比如说我要计算num,那么就肯定会计算num-1和num-2,num-1肯定就会计算num-2和num-3，num-2一定会计算num-3和num-4,那么这个时候，在计算num-1时，我已经计算出num-2了，那么后面我还有必要计算num-3和num-4吗？所以我们就应该想个办法改善一下我们的思路。
我们可以用一个数组来做标记（敲黑板，又一次用到了这种思想！）。先初始化一个num+1长度的数组，里面肯定默认全为0.只要计算了某一个值，我们就修改在数组中的值，然后判断一下就可以了。
1 package com.hw.list0710; 2 3 import java.util.Scanner; 4 5 public class Fibonacci { 6 private int calculate(int num){ 7 int[] arr = new int[num+1]; 8 return recursion(arr, num); 9 } 10 11 private static int recursion(int[] arr, int num){ 12 if(num == 0){ 13 return 0; 14 }else if(num == 1){ 15 return 1; 16 } 17 18 if(arr[num] != 0){ //这里是不重复计算的关键 19 return arr[num]; 20 } 21 22 arr[num] = recursion(arr, num-1) + recursion(arr, num-2); 23 return arr[num]; 24 } 25 26 public static void main(String[] args) { 27 Fibonacci fib = new Fibonacci(); 28 System.out.println("输入你想要在斐波那契数列中查找的位置索引:"); 29 Scanner s = new Scanner(System.in); 30 int index = s.nextInt(); 31 s.close(); 32 int res = fib.calculate(index); 33 System.out.println(res); 34 } 35 }