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;

}

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

Висновки

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


 

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

75211. Понятие субстрата, суперстрата и адстрата 41.5 KB
  Каждое из этих понятий явлений оказывается связанным с историческими событиями народа который владел этим языком. Результат – это кардинальное изменение языков которые они затрагивают: изменяется грамматический строй словарный состав фонетический строй...
75212. КУЛЬТУРА США В КОНЦЕ XVIII – СЕРЕДИНЕ XIX ВЕКОВ 16.1 KB
  Период развития американской культуры между Гражданской и первой мировой войной отличался напряженностью. Писатели архитекторы и художники XIX в. Одна из самых значительных фигур в американской литературе XIX века Марк Твен выдающийся сатирик мастер как реалистической прозы Приключения Тома Сойера Приключения Гекльберри Финна.
75213. Национальный язык. Формы его существования и образования 34 KB
  Национальный язык. Формы его существования и образования Национальный язык – это важнейшая форма. Каждый национальный язык состоит из основной его части – литературного языка и развитых диалектов. Диалекты: Территориальные на определенной территории могли стать национальными языками как провансальский язык на юге Франции.
75214. КУЛЬТУРА И НАУКА США ПОСЛЕ ВТОРОЙ МИРОВОЙ ВОЙНЫ. СОВРЕМЕННАЯ НАУКА И КУЛЬТУРА США 19.68 KB
  КУЛЬТУРА И НАУКА США ПОСЛЕ ВТОРОЙ МИРОВОЙ ВОЙНЫ. СОВРЕМЕННАЯ НАУКА И КУЛЬТУРА США После Второй мировой войны центр мирового искусства переместился из Парижа в НьюЙорк. Кино главный вид искусства и всей культуры США. Классическая музыка в США находится на высоком уровне.
75215. Образование английского национального языка 37.5 KB
  Fisk fisker рыба – древне-английский Sun – sunner сын К концу X века господство было преодолено образовались Уэссекские королевства. К концу средне-английского периода начало XV века грамматический строй сильно изменился. С конца XV века образование раннего ново-английского языка XVI – конец XVII первые десятилетия XVIII. К концу XV века появляются первые типографии.
75217. Понятие литературного языка 36 KB
  Понятие литературного языка Литературный язык играет очень важную роль. Это нормированный язык. Свойства: Нормированность Поливалентность многофункциональность Общеобязательность Стилистическая дифференцированность Функциональная дифференцированность Носит наддиалектный характер носители диалектов понимают этот язык. Например койне может использоваться носителями разных диалектов Имеет свою письменность Норма может быть различной в разные периоды существования языка.