Информация о задаче

Задача 98840

Тема:

[

Динамическое программирование (прочее)

]

Сложность: 4
Классы:

Прислать комментарий

Условие

(Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 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) +...

(знаки у пар членов чередуются, вычитаемые в одной паре равны (3q² - q)/2 и (3q² + q)/2; сумма конечна — мы считаем, что P(k) = 0 при k < 0). Однако и без её использования можно придумать способ вычисления P(n), который существенно эффективнее перебора и подсчёта всех разбиений. Обозначим через R(n, k) (для n $\ge$ 0, k $\ge$ 0) число разбиений n на целые положительные слагаемые, не превосходящие k. (При этом R(0, k) считаем равным 1 для всех k $\ge$ 0.) Очевидно, P(n) = R(n, n). Все разбиения n на слагаемые, не превосходящие k, разобьём на группы в зависимости от максимального слагаемого (обозначим его i). Число R(n, k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения n на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n - i на слагаемые, не превосходящие i (при i $\le$ k). Так что
$\begin{alignat*}{2} R(n,k)&=\sum\limits_{i=1}^{k} R (n-i,i)\qquad &&\text{при $k\le n$},\\ R(n,k)&=R (n,n)\qquad &&\text{при $k \ge n$}, \end{alignat*}$
что позволяет заполнять таблицу значений функции R.

Источники и прецеденты использования


книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	2
Название	Порождение комбинаторных объектов
параграф
Номер	7
Название	Подсчёт количеств
задача
Номер	2.7.1