Question

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

Answer 1

Я тоже сейчас это задание делаю)

Как я думаю способов 0

Так как монеты по 3.6 нам нужно из этих монет получить целое число. Тоесть их можно умножить только на 5. Получится 18. И если 9*2=18, а 18+18=36. Тоесть не получается. А если умножать 3.6 на другие числа получится не целое число, а нам нудно целое.

Короче 0 способов. Я не умею хорошо объяснять. Сорян(

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим массив, где каждый элемент i будет содержать количество способов разменять сумму i монетами по 3, 6 и 9 тугриков. Начнем с базовых случаев: количество способов разменять 0 и 3 тугрика равно 1, а количество способов разменять любую другую сумму меньше 3 равно 0.

Затем для каждого значения i от 3 до 39 будем считать количество способов разменять i-3, i-6 и i-9 тугриков, таким образом получая общее количество способов разменять i тугриков.

Вот таблица, в которой указано количество способов разменять каждую сумму от 0 до 39 тугриков:

makefileCopy code
Сумма:   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39
Способы: 1   0   0   1   0   0   2   0   0   3   0   0   4   0   0   5   0   0   6   0   0   7   0   0   8   0   0   9   0   0   10  0   0   11  0   0   12  0   0   13

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