Разбиение на слагаемые

@steriotip · Регистрация: 22.12.2023

Студворк — интернет-сервис помощи студентам

Дано число N. Ваша задача — посчитать количество способов разбить число N на слагаемые так, чтобы все слагаемые были различны между собой.
Формат ввода
В единственной строке входных данных содержится число
N, причем 1≤N≤2000.
Формат вывода
Выведите искомое количество способов разложить Nна слагаемые. Так как ответ может быть очень большим, выведите его остаток при делении на 1000000007.
Пример
Ввод
5
Вывод
5

@Parramon · 22.12.2023, 13:35

Как только будет продемонстрировано 5 способов разбиения 5 на различные слагаемые - так сразу и ответ будет....

@Red white socks · 22.12.2023, 14:07

Для небольших значений пойдет лобовой код (привел ниже).
Затем находите несколько первых значений, открываете OEIS, ищете последовательность, там вся нужная вам информация.

Python
1
2
3
4
5
6
7
8
9
def f(n, used=set(), p=10**9+7):
    if n:
        return sum(f(n-i, used | {i}) for i in range(1, n+1) if i not in used) % p
    return 1
 
 
#n = int(input())
for i in range (1, 10):
    print(f(i))

Добавлено через 22 минуты
Это читерский способ.
Честный - устранение недостатков "лобового" способа.
Требуется подсчет упорядоченных разбиений, т.е. разбиения, отличающиеся порядком, считаются различными. Поэтому мы не можем применить мемоизацию из-за слишком большого количества вариантов "исключений".
Но можно подметить, что
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\sum_{k=1}^{k(k+1) \le 2n} k!\cdot g(n,k)$
где g(n,k) - количество неупорядоченных разбиений на k уникальных слагаемых. А в неупорядоченных разбиениях нам нет нужды запоминать все уже использовавшиеся слагаемые, а достаточно запомнить только последнее и следующее слагаемое брать больше. И это уже с легкостью кэшируется.

YuS_2 · 22.12.2023, 17:28

Red white socks,
Так я не понял... по какой логике разбиваются числа? На целые, вещественные или какие?
Если вещественные - задача просто содержит в основе полнейшую глупость.
Если целые - таки просто разрывает от любопытства... 5 способов разбиения числа 5 - КАК?!
Покажите, кто-нибудь, что это за...

или 0 тоже считать слагаемым? В общем, опять партизанские условия задачи...

Но ведь нет... есть же условие:

Сообщение от steriotip

1≤N≤2000

@iSmokeJC · 22.12.2023, 17:52

Сообщение от YuS_2

или 0 тоже считать слагаемым?

Даже если и считать. Это ничего не меняет.

Сообщение от YuS_2

Покажите, кто-нибудь, что это за...

Присоединяюсь

YuS_2 · 22.12.2023, 18:20

Сообщение от iSmokeJC

Даже если и считать. Это ничего не меняет.

Не, ну тогда можно предположить...
1+4
2+3
1+4+0
2+3+0
5+0
- но это же противоестественно...

@Red white socks · 22.12.2023, 18:20

Сообщение от YuS_2

Так я не понял... по какой логике разбиваются числа

5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 2 + 3
5 = 1 + 4

YuS_2 · 22.12.2023, 18:23

Red white socks, ???
мде... и это различные способы?

@Red white socks · 22.12.2023, 18:31

YuS_2, да. Разбиения бывают неупорядоченные и упорядоченные. В первом случае перестановка слагаемых считается тем же самым разбиением, во втором - это различные способы. Здесь - второй вариант.
Грубо говоря, требуется подсчитать количество кортежей из различных чисел, в которых сумма равна заданному.

Добавлено через 4 минуты
https://oeis.org/A032020

YuS_2 · 22.12.2023, 18:46

Но это же нонсенс...
Тогда в условии просто необходимо указать, что способы:

Code
1
2
(1+2) != (2+1)
True

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

@Red white socks · 22.12.2023, 19:00

YuS_2, у нас уже была длиннющая беседа на тему условий).
С моей колокольни огрех небольшой. Да, как правило, в р/я литературе разбиения подразумеваются неупорядоченными, а упорядоченные называются композициями. Но встречал и такое, что и то и то обзывают разбиением.
В данном случае вопрос о том - упорядоченное или нет разруливается примером. И трактовка однозначная.

