程序设计问题

[miyazaki]

问题

会员卡每次只能充值 6000 商家项目有： 2880 （每次） 2380 （每次） 目前会员卡余额为 1720 请问要如何充值、如何消费才能把会员卡余额变为 0 ？

问题来源于生活，纯属娱乐，开拓思维

[linhuoqi]

1720 + x * 6000 == y * 2880 + z * 2380
是想找到最小的 x 吧

[miyazaki]

@linhuoqi
是的呀

[winmer]

假设第一种消费 x 次 第二种消费 y 次 充值 n 次
有 6000n=2880x+2380y-1720 (x>-1 y>-1 n>1 x,y,n 为整数)
化简得 300n=144x+119y-860(x>-1 y>-1 n>1 x,y,n 为整数)
取 x=0 则问题转化为求解 y 使得 119y-860 能够整除 300 y 为整数
令 k=119y-860 若 k 满足 k=300n 则 k 个位为 0 乘 9 得 0 的整数只有 0 所以 y 个位为 0
k 十位也为 0 则 y 的十位上数字与 9 的乘积是 6 y 的十位为 4
令 y=40 时 k=119*40-860=3900 已经满足是 300 倍数的条件 接下来考虑 y 取更大值的可能
y=m*100+40 （ m 为非负整数）时 需满足 119*m 被 3 整除 已知 119 不是 3 的倍数 因此 m 是三的倍数
于是当 x=0 时，y 为 300M+40 即可满足上述条件
同理令 y=0 发现无法找到一个整数值 x 使得题目成立，因此 y=0 时 x>0
然后就可以在二维坐标轴上划出一个区域（令 m=x ） 在这个区域里随便搜搜或者暴力枚举...?

[gzfrankie]

python 简单写了个 BFS 搜索

import queue

q = queue.Queue()
visited = set()
def f(x,y,z):
return 1720+6000*x-2880*y-2380*z

def enqueueIfNotExist(try_solution):
if try_solution not in visited:
q.put(try_solution)
visited.add(try_solution)

def main():
q.put((0,0,0))
visited.add((0,0,0))
while not q.empty():
try_solution = q.get()
x = try_solution[0]
y = try_solution[1]
z = try_solution[2]
remain = f(x,y,z)
print("x,y,z=",x,",",y,",",z," remain ",remain)
if remain == 0:
return try_solution
elif remain > 0:
try_solution = (x,y+1,z)
enqueueIfNotExist(try_solution)

try_solution = (x,y,z+1)
enqueueIfNotExist(try_solution)
elif remain < 0:
try_solution = (x+1,y,z)
enqueueIfNotExist(try_solution)


if __name__=="__main__":
main()


最后答案是 8，9，10，即 1720+6000*8-2880*9-2380*10=0

[gzfrankie]

贴上来格式乱了，传个在线 ide 的地址吧，ideone.com/sS9e5Z

[gzfrankie]

点进 ide 的页面能看到所有枚举过程，如果是想尽可能充少点钱的话，比较好的方法：
1，1，2 剩 80
3，6，1 剩 60

[miyazaki]

@gzfrankie 厉害厉害！

[daniel1996]

@gzfrankie 大佬大佬

[spicecch]

@gzfrankie 膜拜大佬

[realkun]

真就技术成就美好生活啊