java的经典算法：菲波拉契数列

// 古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
解：由这个问题可以得出下列的表格
通过表格我们知道：
第一个月：兔子总数 = 1
第二个月：兔子总数 = 1
第三个月：兔子总数 = 2 = 第一个月 + 第二个月
第四个月：兔子总数 = 3 = 第三个月 + 第二个月
以此类推...
得到函数F(n) = F(n-1) +F(n-2)

[图片上传失败...(image-e3feff-1545789643090)]

注意：不能使用int作为返回值，当返回的数量超过int的范围的时候，容易出现负数

// 古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？   
//这是一个菲波拉契数列问题

//不能使用int作为返回值，当返回的数量超过int的范围的时候，容易出现负数
//所以大数用BigInteger接受

import java.math.BigInteger;

public class study_1 {
    
    public static void main(String[] args) {
        long starttime1 = System.currentTimeMillis();
        //使用数组
        System.out.println(useArr(100));
        long endtime1 = System.currentTimeMillis();
        System.out.println("执行运行的时间为1"+(endtime1-starttime));
        //使用递归 （使用递归的执行时间最长，不建议使用递归方法）
        long starttime2 = System.currentTimeMillis();
        System.out.println(useRecursive1(40));

        long endtime2 = System.currentTimeMillis();
        System.out.println("执行运行的时间为2"+(endtime2-starttime2));
        //正常的运算
        long starttime3 = System.currentTimeMillis();
        System.out.println(useRecursive2(40));
        
        long endtime3 = System.currentTimeMillis();
        System.out.println("执行运行的时间为3"+(endtime3-starttime3));
        

        
    }
    
    //使用数组
    public static BigInteger useArr(int n) { 
        BigInteger []a = new BigInteger[n];
        int i = n;
        a[0] = new BigInteger("0");
        a[1] = new BigInteger("1");
        if (i < 2) return a[i];
        for(i = 2; i < n;i++) {
            a[i] = a[i - 1].add(a[i - 2]);
            if (i == n-1){
                return a[i];
            }
        }
        return new BigInteger("0");
    }
    
    //使用递归
    public static BigInteger useRecursive1(int n) {
        if (n < 2) return n==0?(new BigInteger("0")):(new BigInteger("1"));
        return  useRecursive1(n-1).add(useRecursive1(n-2));
    }
    
    //使用递推
    public static BigInteger useRecursive2(int n) {
        BigInteger n1 = new BigInteger("0");
        BigInteger n2 = new BigInteger("1");
        BigInteger tmp = new BigInteger("0");
        for(int i = 1;i < n;i++) {
            tmp = n1.add(n2);
            n1 = n2;
            n2 = tmp;
        }   
        return tmp;
    }

}

上面代码执行之后可以得到

218922995834555169026
执行运行的时间为11
102334155
执行运行的时间为27782
102334155
执行运行的时间为30

参考的博客为：https://blog.csdn.net/u012762573/article/details/48106309