cn onisifor ghibu oradea cercul de informatică metoda divide et...

CN Onisifor Ghibu Oradea Cercul de Informatică

1

Metoda Divide et Impera

1. Prezentare generală

Divide et Impera (Împarte şi Stăpâneşte) este o metodă de programare care se aplică problemelor care pot fi descompuse

în subprobleme independente, similare problemei iniţiale, de dimensiuni mai mici şi care pot fi rezolvate foarte uşor.

Metoda presupune:

- descompunerea problemei iniţiale în subprobleme independente;

- rezolvarea subproblemelor;

- construirea rezultatului prin compunerea soluţiilor problemelor de dimensiuni mici.

Această metodă se poate implementa atât iterativ cât şi recursiv. Datorită faptului că problemele se împart în subprobleme

în mod recursiv, de obicei împărţirea se realizează până când şirul obţinut prin împărţire este de lungime 1, caz în care

rezolvarea subproblemei este foarte uşoară, chiar banală.

2. Modelul matematic

Fie un vector X = (x1, x2, …, xn) asupra căruia se aplică o prelucrare. Pentru orice i, j {1, 2, …, n}

astfel încât i < j, există o valoare p, astfel încât prin prelucrarea secvenţelor {xi, xi+1, …, xp} şi {xp+1, xp

+2, …, xj} se obţin soluţiile corespunzătoare subşirurilor care prin combinare conduc la soluţia prelucrării secvenţei

{xi, xi+1, …, xj}.

Subalgoritm Divide(i,j,rez):

dacă i < j atunci

Împarte(i,j,p)

Divide(i,p,rez1)

Divide(p+1,j,rez2)

rez=Combină(rez1,rez2)

altfel

Rezolvă(rez)

sf. subalgoritm


2

3. Complexitatea metodei

Această metodă conduce în general la un timp de calcul polinomial. Algoritmii divide et impera au o bună comportare în

timp, dacă dimensiunile subproblemelor în care se împarte subproblema sînt aproximativ egale. Dacă lipsesc fazele de

combinare a soluţiilor, viteza acestor algoritmi este şi mai mare (ex. căutarea binară). În majoritatea cazurilor,

descompunerile înjumătăţesc dimensiunea problemei, un exemplu tipic reprezentându-l sortarea prin interclasare.

4. Aplicații

4.1. Aplicații simple

#1019 – Maxim 6 (https://www.pbinfo.ro/?pagina=probleme&id=1019)

Determinaţi valoarea maximă dintr-un şir de numere, folosind metoda Divide et Impera.

Exemplu maxim.in maxim.out

6 8

4 1 8 4 3 5

Metoda presupune împărţirea problemei în subprobleme care se rezolvă, iar apoi rezultatele subproblemelor se

combină şi se obţine soluţia problemei date.

În cazul determinării maximului dintr-un şir de numere, descompunerea problemei revine la a împărţi şirul în

două subşiruri. De exemplu, dacă avem şirul (x1, x2, …, xn) el poate fi împărţit în subşirul (x1, …, xm) şi în

(xm+1, …, xn), unde n este numărul de elemente din şir, iar m = [(1 + n) / 2] este indicele elementului din

mijloc. După deter-minarea maximului pentru fiecare dintre cele două subşiruri (max1 respectiv max2), combinarea

rezultatelor se realizează prin compararea valorilor celor două maximuri (max1 < max2). În funcţie de rezultat se obţine

rezultatul final al valorii maxime din şir, şi anume dacă max1 > max2, vom avea maxim = max1, respectiv maxim

= max2, dacă max1 <= max2.

Dar determinarea lui max1 pentru primul subşir, respectiv a lui max2 pentru al doilea subşir este o problemă de

rezolvat la fel ca problema iniţială pentru întreg şirul. Se va împărţi subşirul {x1, …, xm} în alte două subşiruri şi, la

rândul lor, cele două subşiruri în altele, până când subşirul care se obţine este de dimensiune 1, adică are un singur

element, care este valoarea maximă din acest subşir de lungime 1.

int maxim(int l, int r){

if(l == r) return a[l];//daca avem un singur element acela e maxim

else{

int m = (l + r) / 2;// se determină indicele elementului din mijloc

int max1 = maxim(l, m);//subproblema1 -> maxim din stanga

int max2 = maxim(m + 1, r);// subproblema2 -> maxim din dreapta

return max(max1, max2);//combinare solutie

}

}

#1023 – cmmdc3 (https://www.pbinfo.ro/?pagina=probleme&id=1023)

Se dă un sir cu n elemente, numere naturale nenule. Folosind metoda Divide et Impera, determinaţi cel mai mare divizor

