10943. Как Вы прибавляете?
По заданному целому n
установить количество его разбиений на k неотрицательных слагаемых.
Например, для n = 20 и k = 2 существует 21 разбиение: 0 + 20, 1 +
19, 2 + 18, ..., 19 + 1, 20 + 0.
Вход.
Каждая строка содержит два целых числа n и k (1 £ n,
k £ 100). Последний тест содержит n = k = 0 и не
обрабатывается.
Выход. Для каждого теста вывести
количество разбиений числа n на k неотрицательных слагаемых.
Ответ выводить по модулю 1000000.
Пример входа
20 220 20 0
Пример выхода
21
21
РЕШЕНИЕ
динамическое программирование
Анализ алгоритма
Обозначим через f(n, k)
количество разбиений числа n на k неотрицательных слагаемых. Если
при разбиении числа n на k неотрицательных слагаемых последнее (k
- ое) слагаемое равно i (0 £ i £ n), то
далее число n – i следует разбить на k – 1 слагаемых, что
можно совершить f(n – i, k – 1) способами. Поскольку 0 £ i
£ n, то общее
число разбиений f(n, k) равно f(n, k – 1) + f(n –
1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k
– 1). Или то же самое что
f(n, k) = 
Очевидно, что f(n, 1) = 1,
так как количество способов разбить
число n на одно слагаемое равно единице (этим слагаемым будет само число
n). Имеет место соотношение f(0, k) = 1, так как единственным
разложением числа 0 на k слагаемых будет 0 = 0 + 0 + … + 0 (k
раз). Заведем массив m, в котором положим m[k, n] = f(n, k),
1 £ k, n £ 100. Индексы массива m и функции
f переставлены для удобства программирования: очередная k - ая строка
массива m пересчитывается через предыдущую (k – 1) - ую строку.
Решив рекуррентное соотношение,
можно получить:
f(n, k) = 
= 
Пример
Для n = 20 и k = 2
существует 21 разбиение: 0 + 20, 1 + 19, 2 + 18, ..., 19 + 1, 20 + 0.
Для начальных значений n, k
таблица m[k, n] имеет вид:
|
k \ n |
0 |
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
2 |
1 |
2 |
3 |
4 |
5 |
6 |
|
3 |
1 |
3 |
6 |
10 |
15 |
21 |
|
4 |
1 |
4 |
10 |
20 |
35 |
56 |
Реализация алгоритма
Определим размер MAX массива m и объявим
сам массив m.
#define MAX 101
int m[MAX][MAX];
Обнулим массив m. Проведем
инициализацию, положив f(i, 1) = f(0, i) = 1 (0 £ i
< MAX). Заметим, что
f(n, k) = f(n,
k – 1) + ( f(n – 1, k – 1) + f(n – 2, k – 1)
+ … f(1, k – 1) + f(0, k – 1) ) =
f(n, k – 1) + f(n
– 1, k)
Таким образом,
значение m[i, j] можно пересчитать как сумму m[i, j
– 1] и m[i – 1, j], взятую по модулю 1000000.
memset(m,0,sizeof(m));
for(i = 0; i < MAX; i++) m[1][i] =
m[i][0] = 1;
for(i = 2; i < MAX; i++)
for(j = 1; j < MAX; j++)
m[i][j] = (m[i][j-1] + m[i-1][j]) % 1000000;
Для каждой входной пары чисел n
и k выводим результат, хранящийся в ячейке m[k, n].
while(scanf("%d
%d",&n,&k), n + k > 0)
printf("%d\n",m[k][n]);