Как разложить число на слагаемые
Перейти к содержимому

Как разложить число на слагаемые

  • автор:

Как разложить число на слагаемые

Vladosiya → Call for CERC 2021 archive

atcoder_official → Toyota Programming Contest 2023#7(AtCoder Beginner Contest 328) Announcement

Некропост

yaro → Разбор задач (Яндекс, раунд 2)

JaySharma1048576 → Invitation to CodeChef Starters 107 (Rated till 6-stars) — 8th November

wwwqqq7 → im suck in cp, wot need i to do?

Rl_a_667 → hard situation

mishkfrede → если вышел по разам то танцуй арамзамзам

t ourist → Codeforces Round #850 Editorial

karrigan0108 → How to do JOI19_TIMELEAP

Temirlan-Zh-027-7 → Tutorial for the Educational Codeforces Round 157 (Rated for Div. 2) A

BigBadBully → Contest Anxiety

Ali-M-027-7ba → My one question about contribution.

MikeMirzayanov → Please, read this

Imakf → Codeforces Round 906 Editorial

SHAHria365 → How can i improve number theory ?? suggestion please

JENXLS → Competitive Programming Tutoring

ch_egor → Pinely Round 2 Editorial

ICPCNews → ICPC 2023 Online Challenge powered by Huawei

Jorge_slime → How to learn HASHING ?

Tboros_kylie → sum of prefix sum with n loop

Некропост

gautam94 → Problem 386B two pointers method

-kirito- → TheForces Round #25 Editorial

Некропост

MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces

socoolhaina → Help in a problem — graphs

sevlll777 → Codeforces Round 908 (Div. 1, Div, 2) Editorial

разбить число на слагаемые

дано число
нужно посчитать количество возможных вариантов, как его можно разложить на слагаемые
причем каждое последующее слагаемое должно быть меньше предыдущего
например число 6
5+1
4+2
два возможных варианта

а с числом 10
9+1
8+2
7+3
7+2+1
6+4
6+3+1
6 вариантов

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Число разбиений на нечетные слагаемые
Нужно найти число способов ризбивки числа в виде суммы положительных целых нечетных чисел. ва.

Как разбить число на составляющие
Подскажіте пожалуйста хоть в каком направлении копать задача состоит в том что есть какоето число.

Разбить число 1234 на слагаемые
Здравствуйте. как разбить число 1234 на слагаемые. Т.е 1234=1+2+3+4. Спасибо

Разложить число на слагаемые
Доброго всем времени суток! Подскажите пожалуйста что я не правильно делаю. Нужно разложить целое.

Эксперт С++

476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
Если нужны сами разложения, то так:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
#include using namespace std; ifstream cin("input.txt"); ofstream cout("output.txt"); int a[1000000]; int n, cnt = 0; void p(int pos, int rest, int prev) { if(rest == 0) { cnt++; cout  n  " = "; for(int i = 0; i  pos-1; i++) cout  a[i]  " + "; cout  a[pos-1]  endl; } else { for(int i = 1; i  min(rest,prev-1); i++) { a[pos] = i; p(pos+1, rest - i, i); } } } int main() { cin >> n; p(0,n,n); cout  endl  cnt; }

Нахождение количества разбиений числа на слагаемые

Пусть [math]P(n, m, k)[/math] — количество разбиений числа [math]n[/math] на [math]m[/math] слагаемых, каждое из которых не превосходит [math]k[/math] . Имеет место следующее рекуррентное соотношение:

[math]P(n, m, k) = \left \P(n, m, k — 1) + P(n — k, m — 1, k), & 0 \lt m \leqslant n, 0 \lt k \leqslant n \\ P(n, m, n), & k \gt n \\ 1, & n = 0, m = 0 \\ 0, & \text \end \right. [/math]

Рассмотрим множество разбиений числа [math]n[/math] на [math]m[/math] слагаемых, каждое из которых не больше [math]k[/math] . Разделим его на две непересекающиеся группы — в первой будут все разбиения, которые не содержат в качестве старшего слагаемого [math]k[/math] . Таких разбиений [math]P(n, m, k — 1)[/math] . Во второй — все разбиения со старшим слагаемым [math]k[/math] . Их столько же, сколько разбиений числа [math]n — k[/math] на [math]m — 1[/math] слагаемое, каждое из которых не больше [math]k[/math] , то есть [math]P(n — k, m — 1, k)[/math] .

Количество всех разбиений числа равно [math]\sum\limits_^nP(n, i, n)[/math] . Реализация данного алгоритма методом динамического программирования с меморизацией будет иметь асимптотику [math]O(n^)[/math] .

Алгоритм за O(N 2 )

