数字の組み合わせの合計

Question

できるだけ早く数学的な問題を解決したい。 私は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が除外されます。私は乗算のいくつかが繰り返されていることを知っています。例えば、3回の乗算で（1 * 2）が繰り返されます。どのようにして最小の乗算回数でこの問題を解決できますか？

申し訳ありません。おかげさまで

Answer 1

ここでは、乗算を繰り返したり、除算を使用して置き換えたりすることで「不正行為」しない方法です。アイデアは

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

これであなたの表現を交換することです一般的には、乗算回数は、（n-1）番目の三角形の数n *（n-1）/ 2 -1より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 

唯一の方法：4、および添加同じにカウント（しかし、それらの半分はちょうど1を追加している） - 中間階乗値がちょうど6に乗算の数を減らすために、又は一般的には2 * nがどのアルゴリズムが最も速いかを見つけるには、それらのうちの1つを1つの言語で実行し、タイマーを使用してそれぞれを実行します。

Answer 2

以下は、最も簡単な答えです。

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を掛け、変数resultに加算します。

Answer 3

あなただけの乗算の数を最小限にしたい場合は、このように、添加することによって、すべての乗算を置き換えることができます。ここでは

// 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 

Answer 4

は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));