Розробка уроку — практичної роботи

Тема: упорядкування злиттям мовою PHP.

Мета: навчитися складати програму для впорядкування лінійного масиву методом злиття мовою PHP. Після виконання роботи учень:

Обладнання: комп'ютери зі встановленими ОС та середовищем програмування мовою PHP або стійким сполученням з Інтернетом для використання online-інтепретаторів PHP, (дана) інструкція.

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

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

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

2. Актуалізація опорних знань
Описати поняття, виділені у тексті жирним шрифтом і порівняти з очікуваним.

Масивце структурно організована сукупність елементів, що мають одну назву (ідентифікатор) і різні порядкові номери (індекси).

Елемент масивуодна з величин, що утворюють масив.

Індекс масивувеличина перелічуваного (зазвичай цілого) типу, яка вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці).

Властивості масиву:

Мова PHP є динамічно типізованою. Для масивів це означає: типи елементів масиву можна змінювати протягом виконання коду і для різних елементів по різному.

Cукупність розмірності й діапазонів називають формою масиву.

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

Наприклад, $а[3] — 3-тій елемент масиву , $с[j]j-ий елемент масиву .

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

Способи створення масивів:

Способи заповнення масиву
(подано на прикладі одновимірного масиву):

Виведення масиву можна здійснювати на екран:

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

Алгоритм сортування злиттям було розроблено Джоном фон Нейманом у 1945 році. В основі цього методу лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку.

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

Алгоритм побудовано за принципом «розділяй та володарюй». Масив поділяють на однакові (або практично однакові) за довжиною частини, кожну з яких впорядковують окремо. Після цього впорядковані частини «зливають» — див. ілюстрацію, запозичену з сайту Вікіпедії.

Детальніший опис при впорядкуванні за зростанням має такий вигляд:

  1. Масив поділяють на однакові (або практично однакові) за довжиною частини. Кожну з отриманих частин знову поділяють навпіл до тих пір, поки не отримають одноелементні масиви.

  2. Далі виконують злиття отриманих сусідніх частин (підмасивів):

    • з двох 1-елементних частин утворюють одну 2-елементну частину, розташувавши спочатку менший елемент, а потім більший;

    • з двох 2-елементних частин утворюють одну 4-елементну частину, порівнюючи елементи двох масивів, починаючи з початку. Менший з них записують у новостворений масив. Потім у масиві, елемент якого виявився меншим, переходять до наступного елемента. Далі продовжують порівнювати перші з незаписаних у новий масив елементів і формувати таким чином новий масив. У випадку, якщо одну з частин буде вичерпано, елементи іншої дописують у новостворений масив у тому самому порядку;
  3. В кінці операції злиття елементи новоутвореного масиву перезаписують у початковий масив.

Розіб'ємо задачу впорядкування масиву A із N елементів на простіші підзадачі, кожну з яких розв'яжемо окремо.

Нехай k — натуральне число. Розіб'ємо масив A на частини довжини k, вказавши діапазони зміни індексу (номера) елемента: 0..(k – 1), k..(2k – 1) і т.д. Назвемо масив k-впорядкованим, якщо кожну з цих частин довжини k впорядковано.

Будь-який масив 1-впорядкований. Якщо масив k-впорядкований, і N ≤ k, то він впоряд­кований.

Загальна схема алгоритму має такий вигляд:

$k=1;
while ($k < $N)
{ //перетворити k-впорядкований масив у 2k-впорядкований
  $k=$k*2;
}

Розглянемо процедуру перетворення k-впорядкованого масиву у 2k-впорядкований. Згрупуємо всі підмасиви довжиною k у пари підмасивів. Тепер пару впорядкованих підмасивів зіллємо в один упорядкований підмасив. Виконавши це зі всіма парами, отримаємо 2k-впорядкований масив.

Позначимо через:

t — кількість елементів масиву, що вже перетворено з k-впорядкованого у 2k-впорядкований;

q = t + k — номер останнього елемента першої з пари частин, які будуть «зливати»;

r = t + 2k — номер останнього елемента другої з пари частин, які будуть «зливати».

Інакше кажучи, ми будемо «зливати» дві частини (підмасиви) по k елементів з індексами (t + 1)..q і (q + 1)..r.

$t=0;
while (($t+$k)<=$N)
{ $q=$t+$k;
  if ($t+2*$k>=$N) $r=$N; 
  else             $r=($t+2*$k);
  … // злити підмасиви з індексами t+1..q і q+1..r
  $t=$r;
}

Злиття вимагає використання допоміжного масиву В для запису результатів злиття.

Запровадимо такі позначення:
p0 і q0 — номери останніх елементів частин масиву, що були злиті;
s0 — номер елемента масиву В, якому останнім було змінено значення.

На кожному кроці злиття виконують одну з двох послідовностей вказівок:

Першу послідовність вказівок (взяти елемент з першої частини) виконують при одночасному справдженні таких двох умов:

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

$p0=$t;
$q0=$q;
$s0=$t;
while (($p0!=$q) || ($q0!=$r))
{ if (($p0<$q) && ((($q0==$r)||(($q0<$r) && ($A[$p0]<=$A[$q0])))))
       { $B[$s0]=$A[$p0];  $p0++;  $s0++;}
  else { $B[$s0]=$A[$q0];  $q0++;  $s0++;}
}

Недоліком впорядкування злиттям є використання додаткової пам'яті для збереження масиву такого самого розміру, як і той, що впорядковують. Але при роботі з файлами або списками, доступ до яких здійснюють лише послідовно, це дуже зручний метод. Перевагою алгоритму також є його стійкість (він не міняє місцями однакові за значенням елементи) та прийнятна ефективність O(N log N).

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


Завдання. Використовуючи фрагменти коду, подані у викладі нового матеріалу, написати програму, яка:

Програму записати з назвою Ваше прізвище у теку, вказану вчителем.

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

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

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

  2. Переглянути хореографічну ілюстрацію методу.

  3. Ознайомитися з використанням методу злиття у розв'язуванні задач учнівських олімпіад з інформатики — див. опис розв'язання задачі 3 «Істотні інверсії» ІІІ етапу за матеріалами журнальної публікації.


Текст упорядкувала Шевченко Ірина Анатоліївна, вчитель гімназії "Грейс" Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 10.12.2018 по 14.12.2018.