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;

}

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

Висновки

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


 

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

75360. ОЦІНЮВАННЯ ВАРТОСТІ ЗЕМЕЛЬНОЇ ДІЛЯНКИ, БУДІВЕЛЬ І СПОРУД 157.5 KB
  Особливості оцінки земельної ділянки будівель і споруд. Проблема оцінки незабудованої земельної ділянки або земельної ділянки з поліпшеннями нерухомістю вже давно є об’єктом ретельного дослідження багатьох науковців. Вартість земельної ділянки будівель і споруд визначається їх специфічною корисністю унікальністю довговічністю місцерозрашуванням а також кількістю ринкових пропозицій.
75361. ОЦІНЮВАННЯ РИНКОВОЇ ВАРТОСТІ МАШИН І ОБЛАДНАННЯ 221 KB
  Вживаний у практиці господарювання термін “машини та обладнання” має більш широке значення і не зводиться тільки до четвертої групи типової класифікації основних фондів, яка використовується діючими системами бухгалтерського обліку та статистики.
75362. Нематеріальні активи та методи їх оцінки 185.5 KB
  Визначимо специфічні риси нематеріальних активів: відсутність матеріальної основи для отримання вигод; умовна невіддільність від суб’єкта господарювання; тривалий термін використання; відсутність корисних відходів; невизначеність усього спектру можливих ефектів від використання; підвищений рівень ризику на стадіях створення та використання. Відзначені риси нематеріальних активів характеризують їх в якості об’єкта обліку як узагальнену оцінку результатів творчої діяльності і засобів індивідуалізації юридичних осіб...
75363. ТРУДОВИЙ ПОТЕНЦІАЛ ПІДПРИЄМСТВА ТА ЙОГО ОЦІНЮВАННЯ 210.5 KB
  Роль і значення трудового потенціалу в економічних відносинах. Методологія оцінювання трудового потенціалу підприємства. Методики оцінювання трудового потенціалу підприємства. Роль і значення трудового потенціалу в економічних відносинах Трудові ресурси це економічно активна працездатна частина населення регіону яка володіє фізичними і культурноосвітніми можливостями для участі у економічній діяльності підприємства організації.
75364. ОЦІНЮВАННЯ ВАРТОСТІ БІЗНЕСУ 234 KB
  Відповідно до міжнародних стандартів, оцінювання вартості бізнесу — це акт чи процес формування точки зору оцінювача та підрахунку вартості бізнесу, цілісного майнового комплексу або пов’язаних з ним прав. Визначення вартості окремих елементів бізнесу досліджувалося у попередніх розділах
75365. СУТНІСНА ХАРАКТЕРИСТИКА ПОТЕНЦІАЛУ ПІДПРИЄМСТВА 134 KB
  Властивості потенціалу підприємства. Воблого знайшло обґрунтування поняття потенціалу виробничих сил як потенційної можливості країни виробляти матеріальні блага для задоволення потреб населення. До складових потенціалу в цьому розумінні відносять відповідні трудові матеріальні фінансові та інформаційні ресурси які залучаються у сферу вдосконалення виробництва.
75366. МЕТОДИЧНІ ПІДХОДИ ДО ОЦІНЮВАННЯ ПОТЕНЦІАЛУ ПІДПРИЄМСТВА 333.5 KB
  У випадку визначення майбутньої корисності від господарського використання об’єкту тобто розміру чистого потоку капіталу отриманого інвесторомвласником від експлуатації земельної ділянки будівлі чи споруди очевидно що аналітик апріорі розраховує можливу вартість об’єкту. Усі мультиплікатори поділяються на дві групи у залежності від виокремленої ознаки: Залежно від бази порівняння: ресурсні мультиплікатори у якості бази порівняння беруться суми витрат наприклад вартість капітал підприємства; результатні мультиплікатори у якості...
75367. ТЕОРЕТИЧНІ ОСНОВИ ОЦІНЮВАННЯ ПОТЕНЦІАЛУ ПІДПРИЄМСТВА 142 KB
  Визначити вартість основних виробничих фондів і оборотних фондів досить легко але дати вартісну оцінку трудових ресурсів можна лише непрямим шляхом і з достатнім ступенем умовності що посилюється ще і тим що для живої праці визначальне значення мають її якісні характеристики. Поняття вартості та її модифікації Вартість – це гроші чи грошовий еквівалент який покупець готовий обміняти на якийнебудь предмет чи обєкт. Вартість – це міра того скільки гіпотетичний покупець готовий заплатити за оцінювану вартість. Витрати впливають на ринкову...
75368. Розвиток підприємства: зміст, сучасні концепції та передумови 831 KB
  Розвиток підприємства: зміст сучасні концепції та передумови Поняття економічного розвитку підприємства Підприємницька діяльність передбачає динамічність розвиток і зростання. Його джерелами для підприємства виступають вміння максимально задіяти внутрішні ресурси наявність добре розвинених видів діяльності та ринків збуту постійний процес розробки та впровадження інновацій здатність швидко реагувати на зміни на ринку і використовувати надані можливості. Економічне зростання підприємства розглядають насамперед як необхідну умову...