Как посчитать сумму всех перестановок целого числа

0 / 631

Вычислить сумму перестановок цифр Условия задачи:

Может ли читатель назвать сумму всех целых чисел, которые можно составить из четырех цифр 1, 2, 3, 4? То есть сложение всех таких чисел, как 1 234, 1 423, 4 312 и т. д. Можно, конечно, выписать их все и сделать сложение, но интерес заключается в том, чтобы найти очень простое правило для суммы всех чисел что можно сделать с четырьмя различными цифрами, выбранными всеми возможными способами, но исключая ноль?

Есть два способа решить эту головоломку: один — перебрать все перестановки целого числа и суммировать каждую из перестановок вместе, что довольно просто, второй — найти корреляцию между этими перестановками и вывести формулу для той же самой. который можно использовать для любого числа. В этом блоге мы рассмотрим оба подхода.

Ниже фрагмент кода возвращает сумму всех перестановок целого числа методом грубой силы: -

function permuteAndCalcSum(prefix, string, permute_sum) { var n = string.length; if (n === 0) { permute_sum += parseInt(prefix); return permute_sum; } else { for (var index = 0; index < n; index++) { permute_sum = permuteAndCalcSum(prefix.concat(string[index]), string.slice(0, index).concat(string.slice(index + 1, n)), permute_sum); } } return permute_sum; }

Логика приведенного выше кода довольно проста, он рекурсивно передает подстроки в функцию permuteAndCalcSum() для разных префиксов один за другим, скажем, например, для таких префиксов, как 1,2,3,4 для строки '1234', и повторяет тот же процесс рекурсивно для соответствующих подстрок: 234, 134, 124, 123, снова разбивает эти подстроки на более мелкие подстроки, пока не будет выполнено базовое условие.

Ниже приведены перестановки, полученные этой функцией для чисел 123 и 1234.

Permutations of 123: 123 132 213 231 312 321 Permutations of 1234: 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

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

В случае 1234 комбинация цифр, которая повторяется для каждой из перестановок целого числа, равна

4 4 3 3 2 2
4 4 3 3 1 1
4 4 2 2 1 1
3 3 2 2 1 1

что означает 6 раз, что равно (lengthOfNumber -1) = 4–1 = 3! раз каждая из цифр 1,2,3,4 повторяется..

Для числа 123 комбинация цифр:

3 3 2 2 1 1

что означает 2 раза, что равно (lengthOfNumber -1) = 3–1 = 2! раз каждая из цифр 1,2,3 повторяется.

если мы суммируем эти полученные таким образом цифры, мы получаем сумму каждой из цифр перестановок целого числа. Это можно выразить следующим образом:

4*6! + 3*6! + 2*6! + 1*6! = (4+3+2+1)*6! = Сумма всех цифр * (n-1)! где n = количество цифр в целом числе. В этом случае, поскольку это первые n натуральных чисел без повторений, сумма цифр может быть представлена ​​как n(n+1)/2, поэтому окончательная формула суммы каждой из цифр в разрядах единиц, десятков, сотен и тысяч будет n(n+1)/2 * (n-1)!.

Теперь у нас есть сумма, представленная каждой цифрой в перестановке, легко получить сумму всех целых чисел, суммируя номиналы каждой из сумм цифр, используя степени 10, поскольку это десятичное число.

Итак, окончательная сумма всех перестановок = [10(n-1)+ 10(n-2)+…….+10(n-n)] * Сумма всех цифр * (n-1)! = [10(n-1)+ 10(n-2)+…….+10(n-n)] * (n(n+1)/2) * (n-1)! — — —(1)

Мы можем использовать формулу, приведенную в уравнении (1), для вычисления суммы всех возможных перестановок заданного целого числа. Эта формула также работает для целых чисел с повторяющимися цифрами.

Ниже фрагмент кода представляет приведенную выше формулу (1) с использованием javascript:

function calcSumFormula(length) { var formula_sum = 0; for (var i = length - 1; i >= 0; i--) { formula_sum += Math.pow(10, i); } formula_sum = (length * (length + 1) / 2) * formula_sum * factorial(length - 1); return formula_sum; }

Формула и алгоритм грубой силы являются общими и могут быть применены к любому числу.

Объединение всего вышеперечисленного в один jsfiddle: -

Надеюсь, вам понравилось это читать. Лайкните нас на Golibrary за интересное чтение.

Комментарии

Комментарии

Теги :алгоритмыматематикачислоперестановкиголоволомкисумма

Первоначально опубликовано на www.golibrary.co 16 августа 2017 г.