Embedded Files
Алгоритми пошуку даних
Завдання пошуку даних можна сформулювати так: знайти у множині даних один або декілька елементів, які відповідають заданим властивостям. Пошук даних виконується в різних структурах даних, наприклад у словниках, списках, базах даних, масивах та інших.
Вибір того чи іншого алгоритму пошуку безпосередньо залежить від структури даних, для якої він реалізований. Пошук потрібної інформації може здійснюватись в упорядкованому наборі та в неупорядкованому. Існують алгоритми пошуку даних, які класифікують на основі механізму пошуку.
Класифікація алгоритмів пошуку даних:
• послідовний (лінійний) пошук;
• бінарний (двійковий) пошук;
• пошук із поверненням;
• тернарний пошук.
Послідовний пошук
Припустимо, що в коробці лежать кулі з номерами від 1 до 21. Який алгоритм пошуку кулі з номером 13 можна запропонувати?
Послідовний пошук базується на прямому переборі елементів у невпорядкованому масиві, наприклад зліва направо, і порівнянні кожного з них із заданим значенням.
Нехай дано масив a[0], a[1], ..., a[n] і потрібно визначити, чи є у цьому масиві елемент, значення якого збігається зі значенням с. Зрозуміло, що в масиві може бути декілька значень, які збігаються зі значенням с. Але будемо вважати, що потрібно визначити лише сам факт наявності елемента с в масиві, тобто пошук припиняється одразу після знаходження першого такого елемента.
Сутність алгоритму послідовного пошуку така.
Приклад 1. У міжнародному марафоні беруть участь представники 8 країн. Кількість учасників не обмежена. Учасники від кожної країни мають власний номер і номер країни. Потрібно розробити алгоритм та програму визначення, чи є серед 12 учасників, які фінішували першими, представник команди за номером 5.
Цю задачу можна формалізувати таким чином. Результати масових змагань учасників можна вважати випадковими. Тому сформуємо одновимірний масив цілими випадковими числами в діапазоні від 1 до 8 завдовжки 12 і визначимо першу позицію елемента, на якій розташоване число 5. Розглянемо один із варіантів алгоритму, його подано в словесно-формульній формі.
Програма реалізації алгоритму зображена на рис. 6.6.
Один із можливих результатів виконання програми може бути таким:
Інколи необхідно визначити не тільки наявність заданого елемента в масиві, а й знайти усі ці елементи, наприклад для обчислення їх суми, кількості таких елементів тощо. У такому разі аналізуються всі елементи масиву.
Приклад 2. Розробимо програму для завдання, що сформульовано у прикладі 1, але визначимо кількість учасників країни, зареєстрованої під номером 5, які фінішували в числі перших 12.
Алгоритм розв’язування цього завдання несуттєво відрізняється від попереднього, а програму його реалізації зображено на рис. 6.7.
Один із можливих результатів виконання програми може бути таким:
Практичне завдання (виконайте самостійно)
Практичне завдання (виконайте самостійно)
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Задача 1. Знайти елемент масиву, рівний X, або встановити, що його немає. Для довільного масиву використайте лінійний пошук (перебір). Потім підрахувати кількість шуканих елементів.
Задача 2. Дано масив цілих чисел: 13, 7, 6, 7, 9, 7, 6, 5. Розробіть програму обчислення кількості числа, значення якого вводиться з клавіатури.
Page updated
Google Sites
Report abuse