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;

}

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

Висновки

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


 

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

76534. Значение и место учебника по русскому языку. Анализ учебника русского языка 30 KB
  В этой книге излагаете материал в соответствии с программой по предмету. Цель использования учениками: получение необходимой информации приобретения комплекса умения и навыков Для учителя: источник методической системы который помогает определить методику работы на разных этапах усвоения учебного материала чему и как учить. Систематизирующую: материал представлен в системе усвоение по системе от простого к сложному. Весь теоретический материал может быть представлен в учебниках разными способами: дедукция способ мышления основой является...
76535. Закономерности усвоения родного языка и вытекающие из них принципы 34.5 KB
  Способность ребенка понимать отвлеченное лексическое значение слова в дальнейшем приводит его к пониманию слова как части речи. В какие сроки ребенокдошкольник овладевает указанными выше фактами языка и овладевает ли зависит от того как его обучают речи каков развивающий потенциал языковой среды в которой он растет а самое главное имеет ли он возможность усваивать грамматические и лексические значения родного языка синхронно в нужных пропорциях. Письменная речь усваивается если ее опережает развитие устной речи если она является как...
76536. Упражнения по русскому языку и их виды 27.5 KB
  Приступа по критериям: Упражнение зависит от характера мыслительной деятельности учащихся аналитической и тдОт времени выполненияОт последовательности связано с этом усвоения языкового материала: 1. Пропедовтическиеподготовка к восприятию нового материала ок цент на изучаемую единицу;Иллюстративные наиболее ярко показать примеры тех языковых фактов которые разбираются на уроке;Закрепительные закрепление теоретических сведения: постоянно воспроизведение существенных признаков изучаемого материала.
76537. Методы и приемы обучения русскому языку 40 KB
  Метод - способы взаимодействия учителя и ученика, направленные на достижение положительных результатов обучения. Положительные результаты - достижение цели. Действия: учение и обучение. Классификация Дубникова (основа: характеристика способов мышления - индукция(от частного к общему) и дедукция)
76538. Диктант как метод обучения и форма контроля 32 KB
  Диктант как метод обучения и форма контроля. Среди упражнений с помощью которых происходит формирование умений и навыков используется списывание простое и осложненное обучающие диктанты а также упражнения творческого характера: конструирование словосочетаний и предложений изложения и сочинения малых форм; разные виды грамматического разбора. В методике разработаны различные виды обучающих диктантов. Диктант с карточками удобен на первых этапах закрепления: дети записывают слова поднимая карточку с изучаемой орфограммой что позволяет...
76539. Теоретические методы усвоения русского языка 26.5 KB
  Теоретические методы усвоения русского языка. Федоренко выделяет методы практического изучения языка объяснение непонятных слов подготовка устных сообщений письменных сочинений составление планов конспектов тезисов исправление ошибок грамматических и стилистических обучение работе со справочной литературой методы теоретического изучения языка беседа сообщение чтение правил в учебнике методы теоретикопрактического изучения языка различные упражнения: при изучении грамматики грамматический разбор анализ готового материала...
76540. Языковой разбор и его роль в формировании знаний, навыков и умений обучающихся 30 KB
  Языковой разбор и его роль в формировании знаний навыков и умений обучающихся. Языковый разбор представляет собою лингвистический анализ и толкование предложенного учителем дидактического материала: это могут быть отдельные слова предложения небольшие тексты. Языковый разбор основывается на рецептивной деятельности учащихся так как проводится на готовом языковом материале восприятие которого сквозь призму изученных понятий и правил и составляет суть метода. В зависимости от того какое умение отрабатывается различаются следующие виды...
76542. Методы практического изучения языка и обучения речи. Анализ текста на уроке русского языка 26.5 KB
  Анализ текста на уроке русского языка. Сочинение вид письменной школьной работы изложение своих мыслей знаний на заданную тему Анализ текста. анализ текста создаёт условия для формирования у школьников представления о языковой системе реализации внутрипредметных межуровневых а также метапредметных связей включает уроки русского языка в единую систему филологического образования. Определить тему и проблему текста 3.