Розробка уроку

Тема: бінарний пошук, тернарний пошук, пошук з поверненням мовою мовою JavaScript.

Мета:

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

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

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

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

Хід уроку

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

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

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

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

Бінарний пошук заданого елемента
Розглянемо задачу пошуку номера елемента упорядкованої за зростанням послідовності {an} (масиву), який (елемент) має значення b. Зазвичай для цього використовують двійковий (бінарний) пошук. Він полягає у послідовному поділі (приблизно) навпіл діапазону номерів, у якому проводять пошук. На початку виконання цього алгоритму опишемо такі змінні:

j — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;

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

Алгоритм бінарного пошуку має такий вигляд:

  1. Поки справджується нерівність jk, робити таке:

    • надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;

    • якщо al = b, завершити пошук зі знайденим номером l;

    • якщо al < b, надати значення змінній j = (l + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;

    • якщо al > b, надати значення змінній k = (l – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l.

  2. Завершити пошук, вважаючи його неуспішним.

Тут квадратні дужки (у першій дії всередині циклу) позначають операцію визначення цілої частини.

Дію алгоритму, записаного кодом JavaScript всередені даної HTML-сторінки, можна перевірити, натиснувши таку кнопку:

або розглянувши окрему сторінку HTML. Тут і для кожного наступного подібного прикладу потрібно перейти за посиланням і переглянути код, вибравши у контексному меню (права кнопка миші) перегляд джерела (коду сторінки).

Примітка. Нумерацію елементів масиву у мові JavaScript починають з 0, а у поданому прикладі для зручності користувача це враховано: виведено цей номер, збільшений на 1. Інакше кажучи, відповідь така, ніби нумерацію починають з 1.

У поданому прикладі:

Щоб уникнути помилок, потрібно обов'язково протестувати такі випадки:

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

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

Розгляномо лише перший варіант, бо інший абсолютно симетричний йому.

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

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

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

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

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

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

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

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

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

або розглянувши окрему сторінку HTML.

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

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

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

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

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

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

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

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

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

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

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

h[u,v]=j; // запис ходу j у клітину (u,v)
h[u,v]=0; // відмова від ходу у клітину (u,v)

Все, про що йшлося, можна поєднати у функції:

function step(i,x,y)
{ var u,v;
  for (var 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++;  document.write("Знайдено розв'язок "+r+'<br>'); out(); }
      h[u][v]=0; 
    }
  }
}

Звернення до цієї функції здійснюють з попереднім заповненням масиву h нулями, h[x0, y0] = 1, а значення i для першого звернення дорівнює 2. Нумерація елементів масиву в мові JavaScript починається з 0, що й враховано у коді. Код JavaScript вбудовано у сторінку HTML. Функцію out запроваджено лише для виведення результатів.

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

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

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

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


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

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

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

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


Текст упорядкував Савиченко Андрій Петрович, вчитель спеціалізованої школи І-ІІІ ступенів № 125 м. Києва з поглибленим вивченням англійської мови, під час виконання випускної роботи на курсах підвищення кваліфікації з 10.12.2018 р. по 14.12.2018 р.