Не по теме:

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

Добавлено через 4 минуты

Сообщение от YuS_2

Тогда в условии просто необходимо указать, что способы:

Соглашусь, что было бы не лишним указать это явно. Но минималистский стиль это тоже стиль и имеет право на существование).

YuS_2 · 22.12.2023, 19:19

Сообщение от Red white socks

Но минималистский стиль это тоже стиль и имеет право на существование

Не в математике и тем более, не в программировании... и особенно в питоне, с его явно обозначенным дзеном, который даже в коде интерпретатора вшит.

Python
1
import this

для тех кто запамятовал...

Бритва Оккама, конечно, режет лишние сущности, но исключительно лишние... очень жаль, что не придумали клея имени кого-нибудь, который приклеивал бы недостающие.

@Parramon · 23.12.2023, 01:55

Сообщение от Red white socks

5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 2 + 3
5 = 1 + 4

Согласитесь, что у ТС было "слагаемые". Т.е. минимум два (хотя может и больше, там не понятно). Но тогда к Вашему

Сообщение от Red white socks

5 = 5

должно добавляться "+0", что, автоматически, добавляет "0+5", шестой вариант.

@Royal_X · 23.12.2023, 09:51

Parramon, согласен. Я в словарях проверил слово "слагаемое" - везде написано, что это:
1) число, которое складывается с другим числом в арифметическом действии сложения (мат. значение)
2) то, что вместе с чем-нибудь другим образует какое-либо целое (перен. значение).
В обоих значениях нужно ещё что-то другое.
Соответственно, число 5 слагаемым назвать нельзя!
Сложение, в отличие от инкремента, это бинарная математическая операция. У бинарной операции два аргумента. Аргументы при сложении называются слагаемыми. Именно из-за того, что сложение это бинарная операция, на него действуют свойства коммутативности, ассоциативности и дистрибутивности.
Число 5 можно назвать слагаемым только в паре с 0.
Но тогда по вышеупомянутой логике нужно писать оба варианта:
5 + 0
0 + 5

YuS_2 · 23.12.2023, 11:34

Сообщение от Parramon

Согласитесь, что у ТС было "слагаемые". Т.е. минимум два

Именно! Если число разбивается, то должно быть, минимум два слагаемых... допустим (просто допустим), что слагаемое может быть и одно, но тогда при чем тут разбиение? Логики в этом нет. Ок, можем пока отбросить это предположение, ибо явное противоречие с разбиением.
Ещё, можем допустить, что 0 тоже может быть слагаемым, вот тогда, вариант отсюда, наиболее подходящий под показанный пример. И логика с перестановкой слагаемых, сразу же становится ненужной. Но опять же, надо бы уточнить, а является ли разбиением такая запись числа 5: (5+0)? Т.е. слагаемые-то в наличии, но разбиение ли это? Ведь, исходное число осталось неизменным... вот, в чем вопрос...

В общем, полная жуть там, с пониманием великий русский языка, особенно если задача тупо "переведена", например, с аглицкого, но без корректировки в терминах... составители - какие уж есть...

Добавлено через 3 минуты

Сообщение от Parramon

автоматически, добавляет "0+5", шестой вариант.

там автоматически, добавляется ещё небольшая кучка вариантов, т.к. 0 может быть слагаемым и в других вариантах: 2+3, 1+4 и т.д.

@Red white socks · 23.12.2023, 15:33

Уважаемые Parramon, Royal_X, YuS_2, стоило отойти на минутку...
Ну что ж, господа, шах и мат! Уложили на обе лопатки!
Но я предлагаю на этом не останавливаться и сообщить об этом открытии миру.
Предлагаю начать с Википедии:
Разбиение числа
Композиция числа
ввязаться в войну правок. Это нелегкое дело, но справедливость за нами и я верю в победу!
Потом начать разбор литературы. Вот чтоб долго не ходить взял первое попавшееся, что у меня есть: Кнут, Искусство программирования. т.1. Основные алгоритмы.
И что я вижу - это издевательство над русским языком и там (скрин прилагаю)
Запись числа в виде суммы целых положительных чисел, а в пример включает 5 = 5. Я считаю, что это полное безобразие и так оставлять нельзя! Нужно писать Дональду, и хотя бы в следующих изданиях привести текст к виду, который удовлетворил бы нас.
И знаете, что-то мне кажется, что этот бардак повсеместно. Но ведь трудностей мы не боимся? Положим жизнь на восстановление справедливости! Сами не успеем - завещаем детям!

