java的經(jīng)典算法：菲波拉契數(shù)列

// 古典問題：有一對兔子嗓化，從出生后第3個月起每個月都生一對兔子棠涮，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死刺覆，問每個月的兔子總數(shù)為多少严肪？
解：由這個問題可以得出下列的表格
通過表格我們知道：
第一個月：兔子總數(shù) = 1
第二個月：兔子總數(shù) = 1
第三個月：兔子總數(shù) = 2 = 第一個月 + 第二個月
第四個月：兔子總數(shù) = 3 = 第三個月 + 第二個月
以此類推...
得到函數(shù)F(n) = F(n-1) +F(n-2)

[圖片上傳失敗...(image-e3feff-1545789643090)]

注意：不能使用int作為返回值，當(dāng)返回的數(shù)量超過int的范圍的時候，容易出現(xiàn)負(fù)數(shù)

// 古典問題：有一對兔子驳糯，從出生后第3個月起每個月都生一對兔子篇梭，小兔子長到第三個月后每個月又生一對兔子对室，假如兔子都不死祝高，問每個月的兔子總數(shù)為多少？   
//這是一個菲波拉契數(shù)列問題

//不能使用int作為返回值逢慌，當(dāng)返回的數(shù)量超過int的范圍的時候帘睦，容易出現(xiàn)負(fù)數(shù)
//所以大數(shù)用BigInteger接受

import java.math.BigInteger;

public class study_1 {
    
    public static void main(String[] args) {
        long starttime1 = System.currentTimeMillis();
        //使用數(shù)組
        System.out.println(useArr(100));
        long endtime1 = System.currentTimeMillis();
        System.out.println("執(zhí)行運(yùn)行的時間為1"+(endtime1-starttime));
        //使用遞歸 （使用遞歸的執(zhí)行時間最長袍患，不建議使用遞歸方法）
        long starttime2 = System.currentTimeMillis();
        System.out.println(useRecursive1(40));

        long endtime2 = System.currentTimeMillis();
        System.out.println("執(zhí)行運(yùn)行的時間為2"+(endtime2-starttime2));
        //正常的運(yùn)算
        long starttime3 = System.currentTimeMillis();
        System.out.println(useRecursive2(40));
        
        long endtime3 = System.currentTimeMillis();
        System.out.println("執(zhí)行運(yùn)行的時間為3"+(endtime3-starttime3));
        

        
    }
    
    //使用數(shù)組
    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;
    }

}

上面代碼執(zhí)行之后可以得到

218922995834555169026
執(zhí)行運(yùn)行的時間為11
102334155
執(zhí)行運(yùn)行的時間為27782
102334155
執(zhí)行運(yùn)行的時間為30

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