Раздел «Образование».FIVTLecturesTerm1Lecture6:
<<Лекции ФИВТ, 1-й семестр

Лекция 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

Задача перечисления всех разложений

Идея декомпозиции та же самая. Код меняется несущественно:

#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;
}