Somme des combinaisons de nombres

Question

Je veux résoudre un problème mathématique le plus rapidement possible. J'ai un ensemble de nombres naturels entre 1 et n, par exemple {1,2,3,4, n = 5} et je veux calculer une formule comme ceci:

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

comme vous pouvez le voir, chaque élément de la somme est une multiplication de n-1 nombres dans l'ensemble. Par exemple dans (1 * 2 * 3 * 4), 5 est exclu et dans (1 * 2 * 3 * 5), 4 est exclu. Je sais que certaines des multiplications sont répétées, par exemple (1 * 2) est répété dans 3 des multiplications. Comment puis-je résoudre ce problème avec le moins de multiplications possibles.

Désolé pour un mauvais anglais. Merci.

Answer 1

Voici une façon de ne pas "tricher" en remplaçant la multiplication par une addition répétée ou en utilisant la division. L'idée est de remplacer l'expression avec

1 * 2 * 3 * 4 + 5 * (1 * 2 * 3 + 4 * (1 * 2 + 3 * (1 + 2)))

Cette J'ai utilisé 9 multiplications pour les nombres 1 à 5. En général, je pense que le nombre de multiplications serait inférieur au (n-1) ème nombre triangulaire, n * (n - 1)/2 - 1. Voici le code Python qui stocke valeurs factorielles intermédiaires afin de réduire le nombre de multiplications à seulement 6, ou en général 2 * n - 4, et l'addition comptent au même (mais la moitié d'entre eux sont simplement en ajoutant 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 

la seule façon pour trouver quel algorithme est le plus rapide est de coder al l d'entre eux dans une langue, et exécutez chacun en utilisant une minuterie.

Answer 2

Ce qui suit serait la réponse la plus directe. Procédure pas à pas: utilisez la fonction de réduction pour multiplier toutes les listes de longueur n-1 et les ajouter au résultat de la variable.

Answer 3

Si vous voulez juste réduire le nombre de multiplications, vous pouvez remplacer tous les multiplications par des additions, comme ceci:

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

Voici une réponse qui fonctionnerait avec javascript. Ce n'est pas le moyen le plus rapide car il n'est pas optimisé, mais il devrait fonctionner si vous voulez juste trouver la réponse.

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