题目分析

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(n^3)O(n^3)$，其中n就是对应所需要购买的鸡的数量（100），对于我们要购买的鸡的数量n，由于a的遍历范围为n/5，b的遍历范围为n/3，c的遍历范围为n，因此综合三层循环的时间开销为$O(n\mathrm{/}5\cdot n\mathrm{/}3\cdot n)O(n/5\; ·n/3\; ·n)$，即$O(n^3)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
  • 根据这个结果进行循环遍历，得到输出即可

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)$，只引入整型变量的常数级开销