Составители:
Рубрика:
26
Первый член равен 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
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »