Question

В стране Чунго имеются монеты достоинством в 1,2,3 и 5 Чанго. Сколькими способами в стране Чунго можно дать сдачу в 8 Чанго?

Answer 1

1) 1+1+1+1+1+1+1+1

2)1+1+1+1+1+1+2

3) 1+1+1+1+2+2

4) 1+1+1+5

5)1+1+1+2+3

6) 3+3+2

7) 3+5

8)3+2+2+1

9) 1+2+5

10)3+3+1+1

 

Answer 2

8- 1+ 2+ 5

8-3+5

        ................................................

Answer 3

Чтобы рассчитать количество способов дать сдачу в 8 Чанго при наличии монет достоинством 1, 2, 3 и 5 Чанго, мы можем воспользоваться методом динамического программирования.

Обозначим через dp[i] количество способов дать сдачу суммы i. Тогда рекуррентное соотношение для dp[i] можно записать следующим образом:

\[ dp[i] = \sum_{j \text{ - монета}} dp[i - j], \]

где сумма берется по всем монетам, которые меньше или равны i.

Применим этот подход к вашей задаче. Посчитаем dp[i] для i от 0 до 8:

1. \( dp[0] = 1 \) - один способ дать сдачу, не отдавая ни одной монеты. 2. \( dp[1] = dp[0] = 1 \) - один способ дать сдачу из одной монеты. 3. \( dp[2] = dp[1] + dp[0] = 2 \) - два способа (2 монеты по 1 или 1 монета по 2). 4. \( dp[3] = dp[2] + dp[1] + dp[0] = 4 \) - четыре способа. 5. \( dp[4] = dp[3] + dp[2] + dp[1] + dp[0] = 7 \) - семь способов. 6. \( dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0] = 13 \) - тринадцать способов. 7. \( dp[6] = 24 \) 8. \( dp[7] = 44 \) 9. \( dp[8] = 81 \)

Таким образом, в стране Чунго существует 81 способ дать сдачу в 8 Чанго, используя монеты достоинством 1, 2, 3 и 5 Чанго.