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;

}

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

Висновки

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


 

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

11003. Система и метод философии Гегеля. Диалектический метод Гегеля 25.46 KB
  Система и метод философии Гегеля. Выдающееся значение философии Гегеля заключалось в том что в ней в систематической форме было изложено диалектическое миропонимание и соответствующий ему диалектический метод исследования. Гегель разрабатывал д...
11004. Соотношение философии и науки по предмету. Предмет философии как отношение человека к миру 73.5 KB
  Соотношение философии и науки по предмету. Предмет философии как отношение человека к миру 1. Соотношение философии и науки по предмету. Множество определений философии. Существует множество определений философии и ее предмета1. Древнегреческий философ Платон пола...
11005. Жизнь и философствования Сократа 62 KB
  Жизнь и философствования Сократа Поворотным пунктом в развитии античной философии явились воззрения Сократа 469 – 399 до н.э.. Его имя стало нарицательным и служит для выражения иди мудрости. Сам Сократ ничего не писал был близким к народу мудрецом; философствовал на улиц...
11006. Основные черты средневекового христианского мировоззрения.(Бог, человек и мир в средневековой христианской философии) 38 KB
  Основные черты средневекового христианского мировоззрения.Бог человек и мир в средневековой христианской философии. Особенности философии СредневековьяВыделяют следующие особенности философии Средневековья: философское учение теоцентрично философия Средневеко
11007. Рационалистическая метафизика 17 века (Декарт, Спиноза, Лейбниц) 38 KB
  Рационалистическая метафизика 17 века Декарт Спиноза Лейбниц Рационализм направление признающее разум основой познания и поведения людей. Начал складывать в результате развития математики и естествознания. Исходит из идеи естественного порядка. Утверждает опр
11008. Полемика славянофилоф и западников в русской философии 74 KB
  Полемика славянофилоф и западников в русской философии Своеобразным направлением в русской философии явилось славянофильство ярким представиетелм которого были А.С.Хомяков 18041860 и И.В.Киреевский 18061856 оказавшие значительное воздействие на развитие русской мыс
11009. Истоки философии. Хронология и краткая характеристика основных этапов 46 KB
  Тема. Истоки философии Хронология и краткая характеристика основных этапов. Причины возникновения философии являются и причиной её развития. Данный вопрос является дискуссионным. Основные этапы развития мировой философии преимущественно связываются только с развит...
11010. Гносеология или теория познания 55 KB
  Гносеология. Гносеология или теория познания – это раздел философии в котором изучаются природа познания и его возможности отношение знания к реальности выявляются условия достоверности и истинности познания. Термин Гносеология происходит от греческих слов g...