数字组合的总和

-2

我想以最快的方式解决数学问题。我有一组1到n之间的自然数，例如{1,2,3,4，n = 5}，我想计算一个像这样的公式：数字组合的总和

s = 1 * 2 * 3 * 4 + 1 * 2 * 3 * 5 + 1 * 2 * 4 * 5 + 1 * 3 * 4 * 5 + 2 * 3 * 4 * 5

您可以看到，总和中的每个元素都是乘法集合中有n-1个数字。例如在（1 * 2 * 3 * 4）中排除5，在（1 * 2 * 3 * 5）中排除4。我知道一些乘法是重复的，例如（1 * 2）在3次乘法中重复。如何用最少的乘法数来解决这个问题。

对不起，对英文不好。谢谢。

来源

2017-01-01 Bazinevis

这是一个编程问题？你有什么尝试？是否将分裂算作乘法或其他方式？（我可以想到使用一个或多个分部或互惠的几种方法。）那么添加又如何呢？每个乘法可以被多个加法替代，以便不使用乘法。 –

我不想使用划分。只有乘法和和。这是我想解决的一个更大问题的一部分。我尝试在树中构造数字，但是我找不到能够使用重复乘法的好结构。 – Bazinevis

您还没有回答有关使用添加替换所有乘法的问题。另外，你的目标是最小化时间（正如你在第一句中所说的那样）或乘法（如你在你几乎最后一句中所说的）或其他东西？ –

这是一种不会通过用重复加法或使用除法来代替乘法来“欺骗”的方法。我们的想法是用

1 * 2 * 3 * 4 + 5 *（1 * 2 * 3 + 4 *（1 * 2 + 3 *（1 + 2）））

此替换表达式对数字1到5使用了9次乘法。一般来说，我认为乘法计数将比第（n-1）个三角形数n *（n-1）/ 2 - 1少一个。这里是Python代码，用于存储中间阶乘值以减少乘法的数目只是6，或在一般2 * N - 4，和加法计数到相同的（但其中的一半是刚刚加入1）：

def f(n): 
    fact = 1 
    term = 2 
    sum = 3 
    for j in range(2, n): 
     fact *= j 
     term = (j + 1) * sum 
     sum = fact + term 
    return sum

的唯一办法找出哪个算法最快就是编码al其中一种语言使用计时器运行。

来源

2017-01-01 01:52:00

以下将是最直接的答案。

def f(n): 
    result = 0 
    nList = [i+1 for i in range(n)] 
    for i in range(len(nList)): 
     result += reduce(lambda x, y: x*y,(nList[:i]+nList[i+1:])) 
return result

演练 - 使用reduce函数将所有列表的长度n-1相加并添加到变量结果中。

来源

2017-01-01 01:37:40

我知道这种方式，但有没有一种方法可以使用复制乘法来更快地解决它？ – Bazinevis

@Bazinevis你的意思是递归？ – 2017-01-01 01:48:33

如果你只是希望尽量减少乘法运算的次数，可以通过添加替代所有的乘法，就像这样：

// Compute 1*2*…*n 
mult_all(n): 
    if n = 1 
     return 1 
    res = 0 
    // by adding 1*2*…*(n-1) an entirety of n times 
    for i = 1 to n do 
     res += mult_all(n-1) 
    return res 

// Compute sum of 1*2*…*(i-1)*(i+1)*…*n 
sum_of_mult_all_but_one(n): 
    if n = 1 
     return 0 
    // by computing 1*2*…*(n-1) + (sum 1*2*…*(i-1)*(i+1)*…*(n-1))*n 
    res = mult_all(n-1) 
    for i = 1 to n do 
     res += sum_of_mult_all_but_one(n-1) 
    return res

来源

2017-01-01 01:42:58

这里有一个答案，将用JavaScript工作。这不是最快的方式，因为它没有优化，但它应该工作，如果你想找到答案。

function combo(n){ 
var mult = 1; 
var sum = 0; 
for (var i = 1; i <= n; i++){ 
    mult = 1; 
    for (var j = 1; j<= n; j++){ 
     if(j != i){ 
      mult = mult*j; 
     } 
    } 
    sum += mult; 
} 
return (sum); 
} 

alert(combo(n));

来源

2017-01-01 01:47:45

你说得对。感谢您指出这一点。我会改变它。 –

数字组合的总和

回答

相关问题