高效的算法来计算所有k乘积的和 [英] Efficient algorithm to calculate the sum of all k-products
问题描述
假设您得到一个由n
个数字组成的列表L
和一个整数k<n
.是否有一种有效的方法来计算L
中k
个不同数字的所有乘积之和?
Suppose you are given a list L
of n
numbers and an integer k<n
. Is there an efficient way to calculate the sum of all products of k
distinct numbers in L
?
例如,以L=[1,3,4,6]
和k=2
为例.然后我要寻找的号码是
As an example, take L=[1,3,4,6]
and k=2
. Then the number I am looking for is
1*3 + 1*4 + 1*6 + 3*4 + 3*6 + 4*6
.
您能想到一种避免生成所有大小为k
的子集的方法吗?
Can you think of a way of doing it which avoids generating all the subsets of size k
?
推荐答案
让F(X,k,n)为数组X的前n个元素的k乘积之和.
Let F(X,k,n) be the k-product sum of first n elements of array X.
F(X,k,n)= F(X,k,n-1)+ F(X,k-1,n-1)* X [n]
F(X,k,n) = F(X,k,n-1)+F(X,k-1,n-1)*X[n]
您可以使用动态编程解决的问题.复杂度= O(kn).
which you can solve using dynamic programming. Complexity = O(kn).
F(X,k,n)的结束条件:当n = k F(X,k,k)= X [1] * X [2] * ... * X [n]
End conditions for F(X,k,n): When n=k F(X,k,k) = X[1]* X[2]*...*X[n]
更多详细信息:
F(X,1,1) = X[1]
F(X,1,i) = F(X,1,i-1)+X[i] for i=2...n
For j=2..n:
For i = 1..k:
if i<j:
F(X,i,j) = F(X,i,j-1)+F(X,i-1,j-1)*X[j]
else if i==j:
F(X,i,j) = F(X,i-1,j-1)*X[j]
else:
pass
这篇关于高效的算法来计算所有k乘积的和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!