Обозначим [math]P(n,k)[/math] — количество разбиений числа [math]n[/math] на слагаемые, каждое из которых не превосходит [math]k[/math] . Оно удовлетворяет следующей рекурентной формуле:

[math]P(n,k) = \left \< \begin P(n,k - 1) + P(n - k, k), & 0 \lt k \leqslant n \\ P(n, n), & k \gt n \\ 1, & n = 0, k = 0 \\ 0, & n \neq 0 , k = 0 \end \right.[/math]

Заметим, что нам не нужно считать количество слагаемых [math]m[/math] в разбиении. Достаточно посчитать [math]P(n, k)[/math] — количество разбиений числа [math]n[/math] на произвольное количество слагаемых, каждое из которых не больше [math]k[/math] . Рассмотрим множество таких разбиений. Разделим его на две непересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое [math]k[/math] . Очевидно, таких разбиений [math]P(n, k — 1)[/math] . Во второй группе — те разбиения, в которые слагаемое [math]k[/math] вошло. Их количество совпадает с количеством разбиений числа [math]n — k[/math] на слагаемые, каждое из которых не превосходит [math]k[/math] , и равно [math]P(n — k, k)[/math] .

Количество всех разбиений числа [math]n[/math] равно [math]P(n,n)[/math] . Асимптотика [math]O(n^)[/math] .

Алгоритм за O(N 3/2 )

Рассмотрим алгоритм нахождения количества разбиений числа [math]n[/math] на слагаемые, который работает за [math] O(n \sqrt) [/math] .

Итак, обозначим количество таких разбиений за [math] p(n) [/math] .

Рассмотрим следующее бесконечное произведение:

[math] (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^ + \dots) \dots [/math]

После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять [math]x^[/math] , во второй — [math]x^[/math] и т.д., то их произведение будет равно [math]x^.[/math] Значит, после раскрытия скобок получится сумма мономов вида [math]x^[/math] .

Можно увидеть, что [math] x^n [/math] встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить [math]n[/math] как сумму [math]m_1 + 2m_2 + 3m_3 + . [/math] Каждому такому представлению отвечает разбиение числа [math]n[/math] на [math]m_1[/math] единиц, [math]m_2[/math] двоек и т.д. Таким образом, очевидно, получаются все разбиения, так как из первой скобки мы можем взять любое [math]x^[/math] , где [math]m_i \in [0 \dots \infty),[/math] то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при [math]x^n[/math] равен числу разбиений [math]p(n)[/math] .

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. Полагая [math]0 \leqslant x \lt 1[/math] , по формуле ее суммирования:

[math]1 + x + x^2 + x^3 + \dots = \frac[/math] , [math]1 + x^2 + x^4 + x^6 + \dots = \frac[/math] [math]\dots[/math] [math]1 + x^k + x^ + x^ + \dots = \frac[/math] [math]\dots[/math]

Запишем теперь производящую функцию последовательности [math]p(n)[/math] :

[math]p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac[/math] [math](1)[/math]

Рассмотрим произведение [math](1-x)(1-x^2)(1-x^3). [/math] , т.е. знаменатель правой части формулы [math](1)[/math] . Раскрывая в нём скобки, получим следующий результат:

[math](1 — x)(1 — x^2)(1 — x^3) . = 1 — x — x^2 + x^5 + x^7 — x^ — x^ + x^ + x^ — x^ — x^ + . [/math]

Показатели степеней в правой части — пятиугольные числа [2] , т.е. числа вида [math](3q^2 \pm q)/2[/math] , а знаки при соответствующих мономах равны [math](-1)^q[/math] . Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.

[math] \prod\limits_^\infty \left(1-x^k \right) = \sum\limits_^\infty (-1)^q x^>[/math]

Раскроем в этом произведении первые [math]22[/math] скобки. Мы получим выражение

где в квадратной скобке точками обозначены слагаемые, содержащие [math]x[/math] в более высокой степени, чем [math]22[/math] . Не будем выписывать эти члены, так как после умножения квадратной скобки на [math]1-x^[/math] , [math]1-x^[/math] и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид

Анализируя этот ряд, Эйлер пришел к выводу, что, если превратить бесконечное произведение

в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида [math](-1)^q x^>[/math] , где [math]q[/math] — натуральное число.

