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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найпростішими за формою є масиви розмірності 1 (лише один індекс). Такі масиви називають лінійними або одновимірними чи векторами.

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

Форми оголошення (опису) масиву

Дужки [] вказують лише на те, що змінні розташовано у масиві, але власне масиви ще не існують. Для існування масиву потрібно зарезервувати (виділити) пам'ять за допомогою оператора new.

Загальна форма оператора new щодо одновимірних масивів має такий вигляд:

змінна_масиву = new тип[розмір];

Наприклад,

anArrayOfStrings = new String[9];

Лише після того, як описано масив і для нього зарезервовано пам'ять, можна звертатись до довільного елемента масиву.

Суміщення оголошення і виділення пам'яті для масиву можна здійснити таким чином:

тип назва_змінної[] = new тип[розмір];

У Java нумерацію елементів масиву починають з 0, тому квітню — четвертому місяцю року — відповідає елемент масиву month_days[3] з індексом 3.

Система Java виконує ретельну перевірку того, чи не була випадково здійснено спробу виходу за межі допустимого діапазону значень індексів масиву. Наприклад, у поданій програмі система часу виконання буде перевіряти відповідність значення кожного індексу допустимому діапазону від 0 до 11 включно. Якщо буде спроба звертання до елементів за межами цього діапазону, то це призведе до помилки виконання.

Способи заповнення масиву

  1. З клавіатури за допомогою класу Scanner з пакету java.util. Для отримання консольного введення в класі System визначено об’єкт in. З об’єктом System.in не дуже зручно працювати, тому, як правило, використовують клас Scanner, який у свою чергу використовує System.in — див. наступний приклад.

    package work;
    import java.util.Scanner;
    public class work {
      public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Input array length: ");
        int size = input.nextInt();  // Зчитування розміру масиву у змінну size
        int array[] = new int[size]; // Створення масиву array розміру size
        System.out.println("Input array elements:");
        for (int i = 0; i < size; i++) {
          array[i] = input.nextInt(); // Заповнення масиву
          }
        System.out.print ("Inserted array elements:");
        for (int i = 0; i < size; i++) {
          System.out.print (" " + array[i]); // Виведення введених раніше значень 
          }
        System.out.println();
        }
    }

    Спочатку імпортують клас Scanner з пакету java.util. Для створення самого об'єкта Scanner у його конструктор передають об'єкт System.in. Після цього можна отримувати значення, які вводять з клавіатури. Наприклад, щоб отримати введене число, використовують метод in.nextInt(), який повертає введене з клавіатури цілочисельне значення. В даному випадку в циклі вводяться всі елементи масиву, а за допомогою іншого циклу всі раніше введені елементи масиву виводяться в рядок.

    Клас Scanner має ще кілька методів, які дозволяють отримати введені користу­вачем значення:

    • next() — зчитує введений рядок до першого пробілу;
    • nextLine() — зчитує весь введений рядок;
    • nextInt() — зчитує введене число int;
    • nextDouble() — зчитує введене число double;
    • hasNext() — перевіряє, чи було введене слово;
    • hasNextInt() — перевіряє, чи було введено число int;
    • hasNextDouble() — перевіряє, чи було введено double.

    Методи nextByte / nextShort / nextFloat / nextBoolean класу Scanner за аналогією з nextInt зчитують дані відповідного типу даних.

  2. З файлу. Для того, щоб ввести масив з файлу, потрібно запозичити необхідні складові з бібліотеки Java — див. перші рядки поданого далі коду, у якому є звертання до попередньо створеного текстового файлу input_array.txt. Цей файл має містити (у вказаному порядку) кількість елементів масиву та значення елементів цього масиву у порядку зростання номеру елемента.

    package work;
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Arrays;
    import java.util.Scanner;
    public class work {
      public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("input_array.txt"));
        int size = scanner.nextInt();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
          array[i] = scanner.nextInt();
        }
        scanner.close();
        System.out.println("Array: " + Arrays.toString(array));
      }
    }

  3. За допомогою методу fill для заповнення всього масиву однаковими значеннями.

    package work;
    import java.util.Arrays;
    public class work {
      public static void main(String args[]) {
        int a[] = new int[5];
        Arrays.fill(a, 5);
        for (int i = 0; i < 5; i++) {
          System.out.print("a[" + i + "]=" + a[i] + "; ");
        }
      }
    }
  4. З використанням генератора випадкових чисел Random з двома різними способами ініціалізації:

    • з використанням системих дати й часу (як усталено);
    • з використанням заданого числа типу long.

    При використанні останнього способу зі сталим числом кожного разу буде породжено однакові випадкові значення, тому на практиці в основному застосо­вують саме перший спосіб.

    Методи класу Random:

    • nextBoolean();
    • nextInt();
    • nextLong();
    • nextFloat();
    • nextDouble();

    Останні два методи породжують числа з рухомою крапкою лише з проміжку [0; 1], а цілочисельні — з усього діапазону значень. Але цілі числа можна породжувати і з діапазону від 0 до max – 1 включно (при певному натуральному max), якщо писати так: nextInt(max).

    package work;
    import java.util.Random;
    public class work {
      public static void main(String args[]) {
        Random r = new Random();
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
          a[i] = r.nextInt(9);
          System.out.println("a["+i+"]="+a[i]);
        }
      }
    }

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 do
{
  //
перетворити 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 «Істотні інверсії» ІІІ етапу за матеріалами журнальної публікації.


Текст упорядкувала Овчиннікова Марина Миколаївна, вчитель школи I-III ступенів № 308 Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 10.12.2018 по 14.12.2018 з використанням матеріалів розробки Анікіної Лариси Павлівни, вчителя гімназії № 143 Оболонського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 24.11.2014 по 12.12.2014.