type razb = array[0..100000] of longint;
var n, i, l, k : longint;
    x : razb;
 
procedure next(var x : razb; var l : longint);
var i, j, s : longint;
begin
  i := l - 1;
  s := x[l];
  while (i > 1) and (x[i - 1] <= x[i]) do
    begin
      s := s + x[i];
      dec(i);
    end;
    inc(x[i]);
    l := i + s - 1;
    for j := i + 1 to l do
      x[j] := 1;
end;
 
begin
  readln(n);
  l := n;
  for i := 1 to l do
    x[i] := 1;
    for i := 1 to n do
      write(x[i], ' ');
      writeln;
      repeat
        next(x, l);
        inc(k);
        for i := 1 to l do
          write(x[i], ' ');
          writeln;
      until l = 1;
end.



Лекция 6. Задача разложения числа на слагаемые. Задача подсчета и генерации
Задача подсчета числа разложений
Найдите число p(n) разложений числа n на слагаемые (повторения разрешены, порядок не важен).
Например, для n = 5 число разложений равно 7, а для n = 6 число разложений равно 11:
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1
6 = 6
= 5 + 1
= 4 + 2
= 4 + 1 + 1
= 3 + 3
= 3 + 2 + 1
= 3 + 1 + 1 + 1
= 2 + 2 + 2
= 2 + 2 + 1 + 1
= 2 + 1 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
Начальные значения:
n	 1	 2	 3	 4	 5	 6	 7
p(n)	 1	 2	 3	 5	 7	 11	 ...
Обратите внимание на выбраную систему выписывания всех разложений. Слагаемые записываются в порядке невозрастания.
Посмотрим на разложения 6, которые начинаются на 2. После слагаемого 2 нужно записать разложения 4, в которых слагаемые не превосходят 2.
Параметризация: P(n,k) — число разложений числа n на слагаемые (повторения разрешены, порядок не важен), которые не превосходят k.
Множество всех таких разложений разбивается на две группы — те, которые содержат слагаемое k и те, которые не содержат.
Число последних равно P(n, k-1).
Рассмотрим те, которые содержат слагаемое k. Они выглядят как n = k + ... Вместо троеточия может идти любое разложение числа n - k на слагаемые, которые меньше либо равны k. Их количество равно P(n-k, k).
Итого
P(n,k) = P(n, k-1) + P(n - k, k)
Напишем рекурсивный алгоритм с запоминанием:
#include <stdio.h>

int d[100][100];

int dec(int n, int k) {
  if ( n >= 0 && k >= 0 && d[n][k] > 0 ) return d[n][k];
  if ( n < 0 ) return 0;
  if ( n <= 1 || k == 1 ) return 1;
  d[n][k] =  dec(n, k-1) + dec(n-k, k); 
  return d[n][k];
}

int main() {
  int m, i, j;
  scanf("%d", &m);
  for (i = 0; i < m; i++) {
    for (j = 0; j < m; j++) {
      d[i][j] = -1;
    }
  }
  printf("%d\n", dec(m, m));
  return 0;
}
artem@artem-laptop:~/lectures$ make dec
cc     dec.c   -o dec
artem@artem-laptop:~/lectures$ for((i=1; $i <= 10; i++)); do echo $i | ./dec ;  done
1
2
3
5
7
11
15
22
30
42
artem@artem-laptop:~/lectures$ time (for((i=1; $i <= 90; i++)); do echo $i | ./dec ;  done) > out.txt

real   0m0.856s
user   0m0.228s
sys   0m0.576s
Задача перечисления всех разложений
Идея декомпозиции та же самая. Код меняется несущественно:
кеширование не нужно;
сами разложения последовательно записываются в глобальном массиве a и выводятся;
появляется еще один аргумент — i — номер слагаемого (номер ячейки в массиве a, начиная с которой нужно писать разложение оставшегося "хвоста");
появляется код для вывода разложения;
рекурсивные вызовы логично обернуть в оператор if, чтобы не вызывать функцию для отрицательных аргументов.
#include <stdio.h>

int a[100];

/*
  n - осталось набрать слагаемых на сумму n
  k - слагаемые не больше k
  i - номер очередного слагаемого

  В массиве a, начиная с i-го элемента, перебрать все возможные
  варианты разложения числа n на слагаемые, не превосходящие k.
*/
void dec(int n, int k, int i) {
  if ( n < 0 ) return;
  if ( n == 0 ) {
    // Просьба разложить 0 означает, что раскладывать уже нечего и
    // и уже нет остаточного значения, котрое нужно разложить.
    // Значит в массиве {a[0], a[1], ... a[i-1]} находится некоторое готовое разложение
    // исходного числа n = m.
    int j;
    for (j = 0; j < i; j++) {
      printf("%d ", a[j]);
    }
    printf("\n");
    
  } else {
    if ( n - k >= 0) {
      a[i] = k; // фиксируем i-ое слагаемое
      dec(n - k, k, i + 1);
    }
    
    if ( k - 1 > 0) { 
      dec(n, k - 1, i);
    }
  }
  return;
}

int main() {
  int m, i, j;
  scanf("%d", &m);
  for (i = 0; i <= m; i++) {
    a[i] = 0;
  }
  dec(m, m, 0);
  return 0;
}