Question

СРОЧНО!! ДАЮ 40 БАЛЛОВ!!! Язык программирования - Python. Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими способами можно выдать сдачу в n рублей. Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1. Входные данные Программа получает на вход натуральное число n, не превышающее 106. Выходные данные Выведите ответ на задачу. Примечание Правильное решение задачи можно написать, используя всего один цикл while. Примеры Ввод 2 100000 Вывод 2 1667116705001

Answer 1

Ответ:

--- Python 3.8.3 ---

n = int(input('n: \n'))

counter = 0

for coin1 in range(0, n+ 1):

   for coin2 in range(0, (n // 2) + 1):

       for coin5 in range(0, (n // 5) + 1):

           for coin10 in range(0, (n // 10) + 1):

               if coin1 * 1 + coin2 * 2 + coin5 * 5 + coin10 * 10 == n: counter += 1

print(counter)

для n в пределах 100-200 считает вроде правильно, и достаточно быстро. Что до больших значений n, мне не хватило терпения. Ненормально это, успеть попить чаю в ожидании конца работы программы в 8 строк.

При желании можно использовать как стресс-тест ЦПУ

Answer 2

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

Создадим массив dp длиной n+1, в котором будем хранить количество способов выдать сдачу для каждого значения от 0 до n рублей. Изначально все значения массива dp будут равны 0, кроме dp[0], которое равно 1 (так как есть только один способ выдать сдачу в 0 рублей - не выдавать ничего).

Для каждой монеты (1, 2, 5 и 10 рублей) будем обновлять значения массива dp следующим образом: - для каждого значения i от монеты до n, увеличиваем dp[i] на значение dp[i-монета]. Таким образом, мы складываем все возможные варианты комбинаций с предыдущими монетами (если такие есть).

После прохода по всем монетам получим в массиве dp[n] количество способов выдать сдачу в n рублей.

Пример решения на Python:

n = int(input()) # считываем значение n

dp = [0] * (n+1) # создаем массив длиной n+1 и заполняем его нулями dp[0] = 1 # инициализируем dp[0] значением 1

# проходим по каждой монете и обновляем значения dp for coin in [1, 2, 5, 10]: for i in range(coin, n+1): dp[i] += dp[i-coin]

print(dp[n]) # выводим количество способов выдать сдачу в n рублей

Данное решение имеет сложность O(n), так как мы проходим по всем значениям от 1 до n для каждой монеты. С использованием только одного цикла while данную задачу решить сложнее, потому что нужно будет вручную изменять значения переменных.