V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
MarioLuisGarcia
V2EX  ›  问与答

一个在实际工作中遇到的算法问题,比较基础,求教。

  •  
  •   MarioLuisGarcia · 2014-07-30 16:40:03 +08:00 · 3137 次点击
    这是一个创建于 3772 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有一个长度为n的列表,代表某物品的价格。

    玩家第一次购买该物品时,花费的价格是列表第一项的价格。依此类推,到第n次,花费的是列表第n项的价格。

    从第n+1次开始,每次购买花费的都是列表第n项的价格。

    在一个购买行为里,玩家可以购买多项该物品,如,购买次数为3。如该玩家是首次购买该物品,所花费的钱是列表第1,2,3项的总和。 如玩家在进行该购买行为时,已经买过n次了,那么该购买行为花费的金钱是3*n。

    现在我们仅知道玩家一个购买行为里的购买次数x (不知道他之前买了多少次), 以及该购买所花费的金钱y. 我们需要求出该玩家这个购买行为里所花费的金钱组成(第一个购买次数花了多少钱,第二个花了多少钱,第x个购买次数花了多少钱)。

    我已经想出应该怎么做,先看 x * 列表第n项 是否等于 y, 如果不等于,再看 (x-1) * 列表第n项 + 1 * 列表第n-1项 是否等于 y, 一直到 1* 列表第x项 + 1 * 列表第x-1项 + ... + 列表第1项 是否等于 y 即可

    但是,发现要把这个想法表达成程序语言表达式,对我而言有些困难(用的python)

    特此求教。
    28 条回复    2014-07-31 12:18:23 +08:00
    loryyang
        1
    loryyang  
       2014-07-30 17:07:32 +08:00   ❤️ 1
    除了遍历,其他无解吧。我的第一感觉是这样:

    1. 对于固定的购买次数x,我们只需要过一轮数据,就可以知道起点为i的x次购买总价格是多少,也就是一个[i, y]对,i从0到n
    2. 那么对于某个固定的y,从1的结果里面找到匹配项就行了。ps:匹配项可能会多于一个,这也是我感觉只能遍历的原因。

    复杂度最简单是n*x,当然,你第一步可以稍微优化下,大概是个n+x的复杂度

    想的不是很细致,LZ可以再看看
    mingkaidox
        2
    mingkaidox  
       2014-07-30 17:18:51 +08:00 via Android   ❤️ 1
    这个可能有多解,比如当第n次和第n-1次买价格一样的时候,可能要注意下。
    MarioLuisGarcia
        3
    MarioLuisGarcia  
    OP
       2014-07-30 17:31:08 +08:00
    @loryyang 怎么解大概想出来了,语言表达还在想。不过在提出这个问题后又狂想一阵,有个雏形了,测试中
    MarioLuisGarcia
        4
    MarioLuisGarcia  
    OP
       2014-07-30 17:31:36 +08:00
    @mingkaidox 为什么会有多解的情况?不是很明白。
    MarioLuisGarcia
        5
    MarioLuisGarcia  
    OP
       2014-07-30 18:23:23 +08:00
    @loryyang 好像可以实现了,不过方法有点dirty....
    MarioLuisGarcia
        6
    MarioLuisGarcia  
    OP
       2014-07-30 18:37:41 +08:00
    我的解法(X = 次数,Y = 钱, L = 列表,写法是python)

    T = 0
    while True:
    if X > T and T ==0:
    if L[-1]*(X-T) == Y:
    break
    else:
    T += 1
    elif X > T and T >=1:
    if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
    break
    else:
    T += 1
    elif X <= T:
    if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
    break
    else:
    T += 1
    MarioLuisGarcia
        7
    MarioLuisGarcia  
    OP
       2014-07-30 18:38:43 +08:00
    indentation因为v2ex显示问题不对了。
    MarioLuisGarcia
        8
    MarioLuisGarcia  
    OP
       2014-07-30 18:40:06 +08:00
    T = 0
    while True:
    if X > T and T ==0:
    if L[-1]*(X-T) == Y:
    break
    else:
    T += 1
    elif X > T and T >=1:
    if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
    break
    else:
    T += 1
    elif X <= T:
    if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
    break
    else:
    T += 1
    MarioLuisGarcia
        9
    MarioLuisGarcia  
    OP
       2014-07-30 18:40:27 +08:00
    再试一次排版,还是失败了。。。
    MarioLuisGarcia
        10
    MarioLuisGarcia  
    OP
       2014-07-30 18:41:01 +08:00
    T = 0
    while True:
    \ if X > T and T ==0:
    MarioLuisGarcia
        11
    MarioLuisGarcia  
    OP
       2014-07-30 18:41:28 +08:00
    看来有点弄不明白怎么在v2ex 缩进了。。。。
    qsl0913
        12
    qsl0913  
       2014-07-30 18:52:32 +08:00
    L=[1,2,3,4,5,5,4,3,2,1,1,1,1]
    X=5
    Y=15
    两个解
    qsl0913
        13
    qsl0913  
       2014-07-30 18:53:18 +08:00
    @MarioLuisGarcia markdown
    MarioLuisGarcia
        14
    MarioLuisGarcia  
    OP
       2014-07-30 18:56:14 +08:00
    @qsl0913 看来md的学习优先度要提前了.
    如果列表是递增的,即后一项一定大于或等于前一项,应该就不会出现你所说的情况了吧?
    MarioLuisGarcia
        15
    MarioLuisGarcia  
    OP
       2014-07-30 18:57:11 +08:00
    @qsl0913 oh my god, 难道我要用&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;来缩进代码? @天!
    MarioLuisGarcia
        16
    MarioLuisGarcia  
    OP
       2014-07-30 19:06:17 +08:00
    T = 0
    while True:
    if X > T and T ==0:
    if L[-1]*(X-T) == Y:
    break
    else:
    T += 1
    elif X > T and T >=1:
    if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
    break
    else:
    T += 1
    elif X <= T:
    if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
    break
    else:
    T += 1
    MarioLuisGarcia
        17
    MarioLuisGarcia  
    OP
       2014-07-30 19:06:36 +08:00
    ...从stackoverflow辅助过来也不行。。。
    MarioLuisGarcia
        18
    MarioLuisGarcia  
    OP
       2014-07-30 19:07:20 +08:00
    T = 0
    while True:
    * if X > T and T ==0:
    * if L[-1]*(X-T) == Y:
    * break
    *else:
    * T += 1
    * elif X > T and T >=1:
    * if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
    * break
    *else:
    * T += 1
    * elif X <= T:
    * if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
    * break
    *else:
    * T += 1
    wudikua
        19
    wudikua  
       2014-07-30 19:07:48 +08:00
    @MarioLuisGarcia ```code```
    wudikua
        20
    wudikua  
       2014-07-30 19:08:46 +08:00
    `code`
    wudikua
        21
    wudikua  
       2014-07-30 19:08:54 +08:00
    2b了。。。
    yxjxx
        22
    yxjxx  
       2014-07-30 19:57:50 +08:00
    @MarioLuisGarcia gist吧,v2目前不支持md呢
    lu18887
        23
    lu18887  
       2014-07-31 00:31:30 +08:00 via iPhone
    @wudikua 别逗!
    leafx
        24
    leafx  
       2014-07-31 02:18:28 +08:00
    n= [4, 3, 2, 1]
    x= 2
    y= 13
    so:
    1. *2+ *3 = (4+3) + (2*3) = y(13)
    2. *1+ *3 = 4 + (3*3) = y(13)
    --------------------------------------------------------
    希望你能理解我的用意,虽然概率小点,但是确实存在这样的情况
    MarioLuisGarcia
        25
    MarioLuisGarcia  
    OP
       2014-07-31 10:51:04 +08:00
    @leafx x = 2, y 为什么会等于 13? x 是表示购买的次数啊,一次只会花1次钱。x=2 , y最大是8呀。。
    loryyang
        26
    loryyang  
       2014-07-31 11:21:24 +08:00
    @MarioLuisGarcia 额,这个我也说不好,你多想想这种问题,慢慢的就会有解决思路了。思维是锻炼出来的。如果你觉得说不清楚,写伪代码即可,这个在程序员中间到不是最主要的问题
    leafx
        27
    leafx  
       2014-07-31 12:08:32 +08:00
    @MarioLuisGarcia 是啊, X表示的购买次数,第一次买2项物品,第二次买3项物品,好像符合你的逻辑额
    MarioLuisGarcia
        28
    MarioLuisGarcia  
    OP
       2014-07-31 12:18:23 +08:00
    @leafx y表示的是x次购买所花费的钱。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1105 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 22:40 · PVG 06:40 · LAX 14:40 · JFK 17:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.