НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: РЕКУРСИВНІ АЛГОРИТМИ Варіант №12 Київ 2022 Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями. Теоретична частина Процедура або функція можуть містити виклик до іншої процедури всередині себе. Зокрема, підпрограма може називати себе. В цьому випадку комп'ютеру все одно. Також він, як завжди, послідовно виконує команди, з якими зіткнувся. Якщо згадати математику, то там можна знайти принцип математичної індукції. Вона полягає в наступному: деяке твердження справедливо для будь-якого природного n, якщо 1. він справедливий для n = 1 і 2. з обґрунтованості твердження для будь-якого довільного натурального n = k випливає його дійсність для n = k+ 1. У програмуванні цей прийом називається рекурсією. Рекурсія - це спосіб визначення сукупності об'єктів через саму множину на основі заданих простих основних випадків. Рекурсивна процедура (функція) - це процедура, яка викликає себе безпосередньо або за допомогою інших процедур і функцій. Часова складність Розмір Складність алгоритму Час роботи без використання рекурсії Час роботи з використанням рекурсії  10х10 O(n) Лінійний алгоритм 9,11e-05 0,0001176  50х50  0,0001446 0,0001339  100х100  6,75e-05 0,0001982   Завдання: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Завдання до Варіанту_12
Результати виконання лабораторної роботи:
Код: //Лабораторна робота №2_ПСА //ТР-15_Ткаченко_Майя, Варіант_12 #include <iostream> #include <math.h> #include "chrono" using namespace std; double factor (double k) { double s = k/(pow(k,2)+1); if(k>=1) { return s+factor(k-1); } else return s; } int main() { cout<<"\n------------------------------->>>\n\t< Рекурсивні алгоритми >"; cout<<"\n------------------------------->>>\nОбчислення виконуватимуться за формулою:\n---------------------\n|\ts=E l/(l^2+1)\t|\n---------------------\n\n------------------------------->>>\nДіапазон обчислень (кількість повторень): [1; p]\n------------------------------->>>\n "; double p; cout << "Введіть кількість повторень <p> : "; cin >> p; const auto point1 = chrono::high_resolution_clock::now(); double s=0; double l=1; while(l<=p) { s=s+l/(pow(l,2)+1); l++; } cout<<"\n\t---< Алгоритм без використання факторіалу >---\n"; const auto endpoint1 = chrono::high_resolution_clock::now(); cout << "\n<<<Результати обчислень :" << s; cout << "\n=================================>>>\n<<<Витрачений час :" << chrono::duration<float>(endpoint1 - point1).count() << endl; cout<<"\n\t---< Алгоритм з використанням факторіалу >---\n"; const auto point2 = chrono::high_resolution_clock::now(); cout << "\n<<<Результати обчислень :" << factor(p); const auto endpoint2 = chrono::high_resolution_clock::now(); cout << "\n=================================>>>\n<<<Витрачений час :" << chrono::duration<float>(endpoint2 - point2).count() << endl; return 0; } Посилання на Repl.it : https://replit.com/join/sorvgrfcbn-tr-15tkachienko Висновки Під час виконання лабораторної роботи було розгянуто основи роботи з рекурсивними функціями. Розроблено програму, яка обчислює по формулі, згідно варінту, алгоритм з використанням рекурсивної функції і алгоритм розрахованих через цикл for, також, для кожного алгоритму виводиться час виконання.