Java实现经典算法题：兔子产仔

谁借莪１个温暖的怀抱￠ 2023-06-22 13:59 72阅读 0赞

**目录**

题目

分析

解答

方法一：递归算法

方法二：非递归，直接循环计算总数

方法三：直接利用数学公式法：f(n)=\{\[(1+5^0.5)/2\]^n - \[(1-5^0.5)/2\]^n\}/(5^0.5)

方法四：矩阵的乘法

--------------------

# 题目 #

兔子问题（四种方法）:已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后.第三个月开始生小兔子,假如没有发生死亡，则每个月有多少兔子？

# 分析 #

采用数据的方法，首先列举出从1月到多月的兔子数量，观察数据，找规律。

可以看出，从第3个月开始，每月的兔子总数和对数都是前两个月的总和。从兔子对数看就斐波那契数列。

# 解答 #

## 方法一：递归算法 ##

可以先计算每月的对数，然后乘以2获取总数。

实例方法，传入月份，计算对数，然后乘以2：

/**
 * 计算兔子对数
 *
 * @param month 月份
 * @return 兔子对数
 */
 private int countRabbitsPairNum(int month) {
 if (month < 3) {
 return 1;
 }
 return countRabbitsPairNum(month - 1) + countRabbitsPairNum(month - 2);
 }

也可以直接对总数进行计算，不必再乘以2：

/**
 * 计算兔子数量
 *
 * @param month 月份
 * @return 兔子数量
 */
 private int countRabbitsNum(int month) {
 if (month < 3) {
 return 2;
 }
 return countRabbitsNum(month - 1) + countRabbitsNum(month - 2);
 }

递归算法是常规解法，也相对容易理解。

时间复杂度为O(2^n)；递归调用的深度为n,空间复杂度为O(n)。

## 方法二：非递归，直接循环计算总数 ##

首先，三月份之前，数量都是2；大于3个月的，循环计算，3个变量，一个当前总数，一个上个月的总数，一个临时变量用于数据交换，循环相加的次数等于月份减去2（这里不列举对数和总数的计算区别了，算法基本一致）。

/**
 * 计算兔子数量
 *
 * @param month 月份
 * @return 兔子数量
 */
 private int countRabbitsNum2(int month) {
 if (month < 3) {
 return 2;
 }
 
 // 初始值，第1个月2只，之前是0的
 int lastMonthSum = 2;
 int sum = 2;
 // 数据计算临时值
 int tmp;
 
 for (int i = 0; i < month-2; i++) {
 tmp = sum;
 sum = sum + lastMonthSum;
 lastMonthSum = tmp;
 }
 
 return sum;
 }

时间复杂度为O(n)，空间复杂度为O(1)。

上面两个是常规的可以想到的简单算法，网上搜到还有2算法，但是比较复杂，不实用，这里不详细写。

想了解的可以参见：[https://blog.csdn.net/yanxiaolx/article/details/80484808][https_blog.csdn.net_yanxiaolx_article_details_80484808]

## 方法三：直接利用数学公式法：f(n)=\{\[(1+5^0.5)/2\]^n - \[(1-5^0.5)/2\]^n\}/(5^0.5) ##

时间复杂度为O(1)，空间复杂度为O(1)。

##    方法四：矩阵的乘法 ##

时间复杂度仅为O(log n),空间复杂度为O(1)，时间效率虽然低，但不够实用，源码太过繁琐。

[https_blog.csdn.net_yanxiaolx_article_details_80484808]: https://blog.csdn.net/yanxiaolx/article/details/80484808