comun al elementelor acestui șir.

Exemplu maxim.in maxim.out

7 6

18 54 24 42 108 60 30

https://www.pbinfo.ro/?pagina=probleme&id=1019



3

- descompunerea problemei iniţiale în subprobleme: (left – right) (left, middle), (middle + 1, right) ;

- rezolvarea subproblemelor: daca avem 1 sau 2 elemente in subprobleme aflam cmmdc.

- construirea rezultatului prin compunerea soluţiilor problemelor de dimensiuni mici. Sol cmmdc(cmmdc(left,

middle), cmmdc(middle + 1, right))

int cmmdc(int x, int y){

while(y > 0){

int r = x % y;

x = y; y = r;

}

return x;

}

int solutie(int l, int r){

if(l == r) return a[l];

else if(l + 1 == r) return cmmdc(a[l], a[r]);

else{

int m = (l + r) / 2;

int x = solutie(l, m);

int y = solutie(m + 1, r);

return cmmdc(x, y);

}

}

#1018 – CntImpare (https://www.pbinfo.ro/?pagina=probleme&id=1018)

Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați câte elemente impare

sunt în acest șir.

- descompunerea problemei iniţiale în subprobleme: (left – right) (left, middle), (middle + 1, right) ;

- rezolvarea subproblemelor: daca avem 1 element in subprobleme aflam rezolvam subproblema.

- construirea rezultatului prin compunerea soluţiilor problemelor de dimensiuni mici. Sol nrimpar(left, middle) +

nrimpar(middle + 1, right)

int solutie(int l, int r){

if(l == r) return a[l] % 2 == 1;

else{

int m = (l + r) / 2;

int x = solutie(l, m);

int y = solutie(m + 1, r);

return x + y;

}

}

