НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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
#include
#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 << "Введіть кількість повторень : ";
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(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(endpoint2 - point2).count() << endl;
return 0;
}
Посилання на Repl.it :
https://replit.com/join/sorvgrfcbn-tr-15tkachienko
Висновки
Під час виконання лабораторної роботи було розгянуто основи роботи з рекурсивними функціями. Розроблено програму, яка обчислює по формулі, згідно варінту, алгоритм з використанням рекурсивної функції і алгоритм розрахованих через цикл for, також, для кожного алгоритму виводиться час виконання.
