Python - 我不知道如何在这段代码中工作

Question

我的老师给了我这个代码:

def n_o_c(Q,v):  
    M=[None]*(Q+1)  
    m={}  
    M[0]=0  
    for q in xrange(1,Q+1):  
        M[q]=min(M[q-a]+1 for a in v if q-a>=0)    
    return M[Q],m  

print n_o_c(18,[1,2,5])  

首先我解释一下脚本，这是一个假设的硬币机，我必须知道我需要多少硬币才能支付 Q 数量的 v 个硬币(我们必须尽可能少地使用 IE 来获得 18 个 3x5 硬币、1x2 硬币和 1x1 硬币)

我不明白 M[q] 行是什么意思，我尝试打印 M，结果是从 1 到 18 的每个数字需要多少硬币才能完成该数字。M=[0,1,1,2,2,3,2,2,3,3,2,3,3,4,4,3,4,4,5]q=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]

有人可以解释一下这个分钟是如何工作的吗？

我已经完成了(我知道这不是解决练习的好方法，但我不知道更好的方法)。已解决:

def n_o_c(Q,v):  
    M=[None]*(Q+1)  
    m={}  
    M[0]=0  
    for q in xrange(1,Q+1):  
        M[q]=min(M[q-a]+1 for a in v if q-a>=0)
    monedas=0
    total=Q
    m=[] # did this to change dictionary to array
    while(monedas<M[Q]):
        for a in v[::-1]:
            if total-a >= 0:
                total = total-a
                monedas = monedas +1
                m.append(a)
                break #I forget this break
    return M[Q],m  

print n_o_c(18,[1,2,5])  

Answer 1

min 函数是简单的部分:

Return the smallest item in an iterable

棘手的一点是，这个可迭代是怎么回事？

M[q]=min(M[q-a]+1 for a in v if q-a>=0)    

那个(M[q-a]+1 for a in v if q-a>=0)称为生成器表达式；更一般地说，这是一种理解。

开始于List Comprehensions在官方教程中了解一般理解如何工作，然后 Iterators以及以下两节(生成器和生成器表达式)来了解生成器表达式的不同之处。*

但我可以在这里总结一下，至少足以让您入门。

首先，列表理解:

[M[q-a]+1 for a in v if q-a>=0]

这意味着您想要构建一个列表，就像将其展开到这样的循环中一样:

value = []
for a in v:
    if q-a>=0:
        value.append(M[q-a]+1)
M[q] = min(value)

或者，更直观地，尝试大声朗读:每个 M[q-a]+1 的列表对于每个 a在v如果q-a>=0作为一个英语句子是有意义的，并且与 Python 的含义完全相同。 (如果您有数学背景，您可能想从设置显示的角度来考虑它，但我假设您没有。)

生成器表达式执行相同的操作，只不过它不是构建列表，而是在迭代列表时根据需要创建值。您可以将其视为一种暂时不会浪费内存或时间的魔法列表。要在 Python 中拼写它，只需转动方括号 []放入括号 () (在这种情况下您可以省略它，因为 min 调用中已经有括号)。要大声朗读，只需保留“列表”部分即可。

<小时/>

_{* 一旦您了解了这一点，如果您想了解更多信息，请查看 itertools 模块，读取Generator Tricks for System Programmers由 David Beazley 和 google 提供的 Greg Ewing 关于生成器的演示。}