Python3如何创建部分产品

Question

我有一个很长的名单（大号码）的列表，让我们说，例如：

a=[4,6,7,2,8,2]

我需要得到这个输出：

b=[4,24,168,336,2688,5376]

其中每个b[i]=a[0]*a[1]...*a[i]

我想用这种方式递归地做到这一点：

b=[4] + [ a[i-1]*a[i] for i in range(1,6)] 

但（错误的）结果是：[4, 24, 42, 14, 16, 16]

我不想计算的所有产品每一次，我需要一个有效的方式（如果可能），因为列表很长

目前这个工作对我来说：

b=[0]*6 
b[0]=4 

for i in range(1,6): b[i]=a[i]*b[i-1] 

但它的速度太慢。有任何想法吗？是否有可能避免“for”或以其他方式加速？

Answer 1

您可以逐步计算产品，因为每次下一次计算都会严重依赖于前一次计算。

我的意思是：
1）计算该产品的第一i - 1号
2）第i个产品将等于a[i] *最后i - 1数字

的产品时调用此方法dynamic programming

动态规划（也称为动态优化）是由它分解成更简单的子问题的集合，每个解决这些subpro的解决复杂问题的方法blems只有一次，和存储他们的解决方案

这是实现：

a = [4, 6, 7, 2, 8, 2] 
b = [] 

product_so_far = 1 

for i in range(len(a)): 
    product_so_far *= a[i] 
    b.append(product_so_far) 

print(b) 

该算法的工作在线性时间（O(n)），这是最有效的复杂性，你会得到这样的任务

如果你想有一个小的优化，可以生成b列表到预定长度（b = [0] * len(a)）和，而不是附加，你会在一个循环做到这一点： b[i] = product_so_far