ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 98840
Условие
(Число разбиений; предлагалась на Всесоюзной олимпиаде
по программированию 1988 года) Пусть P(n) — число
разбиений целого положительного n на целые положительные
слагаемые (без учёта порядка, 1 + 2 и 2 + 1 — одно и то же
разбиение). При n = 0 положим P(n) = 1 (единственное
разбиение не содержит слагаемых). Построить алгоритм
вычисления P(n) для заданного n.
РешениеМожно доказать (это нетривиально) такую формулу для P(n):
P(n) = P(n - 1) + P(n - 2) - P(n - 5) - P(n - 7) + P(n - 12) + P(n - 15) +...
(знаки у пар членов чередуются, вычитаемые в одной паре
равны
(3q2 - q)/2 и
(3q2 + q)/2; сумма конечна — мы
считаем, что P(k) = 0 при k < 0).
Однако и без её использования можно придумать способ
вычисления P(n), который существенно эффективнее перебора
и подсчёта всех разбиений.
Обозначим через R(n, k) (для nчто позволяет заполнять таблицу значений функции R. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке