Алгоритми впорядкування табличних величин. Контрольна робота з теми. ТЕМА УРОКУ. - презентация

1

2 Алгоритми впорядкування табличних величин. Контрольна робота з теми. ТЕМА УРОКУ

3 План уроку 1. Пригадай, ти це знаєш ! ( питання на перевірку ). 2. Тестова перевірка : ТЕМА -29, ТЕМА -30 – оцінювання. 3. Загальні поняття про впорядкуваня. 4. Методи впорядкування елементів масиву. 5. Демонстрація роботи методів. 6. Приклади програми впорядкування елементів одновимірного масиву. 7. Контрольна робота з теми : Опрацювання одномірних масивів. 8. Підсумки уроку та домашнє завдання.

4 1. Що таке масив ? 2. Які характеристики має масив ? 3. Як оголошуються масиви ? 4. Які масиви бувають ? 5. Дайте визначення одновимірного масиву ? 6. Які дії потрібно виконати, щоб опрацювати масив ? 7. Яким чином елементи масиву розташовуються в пам ' яті ПК ? 8. Які типи змінних називаються простими, а які структурованими ? 9. Що таке індекс елемента масиву ? 10. Скільки індексів у елемента лінійного масиву ? 11. Яким чином проводиться введення і виведення всіх елементів масиву ? ПРИГАДАЙ, ТИ ЦЕ ЗНАЄШ!

5 Задачі обробки одновимірних масивів. Задачі на змінювання значень елементів таблиці Задачі на пошук елемента з заданою властивістю Задачі на знаходження суми елементів масиву ЦЕ ПОТРІБНО ЗНАТИ!

6 Задача: знайти в масиві максимальний елемент. Алгоритм: Псевдокод: { вважаємо, що перший елемент – максимальний } for i:=2 to N do if a[i] > { максимального } then { запамятати новий максимальний елемент a[i] } Чому цикл від i=2 ? ? ЗРОЗУМІЙ, ЦЕ ПРОСТО!

7 max := a[1]; { вважаємо, що перший – максимальний } iMax := 1; for i:=2 to N do { перевіряємо всі решта } if a[i] > max then { знайшли новий максимальний } begin max := a[i]; { запамятати a[i] } iMax := i; { запамятати i } end; Додатково: як знайти номер максимального елемента? Як спростити? ? По номеру елемента iMax завжди можна знайти його значення a[iMax]. Тому всюди замінюємо max на a[iMax] і забираємо змінну max. a[iMax] ЗРОЗУМІЙ, ЦЕ ПРОСТО!

