Question

Сколькими способами можно разменять купюру "19 рублей" монетами "1 рубль", "3 рубля", "5 рублей" и "8 рублей"?

Answer 1

Чтобы решить эту задачу, будем решать более мелкие.

Например, сколькими способами можно разменять 4 рубля монетами 2 и 1?

Очевидно, что чтобы узнать, сколько есть способов получить 4 рубля, мы можем сложить количество способов получения двух рублей и трех, так как только из них мы можем с помощью 1 рубля и 2 рублей получить 4 рубля. Воспользуемся этой идеей и составим таблицу для нашей задачи, там где левый столбик число монет, а правый, количество способов

0) 1

1) 1

2) 1

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

3) 2

4) 3

Для 5 рублей теперь надо проверять суммы на 5 меньше, получим сумму способов из 0, 2, 4

5) 5

6) 8

7) 12

Ну и для восьмерки мы теперь проверяем также суммы на 8 меньше

8) 20

Всюду ниже (a) - количество способов набрать сумму, равную a

9) (1) + (4) + (6) + (8) = 1 + 3 + 8 + 20 = 32

10) (2) + (5) + (7) + (9) = 1 + 5 + 12 + 32 = 50

11) (3) + (6) + (8) + (10) = 2 + 8 + 20 + 50 = 80

12) (4) + (7) + (9) + (11) = 3 + 12 + 32 + 80 = 127

13) (5) + (8) + (10) + (12) = 5 + 20 + 50 + 127 = 202

14) (6) + (9) + (11) + (13) = 8 + 32 + 80 + 202 = 322

15) (7) + (10) + (12) + (14) = 12 + 50 + 127 + 322 = 511

16) (8) + (11) + (13) + (15) = 20 + 80 + 202 + 511 = 813

17) (9) + (12) + (14) + (16) = 32 + 127 + 322 + 813 = 1294

18) (10) + (13) + (15) + (17) = 50 + 202 + 511 + 1294 = 2057

19 (11) + (14) + (16) + (18) = 80 + 322 + 813 + 2057 = 3272

Ответ: 3272 способа