[已解决]Python：每日一题 274

zltzlt

此题由 @Unicorn# 提供

今天的题目：

小凯手中有无数个两种面值的金币，现在他想购买价格为 price 的商品，问小凯手中的金币是否能够刚好凑成商品的价钱（既不多也不少）？

说明：面值、商品价格均为正整数。

示例 1：

输入：a = 3，b = 7，price = 11
输出：False
解释：3 和 7 无法刚好凑成 11。

示例 2：

输入：a = 6，b = 5，price = 32
输出：True
解释：32 = 6 * 2 + 5 * 4

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2019-11-14 22:52:10

如果说我 5#提的问，都不存在的话，那么我这个成立，并且时间复杂度为 O(1+(price%max(a,b)))

1. def solve(a:int,b:int,price:int)->bool:
   
2.     big = max(a,b)
   
3.     small = min(a,b)
   
4.     temp = divmod(price,big)
   
5.     price = temp[1]
   
6.     for i in range(temp[0]+1):
   
7.         #print('调试',price)
   
8.         if not(price % small):
   
9.             return True
   
10.         price += big
    
11.     return False
    
12. 
    
13. if __name__ == '__main__':
    
14.     print('示例1 False 输出：',solve(3,7,11))
    
15.     print('示例2 True 输出：',solve(6,5,32))
    

复制代码

跳转到最佳答案楼层

archlzy

1. def fun274(a, b, price):
   
2.     for i in range(int(price/max(a,b)),0,-1):
   
3.         if (price - max(a,b)*i) % min(a,b) == 0:
   
4.             return True
   
5.     return False

复制代码

danteer

1. def func(a,b,price):
   
2.     if price < a and price < b:
   
3.         return False
   
4.     elif price >= b and price < a:
   
5.         if price % b == 0:
   
6.             return True
   
7.         else:
   
8.             return False
   
9.     elif price >= a and price < b:
   
10.         if price % a == 0:
    
11.             return True
    
12.         else:
    
13.             return False
    
14.     else:
    
15.         nummap = []
    
16.         for i in range(price+1):
    
17.             nummap.append(False)
    
18.         nummap[a] = True
    
19.         nummap[b] = True
    
20.         for i in range(price+1):
    
21.             if nummap[i] == True:
    
22.                 if i + a <= price:
    
23.                     nummap[i+a] = True
    
24.                 if i + b <= price:
    
25.                     nummap[i+b] = True
    
26.         return nummap[price]

复制代码

Python3005

1. def buy(a , b , price):
   
2.         for m in range(price//a +1):
   
3.                 for n in range(price//b +1):
   
4.                         if a * m + b * n == price:
   
5.                                 return True
   
6.         else:
   
7.                 return False

复制代码

优化一下：

1. def buy(a , b , price):
   
2.         for m in range(price//a +1):
   
3.                 if (price - a * m) % b == 0:
   
4.                         return True
   
5.         else:
   
6.                 return False

复制代码

阴阳神万物主

提问：
1.面额存在小数吗？
2.面额存在单位吗？（如：元、角、分）

爱尔兰咖啡

1. def f(coin1,coin2,price):
   
2.     c_max=max(coin1,coin2)
   
3.     c_min=min(coin1,coin2)
   
4.     a=price/c_max
   
5.     b=price/c_min
   
6.     if a==int(a) or b==int(b):
   
7.         return True
   
8.     else:
   
9.         for i in range(1,int(a)+1):
   
10.             x=(price-c_max*i)/c_min
    
11.             if x==int(x):
    
12.                 return True
    
13.     return False
    
14. temp=f(7,11,1002)
    
15. print(temp)

复制代码

阴阳神万物主

如果说我 5#提的问，都不存在的话，那么我这个成立，并且时间复杂度为 O(1+(price%max(a,b)))

1. def solve(a:int,b:int,price:int)->bool:
   
2.     big = max(a,b)
   
3.     small = min(a,b)
   
4.     temp = divmod(price,big)
   
5.     price = temp[1]
   
6.     for i in range(temp[0]+1):
   
7.         #print('调试',price)
   
8.         if not(price % small):
   
9.             return True
   
10.         price += big
    
11.     return False
    
12. 
    
13. if __name__ == '__main__':
    
14.     print('示例1 False 输出：',solve(3,7,11))
    
15.     print('示例2 True 输出：',solve(6,5,32))
    

复制代码

阴阳神万物主

danteer 发表于 2019-11-14 22:01

这我一眼就能看出毛病！！！
func(a=1,b=5,price=3)，理当返回 True !
你这个马上就能给 False 。

阴阳神万物主

楼主啊，要是说，这样的题目改编……好使吗？



解题的代码：

Stubborn

1. def fun274(a: int, b: int, price: int) -> bool:
   
2.     c,d,e = max(a, b),min(a, b),price // max(a, b)
   
3.     for m in range(e+1):
   
4.         if (price - m * c) % d == 0: return True
   
5.     return False

复制代码

danteer

阴阳神万物主 发表于 2019-11-14 22:59
这我一眼就能看出毛病！！！
func(a=1,b=5,price=3)，理当返回 True !
你这个马上就能给 False 。

昨晚写完就去看剧了，没发现。。。多谢

776667

1. def fun274(a,b,price):
   
2.     for i in range((price//a)+1):
   
3.         for j in range((price//b)+1):
   
4.             if a*i+b*j == price:
   
5.                 return True
   
6.     return False

复制代码

零0℃度

1. def f274(a, b, price):
   
2.     for i in range(price // min(a, b)):
   
3.         if (price - min(a, b) * i) % max(a, b) == 0:
   
4.             return True
   
5. 
   
6.     return False

复制代码

天圆突破

1. a = 3
   
2. b = 7
   
3. price = 10
   
4. if a < b:
   
5.     a, b = b, a
   
6. i = j = 0
   
7. res = False
   
8. while not res or a * i + b * j < price:
   
9.     while True:
   
10.         print (a, i, b, j, a*i + b * j)
    
11.         if a * i + b * j == price:
    
12.             res = True
    
13.             break
    
14.         elif a * i + b * j > price:
    
15.             j = 0
    
16.             break
    
17.         else:
    
18.             j += 1
    
19.         i += 1
    
20. print(res)

复制代码

jdzzj

1. def fun274(a,b,price):
   
2.     n=price//a  #假设每次都放入a, 最多放n件a
   
3.     for i in range(n+1):
   
4.         if price%b==0:
   
5.             return True
   
6.         price-=a
   
7.     return False

复制代码

zltzlt

阴阳神万物主 发表于 2019-11-14 23:12
楼主啊，要是说，这样的题目改编……好使吗？

阴阳神万物主

zltzlt 发表于 2019-11-15 18:45

恩姆？

前奏

def ceshi(a,b,price):
    c=1
    while c <= price:
        d = 1
        jiage = a * c + b * d
        if jiage == price:
            return True
        else:
            d += 1
            while d <= price:
                jiage = a * c + b * d
                if jiage == price:
                    return True
                else:
                    d += 1
            c += 1
    return False
print(ceshi(3,7,11))


def ceshi(a,b,price):
    for i in range(1,(price+1)):
        for c in range(1,(price+1)):
            if (a*i+b*c)==price:
                return True
    return False

print(ceshi(6,5,31))

zltzlt

archlzy 发表于 2019-11-14 21:02

解答错误

输入：a = 16, b = 15, price = 210
输出：False
预期结果：True

zltzlt

danteer 发表于 2019-11-14 22:01

输入 a = 196823, b = 21512, c = 4233838041 出错：MemoryError