Разложение числа на слагаемые
Этот онлайн калькулятор выводит все представления числа n в виде суммы положительных целых чисел.
Данный онлайн калькулятор для введенного числа в диапазоне от 1 до 60 выводит все его представления в виде суммы положительных целых чисел, а также выводит количество таких представлений.
В математике представление числа в виде суммы положительных целых чисел называется разбиением натурального числа n, при этом в канонической записи разбиения слагаемые перечисляются в невозрастающем порядке. Описание алгоритма генерации всех разбиений можно найти под калькулятором.
Разбиение натурального числа
Задача разложения числа на слагаемые
В большинстве источников, которые можно легко найти поиском, приводится рекурсивный алгоритм разложения числа на слагаемые. В данном же калькуляторе, в силу технических причин, используется итеративный алгоритм. Логика алгоритма была взята из статьи на Хабре.
Так как логика алгоритма достаточно лаконичная, приведу ее целиком (с некоторыми комментариями):
Дано: исходный массив в виде единиц — А (1,1,1,1,1).
Размерность массива соответствует числу n, все разложения которого мы ищем.
0) Если получили сумму, тогда остановка алгоритма.
Как и автор статьи, я суммирую элементы в массиве, в конце должен остаться только один элемент с индексом 0, численно равный n.
1) Двигаясь по массиву слева направо, искать в массиве А первый минимальный элемент — x,
последний элемент не учитывается (не участвует в поиске минимального).
Нам нужно как значение элемента, так и его позиция в массиве. Поэтому я не пользуюсь встроенными в Javascript функциями типа min и findIndexOf, а использую одну итерацию по массиву, запоминая как текущий минимальный элемент, так и его позицию, а также сумму до текущего минимального элемента включительно (сумма понадобится ниже).
2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).
Здесь прибавляется единица, и используется метод splice
3) Разложить сумму всех элементов после измененного элемента — x – на единицы.
Здесь добавляем единицы, используя ранее подсчитанную частичную сумму.
Код алгоритма на Javascript приведен ниже (разбиения выводятся в консоль):
function split(n) {
var temp = [];
for(var i = 0; i ＜ n; ++i) temp.push(1);
while(temp[0] != n)
{
console.log(temp);
var min = temp[0];
var minindex = 0;
var sum = temp[0];
var tempsum = temp[0];
for(var j = 1; j ＜ temp.length - 1; ++j) {
tempsum += temp[j];
if (min ＞ temp[j]) {
min = temp[j];
minindex = j;
sum = tempsum;
}
}
temp[minindex] += 1;
sum += 1;
temp.splice(minindex+1);
for (var k = 0; k ＜ n - sum; ++k) temp.push(1);
}
console.log([n]);
}Остается добавить, что, как и в любой другой комбинаторной задаче, число разбиений экспоненциально зависит от числа n. Если для 10 это 42, то для 50 это уже 204 226, а для 100 - 190 569 292. В данном калькуляторе установлено ограничение в 60, что дает 966 467 разложений и считается на моем ноутбуке примерно 12 секунд. При 100 у браузера заканчивалась память и он падал.
Зависимость числа разбиений от n является числовой последовательностью A000041 в онлайн энциклопедии целочисленных последовательностей и обладает рядом некоторых интересных свойств.
Комментарии