Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 7 - METODA DIVIDE ET IMPERA
A.Consideratii teoretice
O abordare obisnuita de rezolvare a unei probleme este impartirea acesteia in mai multe parti mai mici la care solutiile se pot determina usor, si din ele sa se obtina solutia problemei initiale. Aceasta este de fapt principiul pe baza caruia functioneaza metoda DIVIDE ET IMPERA. Printr-un procedeu recursiv, se imparte problema in doua jumatati care se solutioneaza separat si din combinarea solutiilor se obtine solutia problemei date.
Presupunem un vector A cu n elemente asupra caruia vrem sa aplicam aceasta metoda de prelucrare.
Presupunem ca pentru orice p, q <= N, 1 <= p < q <= n, exista m din mulţimea { p, . . . , q-1 } astfel incat prelucrarea secventei { ap, . . . , aq }, se face prelucrand secventele vecine urmatoare { ap, . . . , am }, { am+1, . . . , aq } si apoi combinand rezultatele pentru a obtine prelucrarea intregii secvense { ap, . . . , aq }.
Urmatoarea procedura exemplifica metoda Divide et Impera:
procedure DIVIDE_IMPERA(p, q, a)
begin
if q-p
else
begin
DIVIDE(p, q, m)
DIVIDE_IMPERA(p, m, b)
DIVIDE_IMPERA(m+1, q, c)
COMB(b, c, a)
end
end
Daca dimensiunea problemei initiale sau a subproblemelor aparute este mai mica decat epls, atunci problema se rezolva direct prin procedura SOL solutia fiind in vectorul a.
Solutia se pune in vectorul a, iar solutiile partiale se pun in vectorii b respectiv c. Procedura DIVIDE imparte secventa in doua subsecvente { ap, . . . , am } si { am+1, . . . , aq }, obtinand rezultatul in m.
Prin cele doua autoapelari ale procedurii DIVIDE_IMPERA se rezolva subproblemele punand rezultatele prelucrarilor in b si respectiv in c.
Procedura COMB obtine din solutiile subproblemelor, solutia problemei date. La inceput procedura DIVIDE_IMPERA se apeleaza cu p=1 si q=n.
B.Exemple de programe
INTERCLASAREA UNUI VECTOR
1. In continuare prezentam programul C++ care implementeaza interclasarea elementelor unui vector:
CAUTAREA BINARA
2. Fie un vector v cu n elemente ordonate crescator si un numar nr. Sa se caute acest numar in vector si in caz ca este gasit sa se afiseze indicele pe care se gaseste.
SORTAREA RAPIDA (QUICKSORT)
3. Se da un vector A cu n elemente, si se cere sa se ordoneze crescator.
C.Exercitii si teme
1. Sa se ruleze programele prezentate mai sus.
2. TURNURILE DIN HANOI
Se dau trei tije numerotate cu 1, 2, 3 si n discuri perforate avand diametre diferite. Initial toate discurile sunt asezate pe tija 1, in ordinea crescatoare a diametrelor lor, considerand sensul de la varful tijei la baza ei.
Sa se mute toate discurile pe tija 2 in aceeasi ordine, folosind tija 3 si respectand urmatoarele reguli:
la fiecare pas se muta un singur disc
in permanenta pe fiecare tija deasupra fiecarui disc pot apare numai discuri de diametre mai mici.
3. Ghicirea unui numar ascuns
Fie urmatorul joc: avem un numar x natural intre 0 si 3000 care este ascuns de o persoana. O alta persoana va trebui sa gaseasca numarul ascuns prin incercari cat mai putine, pe baza informatiilor date de persoana care a ascuns numarul, aceasta precizand daca numarul ascuns este mai mare sau mai mic decat numarul presupus.
4. Fiind dat un sir ordonat, sa se scrie un program recursiv care realizeaza cautarea binara, prin impartirea multimii initiale in doua multimi care contin 1/3 respectiv 2/3 din elementele multimii initiale.