Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РЕКУРСИВНІ АЛГОРИТМИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «РЕКУРСИВНІ АЛГОРИТМИ»
Варіант № 16
Дата «15» квітня 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Завдання:
/
рис 1.
Теоретичні відомості:
Мова С підтримує можливість звернення функції самої до себе — рекурсію.Розрізняють пряму і непряму рекурсії. Функція називається прямо рекурсивною, якщо містить у своє му тілі виклик самої себе. Якщо ж функція викликає іншу функцію, що у свою чергу викликає першу, то така функція називається непрямо рекурсивною.
Рекурсивні функції найчастіше використовуються для компактної реалізації рекурсивних алгоритмів.
Класичні приклади використання рекурсії — реалізація операції піднесення до степеня і обчислення факторіала числа. Зазначимо, що ці приклади популярні тільки через їхню зруч ність для пояснення поняття рекурсії, однак вони не дають ви грашу в програмній реалізації порівняно з ітераційним спосо бом розв’язання цих задач.
Розглянемо рекурсивну функцію обчислення факторіала. Для того щоб одержати значення факторіала числа n!, необхід но помножити на n факторіал числа (n-1)!.Ураховуючи, що 0! = 1 та 1! = 1, наведемо приклад цієї функції:
double factorial(double n){//Метод обчислювання факторіалу
if(n <= 1.0)
return 1.0;
else
return (n*factorial(n-1));
}
Хід роботи:
Написано програмний код, який виконує завдання різними способави на вібір, або за допомогою рекурсивної функції, або без неї. Для цього було створено два метода. Результат розрахунків було перевірено калькулятором, помилок не знайдено.
Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів добутку(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку.
Було створенно два методів для полегшення метода main, кожен метод для одного варіанту виповнення завдання.
У MultRec ми маємо рекурсивну функцію тому вона виконується лише n разів. Також ми маємо if і тіло у середині спочатку робиться n-1 разів, а потім ще один раз, тому усього буде n разів. Загалом метод спростити до n+n=2n = Θ(n).
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
20
0.035 msec
50
100
0.043 msec
100
200
0.063 msec
500
1000
0.165 msec
Для другого завдання використано метод Mult, де ми маємо лише один цикл тому його можна звести до 4+2n+n=4+3n = Θ(n).
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
34
0.053 msec
50
154
0.076 msec
100
303
0.095 msec
500
1504
0.134 msec
/
Код програми:
Посилання на код:
https://replit.com/join/bdvvosqxdc-tr-15khavkin
#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%
Оголошення від адміністратора