Комбинаторные алгоритмы для программистов



             

Задачи на разбиение чисел - часть 2


Используя значения
f(N)
для
N = 0,1,2,3,4,5,6,7,8,9
, легко найти
f(10)
:
f(10)=f(6)+f(4)+f(0)=3.
После этого находим
f(11)=f(7) + f(5) + f(1) = 0,
f(12)=f(8) + f(6) + f(2) = 2
и т.д. Наконец, получаем значение
f(18)=8
. Таким образом, марки можно наклеить восемью способами. Эти способы таковы:
10,4,4
;
4,10,4
;
4,4,10
;
6,4, 4,4
;
4,6,4,4
;
4,4,6,4
;
4,4,4,6
;
6,6,6
. Отметим, что значения
f(N)
для
N = 1,2,3,4,5,6,7,8,9
можно было получить иначе, не приводя непосредственно проверки. Дело в том, что при
N < 0
имеем
f(N) = 0
, поскольку отрицательную сумму нельзя уплатить, наклеивая неотрицательное количество марок. В то же время, как мы видели,
f(0) = 1
. Поэтому
f(1)=f(-3)+f(-5)+f(-9)=0
.

Точно так же получаем значение

f(2)=0,f(3)=0
, а для
N = 4
имеем
f(4)=f(0)+f(-2)+f(-6)=1
.

Задача 5.Общая задача о наклейке марок.

Разобранная задача является частным случаем следующей общей задачи:

Имеются марки достоинством в

n_1,n_2,\ldots,n_k
. Сколькими способами можно оплатить с их помощью сумму в
N
рублей, если два способа, отличающиеся порядком, считаются различными? Все числа
n_1,n_2 ,\ldots,n_k
различны, а запас марок неограничен. Здесь на первом месте мы будем указывать число слагаемых, на втором – разбиваемое число и на последнем - ограничения на величину слагаемых.

В этом случае число

f(N)
способов удовлетворяет соотношению
f(N) = f(N - n_1 ) + f(N - n_2 ) + \ldots + f(N - n_k).

(5.5)

При этом
f(N) = 0
, если
f(0)=1
и
N < 0
. С помощью соотношения 5.5 можно найти
f(N)
для любого
N
, последовательно вычисляя
f(1),f(2),\ldots,f(N-1)
.

Рассмотрим частный случай этой задачи, когда

n_1= 1,n_2 = 2,\ldots
,
n_k = k
. Мы получаем всевозможные разбиения числа
N
на слагаемые
1,2,\ldots,k
, причем разбиения, отличающиеся порядком слагаемых, считаются различными. Обозначим число этих разбиений через
\varphi(k;N)
. (На первом месте мы будем указывать число слагаемых, на втором - разбиваемое число и на последнем – ограничения на величину слагаемых.) Из соотношения 5.5 следует, что
\varphi(k;N-1)+\varphi(k;N-2)+\ldots+\varphi(k;N-k).

(5.6)

При этом
\varphi (k;0) = 1
и
\varphi(k;N)= 0
,если
N <0
. Вычисление
\varphi (N;k)
можно упростить, если заметить, что
\varphi (N-1;k)=\varphi(N-2;k)+\varphi(N-k-1;k),
и потому
\varphi(N;k)=2\varphi(N-1;k)-\varphi (N - k - 1;k).

(5.7)

Ясно, что слагаемые не могут быть больше
N
. Поэтому
\varphi(N,N)
равно числу всех разбиений на
N
на натуральные слагаемые (включая и "разбиение"
N = N
. Если число слагаемых равно
s
, то получаем
C_{N - 1}^{s - 1}
разбиений. Поэтому
\varphi(N,N)=C_{N-1}^0+C_{N-1}^1+\ldots+C_{N-1}^{N-1}=2^{N-1}.
Итак, мы доказали, что натуральное число
N
можно разбить на слагаемые
2^{N - 1}
способами. Напомним, что при этом учитывается порядок слагаемых.Например, число 5 можно разбить на слагаемые
2^{5 - 1} = 16
способами.

5 = 55 = 3 + 1 + 15 = 1 + 2 + 2
5 = 4 + 15 = 1 + 3+ 15 = 2 + 1 + 1 + 1
5 = 1 + 45 = 1 + 1 + 35 = 1 + 2 + 1 + 1
5 = 2 + 35 = 2 + 2 + 15 = 1 + 1 + 2 + 1
5 = 3 + 25 = 2 + 1 + 25 = 1 + 1 + 1 + 2
5 = 1 + 1 + 1 + 1 + 1




Содержание  Назад  Вперед