Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РЕКУРСИВНІ АЛГОРИТМИ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи № 2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
РЕКУРСИВНІ АЛГОРИТМИ
Варіант 15
Мета роботи:
Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Теоретична частина:
Рекурсія – це виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Суть рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Але є один нюанс, варто уникати надлишкової глибини рекурсивного алгоритму, тому що це може призвети до переповнення стеку викликів.
Непряма рекурсія – це виклик першою функцією іншої(наприклад вкладеної, а іншою функцією виклик першої.
Завдання до лабораторної роботи:
Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Завдання о 15-го варіанту:
/
Блок-схема до рекурсивної функції:
/
Блок-схема до звичайної реалізації:
/
Результати роботи програми:
Рекурсивна реалізація:
Значення n
Час виконання, мкс
5
234
10
289
30
295
Нерекурсивний алгоритм:
Значення n
Час виконання, мкс
5
289
10
384
30
400
/
/
/
Код програми можна переглянути за посиланням на replit:
https://replit.com/join/utqmbfvxyc-tr-15fundamient
Висновок: Під час виконання даної лабораторної роботи було здобуто практичних навичок у використанні рекурсії. Було реалізовано добуток за допомогою рекурсивної функції, та написано аналог за допомогою нерекурсивної функції. Проведено їх порівняння, та оцінювання часової складності алгоритму. Алогритми виконані вірно, згідно умови.
Копія коду:
#include <iostream> #include <chrono> using namespace std; long long int recursion(int n) { long long int a = 2*n; if(n > 1) { return a * recursion(n-1); } else { return a; } } long long int defaultAlg(int n) { long long int sum = 1; for(int i = 1; i <= n; i++) { sum *= 2*i; } return sum; } int main() { auto start1 = chrono::steady_clock::now(); cout << "recursive function: " << recursion(5) << endl; auto end1 = chrono::steady_clock::now(); cout << "Elapsed time: " << chrono::duration_cast<chrono::microseconds>(end1 - start1).count() << " ms" << endl; auto start2 = chrono::steady_clock::now(); cout << "Non-recursive function: " << defaultAlg(5) << endl; auto end2 = chrono::steady_clock::now(); cout << "Elapsed time: " << chrono::duration_cast<chrono::microseconds>(end2 - start2).count() << " ms" << endl; }
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора