МЕТОДИ ПОШУКУ У МАСИВАХ

Інформація про навчальний заклад

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано

Інформація про роботу

Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

Частина тексту файла (без зображень, графіків і формул):

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО”                     ЗВІТ з лабораторної роботи №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; }
Антиботан аватар за замовчуванням

29.06.2023 21:06-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!