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

Чи доводилося вам виконувати пошук варіантів виходу з лабіринту від його входу? Як у таких випадках ви діяли?

Прочитайте!

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

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

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

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

За допомогою методу з поверненням можна отримати всі перестановки і комбінації даної множини.

Тернарний пошук в інформатиці застосовується для пошуку максимумів або мінімумів функції, яка на деякому відрізку спочатку постійно зростає, потім постійно спадає або спочатку спадає потім зростає.

Алгоритм тернарного пошуку можна реалізувати для пошуку заданого елемента в упорядкованому масиві, поділивши його на три приблизно рівні частини.

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

Далі виконуються дії, аналогічні описаним.

Розв’язання задач

Завдання 1. Знайдіть в Інтернеті відомості про 5 найвищих вершин в Україні. Розробіть програму визначення наявності у цьому переліку назви вершини, яка вводиться з клавіатури.

Розв’язання

Ця програма працює наступним чином:

• Програма визначає масив з назвами 5 найвищих вершин України.
• Потім програма отримує від користувача назву вершини.
• Нарешті, програма перебирає всі вершини в масиві. Якщо назва введеної вершини збігається з назвою однієї з вершин у масиві, то програма встановлює значення змінної found на True. Якщо назва введеної вершини не збігається з жодної з назв вершин у масиві, то програма встановлює значення змінної found на False.
• Наприкінці програма виводить результат.

Завдання 2.  Дано масив цілих чисел: 13, 7, 6, 7, 9, 7, 6, 5. Розробіть програму обчислення кількості числа, значення якого вводиться з клавіатури.

Розв’язання

Завдання 3.  Дано масив цілих чисел: 6, 8, 13, 17, 19, 30, 13, 8. Розробіть програму визначення всіх позицій, на яких знаходиться число, значення якого вводиться з клавіатури.

Завдання 4. Розробіть програму створення масиву, що містить 10 випадкових чисел у діапазоні від 3 до 9 і визначення, чи є у ньому число 6.

Розв’язання

Завдання 5. Дано масив з n цілих чисел. Знайти добуток двох найбільших елементів масиву.

Розв’язання

Завдання 6. Дано масив з n цілих чисел. Виведіть всі його елементи з парними індексами.