题解 | #百钱买百鸡问题#

百钱买百鸡问题

http://www.nowcoder.com/practice/74c493f094304ea2bda37d0dc40dc85b

题目分析

  1. 题目翻译之后的意思是,公鸡一只5元,母鸡一只3元,小鸡三只1元
  2. 用100元买100只鸡,给出所有的购买方案

方法一:暴力遍历

  • 实现思路
    • 直观的我们可以看出公鸡最多20只就超出了价格

    • 母鸡最多34只就超出价格

    • 小鸡100只超出了数量范围

    • 因此在这个三个范围内进行暴力遍历尝试,输出符合题目要求的结果即可

while True:
    try:
        ppp = input()
        for a in range(21):                                                # a 最多买20只
            for b in range(34):                                            # b 最多买33只
                for c in range(101):                                       # c 最多买100只
                    if a + b + c == 100 and 5*a + 3*b + 1*c/3 == 100:
                        print(a,b,c)
                        
        
    except:
        break

复杂度分析

  • 时间复杂度:O(n3)O(n^3),其中n就是对应所需要购买的鸡的数量(100),对于我们要购买的鸡的数量n,由于a的遍历范围为n/5,b的遍历范围为n/3,c的遍历范围为n,因此综合三层循环的时间开销为O(n/5n/3n)O(n/5 ·n/3 ·n),即O(n3)O(n^3)
  • 空间复杂度:O(1)O(1),只引入整型变量的常数级开销

方法二:数学推导

  • 实现思路
    • 我们假定公鸡、母鸡、小鸡数量为a,b,c
    • 则有 a+b+c=100 , 5a+3b+c/3=100
    • 消去c可知
      • b = 25-7a/4
    • 因此我么可以知道a必须是4的倍数,而且b如果为正数的话要求a最大只能取3
    • 根据这个结果进行循环遍历,得到输出即可

alt

while True:
    try:
        ppp = input()
        for i in range(4):        # 数学推导,公鸡只能取0,4,8,12只
            a = 4*i
            b = 25-7*i
            c = 100-a-b
            print(a,b,c)
    except:
        break

复杂度分析

  • 时间复杂度:O(1)O(1),循环的代价和输入无关,针对该问题来讲为了得出结果循环迭代次数是固定的,我们认为是常数级别的开销
  • 空间复杂度:O(1)O(1),只引入整型变量的常数级开销
全部评论
方法一中, for c in range(101):可以去掉, 小鸡数量可以通过100 - 公鸡 - 母鸡数量得出, 没必要再循环。
1 回复 分享
发布于 2022-05-02 10:11
方法二不是a最大只能取3,是a/4最大只能取3吧
7 回复 分享
发布于 2022-04-06 21:34
初中生,这题我会!!!高中生,这题简单!!!大学生,啊吧啊吧(???)
2 回复 分享
发布于 2023-07-05 17:10 香港
直接打印,答案是固定的(手动滑稽)
2 回复 分享
发布于 2023-03-26 16:34 陕西
for c in range(0, 101, 3): 遍历相比会快点
1 回复 分享
发布于 2022-08-03 09:01
这里的c/3代表的应该是小鸡的数量,c应该是小鸡的钱(题目是3只小鸡1元)。
点赞 回复 分享
发布于 03-25 10:43 江苏
这里的ppp输入有什么用处吗?
点赞 回复 分享
发布于 2024-07-03 00:01 湖南
这个方法确实时间复杂度和空间复杂度低,但时间都花在了分析题目上了
点赞 回复 分享
发布于 2022-09-04 20:19 广东
最牛的是还整了个动图。。。
点赞 回复 分享
发布于 2022-05-16 18:35
为什么a必须是4的倍数?
点赞 回复 分享
发布于 2022-04-28 14:43
666
点赞 回复 分享
发布于 2022-03-12 19:22
666
点赞 回复 分享
发布于 2022-03-05 20:03

相关推荐

02-22 20:28
重庆大学 Java
程序员牛肉:首先不要焦虑,你肯定是有希望的。 首先我觉得你得好好想一想自己想要什么。找不到开发岗就一定是失败的吗?那开发岗的35岁危机怎么说?因此无论是找工作还是考公我觉得你都需要慎重的想一想。但你一定要避开这样一个误区:“我是因为找不到工作所以不得不选择考公”。 千万不要这么想。你这个学历挺好的了,因此你投后端岗肯定是有面试机会的。有多少人简历写的再牛逼,直接连机筛简历都过不去有啥用?因此你先保持自信一点。 以你现在的水平的话,其实如果想要找到暑期实习就两个月:一个月做项目+深挖,并且不断的背八股。只要自己辛苦一点,五月份之前肯定是可以找到暑期实习的,你有点太过于高看大家之间的技术差距了。不要焦虑不要焦虑。 除此之外说回你这个简历内容的话,基本可以全丢了。如果想做后端,先踏踏实实做两个项目再说+背八股再说。如果想考公,那就直接备战考公。 但是但是就像我前面说的:你考公的理由可以是因为想追求稳定,想追求轻松。但唯独不能是因为觉得自己找不到工作。不能这么小瞧自己和自己的学历。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
91
21
分享

创作者周榜

更多
牛客网
牛客企业服务