Рекурсивні алгоритми. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100358

Рекурсивні алгоритми

Інформація про навчальний заклад

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2023

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

СТРУКТУРА звіту з лабораторної роботи НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Рекурсивні алгоритми Мета роботи: метою лабораторної роботи є набуття практичних навичок з рекурсивними функціям. Теоретична частина. Рекурсія (лат. recursio) — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається. Приклади де використовують рекурсію: факторіал, числа Фібоначчі, геометричні фрактали, задача ‘Ханоївська вежа’. Є також вужче визначення для рекурсії саме для програмування. Рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції. Прямою рекурсією називається рекурсія, при якій всередині тіла деякої функції міститься виклик тієї ж функції. Непрямою рекурсією називається рекурсія, що здійснює рекурсивний виклик функції шляхом ланцюга викликів інших функцій. При цьому всі функції ланцюга, що здійснюють рекурсію, вважаються рекурсивними. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. / Опис алгоритму Нерекурсивний алгоритм: нерекурсивний алгоритм реалізується через цикл for. Спочатку програма просить у користувача значення k – верхня межа підсумовування, потім через цикл for k разів виконує обчислення q й додає до минулого значення q. Рекурсивний алгоритм: спочатку програма так само просить ввести k, а потім передає це значення у заздалегідь створену функцію sum. Вміст цієї функції замінює цикл for, який є у алгоритмі без рекурсії. Після обрахунків функцією sum, результат повертається в main, де виводиться за допомогою cout. Складність алгоритму Нерекурсивний алгоритм Значення k Час виконання 5 4.5ns 20 5.2ns 100 10.48ns Рекурсивний алгоритм Значення k Час виконання 5 4.7ns 20 5.75ns 100 5.91ns Результати роботи програми Рекурсивна / Нерекурсивна / Програмний код Нерекурсивна / Рекурсивна / Висновок: Виконано завдання двома способами: з використанням цикла for та з використанням рекурсії. Аналіз тривалості виконання обох версій програми показав, що рекурсію краще застосовувати для великої кількості операцій. Оформлений звіт, згідно з вимогами.

Звіт до лабораторної роботи Програмування складних алгоритмів

17.05.2023 18:07

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись