Урок 64                                                                         Інформатика (АП)

Методи впорядкування елементів

одновимірного масиву.

Мета.

Навчальна. Ознайомити учнів з методами впорядкування елементів одновимірного масиву  (сортування вибором, сортування обміном(метод бульбашки)).

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

Виховна. Виховувати наполегливість, естетичність у оформленні, грамотно висловлювати свої думки.

Тип уроку. Засвоєння нових знань і навичок.

Матеріали для роботи з учнями:

План

1. Введення в тему.
2. Логічні вирази та логічні операції, таблиці істиності.
3. Практичні завдання.
4. Типові запитання до уроку.
5. Домашнє завдання.

Пам’ятка для учня!

1. Пригадайте правила техніки безпеки при роботі з ПК.
2. Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Перевірка домашнього завдання.

1. Наявність.
2. Питання.
3. Дано одновимірний масив цілих чисел А[і],  де і = і, 2, …n. Вивести значення елементів масиву:

1)   у зворотному порядку;

2)  з парними індексами;

3)  з непарними індексами;

4)   що є недодатними числами;

5)   що є невід'ємними числами;

6)  що є парними числами;

7)   що є непарними числами.

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

1. Дано масив А: (3, 8, 5, 7, 6). Виконайте дії над елементами масиву.
2. 

Дано масив А[1..5]. Запишіть оператори, які виконують такі дії:

7. ввести з клавіатури значення елементів масиву;

8. вивести на екран значення елементів масиву;

9. знайти добуток елементів масиву;

10. знайти мінімальний елемент масиву;

11. знайти кількість додатних елементів;

12. знайти суму від'ємних елементів.

3. Мотивція.

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

4. Методи впорядкування елементів одновимірного масиву.

Методи сортування масивів

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

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

Задача: 

Var X: Array[1..10] of Real;

Упорядкувати масив X за неспаданням: Х[1] < Х[2] <...< Х[10].

Сортування вибором

Даний метод оснований на тому, що при кожному проході ци­клу переглядається частина масиву довжиною К елементів. При першому проході K=N, тобто в нашому прикладі К=10.

• Відшукується максимальний елемент з Х[1]..Х[10]. Максима­льний елемент міняється місцями з Х[10].
• Довжина частини масиву зменшується на 1, тобто К=9.
• Максимальний елемент з Х[1]..Х[9] міняється місцями з Х[9].
• Максимальний елемент з Х[1]..Х[2] міняється місцями з Х[2].

 For К:=10 Downto 2 Do

Begin         { пошук М-номера MAX(X[1..K])}

M:=l;  MAX:=X[1];

For i:=2 To К Do

if х[і]>мах Then

Begin

   MAX:=X[i]; M:=i;

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

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

End;

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

Метод бульбашки оснований на перестановці сусідніх чисел. Послідовно порівнюються пари сусідніх елементів Х[і] і Х[і+1] (і:1..N-1), і, якщо Х[i]>Х[i+1], то вони міняються місцями. У результаті першого перегляду послідовності на N-му місці буде найбільший з усіх елементів, тобто він, як «найлегший», наче спливає вгору. Потім переглядаються елементи від 1 до N-2; на (N-1)-му місці з’явиться елемент, найбільший серед (N-1) перших елеме­нті і т.д. Перегляд послідовностей довжиною К продовжується до тих  пір, поки К2:

К:=10;

    whіle K>=2 Do Begin

for і:=1 To K-1 Do

if x[i]>x[i+l] Then Begin C:=X[i];

X[i]:=X[i+l];

X[i+l]:=C;

    End;

K:=K-1;

    End;

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

Repeat Prap:=False;

         For і:=1 То 9 Do

   if х[і]>х[і+1] Then Begin

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

X[i+l]:=C;

Prap:= True

      End

Until Not Prap;

5. Створення та реалізація програми.

Задача.

Дано масив А[1..10], значення якого задані випадко­вим чином і знаходяться в межах від 0 до 19. Упорядкувати масив.

1. Опис величин. Опишемо масив таким чином:

         Var A: Array [1..10] of Integer;

Опишіть змінні

М - індекс максимального елемента;

МАХ - ма­ксимальний елемент на К-му проході;

К - довжина частини масиву;

і - змінна для збереження індексу елемента масиву:

          М, МАХ, к, і: integer;

2. Задания значень елементів масиву. Задайте значення масиву А випадковим чином. Виведіть масив на екран:

Randomize;

For і: = 1 То 10 Do А[і]:= Random(20);

For і:= 1 то 10  Do Write (А[і]:3); WriteLn;

3. Додайте до розділу Var опис одновимір­ного масиву В. Створіть масив В з елементів масиву А, упорядкованих за спаданням,

наприклад:

Алгоритм заповнення масиву В може бути таким: Для кожного і від 1 до 10 повторити дії:

