Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Рекурсивні алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
Рекурсивні алгоритми
Варіант 7
Київ 20____
Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Теоретична частина
Процес, у якому функція викликає себе прямо чи опосередковано, називається рекурсією, а відповідна функція називається рекурсивною. Використовуючи рекурсивний алгоритм, деякі проблеми можна вирішити досить легко.
Рекурсія буває прямою та непрямою. Пряма рекурсія визиває сама себе у функції. А в непрямій рекурсії є дві функції, які по черзі викликають один одного(в функції А() викликається функція В(), а в В() викликається функція А()).
Приклад використання рекурсивного алгоритму для знаходження факторіала:
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }
У наведеному вище прикладі визначено базовий випадок для n <= 1. Більше значення числа можна розв’язати шляхом перетворення до меншого, доки не буде досягнуто базового випадку.
Загальне завдання
/
Завдання по варіанту
/
Оцінка складності алгоритму
Складність алгоритму в обох випадках – O(N).
З рекурсією
Величина m
Кількість ітерацій
Час виконання
10
10
8100нс
50
50
12700нс
500
500
120700нс
Без рекурсії
Величина m
Кількість ітерацій
Час виконання
10
10
4300нс
50
50
7600нс
500
500
24200нс
Результат роботи
/
Блок-схема
Main:
/
Рекурсивна функція:
/
Ітераційна функція:
/
Висновок: написано програму, що обраховує значення математичної функції двома способами. Один спосіб використовує метод рекурсії для множення, а інший використовує цикл для тієї ж задачі. Було визначено, що використовуючи цикл алгоритм працює бистріше. Але потрібно зауважити що використання рекурсії все одно доречно використовувати в деяких ситуаціях.
Програмний код
import java.util.*; public class LR2 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Введіть кінцеве значення m: "); int m = scan.nextInt(); System.out.print("Введіть початкове значення n: "); int i = scan.nextInt(); System.out.println("Формула: (3i-2)/3i"); long firstTime = System.nanoTime(); double rec = recursion(i, m, 1); firstTime = System.nanoTime() - firstTime; System.out.println("Результат з використанням рекурсії:\n"+rec + "\nЧас виконання: " + firstTime + " наносекунд"); long secondTime = System.nanoTime(); double notRec = notRecursion(i, m); secondTime = System.nanoTime() - secondTime; System.out.println("Результат без використання рекурсії:\n"+notRec + "\nЧас виконання: " + secondTime + " наносекунд"); } public static double recursion(int i, int m, double res) { if(i<=m) return recursion(i+1, m, res * (3*i-2)/(3*i)); return res; } public static double notRecursion(int i, int m) { double res = 1; for(int j=i;j<=m;j++){ res = res * (3*j-2)/(3*j); } return res; } }
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора