鸡兔同笼 python

题目描述

在一个笼子里关着若干只鸡和兔子，从上面数共有 35 个头，从下面数共有 94 只脚，请问笼子里有几只鸡，几只兔子？

算法1

(暴力枚举) $O(n^2)$

题目中给出了头和脚的数量，因此可以列出方程组：

$$\begin{cases}x + y = 35\\2x + 4y = 94\end{cases}$$

其中 $x$ 表示鸡的数量，$y$ 表示兔子的数量。解方程组可以得到鸡和兔子的数量。

时间复杂度

暴力枚举所有可能的鸡和兔子数量，因此时间复杂度为 $O(n^2)$。

参考文献

Python 代码

算法2

(优化) $O(1)$

根据题目给出的条件，鸡和兔子的总数量为 35，因此最多有 35 只鸡或 35 只兔子，而总脚的数量为 94，因此最少需要 35 只兔子的脚，即 140 只脚，剩下的 94 - 140 = -46 只脚需要由鸡来补足。

由于每只鸡只有两只脚，因此需要补足的脚数必须是偶数，因此如果需要补足的脚数是奇数，则无解。如果需要补足的脚数是偶数，则可以计算出鸡和兔子的数量。

时间复杂度

由于只需要进行简单的计算，因此时间复杂度为 $O(1)$。

参考文献

Python 代码

def chicken_and_rabbit(heads, legs):
# 计算需要补足的脚数
missing_legs = legs - heads * 2
if missing_legs % 2 == 1:
# 需要补足的脚数为奇数，无解
return None
# 计算鸡的数量
chicken = (4 * heads - missing_legs) // 2
# 计算兔子的数量
rabbit = heads - chicken
return chicken, rabbit

# 测试代码
print(chicken_and_rabbit(35, 94)) # (23, 12)
print(chicken_and_rabbit(10, 32)) # (4, 6)
print(chicken_and_rabbit(20, 56)) # None