Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Рекурсивні алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 2
з дисципліни «Програмування складних алгоритмів»
Тема «Рекурсивні алгоритми»
Варіант № 11
Лабораторна робота № 1:
Рекурсивні алгоритми
Мета: набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи
Розробити програми згідно з алгоритмом з використанням рекурсивної
функції та без використання рекурсивної функції. Оцінити час виконання та
складність алгоритму.
Завдання відповідно до варіанту:
/
Теоретичні відомості
Рекурсія – це побудова методу таким чином, що він викликає сам себе. Рекурсивні виклики методу мають завершуватись при досягненні деякої умови. В іншому випадку відбудеться переповнення пам’яті і програма “зависне” не досягнувши обчислення необхідного результату.
Рекурсивний метод – це метод, який сам себе викликає. У рекурсивному методі міститься виклик цього ж методу за його іменем.
Послідовний процес рекурсивних викликів методу є подібний до циклічного процесу.
Як працює рекурсивний виклик методу?
Якщо метод викликає сам себе, то в пам’яті відбуваються наступні процеси:
в системному стеку виділяється пам’ять для нових локальних змінних і параметрів;
програмний код методу виконується з початку з новими локальними змінними і параметрами. Ці локальні змінні та параметри отримують нові початкові значення. Самий програмний код методу не копіюється;
при поверненні з рекурсивного методу відбувається відновлення старих локальних змінних та параметрів а також їх значень у точці виклику цього методу.
Рекурсія завжди порівнюється з ітерацією. Для багатьох задач, рекурсія дає наступні взаємопов’язані переваги:
при виклику рекурсивної функції не потрібно додатково зберігати тимчасові значення локальних змінних. Компілятор будує код рекурсивної функції таким чином, що тимчасові значення локальних змінних автоматично зберігаються при кожному рекурсивному виклику;
у деяких випадках рекурсивні алгоритми виглядають більш спрощено та більш наочно ніж ітераційні. Це пов’язано з тим, що в ітераційних алгоритмах для запам’ятовування проміжних результатів потрібно вводити додаткові змінні, які можуть ускладнити сприйняття ходу виконання самого алгоритму.
Порівняно з ітераційними викликами, побудова рекурсивних викликів має такі недоліки:
для заданого алгоритму рекурсивні виклики працюють повільніше ніж ітераційні. Це пов’язано з додатковими затратами системних ресурсів на неодноразові виклики методів;
багаторазовий виклик методів може призвести до переповнення системного стеку. У цьому випадку середовище CLR згенерує відповідну виключну ситуацію. Тому, важливо, щоб рекурсивний метод був розроблений таким чином, щоб в ньому оголошувалась мінімально можлива кількість параметрів та локальних змінних.
Приклад 1. Використання рекурсії для обчислення факторіала числа:
int factorial(int i)
{
if (i==0) return 1;
else return i*factorial(i-1);
}
Приклад 2. Приклад обчислення суми ряду:
int S(int n)
{
if (n == 1)
return 5;
else
return 5 * n + S(n - 1);
}
Результати роботи
Без рекурсивної функції:
З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Тепер за допомогою циклу for() рахуємо добуток ряду. Обчислюємо часову складність алгоритму.
З використанням рекурсивної функції:
З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Створюємо функцію func() і передаємо значення n. Рахуємо добуток ряду. У головній функції main() викликаємо func(). Обчислюємо часову складність алгоритму.
n
Складність
Час алгоритму
Без рекурсії
10
O(n)
2.169*
10
−5
20
2.555*
10
−5
50
3.21*
10
−5
З рекурсією
10
2.721*
10
−5
20
2.803*
10
−5
50
3.526*
10
−5
1.4. Лістинг програми та результати роботи
Без рекурсії:
#include <iostream>
#include <cmath>
#include <chrono>
using namespace std;
int main() {
double p = 1;
int n = 0;
cout << "Enter the number:" << endl;
cin >> n;
if (n <= 0)
cout << "Error!" << endl;
auto start = chrono::high_resolution_clock::now();
for (int k = 1; k <= n; k++) {
p *= sin (k) / k;
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<float> duration1 = end - start;
cout << "Result of algorithm:" << p << endl;
cout << "The operating time of the first algorithm: " << duration1.count() << endl;
return 0;
}
Результат роботи програми:/
З рекурсією:
#include <iostream>
#include <cmath>
#include <chrono>
using namespace std;
double func(int n);
int main() {
int n = 0;
cout << "Enter the number:" << endl;
cin >> n;
if (n <= 0)
cout << "Error!" << endl;
auto start = chrono::high_resolution_clock::now();
double p = func(n);
auto end = chrono::high_resolution_clock::now();
chrono::duration<float> duration1 = end - start;
cout << "Result of algorithm: " << p << endl;
cout << "The operating time of the first algorithm: " << duration1.count() << endl;
return 0;
}
double func(int n) {
if (n == 0) return 1;
else
return func(n - 1) * (sin (n) / n);
}
Результат роботи програми:
/
1.5. Висновок
У ході виконання лабораторної роботи розроблено програми з використанням та без використання рекурсивної функції. Порівняно часову складність обох алгоритмів, оцінено час виконання та складність алгоритму. Досліджено, що програма без рекурсії працює швидше, ніж інша.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора