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

Перечислите все разбиения натурального числа n на сумму натуральных слагаемых. Разбиения должны удовлетворять следующим условиям:

· Слагаемые в каждом разбиении упорядочены по невозрастанию.

· Все разбиения перечислены в лексикографическом порядке.

Вход. Одно натуральное число n (1 ≤ n ≤ 40).

Выход. Выведите все допустимые разбиения, каждое – в отдельной строке.

Пример входа	Пример выхода
4	1 1 1 1 2 1 1 2 2 3 1 4

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть n = x₁ + x₂ + … + x_k – разбиение числа n на натуральные слагаемые. Исходя из условия задачи, слагаемые любого разбиения должны удовлетворять неравенству:

x₁ ³ x₂ ³ … ³ x_k

Первое слагаемое x₁ может принимать значения от 1 до n, а каждое последующее x_i (2 £ i £ k) – значения от 1 до x_i-1.

Рекурсивная суть процедуры генерации разбиений состоит в следующем: если при разбиении числа n в качестве первого слагаемого выбрано x₁ (x₁ £ n), то далее следует сгенерировать все возможные разбиения числа n – x₁ на слагаемые, не превышающие x₁.

Реализация алгоритма

В массиве x будем генерировать разбиения числа n.

int x[50];

Функция f генерирует разбиения числа n и имеет три аргумента:

· pos – текущая позиция в массиве x;

· max – максимальное допустимое значение слагаемого, которое может находиться в позиции pos;

· n – текущее значение числа, которое необходимо разложить.

void f(int pos, int max, int n)

{

Если значение n стало равным нулю, это означает, что разбиение завершено, и текущее содержимое массива x представляет очередное разбиение. В этом случае выводим массив.

if (n == 0)

{

for (int i = 0; i < pos; i++)

printf("%d ", x[i]);

printf("\n");

return;

}

В позиции pos массива x может находиться любое число от 1 до min(max, n).

for (int i = 1; i <= min(max, n); i++)

{

x[pos] = i;

f(pos + 1, i, n - i);

}

}

Основная часть программы. Читаем входное значение n и запускаем функцию генерации всех возможных разбиений этого числа.

scanf("%d",&n);

f(0,n,n);