java语言求解兔子问题代码分析

1、思考

兔子问题，是费氏数列的形象化说法，它是由一位名为Fibonacci的数学家在它的著作中提出的一个问题。

2、描述

它体术的问题是：若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......

我们使用数学的方式表达出来，便是下面的一组数列：

1、1、2、3、5、8、13、21、34、55、89......

注意：新生的小免子需一个月成长期才会投入生产！而且这些兔子是不死的哦！！！

3、规律

当我们莫名其妙的接触到这个问题的时候，很难找到其中的规律，但是依照数学中数列的规律去思考这个问题，等比？等差？还是其它什么？既然这是一个由数学家提出的问题，那么其中应该有一定的数学规律吧？到底是什么规律呢，仔细分析上面的一组数列，相比你已经有了答案了。没错，它用一句话来表述，从第三项开始，前面两项的和等于第三项。

假设第n项的数值为fn，那么该数列的规律性使用数学公式表达如下：

4、伪代码

所谓伪代码，就是不是真的代码，它并不能在机器上执行，只是一段介于自然语言和编程语言之间的一种表达程序逻辑的有意义的符号。对于兔子问题的伪代码，我们这里使用上述公式的递归方式，可以有以下的伪代码：

Procedure FIB(N) [ 
  IF (N < 0)  
    PRINT ("输入错误");  
 
  IF (N = 0 OR N = 1)  
    RETURN (N);  
  ELSE  
    RETURN ( FIB(N-1) + FIB(N-2) );  
] 

根据之前文章所描述的递归概念，详细情况可以参考之前的《汉诺塔问题》，相比大家对递归已经不会太陌生，那么根据上述我们得到的数学公式，推演出这样的递归伪代码，会非常简洁明了。但是，额，可能大家猜到了，我要说但是。大家是否发现一个问题，当我们的n值过大的时候，程序会比较慢？

如果你发现了，说明你认真思考了这个问题，相比你也应该解决了心中的疑惑。如果还有没有解决疑惑的，就随着我来解决大家的疑惑。为什么会比较慢呢？原因在于，当我们计算后面的第n项的时候，需要再次计算n-1和n-2项，而这两项在之前都是已经被计算过了的，我们再求后面的一个数的时候，还是要在计算一边，无形之中，我们就多做了很多无用功。

那么，我们时候有好的方法去解决这个问题呢？答案是有的。根据上面的分析，当我们在求解第n项的时候，前面n-1和n-2项是已经求解过的，那么，为什么我们不把它存起来呀？？？？

哈哈，有没有瞬间豁然开朗，对呀！我们这里是使用空间换时间，可以大大提高效率哦！这里我就不写伪代码了。

5、代码

好了，关子卖完了，直接上代码：

public class Fibonacci { 
  public static void main(String[] args) { 
    int[] fib = new int[20];  
 
    fib[0] = 0;  
    fib[1] = 1;  
 
    for(int i = 2; i < fib.length; i++) { 
      fib[i] = fib[i-1] + fib[i-2];  
    } 
 
    for(int i = 0; i < fib.length; i++){  
      System.out.print(fib[i] + " ");  
    } 
    System.out.println(); 
  } 
} 

6、思考

这里，我们提出一个思考题，如果兔子它不是生一个兔子，生多个兔子，该怎么求解？当然，我们说的生多个就是定数，不会一个兔子生得多，一个兔子生的少，不然那样就没法求解了。

这里就不上代码了，大家可以自己在网上查找一下合适的资源，看看如何求解。