Інформатика – Поглиблений рівень

Прочитайте!

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

Жадібні алгоритми — це загальна назва методів розв’язування задач оптимізації, при яких на кожному етапі приймається локально  оптимальне рішення.

Жадібний алгоритм — це метод розв’язування оптимізаційних задач, заснований на тому, що процес прийняття рішення можна розбити на елементарні кроки, на кожному з яких приймається окреме рішення.

Ці алгоритми застосовують до тих задач, які можна розбити на окремі прості підзадачі аналогічно тому, як це робиться в алгоритмах динамічного програмування. У жадібних алгоритмах на кожному етапі з множини можливих варіантів вибирається той, який є найкращим у даний момент, із надією, що саме він забезпечить оптимальне розв’язання всієї задачі. Вибір варіанта на кожному етапі повинен відповідати таким вимогам: бути допустимим (відповідати обмеженням задачі); бути оптимальним (найкращим із усіх можливих на даному етапі); бути остаточним (не
можна змінити цей вибір на наступних етапах).

Пояснимо сутність жадібних алгоритмів на прикладі 1.

Приклад 1. Банкомат може видавати купюри номіналом 500, 200, 100, 50  грн. Якими купюрами і в якій кількості повинен видати банкомат суму 2 350 грн, щоб кількість купюр була мінімальною?
Відповідно до методу жадібних алгоритмів програма обслуговування банкомата на кожному кроці повинна вибирати купюри максимального номіналу з числа тих, які можна вибрати, щоб їх загальна кількість була мінімальною. Для цієї суми спочатку слід вибрати чотири купюри номіналом 500 грн, потім одну купюру номіналом 200 грн, далі одну купюру номіналом 100 грн
і, нарешті, одну купюру номіналом 50 грн.

Реалізуйте даний алгоритм.

Приклад 2. Борошно міститься в контейнерах масою 110, 50 і 10 кг. Виберемо мінімальну кількість контейнерів загальною масою 150 кг. Логічно взяти 3 контейнери масою 50 кг. За жадібним алгоритмом спочатку потрібно взяти контейнер максимальної маси (110 кг), на наступних етапах — 4 контейнери масою 10 кг, тобто 5 контейнерів.

Розв’яжіть задачу використовуючи Жадібний алгоритм.

Приклад 3. Визначте, як сплатити суму 91 грн купюрами номіналом 1, 2, 5, 10, 20 і 50 грн так, щоб загальна кількість купюр була мінімальною.

Розв’яжіть задачу використовуючи Жадібний алгоритм.

Приклад 4. Вантажний ліфт може піднімати вантаж до 2000 кг. Є  коробки масою 200 кг, 100 кг, 50 кг, 20 кг, 1 0 кг. Складіть програму, яка за жадібним алгоритмом визначить скільки коробок кожного виду може підняти вантажний ліфт. Кількість коробок кожного виду вводиться з клавіатури. Програма повинна визначити, яка кількість коробок поміститься у ліфт. Якщо помістяться усі коробки – вивести відповідне повідомлення, якщо частина коробок залишиться, вивести їх кількість. Окремо порахувати кількість коробок кожного виду, які залишаться.

Додаткові задачі*

Задача 1. Дано число натуральне число n. Надрукувати ті натуральні числа, квадрат яких не перевищує n.

Задача 2. Складіть програму для знаходження найбільшої цифри заданого натурального числа n.

Задача 3. Складіть програму для визначення того, скільки раз задана цифра зустрічається у натуральному числі n.