Turnurile din Hanoi(https://www.pbinfo.ro/?pagina=probleme&id=2527)

Se dau trei tije verticale A, B şi C. Pe tija A se găsesc discuri de diametre diferite, perforate la mijloc, aranjate în ordine

descrescătoare a diametrelor discurilor, de la bază spre vârf. Celelalte tije sunt goale. Se cere să se găsească o strategie de

mutare a discurilor de pe tija A pe tija B respectând următoarele reguli:




4

La un moment dat se va muta un singur disc (cel care se află deasupra celorlalte discuri pe o tijă).

Un disc poate fi aşezat doar peste un alt disc având diametru mai mare decât al său, sau pe o tijă goală.

Se observă că există reguli stricte privind mutarea unui disc. De asemenea, se observă că dacă pe tija A ar exista un singur

disc, unica mutare necesară ar fi A B.

Pentru două discuri existente pe tija A, mutările ar fi: A C, A B şi C B. Pentru un număr mai mare de discuri,

evident va fi un număr mult mai mare de mutări.

Împărţim problema în subprobleme astfel:

se mută primele n – 1 discuri de pe tija A pe tija C,

se mută ultimul disc (cel care are diametrul cel mai mare) de pe tija A pe tija B,

se mută cele n – 1 discuri de pe tija C pe tija B.

Acum au apărut două probleme mai „simple” şi anume mutarea a n – 1 discuri de pe tija A pe tija C, respectiv cele n – 1

discuri de pe tija C pe tija B. La rândul lor, aceste operaţii se pot împărţi în subprobleme până când rămâne de mutat un

singur disc. Astfel, problema se rezolvă folosind metoda Divide et Impera.

La un transfer al unui disc acesta este în vârful tijei şi este aşezat tot în vârful unei tije, astfel că o mutare este definită prin

numele tijelor de pe care se ia un disc, respec-tiv cea pe care se aşează. Pentru a asigura precizarea lor pentru fiecare

subproblemă care trebuie rezolvată, vom folosi trei parametri (pentru tija sursă, tija destinaţie şi tija auxiliară) care vor

primi valori în momentul autoapelării subalgoritmului.

Subalgoritm Hanoi(n,A,B,C):

dacă n=1 atunci

Mută un disc de pe tija A pe tija B

altfel

Hanoi(n-1,A,C,B)

Mută un disc de pe tija A pe tija B

Hanoi(n-1,C,B,A)

sfârşit dacă

sfârşit subalgoritm

Combinarea soluţiilor subproblemelor nu este necesară în cazul rezolvării acestei probleme.


5

5. Quicksort

Se dă un vector cu n elemente. Folosind metoda sortării rapide sortați crescător elementele vectorului.

Rezolvare:

Quicksort efectuează sortarea bazându-se pe o strategie divide et impera. Astfel, el împarte lista de sortat în două subliste

mai ușor de sortat. Pașii algoritmului sunt:

- se alege un element al listei, denumit pivot

- se reordonează lista astfel încât toate elementele mai mici decât pivotul să fie plasate înaintea pivotului și toate

elementele mai mari să fie după pivot. După această partiționare, pivotul se află în poziția sa finală.

- se sortează recursiv sublista de elemente mai mici decât pivotul și sublista de elemente mai mari decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

int n, a[100002];

void quicksort(int l, int r){

int i = l, j = r, piv = a[l];

while(i <= j){

while(i < r and a[i] < piv) i = i + 1;

while(j > l and a[j] > piv) j = j - 1;

if(i <= j){

swap(a[i], a[j]); i = i + 1; j = j - 1;

}

}

if(l < j) quicksort(l, j);

if(i < r) quicksort(i, r);

}

int main(){

cin >> n;

for(int i = 1; i <= n; i++) cin >> a[i];

quicksort(1, n);

for(int i = 1; i <= n; i++) cout << a[i] << " ";

return 0;

}

6. Problema tăieturilor

Se da o bucata dreptungiulara de tabla avand lungimea L si inaltimea h. Pe suprafata ei se gasesc n gauri, de

coordonate intregi, stiute, cu diametre neglijabile. Sa se decupeze o bucata de tabla de arie maxima, fara gauri,

facand numai taieturi paralele cu laturile placii (verticale sau orizontale). Rezolvare:

Coordonatele găurilor sunt reţinute în doi vectori XV şi YV. Dreptunghiul iniţial, precum şi

dreptunghiurile care apar în procesul tăierii sunt memorate în program prin coordonatele colţului din stânga-sus

(X,Y), prin lungime şi înălţime (L,H).


6

Pentru un dreptunghi (iniţial pornim cu toată bucata de tablă), verificăm dacă avem sau nu o gaură în el

(se caută practic prima din cele n găuri). În situaţia când acesta prezintă o gaură, problema se descompune în

alte patru probleme de acelaşi tip. Dacă bucata nu prezintă găuri, se compară aria ei cu aria unei alte bucăţi fără

gaură, găsită în fazele precedente.

Menţionăm că dreptunghiul de arie maximă fără găuri este reţinut prin aceiaşi parametri ca şi

dreptunghiul cu găuri, în zonele XF, YF, LF, HF.

În concluzie, problema iniţială se descompune în alte patru probleme de acelaşi tip, mai uşoare, întrucât

fiecare nou dreptunghi are cel mult n-1 găuri, dacă dreptunghiul iniţial avea n găuri. La această problemă

compararea soluţiilor constă în a reţine dreptunghiul cu aria maximă dintre cele fără găuri.

Pentru a se afla în interiorul dreptunghiului, gaura trebuie să îndeplinească simultan condiţiile:

1) xv(i)>x;

2) xv(i)<x+l;

3) yv(i)>y;

4) yv(i)<y+h.

Dacă facem o tăietură verticală prin această gaură, obţinem două dreptunghiuri:

1) x, y, xv(i)-x, h;

2) xv(i), y, l+x-xv(i), h.

În urma unei tăieturi pe orizontală se obţin cele două dreptunghiuri:

1) x, y ,l ,yv(i)-y;

2) x, yv(i), l, h+y-yv(i).

int l,h,i,n,xf,yf,lf,hf,xv[10],yv[10];

void dimp(int x, int y, int l, int h, int &xf, int &yf, int& lf, int &h){

int gasit=0, i=1;

while (i<=n && !gasit)//cautam o gaura in interior

if (xv[i]>x && xv[i]<l && yv[i]>y && yv[i]<y+h) gasit=1;

else i++;

if (gasit){ //daca am gasit obtinem cele 4 dreptunchiuri

dimp(x,y,xv[i]-x,h,xf, yf,lf,hf,xv,yv);

dimp(xv[i],y,l+x-xv[i], h,xf,yf,lf,hf,xv,yv);

dimp(x,y,l,yv[i]-y,xf, yf,lf,hf,xv,yv);

dimp(x,yv[i],l,h+y-yv[i], xf,yf,lf,hf,xv,yv);

}

if (l*h>lf*hf){ //verificam daca avem o arie maxima

xf=x; yf=y; lf=l; hf=h;

}

}

int main(){

… //citire l, h, n si coordonatele celor n gauri

dimp(0,0,l,h,-1,-1,0, 0);

cout<< xf<<" " << yf <<" "<<lf<<" "<<hf;

}

cn onisifor ghibu oradea cercul de informatică metoda divide et...

Documents