Question

Программирование на Python. Ведьмаку заплатите чеканной монетойВсем известно, что ведьмак способен одолеть любых чудовищ, однако его услуги обойдутся недешево, к тому же ведьмак не принимает купюры, он принимает только чеканные монеты. В мире ведьмака существуют монеты с номиналами 1, 5, 10, 25.Напишите программу, которая определяет какое минимальное количество чеканных монет нужно заплатить ведьмаку.Формат входных данных На вход программе подается одно натуральное число, цена за услугу ведьмака.Формат выходных данныхПрограмма должна вывести минимально возможное количество чеканных монет для оплаты.​

Answer 1

sm = int(input())

coins = [1, 5, 10, 25]

ls = [0] * (sm+1)

for i in range(1, sm+1):

   ls[i] = float('inf')

   for coin in coins:

       if coin <= i:

           ls[i] = min(ls[i], ls[i-coin]+1)

print(ls[-1])

Answer 2

Вы можете решить эту задачу, используя жадный алгоритм. Жадный алгоритм будет выбирать наибольшие доступные монеты и добавлять их к общей сумме до тех пор, пока сумма не станет равной или большей указанной цене. Вот пример программы на Python для решения этой задачи:

pythonCopy code
def min_coins_for_payment(price):
    # Доступные номиналы монет
    coin_denominations = [25, 10, 5, 1]
    
    # Инициализируем счетчик монет
    coin_count = 0
    
    # Идем по номиналам монет и добавляем их к сумме, пока не достигнем указанной цены
    for coin in coin_denominations:
        while price >= coin:
            price -= coin
            coin_count += 1
    
    return coin_count

# Вводим цену за услугу ведьмака
price = int(input("Введите цену за услугу ведьмака: "))

# Вызываем функцию и выводим результат
min_coins = min_coins_for_payment(price)
print("Минимальное количество чеканных монет для оплаты:", min_coins)

Вы можете ввести цену за услугу ведьмака, и программа вернет минимальное количество чеканных монет, необходимых для оплаты.