Сумма комбинаций номеров

Question

Я хочу как можно быстрее решить математическую задачу. У меня есть набор натуральных чисел от 1 до n, например {1,2,3,4, n = 5}, и я хочу рассчитать формулу следующим образом:

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

, как вы можете видеть, каждый элемент в сумме является умножением n-1 чисел в множестве. Например, в (1 * 2 * 3 * 4) исключается 5, а в (1 * 2 * 3 * 5) исключается 4. Я знаю, что некоторые из умножений повторяются, например (1 * 2) повторяется в 3 из умножений. Как я могу решить эту проблему с наименьшим числом умножений.

Извините за плохой английский. Спасибо.

Answer 1

Это способ, который не «обманывает», заменяя умножение на повторное добавление или используя деление. Идея заключается в том, чтобы заменить выражение с

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

Это использовал 9 умножений для чисел с 1 по 5. В общем, я думаю, что количество умножений будет на единицу меньше, чем (n-1) -е треугольное число, n * (n - 1)/2 - 1. Вот код Python, который хранит промежуточное факторное значение, чтобы уменьшить количество умножений до всего лишь 6, или в общем 2 * п - 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 

Единственного способ найти, какой алгоритм является самым быстрым, - это кодировать все их на одном языке и запускать каждый с использованием таймера.

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 

Пошаговое руководство. Используйте функцию уменьшения, чтобы умножить весь список длины n-1 и добавить к результату переменной.

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