НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «МЕТОДИ ПОШУКУ У МАСИВАХ» Варіант 13 Київ 2022 Мета: Метою лабораторної роботи є отримання практичних навичок в бробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку Теоретичні відомості Лінійний пошук з бар’єром. Ідея алгоритму: – у вихідний масив потрібно тимчасово включити шукане значення. – для одержання результату пошуку потрібно перевірити, чи дорівнює укане значення тому елементу масиву, на якому відбулось завершення роботи лгоритму. – навіть, якщо елемент у початковому масиві був відсутній, і зупинка була дійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. – після завершення пошуку потрібно повернути в кінець масиву початкове начення розміри масиву. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку. Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця. Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює – N. Алгоритм Рабіна-Карпа – це алгоритм пошуку рядка, який шукає шаблон, обто підрядок, у тексті використовуючи хешування. Ідея алгоритму: Є рядок A, довжина якого дорівнює m, потрібно знайти зразок X довжиною n. Виріжемо "віконечко" розміром n і перевіряємо по вхідному рядку. Шукаємо слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжиною n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" і на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах. Завдання до лабороторної роботи: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) задопомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідноваріантів за таким принципом. / Рис. 1. Завдання 13 варіанту. Результат роботи / Висновки: розроблено програму, що виконує пошук у невпорядкованому масиві випадоковиї чисел за допомогою методу лінійного пошуку з бар’єром, який має багато переваг у швидкості виконання на прикладах з великими розмірностями масивів. Також розроблено код, що виконує пошук підстроки з початкової строки та повертає індекс входу підстроки. Метод пошуку розроблено за алгоритмом Рабіна-Карпа. Програмний код public class Lr4 { public static void main(String[] args) { int side = 10; int[][] arr = generateArr(side); displayArr(arr); System.out.println("Введіть елемент, який треба шукати:"); Scanner scanner = new Scanner(System.in); int key = scanner.nextInt(); Point keyPos = null; for (int i = 0; i < arr.length; i++) { int index = searchWithBarrier(arr[i], key); if (index != -1) { keyPos = new Point(i+1, index+1); break; } } if (keyPos == null) System.out.println("Елемент " + key + " не знайдено"); else System.out.println("Елемент " + key + " знайдено у рядку: " + keyPos.x + ", стовпчику: " + keyPos.y); System.out.println("\nЗАВДАННЯ 2"); System.out.println("ВВедіть текст:"); String str = new Scanner(System.in).nextLine(); System.out.println("ВВедіть підстроку:"); String sub = new Scanner(System.in).nextLine(); int index = rubinCarp(str, sub); if (index == -1) System.out.println("Така підстрока відсутня у строці"); else System.out.println("Підстрока починається у строці з " + (index+1) + "-го символа!"); } static int rubinCarp(String str, String sub) { int subCode = sub.hashCode(); for (int i = 0; i <= str.length() - sub.length(); i++) { String currentSub = str.substring(i, i+sub.length()); int currentCode = currentSub.hashCode(); if (currentCode == subCode) if (currentSub.equals(sub)) return i; } return -1; } static int searchWithBarrier(int[] arr, int key) { int temp = arr[arr.length - 1]; arr[arr.length - 1] = key; int i = 0; while(arr[i] != key) i++; if (i != arr.length -1 || (i == arr.length - 1 && temp == key)) { arr[arr.length - 1] = temp; return i; } return -1; }