75666

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

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

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

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

Украинкский

2015-01-24

201.22 KB

2 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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;

}

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

Висновки

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


 

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

10498. Будова атома. Ядро і електронна оболонка. Склад атомних ядер 85 KB
  Тема уроку: Будова атома. Ядро і електронна оболонка. Склад атомних ядер. Навчальна мета: продовжити знайомство з періодичною системою хімічних елементів Д.І. Менделєєва, на основі знань про будову атома розкрити фізичний зміст порядкового номера елемента...
10499. Фенол, визначення взаємного впливу атомів у його молекулі 50.5 KB
  Навчальна мета: ознайомити учнів з будовою фенолу визначити взаємний вплив атомів у його молекулі. Розвивати вміння прогнозувати хімічні властивості органічних сполук виходячи з їхньої будови на прикладі фенолу. Ознайомити з якісною реакцією на феноли. Обладнання: пе...
10500. Ферум: будова атома, поширення в природі. фізичні та хімічні властивості. взаємодія з киснем, сіркою 49.5 KB
  Тема уроку: Ферум: будова атома поширення в природі. фізичні та хімічні властивості. взаємодія з киснем сіркою. Вид заняття: комбінований урок урок повторення і засвоєння нових знань на якому активізування чуттєвого досвіду учнів закріплення знань умінь та навичок пр
10501. Фізичні і хімічні властивості етилену і ацетилену. Одержання етилену і ацетилену 81 KB
  Тема:Фізичні і хімічні властивості етилену і ацетилену. Одержання етилену і ацетилену. Навчальна мета: ознайомити учнів з фізичними і хімічними властивостями ненасичених вуглеводнів розкрити механізм реакції приєднання показати що реакції цього типу є характерними...
10502. Фізичні і хімічні явища. Хімічні реакції 74 KB
  Тема: Фізичні і хімічні явища. Хімічні реакції. Навчальна мета: сформувати поняття про фізичні та хімічні явища їх відмінності, розглянути зовнішні ефекти що супроводжують хімічні реакції визначити умови виникнення та перебігу хімічних реакцій, розкрити значення хім
10503. Кристалічні гратки. Атомні, молекулярні та йонні кристали 57 KB
  Тема: Кристалічні гратки. Атомні молекулярні та йонні кристали. Мета: визначити особливості будови твердих речовин та встановити залежність властивостей речовин від їхньої будови. Тип уроку: комбінований. Обладнання: періодична система хімічних елементів Д. І. Менде...
10504. Хімічний звязок та будова у неорганічних речовинах 100.5 KB
  Тема: Хімічний зв’язок та будова у неорганічних речовинах. Тип уроку: уроклекція. Навчальна мета: Узагальнити та систематизувати знання учнів про хімічний зв’язок, характеризувати взаємозв’язки між складом будовою і властивостями речовин, виробити вм...
10505. Хімічні властивості металів 68 KB
  Тема: Хімічні властивості металів. Навчальна мета: вивчити загальні хімічні властивості металів взаємодію їх з киснем галогенами сіркою кислотами солями розглянути хімічну активність металів та відповідно їх відновні властивості повторити окисно відновні реакці...
10506. Хімічні властивості алкенів: повне і часткове окиснення, приєднання Н2, Gal, НGal, полімеризація. Правило Марковнікова. Механізм реакції приєднання за подвійним зв’язком 38.5 KB
  Тема: Хімічні властивості алкенів: повне і часткове окиснення приєднання Н2 Gal НGal полімеризація. Правило Марковнікова. Механізм реакції приєднання за подвійним зв’язком. Навчальна мета: ознайомити з хімічними властивостями алкенів; розкрити механізм реакції приєднан...