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

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

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

Обладнання: комп’ютери зі встановленими ОС, браузером, XAMPP або стійким сполученням з Інтернетом, (дана) інструкція.

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

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

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку.

2. Актуалізація опорних знань.
Дати відповіді на запитання:

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

3. Вивчення нового матеріалу

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

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

• максимума функції 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.

Тут ε — дійсне число — деяка наперед задана точність пошуку.

Розглянемо реалізацію алгоритму на конкретному прикладі: знайти точку максимуму (3) та обчислити найбільше значення (6) функції f (x) = − x² + 6x − 3 на проміжку [−10; 10].

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

Програмне втілення алгоритму з поверненням проілюструємо на прикладі задачі з назвою «Хід коня». На шахівниці n × n клітин стоїть на полі (x, y) шаховий кінь. Потрібно знайти такий маршрут коня (ходити згідно із шаховими правилами) обходу всієї шахівниці із заходом у кожну клітин по одному разу.

Шаховий кінь ходить за таким правилом: на 2 клітинки у деякому напрямку і на 1 у перпендикулярному.

Наприклад, для шахівниці 8×8 чи 5×5 існує такий розв'язок (див. далі), а для шахівниці 3×3 такого розв'язку немає. Якщо на шахівниці можливі різні шляхи коня, можна шукати всі розв'язки або хоча б один (потрібно уточнити завдання).

Загальна структура алгоритму буде такою: на кожному кроці аналізують, чи можна ще зробити хід куди-небудь. Якщо це можливо, то роблять хід, інакше повертаються на один хід назад. Так роблять до тих пір, поки кількість ходів не стане рівною n² (першим ходом вважають вибір клітини, з якої здійснюють обхід). Загальний вигляд такого алгоритму, записаного кодом функції, такий:

function step ($i,$x,$y) // здійснення ходу $i з поля ($x, $y)
{  // опис локальних змінних
   // вибір чергового ходу
   {  // якщо хід прийнятний, то
      {  // запис ходу
         // якщо дошку не заповнено, то спроба ще одного ходу
         // інакше виведення результату
         // відмова від ходу
      } 
   }
}

Функція step є рекурсивною: вона звертається до самої себе, але вже після зробленого ходу з нової позиції.

Клітинки шахової дошки опишемо у вигляді двовимірного масиву $h розміром $n×$n. Кожний елемент цього масиву буде зберігати номер ходу, на якому це поле відвідав кінь, або нуль, якщо такого ходу ще не зроблено. Змінними $x, $y опишемо поточне розташування коня. Маємо:

• $h[$x,$y] = 0, якщо на поле ($x, $y) ще не ходили;
• $h[$x,$y] = $j, якщо на ході $j коня поставили на поле ($x, $y).

Якщо значення змінної $j дорівнює кількості зроблених ходів, то умову "дошку не заповнено" можна записати за допомогою нерівності $j < $n*$n.

З будь-якої клітинки кінь може стрибнути не більш ніж на 8 клітинок (див. малюнок).

Якщо ($x, $y) — поточні координати коня, то клітинки, на яких кінь може опинитись через один хід, мають такі координати (звичайно, якщо ці клітини існують на шахівниці):

($x + 2, $y + 1),
($x + 1, $y + 2),
($x − 1, $y + 2),
($x − 2, $y + 1),
($x − 2, $y − 1),
($x − 1, $y − 2),
($x + 1, $y − 2),
($x + 2, $y − 1)

— перелічено відповідно до попереднього малюнку. Запровадимо два масиви $a і $b, у які запишемо числа -2, -1, 1, 2 у різних комбінаціях, щоб, при додаванні відповідних елементів цих масивів до поточних координат коня на шаховій дошці дійсно виходили стрибки шахового коня. Наприклад, таким чином:

$a = [2, 1,-1,-2,-2,-1, 1, 2];
$b = [1, 2, 2, 1,-1,-2,-2,-1].

Використовуючи змінні x, y для позначення координат поточної позиції, запровадимо змінні $u, $v для координат наступної позиції:

$u = $x + $a[$k];
$v = $y + $b[$k];

де 0 ≤ $k < 8. Умова прийнятності ходу є кон'юнкцією (логічним "і") таких умов:

• (0 <= $u) && ( $u < $n)
• (0 <= $v) && ( $v < $m)
• $h[$u,$v] == 0.

function step ($i, $x, $y)
{ global $a, $b, $m, $n, $h, $r;
  for ($k=0; $k<8; $k++)
  { $u = $x + $a[$k];
    $v = $y + $b[$k];
    if ((0 <= $u) && ($u <= $m-1) &&
        (0 <= $v) && ($v <= $n-1) && ($h[$u][$v] == 0)) 
    { $h[$u][$v] = $i; 
      if ($i < $n*$m) step($i+1,$u,$v);
      else { $r++;  out($h); } // Виведення розв'язку № $r
      $h[$u][$v] = 0; 
    }
  }
}

• то збільшуємо на 1 номер ходу $i, то зменшуємо його на 1;
• то робимо хід з номером $i, то відмовляємося від нього.

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

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

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

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

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

1. Нерівності-порівняння для f (m₁) і f (m₂) змінити на протилежні за змістом.

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

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

Завдання 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, в описі якої подано єдиний алгоритм оптимального розв'язання логічних задач. Звичайний пошук з поверненням (оптимізований перебір) без проміжних логічних висновків має істотно більший час виконання програми, ніж запропонований автором задачі.

Текст упорядкував Олександр Рудик.