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;

}

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

Висновки

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


 

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

81485. Механизм возникновения желчнокаменной болезни (холестериновые камни). Применение хенодезокеихолевой кислоты для лечения желчнокаменной болезни 103 KB
  Выделение холестерола в жёлчь должно сопровождаться пропорциональным выделением жёлчных кислот и фосфолипидов удерживающих гидрофобные молекулы холестерола в жёлчи в мицеллярном состоянии У большинства больных желчнокаменной болезнью активность ГМГКоАредуктазы повышена следовательно увеличен синтез холестерола а активность 7αгидроксилазы участвующей в синтезе жёлчных кислот снижена. В результате синтез холестерола увеличен а синтез жёлчных кислот из него замедлен что приводит к диспропорции количества холестерола и жёлчных кислот...
81486. Общая схема источников и путей расходования аминокислот в тканях. Динамическое состояние белков в организме 134.22 KB
  Значение аминокислот для организма в первую очередь определяется тем что они используются для синтеза белков метаболизм которых занимает особое место в процессах обмена веществ между организмом и внешней средой. Аминокислоты непосредственно участвуют в биосинтезе не только белков но и большого количества других биологически активных соединений регулирующих процессы обмена веществ в организме таких как нейромедиаторы и гормоны производные аминокислот. Аминокислоты служат донорами азота при синтезе всех азотсодержащих небелковых...
81487. Переваривание белков. Протеиназы - пепсин, трипсин, химотрипсин; проферменты протеиназ и механизмы их превращения в ферменты. Субстратная специфичность протеиназ. Экзопептидазы и эндопептидазы 110.2 KB
  Подавляющее их количество входит в состав белков которые гидролизуются в ЖКТ под действием ферментов протеаз пептидщцролаз. Под действием всех протеаз ЖКТ белки пищи распадаются на отдельные аминокислоты которые затем поступают в клетки тканей. Источником Н является Н2СО3 которая образуется в обкладочных клетках желудка из СО2 диффундирующего из крови и Н2О под действием фермента карбоангидразы карбонатдегидратазы: Н2О СО2 → Н2СО3 → НСО3 H Диссоциация Н2СО3 приводит к образованию бикарбоната который с участием специальных...
81488. Диагностическое значение биохимического анализа желудочного и дуоденального сока. Дать краткую характеристику состава этих соков 109.1 KB
  Анализ желудочного сока является очень важным методом исследования больных с заболеваниями желудка кишечника печени желчного пузыря крови и пр Составная часть Единицы СИ Азот: небелковый 143 343 ммоль л мочевины и аммиака 499 999 ммоль л аминокислот 143 57 ммоль л Хлориды 1551 ммоль л Свободная хлористоводородная кислота 20 ммоль л Мочевая кислота 476 1189 мкмоль л Калий 56 353 мэкв л ммоль л Натрий 313 1893 мэкв л ммоль л Общая кислотность 4060 ммоль л Свободная соляная кислота 2040 ммоль л Связанная соляная кислота...
81489. Протеиназы поджелудочной железы и панкреатиты. Применение ингибиторов протеиназ для лечения панкреатитов 115.09 KB
  Протеолитические ферменты трипсин химотрипсин эластаза карбоксипептидазы А и В выделяются панкреацитами в неактивном состоянии что предотвращает самопереваривание клеток. Трипсин. Трипсиноген и трипсин получены в кристаллическом виде полностью расшифрована их первичная структура и известен молекулярный механизм превращения профермента в активный фермент. В опытах in vitro превращение трипсиногена в трипсинкатализируют не только энтеропептидаза и сам трипсин но и другие протеиназы и ионы Са2.
81490. Трансаминирование: аминотрансферазы; коферментная функция витамина В6. Специфичность аминотрансфераз 144.39 KB
  Из реакции переноса NH2 наиболее важны реакции трансаминирования . 346 относится к альдиминам или шиффовым основаниям во время реакции аминокислота 1 вытесняет остаток лизина и образуется новый альдимин 2. На второй частиреакции те же стадии протекают в противоположном направлении: пиридоксаминфосфат и вторая 2кетокислота образуют кетимин который иэомеризуется в альдимин. Механизм реакции трансаминирования открыт в 1937 году советскими учеными А.
81491. Аминокислоты, участвующие в трансаминировании; особая роль глутаминовой кислоты. Биологическое значение реакций трансаминирования. Определение трансаминаз в сыворотке крови при инфаркте миокарда и болезнях печени 119.25 KB
  Определение трансаминаз в сыворотке крови при инфаркте миокарда и болезнях печени. Чрезвычайно широкое распространение трансаминаз в животных тканях у микроорганизмов и растений их высокая резистентность к физическим химическим и биологическим воздействиям абсолютная стереохимическая специфичность по отношению к Lаминокислотам а также высокая каталитическая активность в процессах трансаминирования послужили предметом детального исследования роли этих ферментов в обмене аминокислот. Таким образом трансаминазы катализируют опосредованное...
81492. Окислительное дезаминирование аминокислот; глутаматдегидрогеназа. Непрямое дезаминирование аминокислот. Биологическое значение. 248.67 KB
  Непрямое дезаминирование аминокислот. Дезаминирование аминокислот реакция отщепления αаминогруппы от аминокислоты в результате чего образуется соответствующая αкетокислота безазотистый остаток и выделяется молекула аммиака. Безазотистый остаток используется для образования аминокислот в реакциях трансаминирования в процессах глюконеогенеза кетогенеза в анаплеротических реакциях для восполнения убыли метаболитов ОПК в реакциях окисления до СО2 и Н2О.
81493. Основные источники аммиака в организме. Роль глутамата в обезвреживании и транспорте аммиака. Глутамин как донор амидной группы при синтезе ряда соединений 184.57 KB
  Роль глутамата в обезвреживании и транспорте аммиака. Основные источники аммиака Источник Процесс Ферменты Локализация процесса Аминокислоты Непрямое дезаминирование основной путь дезаминирования аминокислот Аминотрансферазы ПФ Глутаматдегидрогеназа ND Все ткани Окислительное дезаминирование глутамата Глутаматдегидрогеназа ND Все ткани Неокислительное дезаминирование Гис Сер Тре ГистидазаСерин треониндегидратазы ПФ Преимущественно печень Окислительное дезаминирование аминокислот малозначимый путь дезаминирования Оксидаза...