75666

Рекурсивні алгоритми обробки структур даних

Лабораторная работа

Информатика, кибернетика и программирование

Розробити програму згідно алгоритму з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.

Украинкский

2015-01-24

201.22 KB

4 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №6 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Рекурсивні алгоритми обробки структур даних.

Мета: набуття практичних навичок роботи з рекурсивними функціями.

Завдання:

Розробити програму згідно алгоритму з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.

Варіант № 9.

9

Хід роботи

У програмі створено дві функції: одна рахує добуток у циклі, а інша рекурсивна. Результати, отримані за допомогою двох функцій, ідентичні.  Допустимі значення для n: 2<n<13, так як при значенні більше 12 розв’язок стає меншим  за 10-21.

 

Складність алгоритму

Складність алгоритму без рекурсії дорівнює O( 8N ) від Т ;

Складність рекурсивного алгоритму дорівнює О( N+2 ) від Т, де

Т - час виконання;

N – кількість ітерацій (в завданні n).

Рекурсивний алгоритм має незначно більшу складність, але його використання потребує більше ресурсів, тому вона більш витратна щодо пам’яті. Крім того, багато ресурсів використовується при копіюванні змінних у курсиву функцію.

Блок-схема алгоритму


Лістинг програми

#include <iostream>

#include <cmath>

#include <cstdio>

using namespace std;

double ProductCalc(double n)

{

   double r =1;

   for (double l=2.0; l<=n; ++l)

    r = r * (sin(l)/((l-1)*(l-1)));

   return r;

}

void ProductRecursionCalc(double &r, double n, double l)

{

   if (l>n) return;

   r = r * (sin(l)/((l-1)*(l-1)));

   ++l;

     ProductRecursionCalc(r, n, l);

}

int main()

{

   double n = 0;

   double r = 1;

   double l = 2;

   double add = 0;

   cout<<"Limits:  2 < n < 13\n";

   while (!n)

   {

       cout<<"Input n = ";

       cin>>add;

       if (add>2&&add<13)

           n=add;

       else

           cout<<"\nERROR! Invalid input! Try again:\n\n";

   }

   cout<<"\n~~~~~~~~~ Without recursion ~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n";

   cout<<" r = ";

   printf ("%2.20f\n", ProductCalc(n));

   cout<<"\n~~~~~~~~~~ With recursion ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n";

   cout<<" r = ";

   ProductRecursionCalc(r,n,l);

   printf ("%2.20f\n", r);

   return 0;

}

Результат виконання

Висновки

Набуто практичних навичок роботи з рекурсивними функціями. В результаті виконання роботи виконано програму для обчислення виразу рекурсивним і не рекурсивним методом.


 

А также другие работы, которые могут Вас заинтересовать

55343. Проектная деятельность как способ мотивации педагогов к использованию ИКТ 133.5 KB
  Цель программы: формирование мотивации педагогов к использованию средств ИКТ в учебно-воспитательном процессе. Как известно мотивация побуждение к действию динамический...
55344. ПРОЕКТНА ТЕХНОЛОГІЯ ЯК ШЛЯХ ДО РЕАЛІЗАЦІЇ ОСОБИСТІСНО-ОРІЄНТОВАНОГО НАВЧАННЯ 162.5 KB
  Хотілося б звернути увагу на те що проектні технології навчання відтворюють процеси дослідницької діяльності оскільки містять цикл і мають на меті процеси руху від незнання до знання на відміну від традиційних лінійних технологій навчання.
55345. ПІДСТАВКИ ДЛЯ ПАЯЛЬНИКА 295.5 KB
  Визначити призначення виробу: підставка призначена для утримання електропаяльника в нагрітому чи холодному стані в проміжках між роботою та зберігання матеріалу необхідного при паянні.
55347. Зелений клас 192 KB
  Вирішили зробити проект тому що форма проектування дійсно дає змогу консолідувати зусилля усіх сторін і субєктів навчальновиховного процесу розширює рамки творчої діяльності. Тематичний напрямок проекту.
55348. Біла ромашка - символ чистого дихання 41 KB
  Мета проекту: формування у шкільної молоді моральних цінностей та життєвих навиків, які сприяють вихованню потреби практично впливати на подолання негативних поведінкових проявів...
55349. МОЄ СЕРЦЕ ВІДКРИТЕ ДЛЯ ДОБРА 304.5 KB
  Мета проекту: привернути увагу учнів Манвелівської школи, батьків, вчителів до проблем соціально-незахищених категорій населення сіл Манвелівка, Нововасильківка, Красне, Зоря, Іванівка та поліпшення умов їх життя;
55350. Край, у якому ти живеш. Старожитня Кам’янка 5.42 MB
  Мета: збагачувати знання учнів про рідний край, а також активний словниковий запас учнів; пробудити інтерес до вивчення історії Кам’янки; розширити знання про історичне минуле рідного краю;...