Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №4
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Методи пошуку у масивах»
Варіант № 20
Дата «17» червня 2022
Мета роботи: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Завдання до лабораторної роботи:
1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом.
Завдання для варіанту 20:
«Пошук послідовності елементів в масиві»
Теоретична частина
Алгоритм пошуку — алгоритм, який вирішує задачу пошуку, тобто, знаходить інформацію, яка зберігається в певній структурі даних. Структури даних можуть бути реалізовані за допомогою зв'язаних списків, масивів, дерев пошуку, хеш-таблиць чи інших методів зберігання інформації. Алгоритм пошуку на пряму залежить від структури даних для якої він реалізований.
Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого.
Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку.
– Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних)
– Двійковий пошук (Бінарний пошук)
– Пошук послідовності елементів в масиві.
– Алгоритм Рабіна-Карпа
Лінійний пошук бар’єром
Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти щораз у циклі умова, пов'язане із границями масиву. Це можна забезпечити, установивши в масив так званий бар'єр: будь-який елемент, що задовольняє умові пошуку. Тим самим буде обмежена зміна індексу.
Вихід із циклу, у якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу із циклу перевіряється, не чи бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менше, ніж у лінійного пошуку, але також є величиною того ж порядку, що й N - кількість елементів масиву.
Пошук послідовності елементів в масиві
Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку.
Пошук рядка формально визначається в такий спосіб.
Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N.
Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом).
Виконання роботи
Порівняння часу виконання в залежності від розміру масиву
Спосіб сортування
Розмір
N*N
Кількість ітерацій
Час виконання
Barier search
10*10
91
4.078ms
30*30
758
8.075ms
Word search
10*10
100
0.746ms
30*30
900
5.348ms
/Результати
Для масиву розмірністю 10 на 10 пошук бар’єром:
/
Для масиву розмірністю 10 на 10 пошук послідовності елементів в масиві:/
Для масиву розмірністю 30 на 30 пошук бар’єром:
/
/
Для масиву розмірністю 30 на 30 пошук послідовності елементів в масиві:
/
Висновки: У ході виконання даної лабораторної роботи було отримано практичні навички в обробці масивів, у пошуку елементів масивів методами бар’єрного пошуку та пошуку послідовності, досліджено і вивчено методи пошуку ключових елементів у масивах. Здійснено порівняння та аналіз ефективності використовуваних методів пошуку.
Код програми у вигляді скріншотів
/
/
/
Ви не можете залишити коментар. Для цього, будь ласка, увійдіть
або зареєструйтесь.
Ділись своїми роботами та отримуй миттєві бонуси!
Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!