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

UptoLike

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

Рубрика:

Первый член равен 0, так как сумма оставшихся монет меньше на-

бираемой суммы. Применим ту же рекуррентную формулу к оставше-

муся члену. В результате получим:

F(1, 2, 3, 5, 10, 15, 20; 23) = F(1, 2, 3, 5, 10, 15; 3) + F(1, 2, 3, 5, 10, 15; 23)

В первом члене правой части монеты достоинством в 5, 10 и 15 ко-

пеек можно не учитывать, так как достоинство каждой из этих монет

больше набираемой суммы, т. е. можно правую часть переписать так:

F(1, 2, 3; 3) + F(1, 2, 3, 5, 10, 15; 23) =

=F(1, 2; 0) + F(1, 2;3 ) + F(1, 2, 3, 5, 10; 8) + F(1, 2, 3, 5, 10; 23) =

= 1+ F(1; 1) + F(1; 3) +F(1, 2, 3, 5; 8) + F(1, 2, 3, 5, 10; 23).

Очевидно, что F(1, 2; 0) = 1; F(1, 2; 3) = F(1;1) = 1; F(1; 3) = 0;

F(1, 2, 3, 5, 10; 23) = 0. Поэтому правая часть перепишется в виде:

1 + 1 + 0 + F(1, 2, 3, 5; 8) + 0 = 2 + F(1, 2, 3; 3) + F(1, 2, 3; 8) = 2 + 2 + 0 =

= 4. Таким образом, задача имеет 4 различных решения.

Подчеркнем еще раз, что в этой задаче порядок монет не важен.

3. Задача о размене гривенника (10 копеек). Рассмотрим задачу, в

которой сняты ограничения, как на порядок предметов, так и на их коли-

чество: размен гривенника монетами достоинством в 1, 2, 3, 5 копеек.

Для этого случая рекуррентное соотношение имеет вид

S(1, 2, 3, 5; 10 ) = S(1, 2, 3; 10) + S(1, 2, 3; 5) + S(1, 2, 3; 0).

Таким образом все множество решений разбивается на подмноже-

ства в зависимости от числа монет старшего достоинства, использо-

ванных для размена. Находим все 20 способов размена:

5 ⋅ 25+1 ⋅ 53+2 ⋅ 3+1 2 ⋅ 4+1 ⋅ 2

5+3+2 3 ⋅ 3+1 3+2 ⋅ 2+1 ⋅ 32 ⋅ 3+1 ⋅ 4

5+3+1 ⋅ 23 ⋅ 2+2 ⋅ 2 3+2+1 ⋅ 52 ⋅ 2+1 ⋅ 5

5+2 ⋅ 2+1 3 ⋅ 2+2+1 ⋅ 2 3+1 ⋅ 72+1 ⋅ 8

5+2+1 ⋅ 33 ⋅ 2+1 ⋅ 42 ⋅ 51 ⋅ 10