Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 4 з дисципліни «Програмування складних алгоритмів» Тема «Методи пошуку у масивах» Варіант № 24 Дата «5» травня 2022 Мета роботи: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних . Завдання до роботи Методичні вказівки Лабораторна робота спирається на знання й уміння, отримані при вивченні наступних питань лекції: – Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку. – Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних) – Двійковий пошук (Бінарний пошук) – Пошук послідовності елементів в масиві. – Алгоритм Рабіна-Карпа Завдання до лабораторної роботи: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві згідно варіантів за таким принципом Завдання / 1.2. Теоретичні відомості Задача пошуку елемента в послідовності - одна з важливих задач програмування як з теоретичної, так і практичної точок зору. Ось її формулювання: Нехай A = {a1, a2, ...} - послідовність однотипних елементів і b - деякий елемент, який володіє властивістю P. Знайти місце елемента b в послідовності А. Оскільки представлення послідовності в пам’яті може бути здійснено в виді масиву, задачі можуть бути уточнені як задачі пошуку елемента в масиві A: Знайти максимальний елемент масиву; Знайти даний елемент масиву; Знайти k-тий за величиною елемент масиву; Основні алгоритми пошуку елементів в масиві: Лінійний пошук Ідея : Проглядати почергово елементи масиву, доки не буде знайдено шуканий елемент або не убде досягнуто кінець масиву.       Код ф-ції:  //Передаємо масив, ключ, розмір масиву int linSearch(int arr[], int Key, int arrSize){  for (int i = 0; i < arrSize; i++){ //Шукаємо елемент    if (arr[i] == requiredKey)     return i; //Якщо знайшли  }  return -1; //Якщо елемент не знайшли } Лінійний пошук з бар'єром Ідея : Як і у попередньому випадку, алементи проглядаються по черзі, але для зменшення кількості порівнянь після останнього елемента додається елемент з ключем, що дорівнює шуканому значенню.       Код ф-ції:  //Передаємо масив, ключ, розмір масиву int find(int *arr, int size, int key) {   int last = arr[size - 1]; //Зберігаємо останій елемент масива   arr[size - 1] = key;//Гарантуємо , що значення є в масиві     int i = 0;   for (i = 0; arr[i] != value; ++i) {//Шукаємо індекс елемента   }   arr[size - 1] = last;//Відновлюємо останій елемент   if (i != (size - 1) || value == last) {//Не дійшли до бар'єра або останій елемент був шуканим    return i; //Знайшли елемент   }else{     return -1; //Не знайшли елемент   } } Бінарний пошук Ідея : Пошук реалізується в упорядкованому масиві. Шукане значення слід порівняти з ключем середнього елементу, у результаті цього порівняння визначити, у якій половині масиву знаходиться шуканий ключ, і знову застосувати ту саму процедуру до половини масиву. Процес припиняється, коли буде знайдено елемент, або коли "довжина" таблиці стане менше 1. Код ф-ції: //Передаємо масив, ліву та праву границ, ключ int Search_Binary (int arr[], int left, int right, int key){  int midd = 0;  while (1){  midd = (left + right) / 2; // Середній елемент  if (key < arr[midd])       //Якщо ключ менше середьного значення  right = midd - 1;      // зменшуєм праву границю  else if (key > arr[midd])  //Якщо ключ більше середьного значення  left = midd + 1;    // зменшуєм ліву границю  else                       // ключ == значеню  return midd;           // елемент знайдено    if (left > right)          // Якщо границі зійшлись  return -1;              // елемент не знайдено  } } Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі. Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше. 1.3. Результати роботи Було створенно програму яка генерує матрицю випадкових чисел та шукає потрібний елемент у масиві за допомогою методу пошуку з бар’єром. Також програма шукає масив елементів (у нашому випадку підрядок, з тексту). Метод пошуку Розмір N*N К-сть ітерацій Час виконання  Пошук з бар’єром (невпорядкована) 10*10 146 0,74 ms   50*50 2730 3,28 ms   1.4. Висновки по роботі При виконанні лабораторної роботи №4 було отримано практичні навички в обробці масивів, у пошуку елементів масивів різними методами. Досліджено і вивчено методи пошуку ключових елементів у масивах. 1.5. Лістинг програми package Algoritm.ua; import java.math.BigInteger; import java.util.Calendar; import java.util.Random; import java.util.Scanner; import java.util.SortedMap; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int[][] array = new int[50][50]; System.out.println("Array of numbers"); initialization(array); System.out.print("Enter key:"); int key = scan.nextInt(); long time = System.nanoTime(); barrierSearch(array, key); time = System.nanoTime() - time; System.out.printf("Elapsed %9.5f ms\n", time/1_000_000.0); Scanner scanner = new Scanner(System.in); System.out.println("\nTask №2 Rabin-Karp method "); System.out.print("Enter the text: "); String text = scanner.nextLine(); System.out.print("Enter the key: "); String keyText = scanner.nextLine(); RabinKarp searcher = new RabinKarp(keyText); time = System.nanoTime(); System.out.printf("Index of a first character: %s", searcher.search(text)); time = System.nanoTime() - time; System.out.printf("\nElapsed %9.5f ms\n", time / 1_000_000.0); } public static void barrierSearch(int[][] array, int key) { for (int i = 0, j = 0; i < array.length; i++) { int tp = array[i][array[0].length - 1]; array[i][array[0].length - 1] = key; while (array[i][j] != key) { j++; } if (j == array[0].length - 1) { if (tp == key) System.out.printf("Стовпчик: %d. Рядок: %d \n", j + 1, i + 1); else System.out.println(-1); j = 0; continue; } else System.out.printf("Стовпчик: %d. Рядок: %d \n", j + 1, i + 1); j = 0; } } public static void printArray(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { System.out.printf("%3d", arr[i][j]); } System.out.println(); } } // Ініціалізація випадковими числами public static void initialization(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] = (int) (Math.random() * 20); System.out.printf("%3d", array[i][j]); } System.out.println(); } } static class RabinKarp { static private long dochash = -1L; private String pat; private long patHash; private int M; private long Q; private int R; private long RM; public RabinKarp(int R, char[] pattern) { throw new RuntimeException("Operation not supported yet"); } public RabinKarp(String pat) { this.pat = pat; R = 256; M = pat.length(); Q = longRandomPrime(); RM = 1; for (int i = 1; i <= M - 1; i++) RM = (R * RM) % Q; patHash = hash(pat, M); } private static long longRandomPrime() { BigInteger prime = new BigInteger(31, new Random()); return prime.longValue(); } private long hash(String key, int M) { long h = 0; for (int j = 0; j < M; j++) h = (R * h + key.charAt(j)) % Q; return h; } private boolean check(String txt, int i) { for (int j = 0; j < M; j++) if (pat.charAt(j) != txt.charAt(i + j)) return false; return true; } public int search(String txt) { int N = txt.length(); if (N < M) return -1; long txtHash; if (dochash == -1L) { txtHash = hash(txt, M); dochash = txtHash; } else txtHash = dochash; // check for match at offset 0 if ((patHash == txtHash) && check(txt, 0)) return 0; for (int i = M; i < N; i++) { txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q; txtHash = (txtHash * R + txt.charAt(i)) % Q; int offset = i - M + 1; if ((patHash == txtHash) && check(txt, offset)) return offset; } return -1; } } } Результат виконання: /