Як упорядковувати дані в
лінійній таблиці?
Для розв’язування багатьох задач зручно спочатку впорядкувати
дані за певною ознакою. Наприклад, пошук елемента в масиві чи списку можна
значно прискорити, якщо відповідні дані впорядковані. При цьому ознакою такого
впорядкування може бути за зростанням (якщо значення елементів не
повторюються), за неспаданням (якщо значення елементів можуть
повторюватись), за спаданням, за незростанням.
Правило (ознака), за яким виконують впорядкування елементів,
називають ключем впорядкування. У словниках ключами є слова,
впорядковані в лексикографічному порядку (тобто відповідно до порядку літер в алфавіті).
Список учнів впорядковано за ключем, що відповідає їх номеру в алфавітній книзі
школярів. Дати переважно впорядковуються за ключем «рррр.мм.дд», де рррр — рік,
мм — місяць, дд — день. Основним при організації впорядкування є визначення
відношення порядку на множині елементів, яка впорядковується, тобто для
будь-яких двох елементів цієї множини важливо визначити, який з них слідує за
іншим, передує іншому або що вони збігаються.
Є багато різних методів впорядкування, які відрізняються один
від одного ступенем ефективності. Ступінь ефективності враховує кількість порівнянь
та кількість обмінів, які виконано під час впорядкування: що меншою є така
кількість, то ефективнішим є метод впрорядкування.
Розглянемо один з методів впорядкування лінійної таблиці — метод
вибору. За таким методом спочатку з набору з довільним розташуванням
елементів вибирають елемент із найменшим значенням i виконують його
взаємозаміну зі значенням у першій клітинці таблицi, — таким чином у першій
клітинці таблиці розташовується найменше значення вмісту клітинок таблиці. Далі
знаходять елемент із найменшим значенням з решти n – 1 елементiв i
виконують його взаємозаміну з вмістом клітинки з номером два i т. д. Потім
розглядаються елементи, що лишилися, серед яких знову знаходять найменший, який
потім міняють місцями з вмістом
третьої
клітинки. Таким чином, для прикладу таблиці з 5 елементів, яка містить значення
довжини п’яти олівців, послідовно розглядають чотири різні набори олівців
(чотири таблиці, що мають різну довжину): у першому наборі було п’ять
елементів, у другому — чотири, у третьому — три,
у
четвертому — два. З кожним набором елементів виконують однакові дії:
-
у наборі вибирають найменший елемент, запам’ятовують його номер у
такому наборі (таблиці);
-
знайдений найменший елемент міняють місцями з першим елементом набору,
що розглядається.
Приклад упорядкування лінійної таблиці з 5 цілих чисел продемонстровано
на малюнку
де
жовтим кольором виділено найменший елемент серед елементів, що залишаються для
перегляду на кожному кроці, стрілками — порядок обміну елементами.
Зверніть увагу на те, що хоча лінійна таблиця має п’ять
елементів, достатньо 4 рази знайти найменше значення елементів з іще не
впорядкованої частини лінійної таблиці та обміняти його місцями зі значенням першого
із ще не впорядкованої частини масиву елементів.
Вправа
3. Упорядкування
масиву.
Завдання.
Створіть проект Упорядкування, у якому елементи лінійної таблиці з 10 цілих чисел
впорядковуються за зростанням.
Розробка
проекту в середовищі програмування Lazarus
1. У папці Навчальні проекти своєї структури папок створіть папку Упорядкування.
2. Відкрийте середовище Lazarus
і створіть новий проект.
Розмістіть на екранній формі
об’єкти, самостійно надайте значення їхнім
властивостям.
3. Створіть процедуру опрацювання події Упорядкувати. У вікні редактора коду опишіть змінні, які будуть
використовуватись у проекті: а — масив цілих чисел; i — номер ітерації пошуку мінімального елемента
масиву; j — номер елемента масиву; min
— найменше значення елемента; nmin
— номер найменшого елемента.
var i, j, min, nmin : integer;
а :
array [1..10] of integer;
4. У вікні редактора коду запишіть команди введення
елементів масиву в багаторядкове текстове поле, впорядкування елементів та їх
виведення в багаторядкове текстове поле.
5. Запустіть проект на виконання. Перевірте, чи
відповідають умові завдання дії, пов’язані з об’єктами управління екранної
форми. Якщо є помилки, виправте їх. Завершіть роботу з проектом і середовищем
програмування, зберігши всі зміни.
Розробка
проекту в середовищі Geany
1. Відкрийте середовище програмування Geany.
2. Створіть новий файл програми мовою програмування Python
з іменем Упорядкування
в папці Навчальні
проекти своєї структури папок.
3. У вікні редактора коду запишіть команди введення
значень елементів списку, його впорядкування та виведення списку у вікні виконання
програми. Використайте у проекті змінні: а — список цілих чисел; i — номер ітерації пошуку мінімального елемента
списку; j — номер елемента списку; min
— найменше значення елемента; nmin
— номер найменшого елемента.
Як
прискорити пошук елемента в лінійній таблиці?
Якщо невідомо, які дані зберігаються в лінійній таблиці, то
прискорити пошук елемента, що відповідає певній умові, у програмах мовою
програмування Free Pascal неможливо. Якщо заздалегідь відомі деякі
ознаки даних, серед яких ведеться пошук, наприклад таблиця впорядкована, можна
суттєво скоротити час роботи, застосовуючи спеціальні методи пошуку.
Одним з методів пошуку, більш ефективним, ніж лінійний, є бінарний
(двійковий) пошук, який називається також методом ділення
навпіл. При його використанні на кожному кроці область пошуку скорочується
вдвічі.
Для ознайомлення із цим методом доцільно уточнити властивості
елементів таблиці — вони мають бути впорядковані за зростанням. Позначимо
шуканий елемент масиву (списку) змінною х.
Можливі два випадки:
1) якщо
х менший від елемента, розташованого посередині масиву (списку), тоді
завдяки впорядкованості таблиці можна не розглядати всі елементи, розташовані
правіше від середнього, і застосувати цей метод до лівої половини таблиці;
2) якщо
х більший від елемента, розташованого посередині масиву (списку), тоді,
міркуючи аналогічно, можна виключити з розгляду ліву половину таблиці й
застосувати цей метод до його правої частини.
Таким чином, на кожному кроці відсікається та частина таблиці,
де не може бути знайдено заданий елемент х.
Розглянемо суть методу на прикладі. Наприклад, знайдемо, чи є
серед елементів таблиці з іменем а з 10 цілих чисел, впорядкованих за
зростанням, значення х = 6.
Знайдемо номер елемента, що міститься посередині таблиці: m =
5. Оскільки 6 < а[5], то далі розглядаються лише елементи,
індекси яких менші ніж 5. Про інші елементи можна відразу сказати, що вони
більші за х, оскільки таблиця впорядкована за зростанням, і тому правіше
від а[5] шуканого елемента немає. Далі розглядатимемо тільки елементи
таблиці від а[1] до а[4], знаходимо індекс середнього елемента
цієї частини: m = 2, і порівнюємо задане число 6 з елементом а[2].
Виявляється, що 6 > а[2]. Це означає, що необхідно
розглядати праву частину цієї половини таблиці від а[3] до а[4].
Знову знаходимо індекс середнього елемента m = 3 й порівнюємо його із
шуканим: а[3] = 6. Елемент m знайдено — його номер 3.
У програмах мовою програмування Python для прискорення
пошуку можна використати вбудовані засоби мови, зокрема ідеологію побудови циклу
for, у якому замість індексів елементів можна переглядати самі елементи.
Наприклад, у команді циклу
For elem in a:
змінна
elem «пробігатиме» всі елементи списку а.
Можна не переглядати елементи списку, а просто перевірити
входження елемента elem у список а за допомогою фрагмента
програми:
if elem in a:
print (ꞌЕлемент належить спискуꞌ).
Вправа 4. Швидкий пошук.
Завдання.
У середовищі програмування Lazarus
створіть проект Швидкий
пошук для визначення, чи є вказане
значення серед елементів лінійної таблиці з 10 цілих чисел.
1. У папці Навчальні проекти своєї структури папок створіть папку Швидкий
пошук.
2. Відкрийте середовище Lazarus
і створіть новий проект.
Розмістіть на екранній формі об’єкти, самостійно надайте значень їхнім властивостям.
Наприклад, як на малюнку.
3. Створіть процедуру опрацювання події натиснення
кнопки Відповідь. У
вікні редактора коду опишіть змінні, які будуть використовуватись у проекті: а — масив цілих чисел; x — шуканий елемент; i — номер елемента масиву; m — номер елемента, з якого здійснюють пошук; p — ліва межа пошуку; r — права межа пошуку; f — прапорець пошуку.
var i, m, х, p, r : real;
а :
array [1..10] of real;
f :
boolean;
4. У вікні редактора коду запишіть команди введення елементів
масиву в багаторядкове текстове поле, впорядкування елементів та їх виведення в
багаторядкове текстове поле.
5. Запустіть проект на виконання. Перевірте, чи
відповідають умові завдання дії, пов’язані з об’єктами управління екранної
форми. Якщо є помилки, виправте їх. Завершіть роботу з проектом і середовищем
програмування, зберігши всі зміни.
Комментариев нет:
Отправить комментарий