Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Побудова та аналіз складності рекурсивних алгоритмів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 4
з дисципліни: “Алгоритми та методи обчислень”
на тему: “Побудова та аналіз складності рекурсивних алгоритмів”
Мета лабораторної роботи
Вивчити основні методи організації рекурсивних алгоритмів та дослідження їх ефективності.
Теоретичні відомості
Термін рекурсія дуже популярний у математиці і програмуванні. У широкому смислі, рекурсія — це звертання до самого себе (цей термін походить від латинського слова recursio — повернення). Популярність рекурсії в програмістів у значній мірі пояснюється тим, що вона робить стиль програмування більш декларативним. Це означає, що при складанні алгоритму рішення задачі програміст іноді може схитрувати — звести рішення цієї задачі до рішення тієї ж самої задачі, але при більш простих початкових умовах. Тим самим, він як би «перекладає на плечі» комп'ютера складання дрібних деталей алгоритму. Якщо ж складання всіх навіть самих дрібних деталей алгоритму програміст залишає за собою, його стиль програмування називають не декларативним, а процедурним.
Як приклад розглянемо задачу знаходження максимального серед N чисел. Можна запропонувати наступний спосіб її розв'язання:
Якщо чисел всього два, то їх треба порівняти і взяти більше. Якщо ж чисел більше, ніж два, треба взяти кожне з них (перше, що трапилося), вирішити вихідну задачу обрахування максимального числа серед чисел, що залишилися, порівняти результат з першим числом і взяти більше.
На перший погляд у цьому рішенні є якась недомовленість — для знаходження максимального серед N чисел пропонується знайти максимальне серед N-1 числа. Але, як це не парадоксально, представлений рекурсивний алгоритм рішення даної задачі є цілком коректним. А програма, у якій цей алгоритм реалізований, видає правильний результат.
Індивідуальне завдання
Варіант 12
Написати програму для ітераційної та рекурсивної форм обчислення значення функції згідно з варіантом Для рекурсивної форми обчислення використати рекурсивну функцію з виконанням дій на рекурсивному під’омі (для парних варіантів) або на рекурсивному спуску (для непарних варіантів). Порівняти ефективності ітераційної та рекурсивної форм обчислення значення функції.
Обчислити значення функції:
Код програми
#include <iostream>
#include <conio.h>
#include <cmath>
using namespace std;
unsigned long long factorial(int value)
{
if (value < 0)
throw "value < 0";
if (value == 0)
return 1;
else
return value * factorial(value - 1);
}
long long recursion(int n, unsigned long long factorial)
{
if (n < 0)
throw "n < 0";
if (n == 0)
return 0;
else {
if (n & 1) return recursion(n - 1, factorial / n) + factorial;
else return recursion(n - 1, factorial / n) - factorial;
}
}
inline long long recursion(int n)
{
return recursion(n, factorial(n));
}
void main()
{
try
{
for (int i = 1; i <= 10; i++)
{
cout << "n = " << i << ": " << recursion(i) << endl;
}
cout << "n = -1: ";
cout << recursion(-1) << endl;
}
catch (char str[])
{
cout << "Error: " << str << endl;
}
_getch();
}
Результат виконання програми
/
Висновок
Я вивчив основні методи організації рекурсивних алгоритмів та дослідив їх ефективність.
30.03.2016 11:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора