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

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]

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