Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Рекурсивні алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 2
з дисципліни «Програмування складних алгоритмів»
Тема «Рекурсивні алгоритми»
Варіант № 24
Дата «12» квітня 2022
Лабораторна робота № 2:
Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Завдання до роботи
Методичні вказівки
Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття рекурсії. – Поняття прямої i непрямої рекурсiї.
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгори.
Завдання відповідно до варіанту:
Завдання
/
1.2. Теоретичні відомості
Рекурсивний метод у програмуванні. Рекурсивний метод у програмуванні передбачає розв'язання задачі, rрунтуючись на властивостях рекурсивності окремих об'ектів. При цьому вихідна задача зводиться до вирішення аналоrічних підзадач, які є простішими і відрізняються іншим набором параметрів. При виконаині рекурсивної функції здійснюється багаторазовий перехід від деякого поточного рівня організації алгоритму до нижнього рівня послідовно доти, поки, не буде отримано тривіальне рішення поставленого завдання.
Рекурсивний алгоритм - це алгоритм, в описі якого прямо або непрямо міститься звернення до самого себе. Рекурсивний алгоритм завжди розбиває задачy на частини та класифікується, залежно від того, які функції можна визначити і обчислити з використанням різних форм рекурсії.
Рекурсивні алгоритми відносяться до класу алгоритмів з високою ресурсомісткістю, так як при великій кількості самовикликів рекурсивних функцій відбувається швидке заповнення стекової області. На трудомісткість рекурсивних алгоритмів впливає і кількістъ переданих функцією параметрів.
Важливою характеристикою рекурсивного алгоритму є глибина рекурсивних викликів - найбільше одночасне кількість рекурсивних звернень функції, що визначає максимальну кількість шарів рекурсивного стека, в якому здійснюється зберігання відкладених обчислень. При розробці рекурсивних програм необхідно враховувати, щоб глибина рекурсивних викликів не перевищувала максимального розміру стеку обчислювального середовища.
Переваги рекурсії:
простота і компактність запису алгоритмів;
рекурсивна процедура показує, що потрібно робити, а нерекурсивна — як потрібно робити;
легко програмувати обчислення за рекурентними формулами;
легко доводиться коректність програми — її еквівалентністъ тим формулам, за якими розв'язуеться задача;
з допомогою кінцевого виразу можна визначити нескінчену множину об'ектів.
Недоліки:
неефективне витрачання оперативної пам'яті. Дця кожного рекурсивного виклику однієї і тієї ж функції виділяються нові комірки пам'яті. Кожного разу створюється нова копія цієі функції і всім локальним змінни цієї копіії потрібно нові місця в пам’яті. Тому необхідно уникати описання великої кількості локальних змінниз в процедурі.
низька швидкодія роботи програм. Програми, які містять рекурсивні визначення, як правило, працюють повільніше програм, які вирішують туж саму задачу без використання рекурсії.
1.3. Результати роботи
Завдання 1.
Написано програмний код, який реалізує задачу знайти суму послідовності двома методами: використовуючи рекурсію і без неї.
Алгоритм без рекурсії реалізовано за допомогою одного вкладеного циклу. Складність обох алгоритмів: O(N).
Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій.
N
Складність
Час виконання
Без рекурсії
10
O(N)
0,007 ms
50
0,059 ms
З рекурсією
10
0,036 ms
50
0,048 ms
1.4. Висновки по роботі
При виконанні лабораторної роботи №2 було отримано практичні навички з програмування алгоритму з використанням рекурсивної функції та без нього, визначенно часову складность цього алгоритму. Порівняно час роботи програми з використанням рекурсивної функції та без використання рекурсивної функції. З таблиці, яка подана , видно, що реалізаця програми без рекурсії працює швидше.
.
1.5. Лістинг програми
package Algoritm.ua; import java.util.Scanner; import java.util.concurrent.atomic.AtomicLong; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Введіть значення р(1-3)"); System.out.println("1. p = 10"); System.out.println("2. p = 50");
System.out.println("3. p = 100");
System.out.print("Ваш вибір: "); int sizeArray = scan.nextInt(); if (sizeArray == 1) { int p = 10; AtomicLong time = new AtomicLong(System.nanoTime()); double result = withRecursion(p); time.set(System.nanoTime() - time.get()); System.out.printf("Elapsed with recursion %,9.3f ms\n", time.get() / 1_000_000.0); System.out.printf("Result c = %f\n", result); } if (sizeArray == 2) { int p = 50; AtomicLong time = new AtomicLong(System.nanoTime()); double result = withRecursion(p); time.set(System.nanoTime() - time.get()); System.out.printf("Elapsed with recursion %,9.3f ms\n", time.get() / 1_000_000.0); System.out.printf("Result c = %f\n", result); } if (sizeArray == 1) { int p = 10; AtomicLong time = new AtomicLong(System.nanoTime()); double result = withoutRecursion(p); time.set(System.nanoTime() - time.get()); System.out.printf("Elapsed without recursion %,9.3f ms\n", time.get() / 1_000_000.0); System.out.printf("Result c = %f", result); } if (sizeArray == 2) { int p = 50; AtomicLong time = new AtomicLong(System.nanoTime()); double result = withoutRecursion(p); time.set(System.nanoTime() - time.get()); System.out.printf("Elapsed without recursion %,9.3f ms\n", time.get() / 1_000_000.0); System.out.printf("Result c = %f", result); } }
public static double withRecursion(int p) { if (p==1){ return 0; } else return (Math.log(p)/(p*p)) + withoutRecursion(p-1); } public static double withoutRecursion(int p) { double c = 0; for (int j = 1; j <= p; j++) { c = c + (Math.log(j) / Math.pow(j, 2)); } return c; } }
Результат виконання:
//
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора