Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РЕКУРСИВНІ АЛГОРИТМИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №1
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «РЕКУРСИВНІ АЛГОРИТМИ»
Варіант № 16
Дата «15» квітня 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Завдання:
/
рис 1.
Теоретичні відомості: Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.
Основними мірами обчислювальною складності алгоритмів є:
– часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;
– ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму.
Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних.
Надалі обмежимося тільки аналізом часової складності.
Складність алгоритму описується функцією f(n), де n – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції.
Асимптотична складність алгоритму - спосіб оцінки обчислювальної складності алгоритму «з точністю до константи», застосовуваний в теорії складності. Зазвичай записується в нотації «великого О».
Поширені складності алгоритмів
Складність
Коментар
Приклади
O(1)
Сталий час роботи не залежно від розміру задачі
Очікуваний час пошуку в хеші
O(log n)
Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину
Обчислення xn; двійковий пошук в масиві з n елементів
O(n)
Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час
Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O(n²)
Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час
Елементарні алгоритми сортування
Хід роботи:
Написано програмний код, що створює двовимірнинй динамічний масив випадко вих цілих чисел розмір якого задається через консоль. В результаті програма просить ввід кількості елементів масиву, виводить початковий масив та масив після 1 та 2 завдання. Для завдання 1 програма шукає в рядку максимальний елемент, а потім перезаписує значення елемента на побічній діагоналі на найменше.
Для завдання виконав перевірку, якщо мінімальний елемент є першим елементом, то масив не виводиться, а виводиться повідомлення.
Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку.
Було створенно декілька методів для полегшення метода main, тому для першого завдання було викростано 4 методу: для оголошення массиву, його перетворення та два виводу.
У getMatrix ми маємо цикл в циклі. Перший раз for(int i=0; i<size;i++) ми виконуемо 3 ітерації: ініціалізація і, перевірка, та прирост і. Далі у циклу виконується size-1 раз вже по дві ітерації: перевірка і прирост, і останній раз одна ітерація – перевірка, тому можна звести до формули 3+2*n+1=4+2n. Далі вкладений цикл такий самий і потім вже у ньому лінійні дії які можна звести до (4+2n+3)*n. Тому увесь цей метод можна спростити до 2n^2+9n+4 = Θ(n^2).
У методі perevertMatrix ми спочатку знаходимо найменший член матриці, а потім зміна рядка на стовпчик і навпаки, згідно знаходження знайденого члена. Аналогічно метод можна звести до формули 4+2n + (4+2n)n + 3n^2(для if беремо найгірший варіант, тобто коли він виконується кожний раз у циклі – n^2) + (4+2n) + 3n(перестановка елементів) = 5n^2+11n+8 = Θ(n^2).
Метод printMatrix просто виводить на екран матрицю, тому його можна звести до формули (2n+4) + n + (2n+4)*n + n^2 = 3n^2+7n+4 = Θ(n^2)
Тому увесь алгоритм до першого завдання можна звести до формули 13n^2+34n+20 = Θ(n^2).
Розмір
Складність
Кілкість ітерацій
Час виконання
10x10
Θ (n^2)
1660
0.334 msec
50x50
34220
10.639 msec
100x100
133420
35.811 msec
500x500
3267020
811.762 msec
Для другого завдання використано тільки два методи, оскільки матрицю для роботи було заповнено у перший раз у методі getMatrix і виведено її у методі printMatrix у перший раз, тому було використано тільки метод для його перетворення та виводу опрацьованій матриці.
Метод perevertMatrix2 проводить обмін елементів згідно до другого завдання
(4+2n) + (4+2n)*n + 6n^2 = 8n^2+6n+4 = Θ(n^2).
Загалом увесь алгоритм до другого завдання можна звести до формули 11n^2+13n+8 = Θ(n^2).
Розмір
Складність
Кілкість ітерацій
Час виконання
10x10
Θ (N^2)
1238
0.148 msec
50x50
28158
3.489 msec
100x100
111308
13.100 msec
500x500
2756508
491.107 msec
/
Код програми:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
double MultRec(double mult, int t, int n){//Метод для заповнення матриці
if(t<n){
return(pow(sin(t),3)/(pow(t,2)-1))*MultRec(mult,t+1,n);
} else if (t==n){
return pow(sin(t),3)/(pow(t,2)-1);
}else return 1;
}
double Mult(double mult, int t, int n){//Метод для заповнення матриці
for(int i=t;i<n;i++){
mult=mult*(pow(sin(i),3)/(pow(i,2)-1));
}
return mult;
}
int main(void) {
int n,x,s;
printf("\nЗавдання:\n n\n ┌──┐ sin³t\nf=│ │ ───── , n є [t;n]\n │ │ t²-1\n t=2\n\nВедіть n: ");
scanf("%d", &n);
printf("\nВикористання алгоритму з рекурсивною функцією(1) або без(2): ");
scanf("%d", &x);
double f;
clock_t ttime1,ttime2,ttime3,ttime4;
switch(x){
case 1:
ttime1 = clock();
f=MultRec(1,2,n);
ttime2 = clock();
printf("\nTime of 1 task: %lf msec", (double)(ttime2-ttime1)/CLOCKS_PER_SEC*1000);
printf("\n\nf=%.30f",f);
break;
case 2:
ttime3 = clock();
f=MultRec(1,2,n);
printf("\n\n%.30f",f);
ttime4 = clock();
printf("\nTime of 2 task: %lf msec", (double)(ttime4-ttime3)/CLOCKS_PER_SEC*1000);
break;
}
}
Результат програми: / /
Висновок: У цій лабораторної роботі ознайомилися з видами складності алгоритмів, навчилися їх визначати. Також були отримані навички визначання часової складності алгоритму, вивчено будування алгоритмів з мінімальною часовою складністю для вирішення поставлених задач.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора