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;

}

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

Висновки

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


 

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

57679. Veterans Day 188.5 KB
  Veterans Day is observed with ceremonies at war monuments and cemeteries throughout the nation. Almost every village has a monument to veterans who served in one of the country’s wars.
57680. ЗІРКИ МУЗИКИ 108.5 KB
  It’s true because we can’t imagine our life without music. People all over the world are fond of music. They listen to music, they dance to music, they learn to play musical instruments. People make their own music too.
57681. The Beauty of Future Cities 40.5 KB
  Show the students some photos of the future cities. It can be initial slides of your power point presentation and ask them to guess what the theme of the lesson is. Right you are. Today we are going to have a talk about megacities of today and their future.
57682. Books are Our Friends. The World of Books 44.5 KB
  Objectives: Pupils’ learning outcomes: practical to present and give practice in the use of new words; will learn 8 new words; to present and give practice in the use of “be fond of”, will be able to express their attitude to reading and “be interested in” in the micro dialogues...
57683. Великобританія 59 KB
  So, we have refreshed our knowledge about our topic and it’s time for you to represent your own information about traditions in Great Britain. It was your home task for today.
57684. Favourite Clothes 116 KB
  Materials: a student book, pictures of clothes, cards with the names of clothes, cards with the task for reading, cards for practicing the phrasal verbs, pictures of three persons and cut sentences with their descriptions.
57685. The Earth does not belongs to us we belong to the Earth 36.5 KB
  The aim of the lesson: to develop the logical thought creative abilities, interest to learning English to our planet, to teach pupils to keep the environment clean. Equipment: pictures, songs, drawings, computers, CD, the song – M. D. “Save the Earth”
57687. Мої улюблені страви 43.5 KB
  Teacher: Very good! Я хочу дізнатися, про ваші вподобання на обід. Look at the blackboard, please (слайд 10). Використовуйте фрази «I like... for dinner», «I don`t like... for dinner». Але тепер вам треба пригадати назви продуктів за їхніми малюнками, які ви бачите на дошці.