При раскрытии скобок в исходном произведении слагаемое [math]\pm x^N[/math] встретится столько раз, сколькими способами можно разбить число [math]N[/math] на различные слагаемые. При этом, если число слагаемых четно, то появляется [math]x^N[/math] , а если это число нечетно, то появляется [math]-x^N[/math] . Например, разбиению [math]12=5+4+2+1[/math] соответствует слагаемое [math](-x^5)(-x^4)(-x^2)(-x^1)=x^,[/math] а разбиению [math]12=5+4+3[/math] — слагаемое [math](-x^5)(-x^4)(-x^3)=-x^[/math] . Таким образом, коэффициент при [math]x^N[/math] в разложении [math]A[/math] в ряд равен разности между количеством разбиений [math]N[/math] на четное число различных слагаемых и количеством разбиений [math]N[/math] на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:

Если число [math]N[/math] не может быть представлено в виде [math]N =\frac[/math] , то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида [math]N =\frac[/math] разность между этими количествами равна [math](-1)^q[/math] .

Иными словами, если [math]q[/math] четно, то на одно больше разбиений на четное число слагаемых, а если [math]q[/math] нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга [3] . Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через [math]m[/math] , а число строк нижней трапеции через [math]n[/math] (на рис. 1 слева изображена диаграмма, для которой [math]m=2[/math] , [math]n=3[/math] ).

Рис. 1. [math]m = 2, n = 3[/math]

Преобразование 1. Предположим, что диаграмма содержит не менее двух трапеций, причем [math]m \leqslant n[/math] . В этом случае отбросим первую строку из [math]m[/math] точек, но удлиним последние [math]m[/math] строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.

Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но [math]n \geqslant m+1[/math] . Стираем верхнюю строку и к нижним [math]n-1[/math] строчкам приписываем [math]m[/math] точек.

Преобразование 2.Пусть теперь диаграмма опять содержит не менее двух трапеций, но [math]m \gt n[/math] . Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из [math] n [/math] точек) новой диаграммы. Это можно сделать, так как [math]m \gt n[/math] , и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась — новая диаграмма содержит еще одну строку.

Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если [math]n \leqslant m — 2[/math] (появляющаяся первая строка состоит из [math]n[/math] точек, она должна быть короче бывшей первой строки, уменьшившейся до [math]m-1[/math] точки).

Легко видеть, что описанные преобразования взаимно обратны — если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа [math]N[/math] , допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.

Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо [math]m=n[/math] , либо [math]m=n+1[/math] . В первом случае диаграмма содержит

точек, а во втором — на [math]n[/math] точек больше, т.е. [math]\frac[/math] .

Приведенные рассуждения показывают, что если [math]N[/math] не является числом вида [math]\frac[/math] , то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.

Умножим обе части равенства [math](1)[/math] на [math]\prod\limits_^\infty \left(1-x^k \right) [/math] и воспользуемся пентагональной теоремой:

[math] ( p(0) + p(1) x + p(2) x^2 + \dots)(1 — x — x^2 + x^5 + x^7 — x^ — x^ + \dots) = 1 [/math] [math](2)[/math]

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями [math]x[/math] пишем друг под другом:

[math] p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots [/math] [math] — p(0)x — p(1) x^2 — p(2) x^3 — p(3) x^4 — p(4) x^5 — p(5) x^6 — \dots [/math] [math] — p(0) x^2 — p(1) x^3 — p(2) x^4 — p(3) x^5 — p(4) x^6 — \dots [/math] [math]+ p(0) x^5 + p(1) x^6 + \dots [/math]

Так как [math]p(0) = 1[/math] , то оно сокращается с единицей справа. Так что, чтобы выражение [math](2)[/math] было удовлетворено при любом [math]x[/math] , все коэффициенты должны быть равны [math]0[/math] . Поэтому:

[math] p(1) = p(0) [/math] [math] p(2) = p(1) + p(0) [/math] [math] p(3) = p(2) + p(1) [/math] [math] p(4) = p(3) + p(2) [/math] [math] p(5) = p(4) + p(3) — p(0) [/math] [math]. [/math]

Получаем формулу Эйлера, позволяющую последовательно находить числа [math]p(n)[/math] :

[math] p(n) = p(n-1) + p(n-2)+ . + (-1)^ (p\left(n — \frac\right) + p\left(n — \frac\right)) [/math] .

Асимптотика [math] O(n \sqrt) [/math] получается следующим образом. Так как [math] n — \frac \geqslant 0 [/math] , то получаем [math] q [/math] порядка [math] \sqrt [/math] , а так как находим [math]n[/math] -е число, то получаем [math] O(n \sqrt) [/math] .

Примечания

  1. ↑Последовательность 000041 на OEIS
  2. ↑Википедия — Пятиугольные числа
  3. ↑Википедия — Диаграммы Юнга

См. также

  • Числа Стирлинга первого рода
  • Числа Стирлинга второго рода
  • Производящая функция

Источники информации

  • Wikipedia — Pentagonal number theorem
  • Вайнштейн Ф., Разбиение чисел. Журнал «Квант» № 11, 1988 год
  • Н.Я. Виленкин «Комбинаторика», 2007. стр. 138-141.