8 Програма program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln(Вихідний масив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { вважаємо, що перший – максимальний } for i:=2 to N do { перевіряємо всі решта } if a[i] > a[iMax] then { новий максимальний } iMax := i; { запамятати i } writeln; {перейти на новий рядок} writeln('Максимальний елемент a[', iMax, ']=', a[iMax]); end; випадкові числа в інтервалі [50,150) пошук максимального

9 «1": Заповнити масив з 10 елементів випадковими числами з інтервалу [ ] і знайти в ньому максимальний і мінімальний елементи та їх номери. Приклад: Вихідний масив: максимальний a[4]=10 мінімальний a[8]=-10 2": Заповнити масив з 10 елементів випадковими числами з інтервалу [ ] і знайти в ньому два максимальних елементи та їх номери. Пример: Вихідний масив: максимальний a[4]=10, a[7]=8 СПРОБУЙ ВИКОНАТИ САМОСТІЙНО!

10 Загальні поняття про впорядкування. Загальні поняття про впорядкування. -1; 2; -3; 4; -5; 6; Розглянемо невпорядкований набір із 6 чисел: Питання: Як можна було б ці числа записати в порядку зростання? Проблема: Як описати алгоритм впорядкування за зростанням? -5; -3; -1; 2; 4; 6; ЦЕ ПОТРІБНО ЗНАТИ!

11 Сортування – це розстановка елементів масиву в заданому порядку ( по зростанню, спаданню, останній цифрі, сумі дільників, …). Задача: переставити елементи масиву в порядку зростання. Алгоритми: прості і зрозумілі, проте неефективні для переважної більшості масивів метод бульбашки метод вибору складні, проте ефективні швидке сортування" (Quick Sort) сортування купою" (Heap Sort) сортування злиттям пірамідальне сортування складність O(N 2 ) складність O(N·logN) час N O(N 2 ) O(N·logN) ЦЕ ПОТРІБНО ЗНАТИ!

12 Задача: Задача: Нехай задано змінні а і b, які відповідно дорівнюють 5 і 7. Скласти алгоритм обміну значеннями між цими змінними. program change; var a, b, c: real; Begin write(Введіть два числа); readln (a, b); с:=а; a:=b; b:=a; writeln (a =,a:6:3, b =,b:6:3); Readkey; end. ЗРОЗУМІЙ, ЦЕ ПРОСТО!

13 Дуже часто при розв'язуванні задач, пов'язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення. Розглянемо деякі з методів, що дозволяють впорядкувати елементи таблиць. Методи сортування масивів Методи сортування масивів Методи сортування Методи сортування Метод вибору Метод обміну Метод включення ЦЕ ПОТРІБНО ЗНАТИ!

14 Метод вибору Ідея: знайти мінімальний елемент і поставити на місце першого (поміняти місцями з A[1] ) із решти знайти мінімальний елемент і поставити на друге місце (поміняти місцями з A[2] ), і т.д ЗРОЗУМІЙ, ЦЕ ПРОСТО! полягає в тому, що вибирається мінімальний елемент масиву, а потім виконується його обмін з першим елементом таблиці. Після цього перший елемент вважається впорядкованим і процес повторюється для підмасиву, що містить на один елемент менше за початковий, тобто елементи з 2-го до останнього. Процес повторюється кожен раз для масиву, зменшеного на один елемент. Закінчується він тоді, коли невпорядкований підмасив стає довжиною один елемент. Таким чином, загальна кількість повторень дорівнює N-1 (N - кількість елементів масиву).

15 Program Selection; Const N=20; Var Mas:array[1..N] of integer; i,j,Min,N_Min:integer; Begin For i:=1 to N-1 do begin Min:=Mas[i]; {Зберігання еталону мінімуму} N_Min:=i; {Зберігання номера мінімуму} For j:=i+1 to N do If Mas[j]< Min then Begin Min:=Mas[j]; N_Min:=j; end; {Обмін місцями мінімуму та першого елементу підмасиву} Mas[N_Min]:=Mas[i]; Mas[i]:=Min; end; End. Робота програми Робота програми ЦЕ ПОТРІБНО ЗНАТИ!

16 Метод бульбашки Ідея – бульбашка повітря в стакані води піднімається з дна вверх. Для масивів – самий маленький ("легкий") елемент переміщується вверх ("спливає") починаємо знизу, порівнюємо два сусідніх елементи; вони стоять неправильно, міняємо їх місцями за 1 прохід по масиву один елемент (самий маленький) стає на своє місце ий прохід 2-ий прохід 3-ій прохід Для сортування масиву з N елементів потрібен N-1 прохід (достатньо поставить на свої місця N-1 елемент). ЗРОЗУМІЙ, ЦЕ ПРОСТО!

17 Метод обміну (бульбашки) Метод обміну (бульбашки) Program Bubble; {Сортування за зростанням} Const N=20; Var Mas:array[1..N] of integer; i,j:integer; {i,j - змінні циклу} Rez:integer; {Rez - додаткова змінна для обміну елементів масиву між собою} Begin For i:=1 to N do For j:=1 to N-1 do If Mas[j]>Mas[j+1] then Begin {Обмін елементів масиву через третю змінну} Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez; End; End. ЦЕ ПОТРІБНО ЗНАТИ!

18 Метод вставки Метод вставки На початку сортування масив розбивається на два підмасиви, лівий з яких повинен бути впорядкованим, а правий - ні. У невідомому масиві тільки один елемент можна вважати впорядкованим, тому спочатку ліва відсортована частина складається всього з одного елементу. Потім по черзі беруться елементи з другої невпорядкованої частини і для них знаходиться місце вставки в першу частину таке, щоб впорядкованість не порушувалась. ЗРОЗУМІЙ, ЦЕ ПРОСТО!

19 Метод вставки Метод вставки 12; -8; 0; 30; 5; 100; Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої - всі останні { }. Запишемо тепер процес впорядкування по етапах: І етап: елемент, що впорядковується = -8. 1) -8 < 12, тому виконується обмін, тобто після першого кроку масив має наступний вигляд: На цьому цикл припиняє свою роботу, тому що досягнуто початок масиву (і=1). ІІ етап: елемент, що впорядковується = 0. 1) 0 -8, значить обмін не виконується, здійснюється вихід з циклу, масив залишається без змін. ЗРОЗУМІЙ, ЦЕ ПРОСТО!

20 Метод вставки Метод вставки ІІІ етап: елемент, що впорядковується = 30. 1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін ІV етап: елемент, що впорядковується = 5. 1) 5 0, цикл припиняє свою роботу, масив залишається без змін. V етап: елемент, що впорядковується = ) 100 > 30, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. -8; 0; 5; 12; 30; 100;

21 Метод вставки Метод вставки Program Insert; Const N=20; Var Mas:array[1..N] of integer; i,j,Rez:integer; Begin For i:=2 to N do Begin j:=i; {Цикл працює доки, лівий елемент більший за правий та не досягнуто початок масиву} while (j>1) and (Mas[j]

22 Домашнє завдання 1.Опрацювати презентацію, знати і вміти записати три методи сортування масивів. 2.В робочих зошитах скласти програми до 8, 12 стор.31