Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 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; } }}
Результат виконання:
/