Як прискорити пошук елемента в лінійній таблиці?
Якщо невідомо, які дані зберігаються в лінійній таблиці, то прискорити пошук елемента, що відповідає певній умові, у програмах мовою програмування Free Pascal неможливо. Якщо заздалегідь відомі деякі ознаки даних, серед яких ведеться пошук, наприклад таблиця впорядкована, можна суттєво скоротити час роботи, застосовуючи спеціальні методи пошуку.
Одним з методів пошуку, більш ефективним, ніж лінійний, є бінарний (двійковий) пошук, який називається також методом ділення навпіл. При його використанні на кожному кроці область пошуку скорочується вдвічі.
Для ознайомлення із цим методом доцільно уточнити властивості елементів таблиці — вони мають бути впорядковані за зростанням. Позначимо шуканий елемент масиву (списку) змінною х.
Можливі два випадки:
1) якщо х менший від елемента, розташованого посередині масиву (списку), тоді завдяки впорядкованості таблиці можна не розглядати всі елементи, розташовані правіше від середнього, і застосувати цей метод до лівої половини таблиці;
2) якщо х більший від елемента, розташованого посередині масиву (списку), тоді, міркуючи аналогічно, можна виключити з розгляду ліву половину таблиці й застосувати цей метод до його правої частини.
Таким чином, на кожному кроці відсікається та частина таблиці, де не може бути знайдено заданий елемент х.
Розглянемо суть методу на прикладі. Наприклад, знайдемо, чи є серед елементів таблиці з іменем а з 10 цілих чисел, впорядкованих за зростанням, значення х = 6 (мал. 18.12).
Знайдемо номер елемента, що міститься посередині таблиці: 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 (ꞌЕлемент належить спискуꞌ).
Вправа 1. Швидкий пошук.
Завдання. У середовищі програмування 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. У вікні редактора коду запишіть команди введення елементів масиву в багаторядкове текстове поле, впорядкування елементів та їх виведення в багаторядкове текстове поле.
Комментариев нет:
Отправить комментарий