• навчити використовувати:
  • бінарний пошук в упорядкованому масиві;
  • тернарний пошук максимума чи мінімума функції на заданому проміжку;
  • пошук з поверненням;
• cистематизувати практичні навики роботи за вивченою темою.

Після вивчення матеріалу учень:

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

Обладнання: комп'ютери зі встановленими ОС та середовищем програмування мовою C++ або стійким сполученням з Інтернетом для використання мережевих сервісів.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Вироблення практичних навичок.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

1. Яким словом починають оголошення:
   • використаних модулів;
   • типів;
   • сталих;
   • змінних;
   • міток?
2. Яким символом розмежовують вказівки у коді програми?
3. Що таке масив? Які властивості має масив? Що таке форма масиву?
4. Назвіть відомі вам методи упорядкування лінійних масивів.
5. Які типи простих даних ви знаєте?

3. Інструктаж з ТБ
4. Вивчення нового матеріалу

Бінарний пошук традиційно вивчають вже при першому знайомстві з масивами — див. опис.

Тернарний пошук використовують для пошуку:

• максимума функції f на заданому проміжку [l, r] за умови, що функція спочатку строго зростає, потім досягає максимуму в одній точці або на відрізку, потім строго спадає;

• мінімума функції f на заданому проміжку [l, r] за умови, що функція спочатку строго спадає, потім досягає мінімуму в одній точці або на відрізку, потім строго зростає.

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

1. Вибрати довільні точки m₁ і m₂, що задовольняють нерівності: l < m₁ < m₂ < r. Наприклад, надати значень:
   m₁ = l + (r − l)/3;
   m₂ = r − (r − l)/3.

2. Порахувати значення функції f (m₁) і f (m₂).

3. Якщо f (m₁) < f (m₂) — шуканий максимум поза проміжком [l, m₁) — надати значення:
   l = m₁.

4. Якщо f (m₁) > f (m₂) — шуканий максимум поза проміжком (m₂, r] — надати значення:
   r = m₂.

5. Якщо f (m₂) = f (m₂) — шуканий максимум поза проміжками [l, m₁) і (m₂, r] при строгому зростанні й спаданні f до і після точки максимума при зростанні аргумента — надати значення:
   l = m₁;
   r = m₂.

6. Якщо r − l < ε, вивести значення (l + r)/2, значення f у цій точці і закінчити виконання алгоритму. Інакше перейти до пункту 1.

Тут ε — дійсне число — деяка наперед задана точність пошуку. Див. програму обчислення найбільшого значення функції f (x) = 1 − x² на проміжку [−3, 2].

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

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

Задача про 8 ферзів є частковим випадком загальнішої задачі про розташування n ферзів на шахівниці розміром n × n.

Cтруктура розв'язання задачі про розташування 8 ферзів на шахівниці

• Спочатку ферзя ставити у першому стовпчику шахівниці, потім — у другому, третьому і т.д. Нумерація стовпчиків може бути довільною.

• На кожному такому кроці перебирати усі можливі ходи — способи поставити ще одну фігуру, щоб уникнути атаки цією фігурою наявних на дошці фігур. Для кожного можливого ходу робити хід (приймати гіпотезу) — ставити ферзя на відповідне поле. Якщо таких нерозглянутих ходів немає, повертатися на один хід назад (відхиляти останню прийняту гіпотезу) — прибирати останього поставленого ферзя.

• Так робити до тих пір, поки не переберемо безупішно усі варіанти або не отримаємо розв'язок (один або усі — залежно від формулювання задачі).

Характерним для розв'язання задачі є те, що під час пошуку розв'язку поступово:

• то збільшуємо на 1 номер стовпчика (ходу) i, то зменшуємо його на 1;

• то робимо хід з номером i (тобто ставимо i-го ферзя на дошку), то відмовляємося від цього ходу (прибираємо ферзя).

Це пояснює назву «пошук з поверненням».

Примітка. Розв'язана задача «Хід коня» — частковий випадок пошуку гамільтонового циклу.

4. Інструктаж з ТБ
5. Вироблення практичних навичок

Завдання 1. Змінити код для тернарного пошуку проміжку значень x з [0, 4], при яких вираз |x − 1| + |x − 2| набуває найменших значень.

Вказівка до виконання

1. Якщо однакові значення функції на кінцях поточного відрізка [l, r] такі самі, що й для попереднього відрізка, то мінімум функції досягається на цьому відрізку. Передбачити галуження для цього випадку.

2. Для знаходження меж найбільшого проміжку, на якому досягається мінімум функції, використати поділ (неперервного) діапазону значень між відповід­ними межами поточного й початкового відрізків.

Завдання 2. Створити програму пошуку з поверненням для дешифрації запису дії додавання ten + ten + forty = sixty.

Вказівка до виконання

1. Занумерувати літери у порядку першої появи при зростанні старшинства розряду.

2. Приймати гіпотези щодо значення змінної-літери у встановленому порядку.

3. Вести облік використаних цифр.

4. Можна використати вкладені цикли.

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.
2. При потребі доробити завдання 1 та 2.

3. Ознайомитися з умовами та ідеями розв'язання задач відбірково-тренувальних зборів команди міста Києва: 1.1, 4.2, 6.2, 15.2 (до крапки вказано номер завдання, після крапки вказано номер задачі) — див. посилання. Пересвідчитися у тому, що усі ці задачі розв'язано пошуком з поверненням. Звернути особливу увагу на задачу 6.2, в описі якої подано єдиний алгоритм оптимального розв'язання логічних задач. Звичайний пошук з поверненням (оптимізований перебір) без проміжних логічних висновків має істотно більший час виконання програми, ніж запропонований автором задачі.

Текст упорядкував Гезь Іван Федорович, вчитель СЗШ № 31 Дніпровського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 26.11.2018 по 30.11.2018.