|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 鱼C-小师妹 于 2021-3-25 10:25 编辑
在几个新手总会踩的“坑”｜【辛 酸 血 泪】发出后，师兄们的反应还不错。
让小师妹继续采用“手写+讲解”形式来讲编程技术。
好吧，既然温柔善良可爱如我，那就安排，噔噔噔，就是：
师妹小讲堂
师妹小讲堂
师妹小讲堂
本系列基于 Python，从最简单算法题目，一步一步深入到力扣 5 星难题！
涉及到的共识，流程图，程序结构等等概念。
小师妹都会边讲边在黑板上画出来，一目了然
而底层的知识，小师妹默认你懂！
不懂，请出门左转看小甲鱼老师的课程：
哈哈哈，想想就是一个艰巨的任务，不过，我喜欢！
还不一键三连，废话不多说，开始！
百钱百鸡
中国古代数学家张丘建在他的《算经》中提出了一个著名的“百钱百鸡问题”：
一只公鸡值五钱，一只母鸡值三钱，三只小鸡值一钱，现在要用百钱买百鸡，请问公鸡、母鸡、小鸡各多少只？
咱们直接换成软妹币翻译一下：
其中公鸡 5 块一只，母鸡 3 块一只，3 只小鸡算 1 块，要用 100 块钱买 100 只鸡，数量各是多少？
题目要求买 100 只，由此可知，所买公鸡的数量肯定在 0～20 之间。
同理，母鸡的数量在 0～33 之间。
创建变量 cock 代替公鸡，hen 代替母鸡，chicken 代替小鸡。
那么 cock+hen+chicken == 100，将百钱买百鸡问题就转化成解方程组。
一旦可以写成公式，那么就可以用程序来代替。
除了上面的条件，还有价格之和为 100：cock*5 + hen*3 + chicken/3 == 100
对于方程组，最简单粗暴的方式就是用穷举循环的方法来解决！
反正计算机最擅长的“傻算”。
通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。
cock 的取值范围是 0～20，可用循环语句实现：
钱的数量是固定的，要买的鸡的数量也是固定的！
既然穷举完公鸡，就在其基础上穷举母鸡，然后再在其中穷举小鸡。
每一次都傻算就好，我们可以利用三层循环的嵌套来解决：
- 第一层循环控制公鸡的数量
- 第二层控制母鸡的数量
- 最内层控制小鸡的数量
每层循环的初值 是0（即买的 100 只鸡中，可能没有公鸡，也可能没有母鸡或小鸡）
循环的控制条件就是公鸡、母鸡和小鸡用百钱最多能够买到的数量！
公鸡最多 20 只，母鸡最多 33 只，小鸡最多 100 只。
穷举循环的特点就是把所有情况都考虑到，因此每层循环执行一次，对应循环变量的值就要加 1 。
很傻很粗暴的循环就好，很方便理解对吧。
化成流程图就是（详细步骤见视频）：
根据流程图，构建程序框架如下：
- while cock <= 20:
- # 内层循环控制母鸡数量取值范围为0～33
- hen = 0
- while hen <= 33:
- # 内层循环控制小鸡数量取值范围为0～100
- chicken = 0
- while chicken <= 100:
- # 条件控制
- if (5 * cock + 3 * hen + chicken / 3.0 == 100) and (cock + hen + chicken == 100):
- print("cock=%d,hen=%d,chicken=%d\n" % (cock, hen, chicken))
- chicken += 1
- hen += 1
- cock += 1
在三层循环中，遇到满足 cock+hen+chicken == 100 和 5×cock+3×hen+chicken/3 == 100，则输出。
输出结果：
源码：
chicken.py.zip
(594 Bytes, 下载次数: 43, 售价: 8 鱼币)
优化
以上算法需要穷举尝试 21×34×101=72114 次，算法的效率显然可以优化！
对于本题来说，公鸡的数量确定后，小鸡的数量就固定为 100-cock-hen，无须再进行穷举了！
此时约束条件只有一个，即 5×cock+3×hen+chicken/3=100。
思路有啦，具体代码，自己写！
（答案：
chicken.py.zip
(567 Bytes, 下载次数: 99, 售价: 2 鱼币)
）
欢迎下方留言正确答案！！
|
评分
-
查看全部评分
|
[复制链接]
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2021-1-27 15:17:01
置顶卡
千斤顶
显身卡
楼主
