НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Методи пошуку у масивах Варіант 4 Київ 20____ Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Теоретична частина Лінійний пошук Ідея : Проглядати почергово елементи масиву, доки не буде знайдено шуканий елемент або не буде досягнуто кінець масиву. Лінійний пошук з бар'єром Ідея : Як і у попередньому випадку, елементи проглядаються по черзі, але для зменшення кількості порівнянь після останнього елемента додається елемент з ключем, що дорівнює шуканому значенню. Алгоритм Рабіна — Карпа Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі. Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше. Алгоритм полягає в наступному: обчислити число p; обчислити всі  Для тих s для яких виконати перевірку P[1..m] = T[s+1..s+m]. Псевдокод алгоритму / Завдання по варіанту 1. Знайти заданий елемент у невпорядкованому масиві (не менше10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом / Оцінка складності алгоритму Складність алгоритму пошуку з бар’єром – O(n). Складність алгоритму пошуку Рабіна-Карпа – O(n*m). Спосіб сортування Розмір N*N Час виконання  Пошук з бар’єром 10*10 20мс   50*50 29мс  Пошук методом Рабіна-Карпа 10*10 9мс   50*50 10мс   Результати виконання лабораторної роботи. / Програмний код import java.util.*; public class LR4 { static int iteration1 =0; static int iteration2 =0; public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Введіть розмір масиву: "); int n = scan.nextInt(); int[][] arr = new int[n][n]; for (int i = 0; i < arr.length; i++) for (int j = 0; j < arr.length; j++) arr[i][j] = (int) (Math.random() * 51); System.out.println("Початковий масив для пошуку з бар'єром:"); printArr(arr); System.out.print("Введіть число, яке Ви хочете знайти: "); int num = scan.nextInt(); long firstTime2 = System.currentTimeMillis(); linearSearchWithBarrier(arr, num); firstTime2 = System.currentTimeMillis() - firstTime2; for (int i = 0; i < arr.length; i++) Arrays.sort(arr[i]); System.out.println("\nВідсортований масив для пошуку послідовності алгоритмом Рабіна-Карпа:"); printArr(arr); System.out.print("Введіть кількість чисел у послідовності: "); int amountOfNumbers = scan.nextInt(); int[] sequence = new int[amountOfNumbers]; System.out.print("Введіть послідовність чисел з масиву: "); for (int i = 0; i < amountOfNumbers; i++) { sequence[i] = scan.nextInt(); } long secondTime2 = System.currentTimeMillis(); searchPattern(sequence, arr); secondTime2 = System.currentTimeMillis() - secondTime2; System.out.println("Час виконання пошуку з бар'єром : " + firstTime2 + " мілісекунд."); System.out.println("Час виконання пошуку методом Рабіна-Карпа: " + secondTime2 + " мілісекунд."); } public static void printArr(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { System.out.print(arr[i][j] + "\t"); } System.out.println(); } } public static void linearSearchWithBarrier(int[][] arr, int num) { int temp; int count=0; for (int i = 0; i < arr.length; i++) { iteration1++; temp = arr[i][arr.length - 1]; arr[i][arr.length - 1] = num; int j; for (j = 0; arr[i][j] != num; j++) { iteration1++; } if (j != (arr.length - 1) || num == temp) {//Не уткнулись в бар'єр або останній елемент був шуканим iteration1++; System.out.println("Число " + num + " знайдено у " + (i + 1) + " рядку, " + (j + 1) + " стовпчику"); count++; } arr[i][arr.length - 1] = temp; } if(count==0) System.out.println("Число не знайдено"); iteration1++; System.out.println("Кількість ітерацій: " + iteration1); } static void searchPattern(int[] sequence, int[][] arr) { int count=0; for (int i = 0; i < arr.length; i++) { iteration2++; int n = arr.length; int m = sequence.length; int k; for (int j = 0; j <= n - m; j++) { iteration2++; for (k = 0; k < m; ++k) { iteration2++; if (sequence[k] != arr[i][j + k]) { iteration2++; break; } } if (k == m) { System.out.println("Послідовність знайдено у " + (i + 1) + " рядку, починаючи з стовпчика " + (j + 1)); count++; iteration2++; } } } if(count==0) System.out.println("Послідовність не знайдено"); iteration2++; System.out.println("Кількість ітерацій: " + iteration2); } } Висновки. Під час виконання лабораторної роботи досліджено метод пошуку з бар’єром та алгоритм пошуку Рабіна-Карпа. Написано програму, яка використовує дані методи пошуку. Порівняно та проаналізовано ефективності використовуваних методів пошуку.