Дискретная математика. Ерош И.Л - 84 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

84
4.4.1. «Задача о наклейке марок»
На почте имеются марки достоинством 4, 6 и 10 копеек. Для от
правки заказного письма требуется наклеить марки так, чтобы сумма
составляла 18 копеек. Сколько существует разных вариантов наклей
ки марок?
Будем считать, что порядок наклейки марок важен, т. е. способы
наклейки марок достоинством в 4, 10, 4 копейки и 10, 4, 4 копейки –
разные способы. Тогда можно написать следующее рекуррентное соот
ношение:
F(N) = F(N – 4) + F(N – 6) + F(N –10), (4.18)
где под F(N) понимается число способов наклейки марок в сумме, рав
ной N копейкам. Формула (4.18) показывает, что все множество ре
шений распадается на три несовместных подмножества в зависимости
от того, какой наклеена последняя марка. Подсчитаем значения F(N)
для некоторых начальных значений N. Так, F(N<0) = 0, 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(10) = 3. Тогда для n = 18 полу
чим F(18) = F(14) + F(12) + F(8).
Используя соотношение (4.18) для каждого нового члена, далее по
лучаем F(18) = F(10) + F(8) + F(4) + F(8) + F(6) + F(2) + F(8) = F(10) +
+ 3·F(8) + F(4) + F(6) + F(2) = 3 + 3 + 1 + 1 + 0 = 8.
4.4.2. «Задача об уплате долга»
В кошельке имеются монеты достоинством в 1, 2, 3, 5, 10, 15, 20 и
50 копеек. Требуется уплатить долг в 73 копейки. Каким количеством
способов это можно сделать?
Запишем рекуррентное соотношение в общем случае, когда монеты
имеют достоинство в k
1
, k
2
, k
3
, …, k
m
копеек и требуется набрать суму
в N копеек, при этом произведем ранжирование монет по возрастанию:
F (k
1
, k
2
, k
3
, …, k
m
; N) =
= F(k
1
, k
2
, k
3
, …, k
m–1
; N–k
m
) + F(k
1
, k
2
, k
3
, …, k
m–1
; N). (4.19)
Первый член правой части (4.19) учитывает количество комбина
ций, в которых монета старшего достоинства использована, второй
член – в которых монета старшего достоинства не использована. Для
рассматриваемого примера F(1, 2, 3, 5, 10, 15, 20, 50; 73) = F(1, 2, 3,
5, 10, 15, 20; 73) + F(1, 2, 3, 5, 10, 15, 20; 23).
Первый член полученного выражения равен 0, так как сумма остав
шихся монет меньше набираемой суммы. Применим ту же рекуррент

Страницы