Java 编程经典案例之兔子繁殖迭代问题

20140622120205_CsEcL.thumb.700_0.jpeg

题目

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第6个月的兔子总数为多少?

分析

首先我们要明白题目的意思指的是每个月的兔子总对数;假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子,

那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1、0、0,第二个月分别为0、1、0,

第三个月分别为1、0、1,第四个月分别为,1、1、1,第五个月分别为2、1、2,第六个月分别为3、2、3,第七个月分别为5、3、5……

兔子总数分别为:1、1、2、3、5、8、13……

于是得出了一个规律,从第三个月起,后面的兔子总数都等于前面两个月的兔子总数之和,即为斐波那契数列。

方法一:递归

 public static void main(String[] args) {
    Integer month = 6; // 月份
    Integer pair = f(month);
    System.out.println("答:经过" + month + "个月后,兔子的总数为" + pair + "对。");
}

/**
 * f(n)=f(n-1)+f(n-2) (n>=3)
 * @param month
 * @return
 */
public static Integer f(Integer month){
    if (month ==1 || month == 2) {
        return 1;
    }else {
        return f(month - 1) + f(month - 2);
    }
}

方法二:叠加法

/**
 * 叠加法
 */
public static int getTotalByAdd(int month) {
    int last = 1;//上个月的兔子的对数
    int current = 1;//当月的兔子的对数
    int total = 1;
    for (int i = 3; i <= month; i++) {
        //总数= 上次+当前
        total = last + current;
        last= current ;
        current = total;
    }
    return total;
}

方法三:数组

/**
 * 使用数组
 */
public static int getTotalByArray(int month) {
    int arr[] = new int[month];
    arr[1] = arr[2] = 1;
    for (int i = 2; i < month; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[month - 1] + arr[month - 2];
}


未经允许请勿转载:程序喵 » Java 编程经典案例之兔子繁殖迭代问题

点  赞 (2) 打  赏
分享到: