Урок "Алгоритм впорядкування масиву"

Урок № 50

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

Клас: 9

Мета:

навчальна: сформувати поняття про алгоритм впорядкування елементів табличних величин; навчити учнів розв’язувати задачі на впорядкування табличних величин.

 розвивальна: розвивати логічне та алгоритмічне мислення; сформувати вміння діяти з інструкцією, планувати свою діяльність, аналізувати і робити висновки.

виховна: виховувати інформаційну культуру, уважність, акуратність, дисциплінованість.

Тип уроку: комбінований.

Забезпечення:

дидактичне: Інформатика : підруч. для 9 кл. загальноосвіт. навч. закл. / [О. О. Бондаренко, В. В. Ластовецький, О. П. Пилипчук, Є. А. Шестопалов]. — Харків :Вид-во «Ранок», 2017. — 240 с. : іл., презентація, інструкційна картка, програмне забезпечення Lazarus.

методичне: навчальний план, електронні ресурси.

технічне: комп’ютери з виходом в мережу Інтернет.

План уроку:

І. Організаційний момент

Привітання. Перевірка присутніх та готовність учнів до уроку.

ІІ. Актуалізація опорних знань

• Що таке одновимірний масив?

(це масив, доступ до елементів якого визначається за допомогою одного індекса)

• Що необхідно для послідовного опрацювання елементів масиву?

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

• Для чого призначений компонент StringGrid (вкладка Additional)?

(для виведення різних даних типу String у табличній формі)

ІІІ. Мотивація

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

ІV. Пояснення

Сортування елементів масиву – це впорядкування їх за деякою ознакою.

Отже, розглянемо два найпростіших методи сортування масиву. Нехай потрібно впорядкувати масив Х: array [1..10] of Real; X[1] ≤X[2] ≤…≤X[10].

Сортування вибором максимального елемента

Цей метод заснований на тому, що під час кожного проходу циклу переглядається частина масиву завдовжки К елементів. Наприклад, для масиву X[1..10] під час першого проходу K = 10.

Алгоритм сортування за зростанням:

• відшукати максимальний з елементів X[1]..X[10];
• максимальний елемент поміняти місцями з X[10];
• відшукати максимальний елемент із частини масиву X[1]..X[9];
• максимальний елемент із цієї частини поміняти місцями з X[9];

           <...>

• максимальний елемент із частини масиву X[1]..X[2] поміняти місцями з X[2].

For K := 10 downto 2 do

begin

{ пошук М — номера Мах(X[1..K] }

M := 1; Max := X[1];

For i := 2 to K do

If X[i] > Max Then begin

Max := X[i]; M := i;                                                   вигляд масиву X[1..10] на кожному кроці сортування за

неспаданням вибором максимального елемента   

end;

{ перестановка X[K] і X[M] }

C := X[M]; X[M] := X[K]; X[K] := C;

end;

Сортування обміном (метод бульбашки)

Метод бульбашки ґрунтується на порівнянні та перестановці сусідніх чисел.

Алгоритм сортування за зростанням:

• послідовно порівнювати пари сусідніх елементів X[i] X[i+1] (i:1..N – 1) якщо, X[i] >X[i + 1], то поміняти їх місцями і логічній змінній Prap надати значення True. У результаті першого перегляду елементів масиву на N – му місці буде найбільший з усіх елементів, тобто він як бульбашка, «спливе» вгору;
• виконати такі самі дії з елементами від 1 до (N – 2): на (N – 1) – му місці з’явиться найбільший серед (N – 1) елементів і т. д.

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

Repeat Prap := False;

For i := 1 to 9 do

If X[i] > X[i + 1] Then begin

C := X[i]; X[i] := X[i + 1]; X[i + 1] := C;

Prap := True

end;

Until Prap = False;

V. Формування практичних умінь і навичок

Повторення правил техніки безпеки при роботі за комп’ютером:

Обов’язково!

• Дбайливо і обережно поводитися з технікою;
• Працювати на клавіатурі чистими сухими руками, не натискати на клавіші без потреби;
• Коректно завершувати роботу з тим чи іншим програмним або апаратним засобом;
• Спостерігати за роботою комп’ютера, а при виникненні пошкоджень, незвичних звуків або запахів негайно звернутися до вчителя.

Заборонено!

• Часто вмикати і вимикати комп’ютер без необхідності;
• Торкатися екрана, проводів живлення та заземлення, роз’ємів з’єднувальних кабелів і самих кабелів;
• Класти на апаратуру сторонні предмети;
• Опиратися на пристрої комп’ютера.

Працювати за комп’ютером не більше 20 хвилин!

Обов’язково роботи перерви у роботі за комп’ютером для виконання вправ для очей:

Завдання: Створіть проект, у якому дано одновимірний масив із 6 елементів і визначається, чи є масив упорядкованим за зростанням або спаданням. Якщо масив не впорядковано, вивести відповідь: «Невпорядкована послідовність».

Блок – схема алгоритму розв’язування завдання:

Алгоритм роботи:

1. Відкрийте середовище Lazarus, створіть новий проєкт.
2. Розмістіть на формі компоненти і налаштуйте їх властивості.
3. Для покрокового аналізу ходу впорядкування додаємо на форму компонент StringGrid і налаштуємо його властивості таким чином:
4. У процедурі обробки події для форми запрограмуйте виведення індексів елементів масиву до зафіксованого рядка заголовків стовпців.

5. Опишіть масив А: array[1..6] of Integer; як глобальний.

6. Створіть процедуру обробки події для кнопки Ввести значення і запрограмуйте введення елементів масиву з клавіатури в ході виконання програми.

7. Створіть процедуру обробки події для кнопки «чи упорядкований масив?». Додайте до оператора if, який перевіряє стан змінної Prap, гілку else для перевірки послідовності на спадання.
8. Збережіть проєкт у власній папці із назвою Впорядкованість масиву та скомпілюйте програму.

VІ. Підсумок уроку

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

Рефлексія:

• Що нового сьогодні дізнались?
• Чи виникали труднощі під час практичної роботи?

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

Інформатика : підруч. для 9 кл. загальноосвіт. навч. закл. / [О. О. Бондаренко, В. В. Ластовецький, О. П. Пилипчук, Є. А. Шестопалов]: Опрацювати §36, виконайте тестове завдання 36 із автоматичною перевіркою на сайті «Інтерактивне навчання» (скористайтесь смартфоном та відскануйте QR – код).