Parramon, Royal_X, YuS_2, я правильно понял ваш посыл?

@Parramon · 24.12.2023, 11:41

Уважаемый Red white socks, Вы "либо трусы наденьте, либо крестик снимите". В цитируемом Вами Д. Кнуте написано, что 5 разбивается 7-ю способами, а Ваш код выдает 5

Будем Дональду писать? Или сразу в Спортлото?

PS А давайте еще отрицательные слагаемые добавим? Для куражу!

PPS: ТС давно покинул тему, а мы тут развели....

@thyrex · 24.12.2023, 13:00

Как нельзя кстати появилась тема Разбиение на слагаемые - 1 Рекурсия
Чтобы прекратить обмен любезностями (с переходом на трусы и крестики) по поводу числа 5, посмотрите все возможные его разбиения (а их аккурат 7) в примере выходных данных, отбросьте варианты, где слагаемые совпадают, и добавьте варианты, которые отличаются порядком следования слагаемых, и вуаля - видим тот вариант, который Red white socks написал в сообщении #7. Вот такая c'est la vie

@Royal_X · 24.12.2023, 13:20

Сообщение от thyrex

c'est la vie

c'est de la merde, mec

В статье Composition (combinatorics) всё прекрасно объясняется, в том числе приводятся примеры композиции числа 5 с учетом разных правил. Причем, данная статья, в отличие от тупых условий, которые публикуются на форуме, не содержит слова "слагаемое" (addend, summand).
Я в посте Разбиение на слагаемые уже объяснил, что одно единственное число слагаемым не может являться. А вот касательно того, кто понял этот пост, а кто нет, je m'en fous royalement

YuS_2 · 24.12.2023, 15:00

Подведем итог:
Пренебрежение терминами порождает неясности/двусмысленности и прочую неразбериху...
Пренебрежение терминами в задачах для обучаемых, порождает полный хаос в знаниях на выходе, т.е. полуспециалистов с нечеткими знаниями.
Как итог - споры на ровном месте, вокруг ничего. Ну и куда же без этого: И ракеты, производимые полуспециалистами, могут, с большой долей вероятности, падать на Луну... или не взлетать вообще...

Можно поёрничать высокопарным слогом о незначительности споров вокруг задач, можно обратить внимание на неверную постановку задачи, причем именно тех, кто пытается таки решать (но не "списывать"), а можно просто пройти мимо...
Каждый вправе выбрать свой путь на дороге знаний и уж тем более, вправе самостоятельно выбрать, кому и как указывать правильное направление пути.

Добавлено через 6 минут
"Помимо математических способностей, жизненно важным качеством программиста является исключительно хорошее владение родным языком."©Edsger W. Dijkstra

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@steriotip 0 / 0 / 0 Регистрация: 22.12.2023 Сообщений: 5

	Разбиение на слагаемые 22.12.2023, 12:12. Показов 2533. Ответов 20 Метки help me, help me please, python (Все метки) Дано число N. Ваша задача — посчитать количество способов разбить число N на слагаемые так, чтобы все слагаемые были различны между собой. Формат ввода В единственной строке входных данных содержится число N, причем 1≤N≤2000. Формат вывода Выведите искомое количество способов разложить Nна слагаемые. Так как ответ может быть очень большим, выведите его остаток при делении на 1000000007. Пример Ввод 5 Вывод 5 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	22.12.2023, 13:35
	Как только будет продемонстрировано 5 способов разбиения 5 на различные слагаемые - так сразу и ответ будет.... 2

YuS_2 Любознательный 7406 / 2256 / 360 Регистрация: 10.03.2016 Сообщений: 5,216
	22.12.2023, 18:23
	Red white socks, ??? мде... и это различные способы? 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	22.12.2023, 18:31
	YuS_2, да. Разбиения бывают неупорядоченные и упорядоченные. В первом случае перестановка слагаемых считается тем же самым разбиением, во втором - это различные способы. Здесь - второй вариант. Грубо говоря, требуется подсчитать количество кортежей из различных чисел, в которых сумма равна заданному. Добавлено через 4 минуты https://oeis.org/A032020 1

