НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Методи пошуку у масивах Мета роботи: метою лабораторної роботи є набуття практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Теоретична частина. Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку. Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних). Двійковий пошук (Бінарний пошук). Пошук послідовності елементів в масиві. Алгоритм Рабіна-Карпа. Метод пошуку з бар’єром Ідея алгоритму: – у вихідний масив потрібно тимчасово включити шукане значення. – для одержання результату пошуку потрібно перевірити, чи дорівнює шукане значення тому елементу масиву, на якому відбулось завершення роботи алгоритму. – навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійсненана включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. – після завершення пошуку потрібно повернути в кінець масиву початкове значення розміри масиву Роль бар’єрного елементу виконує включений в масив зразок пошуку Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку. Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця. 5 11 4 11 5 3 10 8 1 4 5 Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює - N Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1.Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2.Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом. Завдання за варіантом: № варіанту Метод пошуку  4 «Бінарний пошук»   Опис алгоритму Створив динамічний масив та заповнив його випадковими числами від 10 до 99. Створив функцію виводу showit для зручності та з її допомогою вивів створений масив. Далі «cin» та «cout» для введення користувачем числа, яке потрібно знайти. Для пошуку бар’єром я вирішив конвертувати двовимірний масив в одновимірний за допомогою створеної функції copyto. Після цього іде процес пошуку бар’єром та вивід результату: індекс елементу та час пошуку. Далі конвертуємо нашу матрицю від меншого до більшого та виводимо її за допомогою функції showit. Знову «cin» та «cout» для введення користувачем числа, яке потрібно знайти. Потім процес пошуку за допомогою методу «Бінарний пошук» та виведення результату: індекс елементу та час пошуку. Складність алгоритму Метод пошуку Час виконання  З бар’єром 0.23нс  Бінарний пошук 0.43нс   Результати роботи програми / / Програмний код https://replit.com/join/heoocfxxxp-ironfire2535 Висновок: