Question

Сколько всего способов разменять купюру в 39 тугриков монетами по 3,6 и 9 тугриков?

Answer 1

Ответ:6

Пошаговое объяснение:

Answer 2

У этой задачи есть 6 спасибо решения.

Answer 3

Для решения этой задачи можно воспользоваться динамическим программированием. Посчитаем количество способов разменять купюру в 39 тугриков монетами по 3, 6 и 9 тугриков.

Обозначим:

• DP(i) - количество способов разменять сумму i тугриков монетами по 3, 6 и 9 тугриков.

Инициализируем DP(0) = 1, так как разменять 0 тугриков можно одним способом - не давая никаких монет.

Затем, для каждой суммы i от 1 до 39, будем вычислять DP(i) на основе предыдущих значений DP(j), где j = i - 3, i - 6 и i - 9 (если такие значения существуют).

Таким образом, DP(i) = DP(i - 3) + DP(i - 6) + DP(i - 9).

Выполним вычисления:

DP(0) = 1 DP(1) = DP(1 - 3) + DP(1 - 6) + DP(1 - 9) = DP(-2) + DP(-5) + DP(-8) = 0 + 0 + 0 = 0 DP(2) = DP(2 - 3) + DP(2 - 6) + DP(2 - 9) = DP(-1) + DP(-4) + DP(-7) = 0 + 0 + 0 = 0 ... DP(9) = DP(9 - 3) + DP(9 - 6) + DP(9 - 9) = DP(6) + DP(3) + DP(0) = 0 + 1 + 1 = 2 ... DP(39) = DP(39 - 3) + DP(39 - 6) + DP(39 - 9) = DP(36) + DP(33) + DP(30) = 4 + 1 + 1 = 6

Таким образом, существует 6 способов разменять купюру в 39 тугриков монетами по 3, 6 и 9 тугриков.