Python每日一练——第4天:百钱百鸡问题(升级版)
前言📢📢
Python每日一练来啦,本文已收录于:《Python每日一练》专栏
此专栏目的在于,帮忙学习Python的小白提高编程能力,训练逻辑思维,每周持续更新中,欢迎免费订阅!!!
1. 问题描述
我国古代数学家张丘建在《算经》一书中曾提出过著名的 “百钱买百鸡” 问题,该问题叙述如下:鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一;百钱买百鸡,则翁、母、雏各几何?
百钱买百鸡的问题算是一套非常经典的不定方程的问题,题目很简单:公鸡每只5元,母鸡每只3元,小鸡3只一元,现要求用100元钱买100只鸡(三种类型的鸡都要买),问公鸡、母鸡、小鸡各买几只?
小伙伴们看了问题描述后,一定要自己先练习,再去看博主的代码和解题思路,才能提高自己的编程水平,全靠自觉哟!!!
欢迎小伙伴们把自己的思路或答案在评论区留言,博主会选一个最优解答进行置顶。
2. 问题分析
数学解法:设公鸡买了x只,母鸡买了y只,小鸡买了z只
数量关系式: x + y + z = 100
钱的关系式:5x + 3y + z/3 = 100
3. 算法思路
1.以公鸡为突破点,公鸡5元一只,100元最多只能买20只,由于三种鸡都要买,所以公鸡数一定是小于20的。
2.母鸡每只3元,100全 拿来买母鸡,最多也不能超过33只机会。
3.设公鸡数为x,母鸡数为y,小鸡z只
4.只要满足 5x+3y+ z/3== 100 和 x + y + z == 100 就可以输出此种组合的结果。
4. 代码实现
实现代码📝:
import time
# 开始时间
start = time.time()
# 外层循环控制公鸡数量取值范围:0~20
for x in range(0, 21):
# 内层循环控制母鸡数量取值范围:0~33
for y in range(0, 34):
# 嵌套内层循环控制小鸡数量取值范围:0~100
for z in range(0, 101):
# 条件判断同时满足 5x+3y+ z/3== 100 和 x + y + z == 100
if (x * 5 + y * 3 + z / 3 == 100) and (x + y + z == 100):
print("公鸡有%d只 母鸡有%d只 小鸡有%d只" % (x, y, z))
# 结束时间
end = time.time()
print("算法总耗时:", end - start)
运行结果👇:
思考:虽然能求出结果,但仔细一想,用了三重循环, 总的循环次数:21 ∗ 34 ∗ 101 = 72114 次,太耗时间了,能不能有一种更好的解决方法呢?
5. 算法升级
思路:买了一只公鸡,花掉5钱,还剩下100 - 5 = 95 钱,买母鸡和小鸡的钱只有95钱,而不是100钱。再买一只母鸡,还剩下100- 5 - 3 = 92钱,那么买小鸡的钱只有92钱……所以每重循坏次数不再是固定的100,而是变化的。
第一重循环(公鸡):100 / 5 = 20 次
第二重循环(母鸡):(100 - x) / 3次
第三重判断(小鸡):100 - x - y次
实现代码📝:
import time
# 开始时间
start = time.time()
for x in range(0, 101, 5): # 公鸡
for y in range(3, 101 - x, 3): # 母鸡
z = 100 - x - y # 小鸡
if (x // 5 + y // 3 + z * 3 == 100) and (x + y + z == 100):
print("公鸡有%d只 母鸡有%d只 小鸡有%d只" % (x // 5, y // 3, z * 3))
# 结束时间
end = time.time()
print("算法总耗时:", end - start)
运行结果👇:
总结:方式2较方式1提升了100倍,这个小小的程序可以说明算法的重要性,用不同的算法,时间复杂度是不一样的。在实现一个功能的基础上,还要兼顾效率的问题。当然这个题目还可以用求不定方程整数解的办法来解决,这个算法用时会更短。
相关文章
- linux terraform环境配置(创建cvm的例子)
- 短信发送接口 – SubMail
- 用 Python 编辑 PDF 文件
- 通过内置对象理解 Python(九)
- 语义化版本 2.0.0
- 【干货日报】用Python实现自动发消息,自定义内容,太省事了!
- 【干货日报】开码开码!python各种快捷键的用法,真不收藏吗!!!
- 用Python帮老哥选出好基金,稳赚一笔,老哥专门提着茅台登门拜访
- 什么是库-适用于当前软件的包
- 如何使用python 执行命令行传入的代码
- iOS+Fastlane自动打包、发布测试、消息通知,完美结合!iOS+Fastlane自动打包、发布测试、消息通知,完美结合!
- 协程理解心得-初探
- 【愚公系列】2021年12月 python爬虫自动化-WEditor自动化APP测试工具安装和使用
- Python中的网关:WSGI
- [源码解析] PyTorch 分布式 Autograd (6) ---- 引擎(下)
- JLight——JavaWeb的轻量级开发框架
- 排序算法的python实现
- python学习笔记10.1 python中的路径
- python学习笔记10.4 通过killpg杀死进程组
- Golang: 插件plugin介绍