Page 200 - 4496

F(N)= F(N - 4)+ F(N - 6) + F(N - 10)
де під F(N) розуміється кількість варіантів наклейки марок
загальною вартістю N. Підрахуємо значення F(N) для деяких
початкових N.
F(N) = 0 при N < 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) = F(10) + F(8) +
F(4) + F(8) + F(6) + F(2) + F(8) = 3 + 1 + 1 + 1 + 1 + 1 = 8.
2. Задача про сплату боргу. В гаманці є монети
номіналом в 1, 2, 3, 5, 10, 15, 20, 50 копійок (по одній штуці).
Потрібно заплатити борг в 73 копійки.
Запишемо рекурентне співвідношення в загальному

випадку, коли монети мають достоїнства в k 1 k 2 ... і k n
копійок і вимагається набрати суму в N копійок:
F (k 1 ,k 2 ,...,k m ;N )  F (k 1 ,k 2 ,...,k m ;N  k m ) F (k 1 ,k 2 ,...,k m 1 ;N )

Перший член правої частини враховує кількість
комбінацій, в яких монета старшого номіналу використаний,
другий член - в яких монета старшого номіналу не
використаний. Для даного прикладу

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, оскільки сума монет, що
залишилися, менша необхідної суми суми. Застосуємо ту ж
рекурентну формулу до члена, що залишився. В результаті
одержимо:
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, 5, 10, 15; 3) + F(1, 2, 3, 5, 10, 15; 23) =

197