Question

PYTHON. Визначте, як сплатити суму 91 грн купюра- ми номіналом 1, 2, 5, 10, 25 і 50 грн так, щоб загальна кількість купюр була мінімальною.​

Answer 1

Ответ:

Ось як виглядає реалізація цього алгоритму на мові Python:

denominations = [50, 25, 10, 5, 2, 1]

total = 91

result = {}

for d in denominations:

result[d] = total // d

total -= result[d] * d

print(result)

Далі: →

Результат виконання цього коду буде наступним:

{50: 1, 25: 1, 10: 1, 5: 1, 2: 0, 1: 1}

Це означає, що для сплати суми 91 грн необхідно використати по такій кількості купюр.

Answer 2

Для розв'язання цієї задачі можна скористатися жадібним алгоритмом, який буде намагатися сплачувати максимально можливу кількість купюр більшого номіналу перед переходом до менших номіналів. Ось алгоритм, який допоможе вам сплатити суму 91 грн мінімальною кількістю купюр:

1. Спробуйте сплатити максимальною можливою кількістю купюр номіналом 50 грн. Якщо сума 91 грн залишається недооплаченою, то додайте одну купюру номіналом 50 грн і відніміть 50 грн від залишку.

2. Повторюйте цей процес для номіналів 25 грн, 10 грн і 5 грн, доки залишок не стане менше або дорівнюватиме 5 грн.

3. Нарешті, сплатіть залишок купюрами номіналом 2 грн і 1 грн, доки залишок не буде дорівнювати нулю.

Ось приклад послідовності оплати для суми 91 грн:

• 1 купюра номіналом 50 грн (залишок: 41 грн)
• 1 купюра номіналом 25 грн (залишок: 16 грн)
• 1 купюра номіналом 10 грн (залишок: 6 грн)
• 1 купюра номіналом 5 грн (залишок: 1 грн)
• 3 купюри номіналом 1 грн (залишок: 0 грн)

Отже, для сплати суми 91 грн вам знадобиться 1 купюра номіналом 50 грн, 1 купюра номіналом 25 грн, 1 купюра номіналом 10 грн, 1 купюра номіналом 5 грн і 3 купюри номіналом 1 грн. Це найменша кількість купюр, якою можна сплатити дану суму.