Задача про способи видачі решти

Теорія алгоритмів

Аналіз та оцінка рекуретних співвідношень: основний рецепт (теорема) та метод підстановки.

Аналіз алгоритму сортування за допомогою купи (пірамідальне сортування).

Побудова, властивості та основні операції над купою.

Аналіз часу виконання алгоритму.

Аналіз алгоритму швидкого сортування.

Алгоритми сортування за лінійний час: аналіз та оцінка часу виконання.

Сортування методом підраховування та вичерпуванням.

Сортування підрахунком —час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.

Аналіз алгоритму
В алгоритмі присутні тільки прості цикли: в рядках 2, 6, 9 — цикл довжини N (довжина масиву), в рядку 4 — цикл довжини K (величина діапазону). Отже складність роботи алгоритму є О(N+K)
В алгоритмі використовуються два додаткових масиви: C і B Тому алгоритм потребує О(N+K)
додаткової пам'яті.
В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (напр. сортування за розрядами).
Використання даного алгоритму є доцільним тільки у випадку малих K (порядку N).

Цифрове сортування.

Порівняльний аналіз методів сортування.

Метод “розділяй та володарюй”.

Динамічне програмування.

Динамічне програмування (ДП) застосовується до задач, у яких
відповідь складається із частин, кожна з яких, у свою чергу, дає оптимальне
розв’язання деякої підзадачі.
• ДП корисне, якщо на різних шляхах розв’язання багаторазово зустрічаються ті
самі підзадачі.
• Основний технічний прийом – запам'ятовувати розв’язання підзадач,
що зустрічаються, на випадок, якщо та ж підзадача зустрінеться знову.

Задача про способи видачі решти.

А)

Б)