Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Рекурсивні алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
Рекурсивні алгоритми
Варіант 13
Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи:
Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Теоретична частина
У програмуванні рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного та/або такого, що виконується), реалізують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.
Варто уникати надлишкової глибини рекурсії, бо це може викликати переповнення стека викликів.
Завдання
/
Результат роботи
/
Програмний код
private static double getRecursedMulti(int b, int n) { if (b > n) return 1.0; return (double)(1.0/(2.0*b - 1)) * getRecursedMulti(b+1, n); } private static double getNotRecursedMulti(int b, int n) { double multi = 1.0; for (; b <= n; b++) { multi *= 1.0/(2.0*b - 1); } return multi; }
Висновки: Розроблено алгоритм з використанням та без використання рекрсії. При однаковій складності рекурсивної або безрекурсивної розробки час виконання у наносекундах повинен різнитись, але, на жаль, відомі методи вимірювання часу не здібні відловити різницю у часі через примітивність алгоритму (різниця є меншою за мілісекунду).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора