МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Побудова та аналіз складності рекурсивних алгоритмів ЗВІТ до лабораторної роботи № 3 з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" МЕТА РОБОТИ Вивчити основні методи організації рекурсивних алгоритмів та дослідження їх ефективності 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все часова ефективність та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування вставкою) не є дуже ефективними. Алгоритм сортування обміном, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам'яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл. Однак справедливе й зворотне. Яким би гарним і ефективним не був обраний алгоритм, але якщо в якості підзадачі він використовує "поганє" сортування, то вся робота з його оптимізації виявляється марною. Невдало реалізоване сортування вхідних даних здатне помітно знизити ефективність алгоритму в цілому. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Завдання:. Написати програму для ітераційної та рекурсивної форм обчислення значення функції згідно з варіантом Для рекурсивної форми обчислення використати рекурсивну функцію з виконанням дій на рекурсивному під’омі (для парних варіантів) або на рекурсивному спуску (для непарних варіантів). Порівняти ефективності ітераційної та рекурсивної форм обчислення значення функції. Варіант 25 : 25)
Результат виконання програми. / Текст програми: using System; namespace Lab4 { class Program { static void Fancshyn(double x, double a, int n) { n--; if (n >= 0) { x = Math.Pow(x + 2, 2); Console.WriteLine("Залишилось {0} дiї, число: {1}", n, x); Fancshyn(x, a, n); } } static void Main(string[] args) { // double y = 0; Console.Write("Введiть кiлькiсть дiй n= "); int n = Convert.ToInt32(Console.ReadLine()); Console.Write("х= "); int x = Convert.ToInt32(Console.ReadLine()); Console.Write("a= "); int a = Convert.ToInt32(Console.ReadLine()); // y = x; Fancshyn(x, a, n); Console.ReadKey(); } } } Висновок: Вивчив основні методи організації рекурсивних алгоритмів та дослідження їх ефективності .