Методи пошуку у масивах

Інформація про навчальний заклад

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

Частина тексту файла (без зображень, графіків і формул):

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

11.05.2023 07:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!