МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робота № 6 "Побудова та аналіз складності рекурсивних алгоритмів" № варіанта = [(ASCII–код першої літери прізвища – велика латинська літера) * (день народження) ] % 37 + 1= = (84*14)%37 + 1 = 1176%37 + 1= 29 + 1=30 Львів – 2012 1. МЕТА РОБОТИ Вивчити основні методи організації рекурсивних алгоритмів та дослідження їх ефективності Завдання:. Написати програму для ітераційної та рекурсивної форм обчислення значення функції згідно з варіантом Для рекурсивної форми обчислення використати рекурсивну функцію з виконанням дій на рекурсивному під’омі (для парних варіантів) або на рекурсивному спуску (для непарних варіантів). Порівняти ефективності ітераційної та рекурсивної форм обчислення значення функції. РОЗВ’ЯЗУВАННЯ: Навести приклад обчислення при n=3 та при n=14 При n=3: y1= 2 = 1,4142 y2= 2 + 2 = 1,8477 y= 2 + 2+ 2= 1,9615 При n=4: y1= 2 = 1,4142 y2= 2 + 2 = 1,8477 y3= 2 + 2+ 2 = 1,9615 y= 2 + 2+ 2+ 2 = 1,9903 3. Ітераційне обчислення. Опис алгоритму розв’язання задачі (навести вигляд ітераційної функції обчислення y) int main(){   int n;   float y=0; 1 операція.   for(int i=n;i>0;i--){ 1 операція. Всього n-1 проходів циклу   y=sqrt(2+y); 3 операції на кожний прохід циклу  } 3 операції на кожний прохід циклу  return y;   }   3.3. Обчислення функції трудомісткості нерекурсивного алгоритму. g+(n)=0 , g*(n)=1 => fА(D) = fn(n)
=1 + 1 + (n-1)*(3+3)= 6n-4=O(n); 4. Рекурсивне обчислення. 4.1. Опис алгоритму розв’язання задачі (навести вигляд рекурсивної функції обчислення y) float funkcia(int ch,float D){ float F; D=sqrt(2+D); if (ch==1){ F=D;} else { F=funkcia(ch-1,D);} return F; } 4.3. Обчислення функції трудомісткості рекурсивного алгоритму. Для аналізу трудомісткості виклику/повернення введемо значення: m -- кількість переданих фактичних параметрів, k -- кількість повернених по адресному посиланню значень, r -- кількість збережених в стеці регістрів. Тоді трудомісткість в елементарних операціях на один виклик і повернення буде виглядати так:
Аналіз трудомісткості рекурсивних алгоритмів і в деякій частині трудомісткість самого рекурсивного виклику можливо виконати різними способами в залежності від того як формується кінцева сума елементарних операцій: - окремо по ланцюгам рекурсивних викликів і повернень; - загалом по вершинам дерева рекурсивних викликів. Продемонструємо цей підхід на прикладі рекурсивного обчислення факторіала. Для розгляданого вище рекурсивного алгоритму обчислення факторіала кількість вершин рекурсивного дерева, дорівнює, очевидно, n, при цьому передається і повертається по одному значенню (m=2,k=1) ,а на останньому рекурсивному виклику значення функції обраховується безпосередньо - в кінці у припущенні про збереження чотирьох регістрів
отримаємо: f(n)=n*2*(2+1+4+1) + 1*2 = 16n - 2 зауважимо що n - параметр алгоритму, а не кількість слів на вході. Результат виконання програми Висновок: На даній лабораторній роботі я визначила складність рекурсивного алгоритму, а саме знаходження факторіалу. Складність такого алгоритму для 3 викликів = , для 4 викликів = . З цих даних виходить, що даний алгоритм відноситься до складності типу N( клас кількісно-залежних по складності алгоритмів. Це алгоритми, функція складності, яких залежить від кількості вхідних даних) Додатки (тексти програм з коментарями). #INCLUDE<STDIO.H> #include<conio.h> #include<iostream> using namespace std; int main(){ int n; float y; cout<<"Vvedit kilkist povtoriv n:"; cin >> n; y=0; for(int i=n;i>0;i--){ y=sqrt(2+y); } cout<<"Pru N="<<n<<" Y="<<y; getch(); return 0; } #INCLUDE<STDIO.H> #include<conio.h> #include<iostream> using namespace std; float funkcia(int ch,float D){ float F; D=sqrt(2+D); if (ch==1){ F=D;} else { F=funkcia(ch-1,D);} return F; } int main(){ int n; float y; float f=0; cout<<"Vvedit kilkist povtoriv n:"; cin >> n; y=funkcia(n,f); cout<<"Pru N="<<n<<" Y="<<y; getch(); return 0; }