У цьому домашньому завданні ми реалізували дві функції для касової системи, яка видає решту покупцеві: жадібний алгоритм і алгоритм динамічного програмування.
Ця функція приймає суму, яку потрібно видати покупцеві, і повертає словник із кількістю монет кожного номіналу, що використовуються для формування цієї суми. Спочатку вибираються найбільші доступні номінали монет.
Ця функція також приймає суму для видачі решти, але використовує метод динамічного програмування для знаходження мінімальної кількості монет, необхідних для формування цієї суми.
- Результат для суми 113: {50: 2, 10: 1, 2: 1, 1: 1}
- Час виконання: миттєвий
- Результат для суми 113: {1: 1, 2: 1, 10: 1, 50: 2}
- Час виконання: миттєвий
- Результат для суми 100000: {50: 2000}
- Час виконання: миттєвий
- Результат для суми 100000: {50: 2000}
- Час виконання: 79.882 секунд
- Жадібний алгоритм працює швидко, але не завжди оптимально з точки зору мінімальної кількості монет.
- Алгоритм динамічного програмування завжди знаходить мінімальну кількість монет, але час виконання значно збільшується при великих сумах.
- Для касових систем, де важлива швидкість, жадібний алгоритм може бути прийнятним вибором.
- Для забезпечення мінімальної кількості монет алгоритм динамічного програмування є кращим вибором, хоча може бути неприйнятним для дуже великих сум через значний час виконання.
Щоб використати функції, ви можете імпортувати їх у ваш скрипт та викликати з потрібною сумою:
from functions import find_coins_greedy, find_min_coins
amount = 113
print(find_coins_greedy(amount)) # Виведе: {50: 2, 10: 1, 2: 1, 1: 1}
print(find_min_coins(amount)) # Виведе: {1: 1, 2: 1, 10: 1, 50: 2}