Розбиття на доданки#2390

Розбиття на доданки (Розбір)

Нехай $n = x_{1} + x_{2} + ... + x_{k}$ n = x_1 + x_2 + ... + x_k — розбиття числа $n$ на натуральні доданки. Згідно з умовою задачі, доданки будь-якого розбиття мають задовольняти нерівність:

x_{1} \geq x_{2} \geq ... \geq x_{k}

x_1 \ge x_2 \ge ... \ge x_k

Перше доданок $x_{1}$ x_1 може приймати значення від $1$ до $n$ , а кожне наступне $x_{i} (2 \leq i \leq k)$ x_i~(2 \le i \le k) — значення від $1$ до $x_{i - 1}$ x_{i-1}.

Рекурсивна суть процедури генерації розбиттів полягає в наступному: якщо при розбитті числа $n$ в якості першого доданка обрано $x_{1} (x_{1} \leq n)$ x_1~(x_1 \le n), то далі слід згенерувати всі можливі розбиття числа $n - x_{1}$ n - x_1 на доданки, що не перевищують $x_{1}$ x_1.

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

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

int x[50];

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

$p os$ — поточна позиція в масиві $x$ ;
$ma x$ — максимальне допустиме значення доданка, яке може знаходитися в позиції $p os$ ;
$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;
  }

C++

У позиції $p os$ масиву $x$ може знаходитися будь-яке число від $1$ до $min (ma x, n)$ 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);