Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Рекурсивні алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
«Рекурсивні алгоритми»
Варіант 18
Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціям.
Теоретична частина
Рекурсія — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.
Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі.
Термін «рекурсія» використовується в різних спеціальних галузях знань — від лінгвістики до логіки, але найширше застосування знаходить у математиці та інформатиці. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення.
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
/
Блок-схема
//
Оцінка складності
Розмір
Складність
Час виконання без рекурсії
Час виконання з рекурсією
10
O(N)
4.1e-05
8.1e-06
100
5.2e-05
2.4e-05
1000
6.6e-05
3.7e-05
Результат роботи
/
Висновок: Було написано програму, що обчислює рівняння за допомогою методу з рекурсією та без неї, а також визначає час виконання кожного з методів.
Програмний код
https://replit.com/join/tgnewlunuy-okseniait
#include <stdio.h>
#include <time.h>
#define r 5
double noRecursion(double);
double recursion(double, double);
int main(void) {
clock_t start = clock(), diff;
double d, k;
printf("r=%d\n", r);
printf("Результат обчислень без рекурсії: %.7f\n", noRecursion(1));
/*diff = clock() - start;
int msec1 = diff * 1000000 / CLOCKS_PER_SEC;
printf("\nЧас виконання: %d мікросекунд \n", msec1%1000);*/
// clock_t start = clock(), diff;
printf("Результат обчислень з рекурсією: %.7f\n", recursion(1, 0));
diff = clock() - start;
int msec1 = diff * 1000000 / CLOCKS_PER_SEC;
printf("\nЧас виконання: %d мікросекунд \n", msec1%1000);
return 0;
}
double noRecursion(double d2){
for(double k=1; k<=r; k++){
double d;
d=1/(2*k);
d2=d2*d;
}
return d2;
}
double recursion(double d, double k){
double d0;
k++;
if (k==r) return (0.5/r);
d0=(1/(2*k))*recursion(d, k);
return d0;
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора