lucrare de laborator apa cozma nicolae lab1
Post on 02-Aug-2015
73 Views
Preview:
DESCRIPTION
TRANSCRIPT
LUCRARE DE LABORATOR NR. 1
Tema: Analiza algoritmilor (Timpul de execuţie al algoritmilor).
Scopul lucrării:1. Analiza empirică a algoritmilor.2. Analiza teoretică a algoritmilor.3. Determinarea complexităţii temporale şi asimptotice a algoritmilor
Sarcina pentru lucrarea nr.1: Numerele lui Fibonacci
Şirul lui Fibonacci este definit prin următoarea recurenţa:
Acest celebru şir a fost descoperit în 1202 de către Leonardo Pisano (Leonardo din Pisa), cunoscut sub numele de Leonardo Fibonacci. Cel de-al n-lea termen al şirului se poate obtine direct din definiţie:
function fib1(n) if n < 2 then return n else return fib1(n-1) + fib1(n-2)
Această metodă este foarte ineficienta, deoarece recalculează de mai multe ori aceleaşi valori. Iată acum o altă metodă, mai performantă, care rezolvă aceeaşi problemă.
function fib2(n) i 1; j 0 for k 1 to n do j i + j i j - i return j
Mai există un algoritm :
function fib3(n) i 1; j 0; k 0; h 1 while n > 0 do if n este impar then t jh j ih+jk+t i ik+t t h2
h 2kh+t k k2+t n n div 2 return j
1
Anexa 1: Listingul programului:#include <iostream>#include <time.h>#include <conio.h>#include <stdio.h>using namespace std;int fib1(int n);int fib2(int n);int fib3(int n);int main(){
int n;time_t start, end;cout << "Dati n: "; cin >> n;start = time(NULL);cout << endl << fib1(n);end = time(NULL);printf("\ntimp de %.2f\n", difftime(end, start));cout<<endl;start = time(NULL);cout << endl << fib2(n);end = time(NULL);printf("\n timp de %.2f\n", difftime(end, start));cout<<endl;start = time(NULL);cout << endl << fib3(n);end = time(NULL);printf("\n timp de %.2f\n", difftime(end, start));cout<<endl;return 1;
}int fib3(int n){int i=1,j =0, k=0, h=1,t;
while (n > 0){if (n%2==1) {
t= j*h;j= i*h+j*k+t;i= i*k+t;
}t = h*h;h= 2*k* h+ ;k = k*k+t;n = n/2;
}return j;
}int fib2 (int n){int i=1,j =0;for (int k=0;k<n;k++) {
j=i+j;i=j-i;
}return j;}int fib1 (int n){
if (n < 2) return n;else return fib1(n - 1) + fib1(n - 2);
}
2
Anexa 2: Screenshot
SARCINA DE BAZĂ:1. Efectuaţi analiza empirică a algoritmilor propuşi.2. Determinaţi relaţia ce determină complexitatea temporală pentru aceşti algoritmi.3. Determinaţi complexitatea asimptotică a algoritmilor.4. Faceţi o concluzie asupra lucrării efectuate.
Întrebări de control:1. Enumeraţi factorii ce influenţează timpul de execuţie al algoritmului.2. Când timpul de execuţie al algoritmului este dat de o relaţie de recurenţă ?3. Care sunt regulile generale pentru evaluarea timpului de execuţie?4. Care sunt etapele analizei empirice şi în care cazuri se face analiza empirică a
algoritmilor?5. Ce proprietăţi posedă funcţiile asimptotice?
3
top related