• знайти Мах - максимальний елемент масиву А;
• змінній К присвоїти номер максимального елемента масиву А;
• елементу масиву В з індексом і присвоїти значення Мах;
• елементу А[К] присвоїти значення, яке гарантовано менше за будь-який елемент масиву А (наприклад, —1000).

For І:=1 То 10 Dо

Begin

MAX:=-1000;

For j:=l To 10 Do

If A[j]>MAX Then

Begin MAX:=A[j];

j:=k;

        End;

        B[i]=A[k];   A[k]:= -1000;

End;

Виведіть масив В на екран.

4. Упорядкуйте масив А[1..10] за неспаданням (А[1] < А[2] <...< А [10]) методом бульбашки. Виведіть упорядкований масив А на екран.
5. Вставте оператори для друкування рядка елементів масиву А на екран на кожному кроці сортування.

К:=10;

While К>=2 Do Begin

For і:=1 То к-1 Do

If   А[і]>А[і+1]   Then   Begin

С:=А[і];

А[і]:=А[і+1];

А[і+1]:=С

     End;

К:=К-1;

For і:=1 То К Do Write (А[і]: 4);

WriteLn;

End;

Запустіть програму на виконання і проаналізуйте хід сортуван­ня.

6. В несіть зміни у програму з тим, щоб упорядкувати масив за незростанням (А[1] > А[2] >...> А[10]). Виведіть упорядкований масив А на екран.

Масиви

6. Питання до уроку.

1. У чому полягає сутність методу сортування вибором максимального елемента ?
2. У чому полягає сутність методу сортування «бульбашкою»?
3. Як скоротити кількість проходів по масиву при сортуванні мето­дом «бульбашки»?
4. Дано фрагмент програми, призначений для розв 'язування такої задачі:

У масиві А [1.. 10] переставити місцями елементи, що сто­ять на парних і непарних, місцях: А[1] <-> А[2], …, А[9] <-> А[10]. Заповніть пропуски в тексті програмного коду.

While 1<=... Do Begin

С:=А[і];

А[і]:=А[... ];

А[... ]:=С;

і:=...

      End;

5. Де може стояти найбільший елемент масиву, якщо масив не упо­рядковано?
6. Де може стояти найменший елемент масиву, якщо масив упоряд­ковано за зростанням? за спаданням?
7. Для кожної пари сусідніх елементів масиву А виконується операція

S:=S + Byte (А[і] >= А[і+1 ])        (Byte (True) = 1; Byte (False) = 0)

Початкове значення S дорівнює 0. Чому дорівнює кінцеве значення S, якщо вхідний масив було:

а) упорядковано за зростанням;

б) упорядковано за спаданням;

в) не упорядковано?

Запишіть фрагмент програмного коду, призначений для виконан­ня таких дій:

8. Найбільший елемент послідовності з 10 чисел замінити нулем.
9. Переставити місцями перший і найбільший елементи послідовно­сті з 10 чисел.
10. Найбільший і найменший елементи масиву з 10 елементів за­мінити середнім арифметичним найбільшого і найменшого елементів.
11. Упорядкувати масив з 10 чисел за незростанням методом вибору найменшого елемента.
12. Структуруйте запис:

For i:=1 То 3 Do Begin For j:=1 То 2 Do Write[j:2]; WriteLn End;

Запишіть протокол роботи циклів.

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

1. Вивчити конспект.
2. Вправа. «Упорядкування одновимірних масивів даних»

1)   Дано одновимірний масив з 6 елементів. Визначити, чи є масив упорядкованим за зростанням або за спаданням. Як­що масив не упорядкований взагалі, вивести відповідь «Не упорядкована послідовність».

Блок-схема алгоритму розв'язування завдання наведена на малюнку.

2)           Опишіть масив.

Var A: Array [1..6] of integer;

Опишіть змінні, які будуть необхідні для розв'язування задачі.

3)   Запишіть оператори введення масиву А з клавіатури.

4)  Перевіримо, чи є масив упорядкованим за неспаданням. Ал­горитм розв'язування завдання: перебираємо всі елементи від 2-го до останнього. Якщо поточний елемент не більший за попередній, то прапорцевій змінній Ргар присвоюємо зна­чення False. Якщо після перегляду масиву прапорцева змінна отримала значення False, - це означає, що послідовність не була зростаючою.

Ргар := True;

For і := 2 То б Do if а(і) <= а(і - 1) Then Ргар := False;

if Prap Then WriteLn ('За неспаданням’);

5)  Додайте до оператора If, який перевіряє стан прапорцевої змінної Ргар, гілку Else і організуйте перевірку послідовнос­ті на незростання. Користуйтесь блок-схемою алгоритму.

6) Перевірте роботу програми для випадків упорядкованої за неспаданням, упорядкованої за незростанням, неупорядкованої послідовностей.