V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
miyazaki
V2EX  ›  奇思妙想

程序设计问题

  •  
  •   miyazaki · 2020-06-16 13:10:41 +08:00 · 2270 次点击
    这是一个创建于 1606 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题

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

    问题来源于生活,纯属娱乐,开拓思维
    
    10 条回复    2020-06-18 21:16:38 +08:00
    linhuoqi
        1
    linhuoqi  
       2020-06-16 14:29:35 +08:00
    1720 + x * 6000 == y * 2880 + z * 2380
    是想找到最小的 x 吧
    miyazaki
        2
    miyazaki  
    OP
       2020-06-16 14:48:11 +08:00
    @linhuoqi
    是的呀
    winmer
        3
    winmer  
       2020-06-16 15:09:37 +08:00
    假设第一种消费 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
        4
    gzfrankie  
       2020-06-16 15:14:51 +08:00
    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
        5
    gzfrankie  
       2020-06-16 15:22:44 +08:00   ❤️ 1
    贴上来格式乱了,传个在线 ide 的地址吧,ideone.com/sS9e5Z
    gzfrankie
        6
    gzfrankie  
       2020-06-16 15:41:09 +08:00   ❤️ 1
    点进 ide 的页面能看到所有枚举过程,如果是想尽可能充少点钱的话,比较好的方法:
    1,1,2 剩 80
    3,6,1 剩 60
    miyazaki
        7
    miyazaki  
    OP
       2020-06-16 15:45:29 +08:00
    @gzfrankie 厉害厉害!
    daniel1996
        8
    daniel1996  
       2020-06-16 18:45:51 +08:00
    @gzfrankie 大佬大佬
    spicecch
        9
    spicecch  
       2020-06-16 18:51:39 +08:00
    @gzfrankie 膜拜大佬
    realkun
        10
    realkun  
       2020-06-18 21:16:38 +08:00
    真就技术成就美好生活啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2764 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 01:54 · PVG 09:54 · LAX 17:54 · JFK 20:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.