@Royal_X 6221 / 2919 / 1046 Регистрация: 01.06.2021 Сообщений: 10,807
	23.12.2023, 09:51
	Parramon, согласен. Я в словарях проверил слово "слагаемое" - везде написано, что это: 1) число, которое складывается с другим числом в арифметическом действии сложения (мат. значение) 2) то, что вместе с чем-нибудь другим образует какое-либо целое (перен. значение). В обоих значениях нужно ещё что-то другое. Соответственно, число 5 слагаемым назвать нельзя! Сложение, в отличие от инкремента, это бинарная математическая операция. У бинарной операции два аргумента. Аргументы при сложении называются слагаемыми. Именно из-за того, что сложение это бинарная операция, на него действуют свойства коммутативности, ассоциативности и дистрибутивности. Число 5 можно назвать слагаемым только в паре с 0. Но тогда по вышеупомянутой логике нужно писать оба варианта: 5 + 0 0 + 5 2

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	23.12.2023, 15:33
	Уважаемые Parramon, Royal_X, YuS_2, стоило отойти на минутку... Ну что ж, господа, шах и мат! Уложили на обе лопатки! Но я предлагаю на этом не останавливаться и сообщить об этом открытии миру. Предлагаю начать с Википедии: Разбиение числа Композиция числа ввязаться в войну правок. Это нелегкое дело, но справедливость за нами и я верю в победу! Потом начать разбор литературы. Вот чтоб долго не ходить взял первое попавшееся, что у меня есть: Кнут, Искусство программирования. т.1. Основные алгоритмы. И что я вижу - это издевательство над русским языком и там (скрин прилагаю) Запись числа в виде суммы целых положительных чисел, а в пример включает 5 = 5. Я считаю, что это полное безобразие и так оставлять нельзя! Нужно писать Дональду, и хотя бы в следующих изданиях привести текст к виду, который удовлетворил бы нас. И знаете, что-то мне кажется, что этот бардак повсеместно. Но ведь трудностей мы не боимся? Положим жизнь на восстановление справедливости! Сами не успеем - завещаем детям! Parramon, Royal_X, YuS_2, я правильно понял ваш посыл? Миниатюры 1

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	24.12.2023, 11:41
	Уважаемый Red white socks, Вы "либо трусы наденьте, либо крестик снимите". В цитируемом Вами Д. Кнуте написано, что 5 разбивается 7-ю способами, а Ваш код выдает 5 Будем Дональду писать? Или сразу в Спортлото? PS А давайте еще отрицательные слагаемые добавим? Для куражу! PPS: ТС давно покинул тему, а мы тут развели.... 1

@thyrex 14449 / 7488 / 1582 Регистрация: 06.09.2009 Сообщений: 27,132
	24.12.2023, 13:00
	Как нельзя кстати появилась тема Разбиение на слагаемые - 1 Рекурсия Чтобы прекратить обмен любезностями (с переходом на трусы и крестики) по поводу числа 5, посмотрите все возможные его разбиения (а их аккурат 7) в примере выходных данных, отбросьте варианты, где слагаемые совпадают, и добавьте варианты, которые отличаются порядком следования слагаемых, и вуаля - видим тот вариант, который Red white socks написал в сообщении #7. Вот такая c'est la vie 2

YuS_2 Любознательный 7406 / 2256 / 360 Регистрация: 10.03.2016 Сообщений: 5,216
	24.12.2023, 15:00
	Подведем итог: Пренебрежение терминами порождает неясности/двусмысленности и прочую неразбериху... Пренебрежение терминами в задачах для обучаемых, порождает полный хаос в знаниях на выходе, т.е. полуспециалистов с нечеткими знаниями. Как итог - споры на ровном месте, вокруг ничего. Ну и куда же без этого: И ракеты, производимые полуспециалистами, могут, с большой долей вероятности, падать на Луну... или не взлетать вообще... Можно поёрничать высокопарным слогом о незначительности споров вокруг задач, можно обратить внимание на неверную постановку задачи, причем именно тех, кто пытается таки решать (но не "списывать"), а можно просто пройти мимо... Каждый вправе выбрать свой путь на дороге знаний и уж тем более, вправе самостоятельно выбрать, кому и как указывать правильное направление пути. Добавлено через 6 минут "Помимо математических способностей, жизненно важным качеством программиста является исключительно хорошее владение родным языком."©Edsger W. Dijkstra 0