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;

}

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

Висновки

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


 

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

75762. Взаимодействие человека и техносферы 12.42 KB
  Взаимодействие человека и техносферы Человек и окружающая его среда гармонично взаимодействуют и развиваются лишь в условиях когда потоки энергии вещества и информации находятся в пределах благоприятно воспринимаемых человеком и природной средой. Любое превышение привычных уровней потоков сопровождается негативными воздействиями как на человека так и природную среду. и действиями человека. комфортное оптимальное когда потоки соответствуют оптимальным условиям взаимодействия: создают оптимальные условия деятельности и отдыха;...
75763. Понятие опасных и вредных производственных факторов 42.64 KB
  Понятие опасных и вредных производственных факторов По степени и характеру действия на организм все факторы условно делят на вредные и опасные. К вредным относятся такие факторы которые становятся в определенных условиях причиной заболеваний или снижения работоспособности. Опасными называют такие факторы которые приводят в определенных условиях к травматическим повреждениям или внезапным и резким нарушениям здоровья. И опасные и вредные факторы могут быть естественного или природного и антропогенного характера т.
75764. Теоретические основы и практические функции БЖД 21.59 KB
  Иначе говоря традиционно в данном научном направлении рассматривается преимущественно лишь локальная система жизнедеятельности как образующая своего рода фундамент безопасности для системы более высокого уровня так называемой глобальной системы жизнедеятельности. Соответственно можно выделить пространство локальной безопасности жизнедеятельности которое составляет часть более общего пространства глобальной безопасности жизнедеятельности. Кроме того говоря о локальной безопасности жизнедеятельности следует учитывать что в последнее время...
75765. Индивидуальный и социальный риск 15.64 KB
  Индивидуальный и социальный риск Наиболее распространенной оценкой опасности является риск. Риск частота реализации опасностей. Риск расценивается или как опасное условие при котором выполняется деятельность или же как действие совершаемое в условиях неопределенности. Различают индивидуальный и социальный риск.
75766. Основные задачи БЖД 12.77 KB
  Основные задачи БЖД Безопасность жизнедеятельности представляет собой область научных знаний охватывающих теорию и практику защиты человека от опасных и вредных факторов во всех сферах человеческой деятельности сохранение безопасности и здоровья в среде обитания. Эта дисциплина решает следующие основные задачи: идентификация распознавание и количественная оценка негативных воздействий среды обитания; защита от опасностей или предупреждение воздействия тех или иных негативных факторов на человека; ликвидация отрицательных последствий...
75767. Опасность – центральное понятие БЖД 14.38 KB
  Опасность центральное понятие БЖД Опасность центральное понятие в науке БЖД под которым подразумеваются любые явления процессы объекты свойства предметов способные в определенных условиях причинить ущерб здоровью и жизни человека. Опасность хранят все системы имеющие энергию химически или биологически активные компоненты а так же свойства несоответствующие условиям жизнедеятельности человека. Потенциальный означает опасность возможная скрытая отложенная на потом. Признаками определяющими опасность являются: ...
75768. Номенклатура опасностей. Идентификация опасностей 16.99 KB
  Номенклатура опасностей. Идентификация опасностей. В процессе идентификации выявляются номенклатура опасностей. Главное в идентификации заключается в установлении возможных причин проявления опасностей.
75769. ДИАГНОСТИКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ МЛАДШИМИ ШКОЛЬНИКАМИ СОДЕРЖАТЕЛЬНОЙ ЛИНИИ «ЧЕЛОВЕК-ОБЩЕСТВО» 179 KB
  Система диагностики результатов освоения младшими школьниками образовательной области Окружающий мир. Оценивание как основой метод диагностики результатов освоения содержательных линий. Оценивание метапредметных результатов освоения содержательных линий образования.
75770. Методы теории вероятностей в анализе безопасности и надежности летательных аппаратов 1.04 MB
  Теория вероятностей возникла в середине 17 в. То, что случайные явления представляют собой не исключение, а правило в реальном мире, было замечено еще в древности. Об этом словами Лукреция Кара прекрасно говорит Альфред Реньи.