18.鸡兔同笼问题

四曲

2020 年 11 月 18 日

773 次浏览

暂无评论

3180字数

Python笔记

问题：今有雉、兔同笼，上有三十五头，下有九十四足，问雉、兔各几何？

1.数学解法

首先，我们抛开编程，想一下有没有单纯的利用数学来解决这个问题？

答案肯定是有的，比如，使用方程来进行计算，设鸡有x只，兔有y只，那么我们可以列出以下方程：

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

最后可以解出最后的结果：x=23;y=12

当然，除了方程以外，我们还有其他的方式来解出这道题
假设有35只鸡
脚的数量:$35*2=70(只)$
剩余脚的数量:$94-70=24(只)$
由于兔子比鸡多了两只脚，因此剩下的脚全部都是兔子的$$
兔子的数量：$24 \div2=12(只)$
鸡的数量:$35-12=23(只)$
通过假设的方式，我们也可以计算出正确答案

2.穷举算法的实现

但是对于计算机来说，它可没有这么聪明，能够直接分析题干，并且列出算式，最终写出答案，虽然计算机虽然不具备分析能力，但是它却具有很强的计算能力，因此，既然无法直接分析题干，那就一个个对可能的答案进行测试，直到找到正确答案为止，这个就是穷举法，“穷”表示穷尽的意思，就是列出所有可能的结果，并从中找出正确答案。

因此，对于上面这个问题，计算机可以这么做

$$ 假设兔子的数量为：1 \\ 那么鸡的数量为：35-1 \\ 检查\quad 兔子的数量*4+鸡的数量*2 \quad是否等于94 $$

$$ 假设兔子的数量为：2 \\ 那么鸡的数量为：35-2 \\ 检查\quad 兔子的数量*4+鸡的数量*2 \quad是否等于94 $$

$$ 假设兔子的数量为：3 \\ 那么鸡的数量为：35-3 \\ 检查\quad 兔子的数量*4+鸡的数量*2 \quad是否等于94 $$

可以看到，这肯定是一个循环的过程，因此，经过这个思路，我们就很容易写出代码

for i in range(1,36):
    chicken=i
    rabbit=35-i
    if chicken*2+rabbit*4==94:
        print("鸡的数量为：",i)
        print("兔子的数量为：",35-i)

#运行结果
#鸡的数量为： 23
#兔子的数量为： 12

3.format()函数的妙用

format()函数用来对字符串进行格式化，什么叫做格式化呢？就是让字符串按照我们的要求进行打印，使用format()函数也非常简单，使用str.format()的形式即可，str可以替换成任意字符串

可以代替字符串的{}和:两个符号，比如：

print("{},{}".format("hello","world"))

# 运行结果：
# hello,world

以上例子没有指定顺序，那么format就会按照默认顺序来进行替换

当然，还可以指定顺序来进行替换，顺序还是从0开始

print("{1},{0},{1}".format("hello","world"))

# 运行结果：
# world,hello,world

还可以通过设置参数的方式来进行替换

print("name:{name},age:{age}".format(name="siqu",age=32))

# 运行结果：
# name:siqu,age:32

有了format之后，我们就可以采用新的方式来输出我们运算出来的结果了

for i in range(1,36):
    chicken=i
    rabbit=35-i
    if chicken*2+rabbit*4==94:
        print("鸡的数量：{},兔子的数量为：{}".format(i,35-i))

#运行结果
#鸡的数量：23,兔子的数量为：12

显示的结果会更加简单明了

4. break跳出循环

接下来，我们来看看，我们这个程序是否还有值得去优化的地方，我们将数值改大，并且测试一下运行时间

import time

start=time.time()

head=3500000    #表示有多个头
foot=9400000    #表示有多少个脚
for i in range(1,head+1):
    chicken=i
    rabbit=head-i
    if chicken*2+rabbit*4==foot:
        print("鸡的数量：{},兔子的数量为：{}".format(i,head-i))

end=time.time()
print("运行的时间为：{}".format(end-start))

#运行结果
# 鸡的数量：2300000,兔子的数量为：1200000
# 运行的时间为：2.151245355606079

有三百五十万个头的时间，我们运算出结果，需要2.15秒的时间，我们可以仔细想想，当我们第一次运算出正确结果之后，我们还有必要往下算么？比如当head等于35，foot等于94时，我们总共需要循环35次，但是当i=23的时候，我们就没有必要在继续循环了，因为我们已经找到了正确答案，因此，当我们找到正确答案后，我们可以通过break来跳出循环

import time

start=time.time()

head=3500000    #表示有多个头
foot=9400000    #表示有多少个脚
for i in range(1,head+1):
    chicken=i
    rabbit=head-i
    if chicken*2+rabbit*4==foot:
        print("鸡的数量：{},兔子的数量为：{}".format(i,head-i))
        break

end=time.time()
print("运行的时间为：{}".format(end-start))

#运行结果
# 鸡的数量：2300000,兔子的数量为：1200000
# 运行的时间为：1.456103801727295

我们发现，运行时间的确减少了很多