Question

проезд в городском транспорте стоит 22 денег. У мамы с папой 50 тенге одной монетой. У кондуктор есть монеты в 1, 2, и 5 тенге. сколькими способами кондуктор может дать сдачу? записать ответов только количество способов без их перечисления. способы считаются различными, если используются разные монеты. порядок не важен.

Answer 1

22 *2 = 44
50 -44 =6
5 тг и 1 тг

Answer 2

Для решения этой задачи можно использовать метод динамического программирования.

Представим, что у нас есть таблица, в которой строки соответствуют возможным остаткам от сдачи (от 0 до 22 тенге), а столбцы соответствуют доступным монетам (1, 2 и 5 тенге). Заполним таблицу снизу вверх, начиная с базового случая, когда остаток равен 0.

Используя формулу: T[i][j] = T[i][j-1] + T[i - coins[j]][j],

где T[i][j] - количество способов дать сдачу остатку i с помощью монет j и меньших (coins[j] - номинал монеты j), а T[i][j-1] - количество способов, если мы не используем монету j.

Построим таблицу и найдем значение T[22][2]:

Copy code
   0   1   2   5

0: [1 0 0 0] 1: [1 1 0 0] 2: [1 1 1 0] 3: [1 1 1 1] 4: [1 1 2 1] 5: [1 1 2 2] 6: [1 1 3 2] 7: [1 1 3 3] 8: [1 1 4 3] 9: [1 1 4 4] 10: [1 1 5 4] 11: [1 1 5 5] 12: [1 1 6 5] 13: [1 1 6 6] 14: [1 1 7 6] 15: [1 1 7 7] 16: [1 1 8 7] 17: [1 1 8 8] 18: [1 1 9 8] 19: [1 1 9 9] 20: [1 1 10 9] 21: [1 1 10 10] 22: [1 1 11 10]

Ответ: Кондуктор может дать сдачу 11 различными способами.