Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи пошуку у масивах
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2023
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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); } }
Висновки.
Під час виконання лабораторної роботи досліджено метод пошуку з бар’єром та алгоритм пошуку Рабіна-Карпа. Написано програму, яка використовує дані методи пошуку. Порівняно та проаналізовано ефективності використовуваних методів пошуку.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора