Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 8 - 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 ca avem 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 multimea { 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 secvente { ap, . . . , aq }.
Urmatoarea procedura scrisa in pseudocod, exemplifica metoda Divide et Impera.
Daca dimensiunea problemei initiale sau a subproblemelor aparute este mai mica decat eps, 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.
procedure DIVIDE_IMPERA(p, q, a)
begin
if q-p<=eps then
SOL(p, q, a)
else
begin
DIVIDE(p, q, m)
DIVIDE_IMPERA(p, m, b)
DIVIDE_IMPERA(m+1, q, c)
COMB(b, c, a)
end
end
Prezentam in continuare metoda Divide et Impera aplicata pentru a sorta un vector A cu n elemente prin interclasare.
procedure SORT(p, q, A)
begin
if ap > aq then
begin
t<-ap
ap<-aq
aq<-t
end
end
procedure DIVIDE_IMPERA(p, q, A)
begin
if q - p <= 2 then SORT(p, q, A)
else
begin
m<-[( p + q ) / 2]
DIVIDE_IMPERA(p, m, A)
DIVIDE_IMPERA(m+1, q, A)
INTERCLASARE(p, q, m, A)
end
end
procedure INTERCLASARE(p, q, m, A)
vector A, B
begin
i<-p, j<-m+1, k<-1
while (i<=m) and (j<=q)
begin
if ai<=aj then
begin
bk<-ai
i<-i+1
k<-k+1
end
else
begin
bk<-aj
j<-j+1
k<-k+1
end
end
if i<=m then
for j=i to m do
begin
bk<-aj
k<-k+1
end
else
for i=j to q do
begin
bk<-ai
k<-k+1
end
k<-1
for i=p to q do
begin
aj<- bk
k<=k+1
end
end
{programul principal}
begin
for i=1 to n do read(Ai)
DIVIDE_IMPERA(1, n, A)
for i=1 to n do write(Ai)
end.
Descompunerea unui vector in alti doi vectori ce urmeaza a fi sortati, are loc pana cand avem de sortat vectori cu maxim doua componente. Procedura SORT ordoneaza crescator un vector de maxim doua elemente si corespunde procedurii SOL din schema generala. Procedura INTERCLASARE interclaseaza rezultatele si corespunde procedurii COMB din schema generala. Procedura DIVIDE_IMPERA implementeaza strategia generala a metodei. Procedura DIVIDE este realizată prin instructiunea m<-[( p + q ) / 2].
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 mută 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 numrul 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.