Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи пошуку у масивах
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №4
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Методи пошуку у масивах»
Варіант № 15
Дата « 9 » червня 2022
Мета роботи:
Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методі
Теоретичні відомості:
Пошук методом бар’єром
Перевагою методу простого пошуку є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку можна було б не вказувати, що прискорило б пошук. Це наштовхує на думку, у вихідний масив потрібно тимчасово включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді після завершення пошуку потрібно повернути в кінець масиву початкове значення. Для одержання результату пошуку потрібно перевірити , чи дорівнює шукане значення тому елементові масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Включення повинно здійснюватись тільки замість останнього елементу масиву, після якого інших елементів немає.
Пошук послідовності елементів масиву
Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку. Проте, це завдання надзвичайно важливе – воно застосовується в текстових редакторах, СУБД, пошукових машинах тощо. Пошук рядка формально визначається в такий спосіб. Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N. Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом).
Алгоритм Рабіна-Карпа
Алгоритм Рабіна-Карпа – це алгоритм пошуку рядка, який шукає шаблон, тобто підрядок, у тексті використовуючи хешування. Ідея алгоритму: Є рядок A, довжина якого дорівнює m, потрібно знайти зразок X довжиною n. Виріжемо "віконечко" розміром n і перевіряємо по вхідному рядку. Шукаємо слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжиною n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" і на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах
Завдання для виконання:
1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом:
/
Результат виконання роботи:
Пошук бар’єром:
Розмір матриці
Час виконання
10х10
4542 мс
50х50
21047 мс
100х100
48426 мс
Пошук послідовності елементів в масиві:
Розмір матриці
Час виконання
10х10
3399 мс
50х50
11271 мс
100х100
22968 мс
//
Висновок: Під час виконання даної лабораторної роботи було набуто практичних навичок в обробці масивів, а саме, виконано пошук елементів у матриці зі допомогою методу з бар’єром, та пошук послідовності елементів у масиві. Часова характеристика даних алгоритмів наведена у таблицях вище. Виконані алгоритми працюють згідно вимог.
Посилання на Replit: https://replit.com/join/jvwwqczymu-tr-15fundamient
Копія коду:
#include <iostream>
#include <chrono>
using namespace std;
void barrierSearch(int *mat, int findElement, int matSize, int i){
int j=0;
mat[matSize] = findElement;
while(mat[j] != findElement) {
j++;
}
if(j == matSize) {
cout << "-1\n";
} else {
cout << "Element found at index: [" << i << "][" << j << "]\n";
}
}
void findSequence(int *mat, int *sequence, int size, int matSize, int i){
bool flag = false;
for(int j = 0; j < matSize - size + 1; j++){
for(int k = 0;k < size;k++) {
if(mat[j + k] != sequence[k]) {
break;
} else if(k == size - 1) {
cout << "Sequence found at index: [" << i << "][" << j << "]\n";
flag = true;
}
}
}
if(!flag) {
cout << "-1\n";
}
}
int main() {
srand(time(NULL));
int matSize;
cout << "Enter size of matrix:\n";
cin >> matSize;
int** mat = new int*[matSize];
for(int i = 0; i < matSize; i++) {
mat[i] = new int[matSize];
}
//input
for(int i = 0; i < matSize; i++) {
for(int j = 0; j < matSize; j++) {
mat[i][j] = rand() % 62 + (-30);
}
}
//output
cout << "Generated matrix: \n";
for(int i = 0; i < matSize; i++) {
for(int j = 0; j < matSize; j++) {
cout << mat[i][j] << "\t";
}
cout << endl;
}
int findElement;
cout << "Enter an Element to find:\n";
cin >> findElement;
auto start1 = chrono::steady_clock::now();
// barrier search
for(int i = 0;i < matSize;i++){
barrierSearch(mat[i], findElement, matSize, i);
}
auto end1 = chrono::steady_clock::now();
cout << "\nElapsed time: " << chrono::duration_cast<chrono::microseconds>(end1 - start1).count() << " ms\n";
int size;
cout << "\nEnter capacity of sequence of number:\n";
cin >> size;
// sequence input
int sequence[size];
cout << "Enter an sequence(like array):\n";
for(int i = 0; i < size; i++) {
cin >> sequence[i];
}
auto start2 = chrono::steady_clock::now();
// sequence finder
for( int i = 0; i < matSize; i++) {
findSequence(mat[i], sequence, size, matSize, i);
}
auto end2 = chrono::steady_clock::now();
cout << "\nElapsed time: " << chrono::duration_cast<chrono::microseconds>(end2 - start2).count() << " ms\n";
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора