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;

}

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

Висновки

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


 

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

8699. Світові релігії. Християнство. Розкол християнства, його гілки 127 KB
  Світові релігії. Християнство План. 1. Християнство, його віровчення і культ. 2. Нехристиянські джерела про виникнення християнства. 3. Розкол християнства, його гілки. 4. Етапи життя мусульманина. Принципи і мораль мусульманства. Християнство Христ...
8700. Культура середньовічного суспільства Київської Русі: Від язичництва до християнства 93 KB
  Дохристиянські вірування східних словян. Поширення християнства на території Східної Європи і причини його розповсюдження. Прийняття християнства за Володимира Святославовича...
8701. Сучасна релігійна ситуація в Україні 92 KB
  Сучасна релігійна ситуація в Україні План. Християнські конфесії в Україні. Православний вузол України. Протестантські церкви в Україні. Мусульманські та іудейські громади в Україні. Громади нетрадиційної релігійності, їхні...
8702. О граде божьем. ок. 426 н.э. (Августин Блаженный) 4.49 MB
  О граде божьем. ок.426 н.э. (Августин Блаженный) Предисловие В этом сочинении, любезнейший сын мой Марцеллин, тобою задуманном, а для меня, в силу данного мною обещания, обязательном, я поставил своей задачей защитить град Божий, славнейший как в ...
8703. Августин Блаженный О свободе воли 234.5 KB
  Sanctus Aurelius Augustinus De libero arbitrio (Перевод выполнен по изданию Ермаковой М.Е.) Августин Блаженный О свободе воли Книга вторая Глава I 1. Эводий. Итак, разъясни мне, если это возможно, почему Бог дал человеку свободу воли, ибо, если бы ч...
8704. Песня русская в березах, песня русская в хлебах. Конспект 29 KB
  Песня русская в березах, песня русская в хлебах. Если вдуматься в смысл таких выражений, как Вся Россия просится в песню, С песней на Руси родились, С доброй песней и жизнь хороша, то становится очевидным, что жизнь русского человека немы...
8705. Что за прелесть эти сказки. Урок 70 KB
  Что за прелесть эти сказки О обращаясь к литературным источникам, композиторы часто создают на их основе инструментальные произведения. Эти сочинения называют программной музыкой. 0ни нередко имеют название литературного произведения или сопровождаю...
8706. Педагогическая психология. Психология педагогического общения 5.52 MB
  Педагогическая психология o Тема 1. Предмет и задачи педагогической психологии o Тема 2. Методы педагогической психологии o Тема 3. Научение и учение o Тема 4. Обучение и развитие o Тема 5. Учебная деятельность o Тема 6. Мотивы чтения o Тема 7. Усвое...
8707. Методика організації самостійної роботи майбутніх інженерів-педагогів при викладанні дисципліни Деталі машин (на прикладі Української інженерно-педагогічної академії) 1.49 MB
  РЕФЕРАТ Мета дослідження: Теоретично обґрунтувати та розробити методику організації самостійної роботи майбутніх інженерів-педагогів при вивченні дисципліни Деталі машин (на прикладі Української інженерно-педагогічної академії)...