НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №4
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
«МЕТОДИ ПОШУКУ У МАСИВАХ»
Варіант 18
Мета: Отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Теоретична частина
Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є:
Час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритмизазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
Необхідність додаткової пам'яті для сортування. Зазвичай необхідно O(1) пам'яті.
Стабільність (англ. Stability) — стабільне сортування не змінює взаємного розташування елементів з однаковими ключами.
За час :
Сортування вибором — (англ. Selectionsort) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
Сортування вставкою(включенням) — (англ. Insertionsort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
Сортування обміном (сортування бульбашкою, англ. Bubblesort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
Завдання до лабораторної роботи:
1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за
допомогою методу пошуку з бар’єром.
2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно
варіантів за таким принципом.
/
Блок-схема
/
/
Оцінка складності
Назва методу
Розмір матриці
Час виконання
Бар’єром
10x10
1.7е-04
50x50
4.1е-04
100x100
9,1е-04
Рабіна-Карпа
10x10
2.5е-04
50x50
5.7е-04
100x100
9.3е-04
Результат роботи
/
/
Висновок: Було написано програму, що шукає задане значення в матриці методами бар’єру та Рабіна-Карпа. Обидва алгоритми перевірені на швидкість.
Програмний код
https://replit.com/join/saemtspjmf-okseniait
#include <stdio.h>
#include <math.h>
#include <time.h>
#define BLU "\e[0;34m"
#define WHT "\e[0;37m"
int main(void) {
int L=100;
int arr1[L][L];
int arr2[L][L];
int i, j, k, t, n, m, key1;
for(i=0; i<L; i++){
for(j=0; j<L; j++){
arr1[i][j]=rand()%50+1;
arr2[i][j]=rand()%40+10;
}
}
printf("Завдання 1\n");
clock_t start = clock(), diff;
printf("Введіть шуканий елемент: ");
scanf("%d", &key1);
for(i=0; i<L; i++){
for(j=0; j<L; j++){
if(arr1[i][j]==key1){
printf(BLU"%d \t"WHT, arr1[i][j]);
}
else{
printf("%d \t", arr1[i][j]);
}
}
printf("\n");
}
printf("\n");
for(i=0; i<L; i++){
t=arr1[i][L-1];
arr1[i][L-1]=key1;
for(j=0; arr1[i][j]!=key1; j++){
}
if(j!=(L-1) || key1 == t){
printf("Елемент %d знайдено у рядку %d, у стовпчику %d\n", key1, i+1, j+1);
}
arr1[i][L-1]=t;
}
diff = clock() - start;
int msec1 = diff * 1000000 / CLOCKS_PER_SEC;
printf("\nЗавдання 2\n");
//clock_t start = clock(), diff;
int l;
int key2[l];
for(k=0; k<L; k++){
for (i=1; i<L; i++){
t = arr2[k][i];
for (j=i-1; j>=0 && arr2[k][j]>t; j--){
arr2[k][j+1] = arr2[k][j];
}
arr2[k][j+1] = t;
}
}
printf("Введіть послідовність: ");
l=2;
for(i=0; i<l; i++){
scanf("%d", &key2[i]);
}
for(i=0; i<L; i++){
for(j=0; j<L; j++){
if(arr2[i][j]==key2[0] && arr2[i][j+1]==key2[1]){
printf(BLU"%d \t%d \t"WHT, arr2[i][j], arr2[i][j+1]);
j++;
}
else{
printf("%d \t", arr2[i][j]);
}
}
printf("\n");
}
printf("\n");
for(i = 0; i <L; i++) {
int n = L;
int m = l;
int k;
for(j = 0; j <= n - m; j++) {
for(k = 0; k <m; ++k) {
if(key2[k] != arr2[i][j + k]) {
break;
}
}
if(k == m) {
printf("Послідовність знайдено у рядку %d, починаючи зі стовпчика %d\n", i+1, j+1);
}
}
}
//diff = clock() - start;
//int msec1 = diff * 1000000 / CLOCKS_PER_SEC;
printf("\nЧас виконання: %d мікросекунд \n", msec1%1000);
return 0;
}