Разложение числа на слагаемые на Prolog

Есть две формулировки этой задачи. Первая: Нужно написать функцию, находящую все возможные композиции числа и его разбиения.
И композиции и разбиения являются вариантами разложения числа на слагаемые. При этом композиции учитывают порядок следования элементов, а разбиения — нет (на рисунке приведены примеры композиций). Вторая: Для заданных чисел n и k вычислите количество представлений числа n в виде суммы k слагаемых (перестановки слагаемых новым представлением не считаем). Например, разложение числа 7 на 3 слагаемых: 5+1+1
4+2+1
3+3+1
3+2+2 больше вариантов представления числа 7 тремя слагаемыми нет, поэтому результат равен 4. Нужен код для обоих.

25.03.2015 в 17:02 #2123

Обе задачи решаются рекурсивно. Пусть требуется разложить число Number на слагаемые без учета порядка их следования.
После генерации первого слагаемого ( Addend ) задача уменьшается, т.к. теперь требуется разложить Number-Addend .
Очевидно, в качестве слагаемого должны подставляться все числа в диапазоне от 1 до Number. Для генерации таких чисел можно использовать встроенную функцию between.

number_partitions(0, []):-!. number_partitions(Number, [Addend|TailComprosition]):- between(1, Number, Addend), TailNumber is Number - Addend, number_partitions(TailNumber, TailComprosition).

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

number_compositions(Number, Composition):- number_compositions(Number, 1, Composition).

Вспомогательная функция инициализирует начальное значение предыдущего слагаемого единицей.

number_compositions(0, _PreviousAddend, []):-!. number_compositions(Number, PreviousAddend, [Addend|TailComprosition]):- between(PreviousAddend, Number, Addend), TailNumber is Number - Addend, number_compositions(TailNumber, Addend, TailComprosition).

Генерация композиций отличается от разбиений лишь тем, что в качестве нижней границы функции between передается значение предыдущего слагаемого. Примеры разложения чисел приведены на снимках экрана.

08.12.2021 в 19:56 #8353
Реализация второго варианта задачи на SWI Prolog выглядит так:

expansion(0, []):-!. expansion(Value, [Component|TailComponents]):- between(1, Value, Component), TailValue is Value - Component, expansion(TailValue, TailComponents). expansion(Value, Size, Components):- length(Components, Size), expansion(Value, Components). unique_expansion(Value, Size, Variant):- findall(Components, expansion(Value, Size, Components), AllVariants), maplist(msort, AllVariants, SortedVariants), list_to_set(SortedVariants, Set), member(Variant, Set). count_expansions(Value, Size, Count):- findall(Components, unique_expansion(Value, Size, Components), AllVariants), length(AllVariants, Count).

Функция expansion\2 выполняет разложение числа на все возможные слагаемые без ограничения длины и без учета перестановок. На выходе она формирует список вариантов. Например [[1,2,3],[1,3,2]] . Работает она так:
1. Если число равно нулю — то его разложение — пустой список слагаемых.
2. Иначе выбирается число ( Component ) от 1 до Value , которое будет являться слагаемым. Выбирается число с помощью стандартной функции between.
3. Это слагаемое вычитается из разлагаемого числа, остаток обрабатывается (разлагается) рекурсивно.
4. К полученному от рекурсивного вызова результату дописывается наше слагаемое ( Component ). Итак, мы получили все возможные варианты разложения, но нужны не все, а только длины N. Для этого написана функция expansion\3 , которая дополнительным аргументом принимает количество слагаемых. С помощью стандартного предиката length накладывается ограничение на длину получаемого списка. Теперь получены все варианты разложения заданной длины, однако надо убрать варианты, являющиеся перестановками. То есть [1,1,2] и [1,2,1] — одно и тоже разложение. Чтобы убрать такие варианты — каждый список, задающий вариант надо отсортировать. Для этого к вариантам применяется стандартная функция msort , в других диалектах Prolog можно взять любую функцию сортировки отсюда. Функция sort , в отличии от msort формирует на выходе не список, а множество. Это значит что разложение [1,5,1] будет преобразовано в [1,5] . Так как такое преобразование в этом случае ненужно — используется msort . Для применения сортировки к каждому элементу списка используется функционал maplist . В списке отсортированных вариантов разложения нужно убрать повторы элементов. Для этого используется стандартная функция list_to_set , для других диалектов реализацию можно взять там. Так как в этом задании не требуется выводить все варианты, а требуется лишь посчитать их количество — то все варианты собираются в список с помощью предиката findall , а затем определяется его длина.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *