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;

}

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

Висновки

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


 

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

36760. Создание «интерфейса пользователя» в среде Scada- системы «Genesis 32» 145 KB
  Ознакомиться с современными направления промышленной автоматизации на базе сетевых технологий с использованием Scd систем что может Scdсистема и ОРСтехнологий. Ознакомиться со Scd системой GENESIS 32 3. Отработать навыки использования современных программноаппаратных средств при построении распределенных информационных систем Общие сведения Scd системы задачи функции см.
36761. Конфигурация глобальной среды. Активизация механизма SSI 46.5 KB
  conf и пропишите в нем директиву которая будет задавать каталог где будут храниться webстраницы сервера: DocumentRoot vr www ваша_фамилия html Сохраните изменения и выйдите из редактора nno. В каталоге где должны храниться webстраницы сервера vr www ваша_фамилия html создайте файл с именем index.html следующего содержания на месте многоточия подставьте свои фамилию и имя: html hed title My web pge title hed body My nme is h1 My web server is working h1 body html Для создания файла введите nno имя_файла...
36763. ИССЛЕДОВАНИЕ ШЕРОХОВАТОСТИ ПОВЕРХНОСТИ 180 KB
  1: а средним арифметическим отклонением профиля R: R=i 1 б высотой неровностей профиля по десяти точкам Rz: Rz=i mx i min 2 где i mx и i min определяются относительно средней линии; в наибольшей высотой неровностей профиля Rmx расстояние между линией выступов и линией впадин профиля в пределах базовой длины; г средним шагом неровностей профиля Sm: Sm=...
36764. Исследование устойчивости линейных систем автоматического регулирования 271 KB
  Пакет моделирования Mtlb. Теоретическая часть Согласно структурной схемы данной математической модели соответствует система дифференциальных уравнений третьего порядка: 1 и уравнение в матричной форме: 2 Характеристическая матрица этого уравнения имеет вид: 3 Соответствующий характеристический полином третьего порядка: р = р3 с1 р2 с2 р с3 4 где коэффициенты сi i = 13 определяются выражениями: с1 = k2 k5 c2 = k2 k5 k4 k3 k6 5 c3 = k2 k3 k6 k1 k4. При заданных величинах коэффициентов полинома...
36765. Исследование метода компьютерной стеганографии для защиты информации 122 KB
  Цель работы Исследование метода замены младших бит используемого в компьютерной стеганографии для защиты информации. Таким образом если цель криптографии состоит в блокировании несанкционированного доступа к информации путём шифрования содержания секретных сообщений то цель стеганографии в скрытии самого факта существования секретного сообщения. При необходимости оба способа могут быть объединены и использованы для повышения эффективности защиты информации.
36766. ИЗУЧЕНИЕ СВОБОДНЫХ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА 482 KB
  ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 4 ИЗУЧЕНИЕ СВОБОДНЫХ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА. Цель работы: Определение коэффициента жесткости пружины по удлинению пружины и методом колебаний пружинного маятника. Такой функцией является функция описывающая гармонические колебания...
36767. Перевод числа из одной системы счисления в другую 44.5 KB
  Варианты 1 15: Перевод из системы по основанию 10 в систему по основанию 2; Перевод из системы по основанию 10 в систему по основанию 4; Перевод из системы по основанию 10 в систему по основанию 8; Перевод из системы по основанию 10 в систему по основанию 16; Перевод из системы по основанию 8 в систему по основанию 10; Перевод из системы по основанию 8 в систему по основанию 2; Перевод из системы по основанию 8 в систему по основанию 4; Перевод из системы по основанию 8 в систему по основанию 16; Перевод...
36768. Размещение графики в документе 310.01 KB
  Работа с графикой в процессоре Word может строиться по трем направлениям.