Lucrare de specialitate in vederea obtinerii atestatului profesional de informatica
Divide et impera
Notiuni introductive: ...........pag 2
Tehnica algoritmului DIVIDE ET IMPERA ;
Conditiile necesare pentru aplicarea algoritmului DIVIDE ET IMPERA ;
Etapele rezolvarii unei probleme ;
Aplicatii :
1. Maximul unui sir..................pag 5
2. Cel mai mare divizor comun al unui sir......... pag 7
3. Cautarea binara..................pag 8
4. Interclasarea...................pag 10
5. Sortarea rapida..................pag 13
6. Turnurile din Hanoi................pag 16
7. Problema taieturilor................pag 19
Concluzii.................pag 23
Bibliografie................pag 24
Notiuni introductive
Dictonul latin, care se traduce prin " dezbina si stapaneste ", sintetizeaza modalitatea prin care romanii au ajuns stapanii lumii antice. Ca tehnica, metoda de programare DIVIDE ET IMPERA consta in impartirea problemei initiale de dimensiuni [n] in doua sau mai multe probleme de dimensiuni reduse .In general se executa impartirea in doua subprobleme de dimensiuni aproximativ egale si anume [n/2] . Impartirea in subprobleme are loc pana cand dimensiunea acestora devine suficient de mica pentru a fi rezolvate in mod direct(cazul de baza).Dupa rezolvarea celor doua subprobleme se executa faza de combinare a rezultatelor 222i87c in vederea rezolvarii intregii probleme .
Metoda DIVIDE ET IMPERA se poate aplica in rezolvarea unei probleme care indeplineste urmatoarele conditii :
se poate descompune in ( doua sau mai multe) suprobleme ;
aceste suprobleme sunt independente una fata de alta (o subproblema nu se rezolva pe baza alteia si nu se foloseste rezultatele celeilalte);
aceste subprobleme sunt similare cu problema initiala;
la randul lor subproblemele se pot descompune (daca este necesar) in alte subprobleme mai simple;
aceste subprobleme simple se pot solutiona imediat prin algoritmul simplificat.
Etapele rezolvarii unei probleme (numita problema initiala) in DIVIDE ET IMPERA sunt :
descompunerea problemei initiale in subprobleme independente ,similare problemei de baza ,de dimensiuni mai mici ;
descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediat ,prin algoritmul simplificat ;
rezolvarea subproblemelor simple ;
combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mari ;
combinarea ultimelor solutii determina obtinerea solutiei problemei initiale .
Metoda DIVIDE ET IMPERA admite o implementare recursiva, deoarece subproblemele sunt similare problemei initiale, dar de dimensiuni mai mici .
Principiul fundamental al recursivitatii este autoapelarea unui subprogram cand acesta este activ; ceea ce se intampla la un nivel ,se intampla la orice nivel ,avand grija sa asiguram conditia de terminare ale apelurilor repetate .Asemanator se intampla si in cazul metodei DIVIDE ET IMPERA ; la un anumit nivel sunt doua posibilitati :
s-a ajuns la o (sub)problema simpla ce admite o rezolvare imediata caz in care se rezolva (sub)problema si se revine din apel (la subproblema anterioara,de dimensiuni mai mari);
s-a ajuns la o (sub)problema care nu admite o rezolvare imediata, caz in care o descompunem in doua sau mai multe subprobleme si pentru fiecare din ele se continua apelurile recursive(ale procedurii sau functiei).
In etapa finala a metodei DIVIDE ET IMPERA se produce combinarea subproblemelor (rezolvate deja) prin secventele de revenire din apelurile recursive.
Etapele metodei DIVIDE ET IMPERA (prezentate anterior)se pot reprezenta prin urmatorul subprogram general (procedura sau functie) recursiv exprimat in limbaj natural:
Subprogram DIVIMP (PROB);
Daca PROBLEMA PROB este simpla
Atunci se rezolva si se obtine solutia SOL
Altfel pentru i=1,k executa DIVIMP(PROB) si se obtine SOL1;
Se combina solutiile SOL 1, ,SOL K si se obtine SOL;
Sfarsit _subprogram;
Deci ,subprogramul DIVIMP se apeleaza pentru problema initiala PROB; aceasta admite descompunerea in K subprobleme simple ;pentru acestea se reapeleaza recursiv subprogramul ;in final se combina solutiile acestor K subprobleme.
De obicei problema initiala se descompune in doua subprobleme mai simple ; in acest caz etapele generale ale metodei DIVIDE ET IMPERA se pot reprezenta concret,in limbaj pseudocod ,printr-o procedura recursiva astfel :
Procedura DIVIMP(li,ls,sol);
Daca ((ls-li)<=eps)
Atunci REZOLVA (li,ls,sol);
Altfel
DIVIDE (li,m,ls);
DIVIMP(li,msol1);
DIVIMP(m,ls,sol2);
COMBINA(sol1,sol2,sol);
Sfarsit_ procedura;
Procedura DIVIMP se apeleaza pentru problema initiala care are dimensiunea intre limita inferioara (li) si limita inferioara(ls);daca (sub)problema este simpla (ls-li<=eps),atunci procedura REZOLVA ii afla solutia imediat si se produce intoarcerea din apelul recursiv;daca (sub)problema este (inca) complexa ,atunci procedura DIVIDE o imparte in doua subprobleme ,alegand pozitia m intre limitele li si ls ;pentru fiecare din cele doua subprobleme se reapeleaza recursiv procedura DIVIMP; in final ,la intoarcerile din apeluri se produce combinarea celor doua soluitii sol1 si sol2 prin apelul procedurii COMBINA.
Este evident ca nu orice problema poate fi rezolvata prin aceasta metoda, din cauza necesitatii descompunerii repetate in subprobleme. Eleganta si simplitatea rezolvarilor problemelor ( relativ putine la numar ) care se preteaza metodei, au facut insa ca aceasta tehnica de programare sa fie constant inclusa intre metodele de baza pentru rezolvarea problemelor in informatica, desi metoda are si dezavantaje ( legate de recursivitate ).
Aplicatii
Maximul unui sir
Se cere sa se gaseasca valoarea maxima dintr-un sir de numere reale. ( Aceasta problema admite o rezolvare clasica, dar in scop didactic, pentru simplitatea ei, apelam la metoda " DIVIDE ET IMPERA
Presupunem ca sirul are mai mult de doua numere, deci nu este o problema elementara ( care sa admita o rezolvare imediata ) si prin urmare suntem nevoiti sa spargem problema in doua subprobleme, impartind sirul dat in doua subsiruri. Se cauta valoarea maxima a fiecarui subsir dupa care se alege maximul dintre cele doua valori. Fie i,j, rangurile de inceput, respectiv de sfarsit ale unui subsir. Daca diferenta intre i si j este mai mare ca 1 ( subsirul are mai mult de doua elemente ) subproblema nu este inca elementara si se continua divizarea in subprobleme, in care noile ranguri sunt ( i, (i+j)/2 ), respectiv ( ( i + j )/2 + 1 , j ) unde, evident , ( i + j )/2 este rangul termenului din mijlocul sirului.
Daca diferenta dintre i si j este mai mica decat 2, problema este elementara si se rezolva imediat
Combinam apoi rezultatele partiale, retinand intotdeauna valoarea maxima dintre cele doua.
Acest algoritm transpus in C++ arata astfel :
# include < iostream.h >
float v[30];
int n;
float max ( int i, int j )
void main ( )
cout << " max = " << max ( 1 , n ) <<endl ; // ****
* autoapel recursiv pentru primul subsir
** autoapel recursiv pentru al doilea subsir
// *** combinarea solutiilor partiale
// **** apelul functiei max ( 1 , n ), care a rezolvat problema
Cel mai mare divizor comun al unui sir
Sa se determine cel mai mare divizor comun al unui sir de numere naturale prin metoda " DIVIDE ET IMPERA
Se pleaca de la functia elementara, recursiva, divcom, care returneaza cmmdc al numerelor naturale a si b :
Conform strategiei " DIVIDE ET IMPERA " , vom imparti sirul numerelor naturale pentru care dorim sa calculam c.m.m.d.c. in subsiruri carora le aplicam aceiasi strategie pana obtinem subsiruri elementare de unul sau doua numere ( cazul de baza ). Apoi, cu aceiasi functie calculam cmmdc al subsirurilor s.a.m.d. ( combinam solutiile partiale ).
Programul C++ este urmatorul :
int divcom ( int a , int b ) /* functia calculeaza cmmdc a doua
numere naturale */
int cmmdc ( int i , int j ) /* functia implementeaza strategia
" Divide & Impera " */
Cautarea binara
Se citeste un vector cu n componente intregi, ordonat crescator si o valoare intreaga x. Sa se decida daca numarul x se gaseste sau nu printre numerele citite. Daca da, sa se tipareasca indicele componentei vectorului care-l contine pe x ( problema cautarii binare, algoritm clasic ).
Presupunem ca numarul cautat, x, se gaseste printre componentele vectorului. Strategia " DIVIDE ET IMPERA " va diviza sirul dat, in mod repetat, in doua subsiruri avand limitele inferioare i, respectiv ( i + j )/2 , iar cele superioare ( i + j )/2 + 1, respectiv j. Exploatand faptul ca vectorul de numere este sortat, la fiecare pas va compara pe x cu numarul aflat la mijlocul sirului. Sunt posibile trei situatii :
a) Valoarea cautata este egala cu componenta din mijlocul sirului de numere sortate. In acest caz, problema este rezolvata ( cazul de baza )
b) Valoarea cautata este mai mica decat componenta din mijloc. Tinand cont ca sirul este sortat, daca, asa cum am presupus, x se gaseste in vector, el nu poate fi decat in subsirul din jumatatea stanga a sirului, de limite i respectiv ( i + j )/2 , iar cautarea in subsirul din dreapta va fi abandonata.
c) Valoarea cautata este mai mare decat componenta din mijloc. Rezulta ca x se gaseste in subsirul din jumatatea dreapta a a sirului, de limite ( i + j )/2 + 1, respectiv j iar cautarea in subsirul din jumatatea stanga a sirului va fi abandonata.
Repetand rationamentul, la fiecare comparatie cu valoarea din mijloc, domeniul de cautare se injumatateste, ceea ce face ca algoritmul sa fie extrem de eficient ( in cel mai defavorabil caz se executa un numar de log2(n) comparatii fata de n comparatii in situatia ca am aplica un algoritm elementar de comparare a lui x cu fiecare valoare din vector). Algoritmul se sfarseste cand fie am gasit pe x, fie limita inferioara, i, care tot creste, va depasi limita superioara, j, care tot scade. In acest ultim caz, valoarea cautata, x, nu se gaseste printre valorile sirului dat.
Implementarea in C++ este :
# include < iostream.h >
int n, v[30], x ;
void cauta( int i, int j )
void main ( )
cout << " x = " ; cin >> x ;
cauta ( 1 , n ) ; // apel pentru rezolvarea problemei
// * autoapel recursiv pentru subsirul din jumatatea stanga a sirului dat
// ** autoapel recursiv pentru subsirul din jumatatea dreapta a sirului dat
Interclasarea
Fiind dat un vector cu n componente, sa se sorteze crescator prin metoda interclasarii.
Reamintim ca interclasarea a doi vectori ( algoritm clasic, tratat la capitolul vectori, clasa a IX-a ) este o operatie prin care, cu elementele a doi vectori sortati ( crescator, de exemplu ), formam vectorul, sortat ( crescator ), avand toate elementele celor doi vectori.
Conform strategiei " Divide & Impera " , cream functia divimp care imparte repetat,recursiv, vectorul de sortat in subvectori pana se ajunge la cazul de baza ( vectori de cel mult doua componente, care admit sortare imediata )
Cazul de baza, sortarea unui vector elementar cu cel mult doua componente, este rezolvat prin functia sort.
Solutia finala se obtine prin combinarea solutiilor partiale, prin interclasare, de catre functia interc .
O varianta in C++ ar putea fi :
#include<iostream.h>
int a[10],n;
void sort(int p,int q,int a[10])
void interc (int p,int q, int m, int a[10])
else
if (i<=m)
for(j=i;j<=m;j++)
else
for(i=j;i<=q;i++)
k=1;
for(i=p;i<=q;i++)
void divimp(int p,int q, int a[10])
main()
divimp(1,n,a);
for(i=1;i<=n;i++)
cout<<a[i]<<' ';
OBSERVATII
mecanismul general de tip Divide et Impera se gaseste implementat in procedura "divi" ;
o astfel de abordare a problemei sortarii unii vector conduce la economie de timp de calcul ,deoarece operatia de interclasare a doi vectori deja ordonati este foarte rapida ,iar ordonarea independenta celor doua jumatati(mini- vectori) consuma in total aproximativ a doua parte din timpul care ar fi necesar ordonarii vectorului luat ca intreg .
Sortarea rapida
Sortarea rapida. Sa se sorteze crescator un vector de numere intregi ( sau reale ).
Este necesara o functie POZ care trateaza o portiune din vector, cuprinsa intre indicii dati de li (limita inferioara) si ls (limita superioara). Rolul acestei functii este de a pozitiona prima componenta a[li] pe o pozitie k cuprinsa intre li si ls, astfel incat toate componentele vectorului cuprinse intre li si k-1 sa fie mai mici sau egale decat a[k] si toate componentele vectorului cuprinse intre k+1 si ls sa fie mai mari sau egale decat a[k].
In aceasta functie exista doua moduri de lucru:
a) i ramane constant, j scade cu 1;
b) i creste cu 1, j ramane constant;
Functia este conceputa astfel:
initial, i va lua valoarea li, iar j va lua valoarea ls (elementul care initial se afla pe pozitia li se va gasi mereu pe o pozitie data de i sau de j);
se trece in modul de lucru a);
atat timp cat i<j, se executa:
daca a[i] este strict mai mare decat a[j], atunci se inverseaza cele doua numere si se schimba modul de lucru;
i si j se modifica corespunzator modului de lucru in care se afla programul;
k ia valoarea comuna a lui i si j.
Exemplu:
Pentru a=(6,9,3,1,2), li=1, ls=5; modul de lucru a):
i=1, j=5;
a[1]>a[5], deci se inverseaza elementele aflate pe pozitiile 1 si 5, deci a=(2,9,3,1,6) si programul trece la modul de lucru b);
i=2, j=5;
a[2]>a[5], deci a=(2,6,3,1,9) si se revine la modul de lucru a);
i=2, j=4;
a[2]>a[4], deci a=(2,1,3,6,9); se trece la modul de lucru b);
i=3, j=4;
functia se incheie, elemetul aflat initial pe pozitia 1 se gaseste acum pe potitia 4, toate elementele din stanga lui fiind mai mici decat el, totodata elementele din dreapta lui fiind mai mari decat el (k=4).
Alternanta modurilor de lucru se explica prin faptul ca elementul care trebuie pozitionat se compara cu un element aflat in dreapta sau in stanga lui, ceea ce impune o modificare corespunzatoare a indicilor i si j.
Dupa aplicare functiei POZ, este evident ca elementul care se afla initial in pozitia li va ajunge pe o pozitie k si va ramane pe acea pozitie in cadrul vectorului deja sortat, fapt care reprezinta esenta algoritmului.
Functia QUICK are parametrii li si ls (limita inferioara si limita superioara). In cadrul ei se utilizeaza metoda Divide et Impera, dupa cum urmeaza:
se apeleaza POZ;
se apeleaza QUICK pentru li si k-1;
se apeleaza QUICK pentru k+1 si ls;
Programul in C++ este urmatorul :
# include < iostream.h >
int v 30 , n, k ;
void poz ( int li , int ls , int & k, int v [30 ] ) /* k este parametru
variabil, valoarea sa e folosita in functia quick
if ( inv ) j
else i + +;
k = i ;
void quick ( int li , int ls )
void main ( )
void main ( )
Problema taieturilor
7. 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 ).
Coordonatele gaurilor sunt retinute in doi vectori vx[i] pentru abscisele gaurilor si vy[i] pentru ordonate ( acesti vectori nu sunt neaparat sortati, gaurile putand fi memorate in ordine cronologica, de exemplu ). Dreptunghiul initial si apoi dreptunghiurile care apar in procesul de taiere sunt memorate prin coordonatele coltului din stanga jos ( x, y ), prin lungime L si prin inaltime h ( fiecare dreptunghi se identifica printr-un set de 4 variabile : x, y, L, h, cu ajutorul carora se formeaza coordonatele celor 4 colturi ).
Pentru fiecare dreptunghi, incepand cu cel initial, cautam daca exista gaura ( existenta gaurii este semnalizata de variabila logica gasit ). Conditiile pentru ca o gaura sa se gaseasca intr-un dreptunghi dat de coordonate ( x, y, L, h ) sunt :
a) vx[i] > x
b) vx[i] < x+L
c) vy[i] > y
d) vy[i] < y+h
In situatia cand avem o gaura, vom face prin ea doua taieturi, una orizontala si alta verticala, ceea ce face ca dreptunghiul curent sa se divida in alte patru, deci problema admite o descompunere in alte patru de acelasi tip ( conform strategiei " DIVIDE ET IMPERA " ). Aria maxima se memoreaza prin coordonatele dreptunghiului de arie maxima ( xM, yM, LM, hM ). Daca nu avem gaura in dreptunghiul curent, acesta ar putea fi solutia problemei, deci aria acestuia se compara cu aria maxima retinuta pana la momentul respectiv si daca este cazul, se va retine ca arie maxima.
Consideram ca dreptunghiul initial ( bucata de tabla data ) are coltul din stanga jos in originea sistemului de coordonate ( x=0,y=0 ), lungimea L si inaltimea h.
O ilustrare a
dreptunghiului initial ( 0,
(vx[1],h) (L,h)
(0,h)
C D
(vx[1], vy[1] )
(0,vy[1]
(L,vy[1])
A B
(0,0)
(vx[1],0) (L,0)
Daca facem o taietura orizontala prin prima gaura considerata ( vx[1] , vy[1] ), vom obtine doua dreptunghiuri si anume :
a)
0,
b) 0, vy[1], L, h-vy[1] , dreptunghiul C+D
Daca facem o taietura verticala prin aceiasi gaura, vom obtine doua dreptunghiuri si anume :
c) 0, 0, vx[1], h , dreptunghiul A+C
d) vx[1], 0 , L-vx[1], h , dreptunghiul B+D
Un rationament similar se poate face pentru un dreptunghi oarecare, curent, obtinut in urma unui numar neprecizat de taieturi.
(vx[i],y+h) (x+L,y+h)
(x,y+h)
C D
(vx[i], vy[i] )
(x,vy[i] (x+L,vy[i])
A B
(x,y)
(vx[i],y) (x+L,y)
In acest caz, daca facem o taietura orizontala prin gaura de coordonate ( vx[i] , vy[i] ), vom obtine doua dreptunghiuri si anume :
a) x, y, L, vy[i]-y , dreptunghiul A+B
b) x, vy[i], L, y+h-vy[i] , dreptunghiul C+D ,iar dupa o taietura verticala, dreptunghiurile :
c) x, y, vx[i]-x, h , dreptunghiul A+C
d) vx[i], y , x+L-vx[i], h , dreptunghiul B+D
Cu notatiile de mai sus, programul in C++ arata astfel :
# include < iostream.h >
int L, h, i, n, xM, yM, LM, hM, vy[30] , vx[30] ;
void taiere ( int x, int y, int L, int h, int & xM, int & yM, int & LM,
int & hM ,int vx[30] ,int vy[30] ) //**
/* am apelat functia taiere ptr. dreptunghiurile A,B,C,
respectiv D, asa cum apar ele in desenul de mai sus */
else if ( L * h > LM * hM ) /* daca nu avem gaura,
dreptunghiul curent poate fi cel
cautat si trebuie vazut daca are arie maxima.
Daca da, coordonatele sale sunt atribuite solutiei
curente */
/* ** functia are urmatorii parametri :
a) x,y coordonatele coltului din stanga jos al dreptunghiului
b) L,h lungimea, respectiv inaltimea dreptunghiului
c) Parametrii variabili xM, yM, LM, hM, prin care se identifica dreptunghiul de arie maxima
d) vx si vy, cei doi vectori care memoreaza coordonatele gaurilor */
void main ( )
cout << " L= " ; cin >> L ; // citim dimensiunile tablei
cout << " h= " ; cin >> h ;
taiere ( 0,
care rezolva problema */
cout << " dreptunghiul de arie maxima are coordonatele : " <<endl ;
cout << " x = " << xM << ',' << " y = " << yM << endl ;
cout << " L = " << LM << ',' << " h = " << hM << endl ;
cout << " de arie A = " << LM * hM << endl ;
CONCLUZII :
Algoritmii de tip Divide et Impera au buna comportare in timp ,daca se indeplinesc urmatoarele conditii:
dimensiunile subprogramelor(in care se imparte problema initiala )sunt aproximativ egale("principiul balansarii");
lipsesc fazele de combinare a solutiilor subproblemelor(cautare binara).
Bibliografie:
Tudor Sorin, Vlad Huntanu
MANUAL DE INFORMATICA INTENSIV CLS a-XI-a,
Editura L&S Soft;
MANUAL DE INFORMATICA PENTRU CLS.a-X a,
Editura Niculescu ;
Radu Visinescu,
BAZELE PROGRAMARII ,
Editura Petrion ;
Cristian Udrea,
TEORIE SI APLICATII,
Editura Arves ;
|
