Question

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

Answer 1

Можно написать программу на каком-либо языке программирования. Например Python:

n = 66
count = 0
for i in range(67):
  for j in range(34):
     for k in range(14):
         for l in range(7):
            if n == i*1+j*2+k*5+l*10:
                count += 1
print('Всего способов - ', count)

Та же программа на языке Pascal:

var i,j,k,l,n,count:integer;

begin
n := 66;
count := 0;
for i:=0 to 66 do
    for j:=0 to 33 do
        for k:=0 to 13 do
            for l:=0 to 6 do
                if n = (i*1+j*2+k*5+l*10) then count += 1;
  writeln('Всего способов - ', count);
end.

Ответ: 700

Answer 2

Задача решается методом динамического программирования. dp[i] - сколькими способами можно набрать i рублей.
Очевидно, dp[i] = dp[i - 5] + dp[i - 10] + dp[i - 2] + dp[i - 1]

программа во вложении

Answer 3

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

Пусть f(n, k) - количество способов набрать сумму n рублей, используя монеты достоинством от 1 рубля до k рублей. Тогда искомое количество способов будет равно f(66, 10).

Сначала заполним базовые значения: - f(0, k) = 1, так как сумму 0 рублей можно получить без использования монет; - f(n, 0) = 0, так как без монет невозможно набрать положительную сумму.

Далее будем заполнять значения таблицы f по формуле: f(n, k) = f(n, k-1) + f(n-k, k) - первое слагаемое f(n, k-1) означает количество способов набрать сумму n рублей, не используя монету достоинством k рублей; - второе слагаемое f(n-k, k) означает количество способов набрать сумму (n-k) рублей, используя монету достоинством k рублей.

Применим эту формулу для всех значения n от 1 до 66 и k от 1 до 10, заполняя таблицу f:

n \ k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ----------------------------------------------------------------- 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 3 | 1 | 2 | 2 | 4 | 5 | 7 | 8 | 10 | 11 | 13 | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | 66 | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |

Таким образом, ответ на задачу равен f(66, 10) = 382. Значит, существует 382 способа набрать сумму 66 рублей, используя монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей.