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

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

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

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

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

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

Хід уроку

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

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

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

Елемент масивуодна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

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

Масив має такі властивості:

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

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

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

Можна використовувати від’ємні індекси: для натурального числа j вираз a[-j] повертає значення a[a.length - j]. Тут a.length — довжина масиву a. Наприклад: а[-1] — останній елемент масиву а, а[-2] — 2-й з кінця елемент масиву а.

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

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

Способи виведення елементів масиву

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
  end
  … # злити підмасиви з індексами t+1..q і q+1..r
  t=r;
end

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

Запровадимо такі позначення:
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=p0+1
    s0=s0+1
  else
    B[s0]=A[q0]
    q0=q0+1
    s0=s0+1
  end
end 

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

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


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

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

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

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

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

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

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


Текст упорядкував Шевчук Станіслав Олегович, вчитель гімназії № 283 Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 29.10.2018 по 02.11.2018. У роботі використано матеріали роботи Анікіної Лариси Павлівни.