Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи пошуку у масивах
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №4
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Методи пошуку у масивах»
Варіант № 16
Дата «02» травень 2022
Київ 2022
Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами, дослідження і вивчення методів пошуку ключових елементів у масивах, здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Завдання до лабораторної роботи:
Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом.
/
Рисунок 1
Теоретичні відомості:
Сутність методу полягає в тому, що елементи масиву послідовно порівнюються зі зразком пошуку. Якщо має місце співпадання, то пошук закінчується. Інакше здійснюється перехід до наступного елементу. Отже, пошук припиняється або при досягненні кінця масиву, або при знаходженні заданого елемента. Оскільки наявність та місцезнаходження елементу наперед невідомі, то для практичної реалізації алгоритму потрібно застосувати цикл з передумовою. Перевірку знаходження елементу здійснимо за значенням змінної i, що є індексом поточного елементу масиву. Якщо значення цієї змінної перевищує n (кількість елементів масиву), то елемент не знайдений, а отже, в масиві відсутній. Алгоритм простого пошуку запишемо у вигляді відповідної процедури.
Метод пошуку з бар’єром.
Перевагою методу простого пошуку є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку можна було б не вказувати, що прискорило б пошук. Це наштовхує на думку, у вихідний масив потрібно тимчасово включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді після завершення пошуку потрібно повернути в кінець масиву початкове значення. Для одержання результату пошуку потрібно перевірити , чи дорівнює шукане значення тому елементові масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Включення повинно здійснюватись тільки замість останнього елементу масиву, після якого інших елементів немає.
Пошук послідовності елементів в масиві
Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку. Проте, це завдання надзвичайно важливе – воно застосовується в текстових редакторах, СУБД, пошукових машинах тощо.
Пошук рядка формально визначається в такий спосіб.
Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N. Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом).
Приклад 1. Потрібно знайти всі входження зразка W = abaa у тексті T = abcabaabcabca.
/
Рисунок 2
Відповідь: Зразок входить у текст тільки один раз, зі зсувом S = 3, індекс і =4.
Хід роботи:
Написано програмний код, який виконує 2 завдання: перше за методом барьерного пошуку, друге пошук послідовності в масиві. Для цього було створено два метода.
Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів матриці(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку.
Було створенно метод для полегшення метода main, у якому відбувалося наповнення матриці випадковими числами(getArr). цей метод можна спростити до 2n^2+9n+4 = Θ(n^2).
Метод barrierSearch має цикл while який перевіряє усі значення, тому буде 2*n*n = Θ(n^2).
З barrierSearch: 2*n*n = 2*n^2= Θ(n^2).
З пошуком послідовності: 2*n^2 + 4n +4= Θ(n^2).
З barrierSearch:
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
200
0.001 msec
50
5000
0.003 msec
100
20000
0.003 msec
500
500000
0.004 msec
З pospos:
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
244
0.001 msec
50
5204
0.003 msec
100
20404
0.004 msec
500
502004
0.006 msec
/
Код програми:
Посилання на код:
https://replit.com/join/qxomtlclzm-tr-15khavkin
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
void swap(int a, int b){
int t;
t = a;
a = b;
b = t;
}
void printArr(int** Arr, int rows, int colu){//Метод для виводу матриці
for(int i=0; i<rows;i++){
printf("\n");
for(int j=0;j<colu;j++)
printf("\t%d\t", Arr[i][j]);
}
}
void getArr(int** mat, int rows, int colu){//Метод для заповнення матриці
srand(time(NULL));
int ran;
for(int i=0; i<rows;i++){
for(int j=0;j<colu;j++){
ran = rand() % 61 - 30; //Генерація випадкого числа від -30 до 30
mat[i][j]=ran;
}
}
}
void sortArr(int** Arr, int rows, int colu)
{
for (int k = 0; k < rows; k++)
for (int p = 0; p < colu; p++)
for (int i = 0; i < rows; i++)
for (int j = 0; j < colu; j++)
if (Arr[i][j] > Arr[k][p]){
int t;
t = Arr[i][j];
Arr[i][j] = Arr[k][p];
Arr[k][p] = t;
}
}
int barrierSearch(int* NewArr, int Length, int Key)
{
int i = 0;
NewArr[Length - 1] = Key;
while (NewArr[i] != Key) {
i++;
}
if (i == Length + 1)
return -1;
else
return i;
}
void convArr(int** Arr, int* NewArr, int Rows, int Cols){
for (int i = 0; i < Rows; i++)
for (int j = 0; j < Cols; j++)
NewArr[i * Cols + j] = Arr[i][j];
}
int pospos(int *arr, int sizeArr, int *sequence, int sequenceSize) {//функція пошуку послідовоності
int j = 0;
for (int i = 0; i < sizeArr; i++) {//пошук послідовності від першого елементу масива
if (arr[i] == sequence[0])//знайдено перше збіг
j = 0;
while (i + j<sizeArr && arr[i + j] == sequence[j]){// елементи послідовності збігають і не останій елемент масиву
j++;
if (j == sequenceSize) {//проверили все элементы последовательности совпадают
printf("Починаючи з %d-го елементу масива знайдені\nВсе элементы последовательности совпадают", i);
return i;
}
}
}
printf("Збігу не знайдено");
return 0;
}
int main(void) {
int n,m,x,s,V,K,key,key1,key2,index;
printf("\nВедіть N, M: ");
scanf("%d %d", &n, &m);
int** array=(int**)malloc(n * sizeof(int*));
for (int i=0; i < n; i++){
array[i]=(int*)malloc((m)*sizeof(int));
}
printf("\nЗавдання 1 \nПервісна матриця\n");
getArr(array, n ,m);
printArr(array, n ,m);
printf("\nВедіть число, яке ви хочете знайти:\n");
scanf("%d", &key);
int size = n*m;
int* newArr=(int*)malloc(size * sizeof(int));
convArr(array, newArr, n, m);
index=0;
clock_t ttime1,ttime2,ttime3,ttime4;
ttime1 = clock();
index = barrierSearch(newArr, size, key);
ttime2 = clock();
if (index != -1)
printf("Шукане число: Ряд: %d Стовпчик: %d", index / m + 1 ,index % m + 1);
printf("\nВитрачений час на завдання 1: %lf msec\n\n", (double)(ttime2-ttime1)/CLOCKS_PER_SEC*1000);
printf("\nЗавдання 2 \nВідсортована матриця\n");
sortArr(array, n ,m);
printArr(array, n ,m);
convArr(array, newArr, n, m);
free (array);
index=0;
int kil;
printf("\nВведіть кількість елементів послідовністі:\n");
scanf("%d", &kil);
int *posl;
posl=(int*)malloc(kil * sizeof(int));
printf("\nВведіть послідовність:\n");
for (int i = 0; i < kil; i++)
scanf("%d", &posl[i]);
ttime3 = clock();
index = pospos(newArr, size, posl, kil);
ttime4 = clock();
printf("\nВитрачений час на завдання 2: %lf msec\n\n", (double)(ttime2-ttime1)/CLOCKS_PER_SEC*1000);
return 0;
}
Результат програми: / /
Висновок: У цій лабораторної роботі ознайомилися з методами пошуку елементів у масиві. Перевірили варіанти розв’язання завдання на часову складність і кількість ітерацій. Довели практичну доцільність пошуку бар’єром і його маленьку складність. Для маленьких обсягів масиву розбіжність невелика. Зроблено звіт до лабораторної роботи та надіслано викладачу.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора