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



             

Задачи на разбиение чисел


Теперь мы переходим к задачам, в которых все разделяемые предметы совершенно одинаковы. В этом случае можно говорить не о разделении предметов, а о разбиении натуральных чисел на слагаемые (которые, конечно, тоже должны быть натуральными числами).

Здесь возникает много различных задач. В одних задачах учитывается порядок слагаемых, в других - нет.

Задача 4. Отправка бандероли.

За пересылку бандероли надо уплатить 18 рублей. Сколькими способами можно оплатить ее марками стоимостью 4, 6, и 10 рублей, если два способа, отличающиеся порядком марок, считаются различными (запас марок различного достоинства считаем неограниченным)?

Обозначим через

f(N)
число способов, которыми можно наклеить марки в 4, 6 и 10 рублей так, чтобы общая стоимость этих марок равнялась
N
. Тогда для
f(N)
справедливо следующее соотношение:
f(N) = f(N- 4) + f(N - 6) + f(N - 10).

(5.4)

Пусть имеется некоторый способ наклейки марок с общей стоимостью
N
, и пусть последней наклеена марка стоимостью 4 рубля. Тогда все остальные марки стоят (
N - 4
) рубля. Наоборот, присоединяя к любой комбинации марок общей стоимостью (
N - 4
) рубля одну четырехрублевую марку, получаем комбинацию марок стоимостью
N
рублей. При этом из разных комбинаций стоимостью (
N - 4
) рублей получается разные комбинации стоимостью
N
рублей. Итак, число искомых комбинаций, где последней наклеена марка стоимостью 4 рубля, равно
f(N - 4)
.

Точно так же доказывается, что число комбинаций, оканчивающихся на на шестирублевую марку, равно

f(N - 6)
, а на десятирублевую марку оканчиваются
f(N - 10)
комбинацией. Поскольку любая комбинация оканчивается на марку одного из указанных типов, то по правилу суммы получаем соотношение 5.4.

Соотношение 5.4 позволяет свести задачу о наклеивании марок на сумму

N
рублей к задачам о наклеивании марок на меньшие суммы. Но при малых значениях
N
задачу легко решить непосредственно. Простой подсчет показывает, что
f(0)=1,f(1)=f(2)=f(3)=0,f(4)=1,f(5) = 0,f(6) = 1,f(7)=0,f(8)=1,f(9)=0.
Равенство
 f(0)=1
означает, что сумму в 0 рублей можно уплатить единственным образом: совсем не наклеивая марок. А сумму в 1,2,3,5,7 и 9 рублей вообще никак нельзя получить с помощью марок стоимостью 4, 6 и 10 рублей.


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