Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи пошуку у масивах
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 4
з дисципліни «Програмування складних алгоритмів»
Тема «Методи пошуку у масивах»
Варіант № 11
Лабораторна робота № 4:
Методи пошуку у масивах
Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами, дослідження і вивчення методів пошуку ключових елементів у масивах, здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Завдання до лабораторної роботи
Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом.
№ варіанту
Метод пошуку
11
Бінарний пошук
Теоретичні відомості
Алгоритм пошуку — алгоритм, який вирішує задачу пошуку, тобто, знаходить інформацію, яка зберігається в певній структурі даних. Структури даних можуть бути реалізовані за допомогою зв'язаних списків, масивів, дерев пошуку, хеш-таблиць чи інших методів зберігання інформації. Алгоритм пошуку на пряму залежить від структури даних, для якої він реалізований.
Алгоритми пошуку класифікуються на основі їх механізму пошуку. Є послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних, лінійний та бінарний пошуки, алгоритм Рабіна-Карпа, метод пошуку з бар’єром та ін.
Лінійний пошук
Лінійний пошук належить до найбільш простих способів пошуку даних. Мета лінійного пошуку – знайти потрібний елемент (ключ) в масиві даних. В алгоритмі лінійного пошуку кожен елемент масиву послідовно порівнюється з ключем до тих пір, поки не буде знайдено потрібний елемента або не буде проскановано увесь масив.
В контексті лінійного пошуку можуть виникати наступні задачі:
визначити наявність заданого елементу в масиві (наборі даних);
визначити кількість входжень заданого елементу в масиві;
визначити номер позиції або масив номерів позицій розміщення заданого елементу в масиві.
Реалізація лінійного пошуку може бути розширена для використання в багатовимірних масивах.
Приклад:
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;
}
еlse
{
return -1;
}
}
}
Пошук бар’єром
Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти щораз у циклі умови, пов'язаної із границями масиву. Це можна забезпечити, установивши в масив так званий бар'єр: будь-який елемент, що задовольняє умові пошуку. Тим самим буде обмежена зміна індексу.
Вихід із циклу, у якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу із циклу перевіряється, чи не бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менша, ніж у лінійного пошуку, але також є величиною того ж порядку, що й N - кількість елементів масиву.
Існує два способи установки бар'єра: додатковим елементом або замість крайнього елемента масиву.
Приклад:
int LіnSearchQuіck(іnt m[n+1], іnt key)
{
іnt і=0;
M[n]=key;
whіle (m[і]!=key) і++ ;
іf (і==n+1)
return – 1;
else
return і;
}
Двійковий (Бінарний) пошук
Алгоритм двійкового пошуку можна використати для пошуку елемента із заданою властивістю тільки в масивах, упорядкованих по цій властивості. Так при пошуку числа із заданим значенням необхідно мати масив, упорядкований по зростанню або по убуванню значень елементів. А, наприклад, при пошуку числа із заданою сумою цифр масив повинен бути впорядкований по зростанню або по убуванню сум цифр елементів.
Ідея алгоритму полягає в тому, що масив щораз ділиться навпіл і вибирається та частина, де може перебувати потрібний елемент. Розподіл триває поки частина масиву для пошуку більше одного елемента, після чого залишається перевірити цей елемент, що залишився, на виконання умови пошуку.
Існують дві модифікації цього алгоритму для пошуку першого й останнього входження. Все залежить від того, як вибирається середній елемент: округленням у меншу або більшу сторону. У першому випадку середній елемент ставиться до лівої частини масиву, а в другому - до правого.
У процесі роботи алгоритму двійкового пошуку розмір фрагмента, де цей пошук повинен тривати, щораз зменшується приблизно у два рази. Це забезпечує обчислювальну складність алгоритму порядку логарифма N по підставі 2, де N - кількість елементів масиву.
Приклад:
Int BinarySearch(іnt A[0..N-1], іnt value) {
low = 0
high = N - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid //знайдено
}
return -1 //не знайдено
}
Алгоритм Рабіна-Карпа
Алгоритм Рабіна-Карпа – це алгоритм пошуку рядка, який шукає шаблон, тобто підрядок, у тексті використовуючи хешування.
Ідея алгоритму:
Є рядок A, довжина якого дорівнює m, потрібно знайти зразок X довжиною n.
Виріжемо "віконечко" розміром n і перевіряємо по вхідному рядку. Шукаємо слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжиною n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше.
Якщо значення цієї функції на слові в "віконечку" і на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах.
Результати роботи
Створюємо динамічний двовимірний масив arr[][] розмірністю row*column (задаємо з клавіатури). Ініціалізуємо псевдовипадковими числами за допомогою функції srand(time(NULL)) з бібліотеки #include <ctime> у діапазоні від 50 до 350. Для пошуку заданого елемента двовимірний масив перетворимо з одновимірний. Для цього створимо функцію transferArray(), у яку передаємо динамічні одновимірний та двовимірний масиви й розмірність. Вкладеним циклом for() заповнюємо newArr[], розмірність якого row*column, елементами з arr[][].
Створюємо функцію searchWithBarrier() для пошуку елемента методом з бар’єром. Для цього позначимо, що останній елемент масиву є ключем. Циклом while() проходитимемось по всім елементам та рахуватимемо ітерації поки не знайдеться потрібний елемент. Якщо такого елементу немає, то повертаємо -1, а якщо є, повертаємо знайдене число.
Для бінарного пошуку створимо функцію binarySearch(), у яку передаємо одновимірний масив, ліву та праву межі, елемент, який потрібно знайти. Лівою межею є найперший елемент, а правою – останній. Для пошуку елементу спочатку треба відсортувати масив. Для цього створимо функцію sortArray(). Циклом while() шукатимемо потрібний елемент. Він виконуватиметься доти, поки межі не зійдуться. Змінна m відповідає за середнє число. Якщо середній елемент більший за вказане число, то праву межу зміщуємо на 1 вліво. Якщо середній елемент менший за вказане число, то ліву межу зміщуємо на 1 вправо. В іншому випадку повертаємо задане число.
Функція arraySearch() відповідає за здійснення пошуку ключа (необхідного числа) методом з бар’єром та бінарним пошуком. До неї передаємо початковий масив, його розмірність та номер завдання (змінна operationForSearch). У ній створюємо змінну key – змінна для пошуку необхідного елемента, значення якої уводитимемо з клавіатури. Якщо метод пошуку 1, виконується пошук методом з бар’єром, якщо 2 – бінарний пошук. Обчислюємо час виконання алгоритму та виводимо необхідні результати. Для виведення номеру рядка потрібно індекс елемента поділити на кількість стовпців, а для номеру стовпця - індекс елемента поділити з остачею на кількість стовпців.
Передаємо створені функції в main(). Звільняємо пам’ять динамічних масивів. Для виведення результатів створено функції print().
Назва методу
Розмірність масиву
Кількість ітерацій
Час виконання
Метод з бар’єром
10*10
32
4*
10
−7
с
50*50
419
1.3*
10
−6
с
100*100
105
5*
10
−7
с
Бінарний пошук
10*10
7
5*
10
−7
с
50*50
9
4*
10
−7
с
100*100
9
5*
10
−7
с
1.4. Висновок
У ході лабораторної роботи було ознайомлено з методами пошуку в масивах. Отримано практичні навички в обробці масивів, у пошуку елементів масивів різними методами, досліджено і вивчено методи пошуку ключових елементів у масивах, здійснено порівняння та аналіз ефективності використовуваних методів пошуку.
Лістинг програми та результати роботи
#include <iostream>
#include <ctime>
#include <iomanip>
#include <chrono>
using namespace std;
int iterations = 0;
void initialMatrix(int** arr, int row, int column);
void print(int** arr, int row, int column);
void transferArray(int** arr, int* newArr, int row, int column);
void sortArray(int** arr, int row, int column);
int searchWithBarrier(int* newArr, int size, int key);
int binarySearch(int* newArr, int l, int r, int key);
void arraySearch(int** arr, int row, int column, int operationForSearch);
int main() {
int row, column;
cout << "Enter rows count: ";
cin >> row;
cout << "Enter columns count: ";
cin >> column;
int** arr = new int* [row];
for (int i = 0; i < row; i++)
arr[i] = new int[column];
cout << "Task 1\nInitial matrix: " << endl;
initialMatrix(arr, row, column);
print(arr, row, column);
arraySearch(arr, row, column, 1);
cout << "Task 2\nSorted matrix: " << endl;
sortArray(arr, row, column);
print(arr, row, column);
arraySearch(arr, row, column, 2);
for (int i = 0; i < row; i++) {
delete[] arr[i];
}
delete[] arr;
return 0;
}
void initialMatrix(int** arr, int row, int column) {
srand(time(NULL));
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
arr[i][j] = 50 + rand() % 300;
}
}
}
void print(int** arr, int row, int column)
{
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
cout << setw(5) << arr[i][j] << " ";
}
cout << endl;
}
}
void transferArray(int** arr, int* newArr, int row, int column)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
newArr[i * column + j] = arr[i][j];
}
}
}
void sortArray(int** arr, int row, int column)
{
for (int k = 0; k < row; k++)
for (int p = 0; p < column; p++)
for (int i = 0; i < row; i++)
for (int j = 0; j < column; j++)
if (arr[i][j] > arr[k][p])
swap(arr[i][j], arr[k][p]);
}
int searchWithBarrier(int* newArr, int size, int key)
{
int i = 0;
newArr[size - 1] = key;
while (newArr[i] != key)
{
iterations++;
i++;
}
if (i == size + 1)
return -1;
else
return i;
}
int binarySearch(int* newArr, int l, int r, int key)
{
while (l <= r) {
iterations++;
int m = l + (r - l) / 2;
if (newArr[m] > key)
r = m - 1;
if (newArr[m] < key)
l = m + 1;
else
return m;
}
return -1;
}
void arraySearch(int** arr, int row, int column, int operationForSearch)
{
int key;
cout << "\nEnter the number you want to find: ";
cin >> key;
iterations = 0;
int size = row * column;
int* newArr = new int[size];
transferArray(arr, newArr, row, column);
int index = 0;
auto start = chrono::high_resolution_clock::now();
if (operationForSearch == 1)
{
index = searchWithBarrier(newArr, size, key);
}
else if (operationForSearch == 2)
{
index = binarySearch(newArr, 0, size, key);
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<float> duration = end - start;
if (index != -1) {
cout << "Our number: row: " << (index / column) + 1 << "\tcolumn: " << (index % column) + 1 << endl;
cout << "The operating time of the algorithm: " << duration.count() << endl;
cout << "Number of iterations: " << iterations << endl;
}
delete[] newArr;
}
1.6. Результат
/
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора