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

@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

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

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

	Разбиение на слагаемые 22.12.2023, 12:12. Показов 2632. Ответов 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 6236 / 2946 / 1047 Регистрация: 01.06.2021 Сообщений: 10,980
	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 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	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