Sem 04 - Divide Et Impera

ATP - Seminar 4 - Recursivitate II Metoda Divide et impera - Utilizata in rezolvarea unor probleme complexe ce se pot descompune in probleme cu complexitate mai mica; - Prin combinarea solutiilor problemelor rezultate in urma descompunerii (dupa reguli simple) se obtine o solutie pentru problema initiala; - Pentru fiecare problema rezultata in urma descompunerii, se aplica acelasi procedeu de descompunere; - Algoritmul este de tip recursiv, implementarea fiind realizata de obicei prin subprogram recursiv. Exemple: 1. Sa se scrie programul C pentru identificarea maximului dintr-un vector. a) Solutie 1 – descompunere in doua jumatati, fiecare cu solutia s1 si respective s2. Se va calcula maximul dintre s1 si s2. b) Solutie 2 – reducerea problemei succesiv la o problema mai simpla, determinandu-se primele n-1 componente ale secventei (fie s1). Solutia problemei este max (s1,an). 2. Cautare binara Sa se scrie programul C pentru cautarea unei valori date intr-un vector ordonat. Exemplu numeric: Dimensiunea vectorului:6 v[0]=1 v[1]=3 v[2]=5 v[3]=7 v[4]=9 v[5]=10 Numarul cautat este:10 Gasit, cu indicele = 5

Upload
corinutza260
Category

Documents
view
15
download
2

Embed Size (px):

Transcript of Sem 04 - Divide Et Impera

ATP - Seminar 4 - Recursivitate II

Metoda Divide et impera Utilizata in rezolvarea unor probleme complexe ce se pot descompune in probleme cu complexitate mai mica; Prin combinarea solutiilor problemelor rezultate in urma descompunerii (dupa reguli simple) se obtine o solutie pentru problema initiala; Pentru fiecare problema rezultata in urma descompunerii, se aplica acelasi procedeu de descompunere; Algoritmul este de tip recursiv, implementarea fiind realizata de obicei prin subprogram recursiv.

Exemple:

1. Sa se scrie programul C pentru identificarea maximului dintr-un vector.a) Solutie 1 descompunere in doua jumatati, fiecare cu solutia s1 si respective s2. Se va calcula maximul dintre s1 si s2.b) Solutie 2 reducerea problemei succesiv la o problema mai simpla, determinandu-se primele n-1 componente ale secventei (fie s1). Solutia problemei este max (s1,an).

2. Cautare binara Sa se scrie programul C pentru cautarea unei valori date intr-un vector ordonat.

Exemplu numeric:Dimensiunea vectorului:6v[0]=1v[1]=3v[2]=5v[3]=7v[4]=9v[5]=10Numarul cautat este:10Gasit, cu indicele = 5

Indicatii:

void caut (intreg i,intreg j){ daca (x==v[(i+j)/2]) mesaj ("Gasit cu indicele %d", (i+j)/2); altfel daca (i0) cod=3; altfel daca (n==0) cod=0; altfel { *sol=(a+b)/2; daca ((*f)(*sol)==0) cod=1; altfel daca (fabs(a-b)