Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ ПОШУКУ У МАСИВАХ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2023
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №4
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
МЕТОДИ ПОШУКУ У МАСИВАХ
Варіант №12
Київ 2022
Мета:
Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Теоретична частина
Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних.
Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку.
Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних). Метод пошуку з бар’єром
Ідея алгоритму:
– у вихідний масив потрібно тимчасово включити шукане значення;
– для одержання результату пошуку потрібно перевірити, чи дорівнює шукане значення тому елементу масиву, на якому відбулось завершення роботи алгоритму;
– навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку;
– після завершення пошуку потрібно повернути в кінець масиву початкове значення розміри масиву.
Роль бар’єрного елементу виконує включений в масив зразок пошуку.
Метод пошуку з бар’єром
Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку. Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця. Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює - N.
Пошук послідовності елементів в масиві
Алгоритм прямого (послідовного) пошуку
Ідея алгоритму:
1) i = 1,
2) порівняти i-й символ масиву T з першим символом
масиву W,
3) збіг → порівняти другий символ і так далі,
4) розбіжність → i = i + 1 і перехід до пункту 2.
Умова закінчення алгоритму:
1) підряд М порівнянь вдалі,
2) i + M > N, тобто слово не знайдене.
Часова складність
Метод
Розмір
Час виконання
Бар’єр
10х10
27 мкс
50х50
119 мкс
100х100
809 мкс
Пошук послідовності
в масиві
10х10
25 мкс
50х50
42 мкс
100х100
49 мкс
Завдання:
1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом.
Завдання до Варіанту_12
Результати виконання лабораторної роботи:
Код:
//Лабораторна робота №4_ПСА
//ТР-15_Ткаченко_Майя, Варіант_12
#include <iostream>
#include <chrono>
using namespace std;
void poshukbar(int *arr, int ex, int rozmir, int k){
int j=0;
arr[rozmir] = ex;
while(arr[j] != ex) {
j++;
}
if(j == rozmir) {
cout << "";
} else {
cout << "<< ІНДЕКС >> шуканого елементу : [" << k << "][" << j << "]\n";
}
}
void poslidovnist(int *arr, int *p, int n, int M, int k){
bool flag = false;
for(int j = 0; j < M - n + 1; j++){
for(int k = 0;k < n;k++) {
if(arr[j + k] != p[k]) {
break;
} else if(k == n - 1) {
cout << " Послідовність знаходиться за << ІНДЕКСОМ >>:[" << k
<< "][" << j << "]\n";
flag = true;
}
}
}
if(!flag) {
cout << "";
}
}
int main() {
srand(time(NULL));
int n;
cout << "===================>\n<<<Введіть розмір масиву :\n";
cin >> n;
int** arr = new int*[n];
for(int i = 0; i < n; i++)
{
arr[i] = new int[n];
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
arr[i][j] = rand() % 100 -60;
}
}
cout <<"--------------------\nПочаткова матриця :\n ";
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << arr[i][j] << "\t";
}
cout << endl;
}
int ex;
cout<<"--------------------\n";
cout << "<<-- Введіть елемент для пошуку :";
cin >> ex;
auto st1 = chrono::steady_clock::now();
for(int i = 0;i < n;i++){
poshukbar(arr[i], ex, n, i);
}
auto e1 = chrono::steady_clock::now();
cout << "--<ЧАС ВИКОНАННЯ (мкс): " << chrono::duration_cast<chrono::microseconds>(e1 - st1).count();
int sq;
cout << "\n===================>\n<<<Введіть кількість елементів послідовності :";
cin >> sq;
int strichka[sq];
cout << "<<-- Введіть послідовність :";
for(int i = 0; i < sq; i++) {
cin >> strichka[i];
}
auto st2 = chrono::steady_clock::now();
for( int i = 0; i < n; i++) {
poslidovnist(arr[i], strichka, sq, n,i);
}
auto e2 = chrono::steady_clock::now();
cout << "\n--<ЧАС ВИКОНАННЯ (мкс): " << chrono::duration_cast<chrono::microseconds>(e2 - st2).count();
}
Посилання на Repl.it :
https://replit.com/join/hsdtpinxpz-tr-15tkachienko
Висновки
Під час виконання лабораторної роботи було розгянуто основи роботи з пошуком елементів і послідовностей. Розроблено програму, яка здатна знайти введене значення в двовимірному масиві і вказати його індекс, а також послідовність елементів і вказати значення, з якого починається послідовність.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора