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;

}

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

Висновки

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


 

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

39733. Товарный ассортимент и товарная номенклатура 18.24 KB
  Широта товарного ассортимента. Решение о наращивании товарного ассортимента. Товарный ассортимент любой фирмы является частью общего товарного ассортимента предлагаемого отраслью в целом. Наращивание ассортимента происходит тогда когда фирма выходит за пределы того что производит в настоящее время.
39734. Жизненный цикл товара 16.75 KB
  Характерным является небольшой рост объёмов продаж и соответственно прибыль минимальна или её вообще нет. Период быстрого роста объёма продаж если товар принят рынком и спрос на него растёт. Прибыль также возрастает по мере увеличения объёма продаж. Объемы продаж значительны но дальнейшего роста продаж не наблюдается.
39735. Ценообразующие факторы 16.94 KB
  Все многообразие ценообразующих факторов как показывает экономическая практика можно разделить на три группы: базовые неконъюнктурные; конъюнктурные; регулирующие связанные с государственной политикой. Действие этой группы факторов различно на рынках разных типов. Так в условиях товарного рынка неконъюнктурные факторы считаются внутрипроизводственными затратными стоимостными поскольку движение цен под воздействием лишь этих факторов однонаправлено с движением затрат. Действие конъюнктурных факторов объясняется изменчивостью...
39737. Возникновение и сущность маркетинга, сбытовой и маркетинговой подходы к деятельности фирмы, цели маркетинга 167.5 KB
  Возникновение и сущность маркетинга сбытовой и маркетинговой подходы к деятельности фирмы цели маркетинга. Становление маркетинга как основы экономического поведения фирмы следует отнести к периоду последующему за великой депрессией охватившей Запад в 19291933 годах . Основными понятиями сферы маркетинга являются следующие: нужды потребности запросы товар обмен сделка и рынок. Введение в практику предпринимательства концепции маркетинга позволяют решить целый комплекс вопросов: 1.
39738. Маркетинг. Общие понятия маркетинга 872 KB
  Спрос это совокупный запрос группы потребителей. Предвидеть прогнозировать спрос можно только постоянно изучая потребителей так чтобы разрабатывать и предлагать именно то что они хотят и в чем нуждаются. Стимулировать значит вызывать у потребителей стремление к тому что предлагает фирма привлекательно оформляя продукт интенсивно его рекламируя и так далее. Маркетинговая деятельность может быть направлена как на потребителей так и на население в целом.
39739. Воплощение черт неомифологизма в произведении Дюрренматта «Минотавр» 30.39 KB
  Вступление Сегодня мы с вами познакомимся с необыкновенным произведением Дюрренматта драматической балладой Минотавр об одиночестве главного героя а именно Минотавра и попробуем найти черты неомифологизма в этом произведении. Наша тема Воплощение черт неомифологизма в произведении Дюрренматта Минотавр . Дюрренматта.
39740. Воплощение черт неомифологизма в произведении Дюрренматта 25.53 KB
  Дюрренматт классик швейцарской литературы.Идейнохудожественный анализ произведения Дюрренматта Минотавр: жанровые особенности; образ дюрренматтовского Минотавра в сопоставлении с древнегреческим Минотавром; черты неомифологического сознания в произведении. Работа по теме урока Сегодня мы с вами проанализируем замечательное произведение швейцарского классика Дюрренматта Минотавр и попробуем проследить неомифологические черты в данном произведении.
39741. Метод (метод исследования) 35.5 KB
  В общей психологии это один из основных эмпирических методов психологического исследования состоящий в преднамеренном целенаправленном систематическом восприятии психических явлений с целью изучения их специфических изменений в определенных условиях. Метод занимает промежуточное положение между методом простого объективного наблюдения и методом лабораторного эксперимента. Создан Лазурским с целью избежать недостатков методов наблюдения и эксперимента и соединить их достоинства; формирующий эксперимент ход которого направлен на...