DIVIDE & IMPERA
Metoda Divide et Impera (Imparte şi Stăpâneste) 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. Procesul se reia până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condiţiile de terminare).
Un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilităţi:
- s-a ajuns la o problemă care admite o rezolvare imediată (condiţia de terminare), caz în care se rezolvă şi se revine din apel;
- nu s-a ajuns în situaţia de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmând un apel recursiv al funcţiei, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
Aceasta metodă (tehnică) se poate implementa atât iterativ cât şi recursiv. Dat fiind că problemele se împart în subprobleme în mod recursiv, de obicei împărţirea se realizează până când şirul obţinut este de lungime 1, caz în care rezolvarea subproblemei este foarte uşoară.
De exemplu, fie un vector X=[x1, x2, x3, …xi … xp… xj, …xn] asupra căruia se aplică o prelucrare. Pentru orice secvenţă din vector delimitată de indecşii i si j, i<j există o valoare p, astfel încât prin prelucrarea secvenţelor :
xi, xi+1, xi+2, xi+3, …xp si xp+1, xp+2, xp+3, …xj
se obţin soluţiile corespunzatoare celor două subşiruri care, prin compunere, conduc la obţinerea soluţiei prelucrării secvenţei:
xi, xi+1, xi+2, xi+3, …xj
Fiind un caz particular de recursivitate, metoda “Divide et Impera” poate sa fie mare consumatoare de resurse de calculator, în special timp.
Sa luăm exemplul găsirii maximului dintr-un vector oarecare (cazul vectorului ordonat va fi abordat în capitoul “Căutare Binară”).
Fie vectorul v[] de mai jos, cu 32 de elemente:
43 12 35 25 44 81 98 26 77 52 49 38 56 71 59 42 85 23 43 77 76 27 36 43 53 61 85 90 42 30 15 32Maximul este, aşa cum este uşor de observat, 98.
Metoda iterativă are comllexitatea O[n], fiind necesară străbaterea completă a vectoului, deci 32 de calcule.
Pentru varianta recursivă, împărţim vectorul în doi subvectori:
43 12 35 25 44 81 98 26 77 52 49 38 56 71 59 4285 23 43 77 76 27 36 43 53 61 85 90 42 30 15 32
şi calculăm două maxime, m1 şi m2, câte unul pentru fiecare dintre cei doi subvectori (în acest caz, m1 = 98 şi m2 = 90), iar maximul pentru tot vectorul va fi cea mai mare dintre cele două valori (in acest caz, 98).
Dar, pentru fiecare dintre cei doi vectori, aplicăm aceeaşi tactică: primul subvector se împarte în
43 12 35 25 44 81 98 2677 52 49 38 56 71 59 42
iar cel de-al doilea în
85 23 43 77 76 27 36 43
53 61 85 90 42 30 15 32
şi continuăm în acest fel până când obţinem vectori de unu sau două elemente, pentru care maximul se obţine direct. Deci … recursivitate.
Pentru compararea complexităţii am introdus o variabilă contor – nrapel – pentru a număra de câte ori am apelat funcţia recursivă max().
Programul ar putea arăta aşa:
Rulând acest program, se obţin rezultatele:
O variantă online poate fi experimentată la 
sau la maxDiv
EXEMPLE DE PROBLEME REZOLVATE PRIN METODA DIVIDE & IMPERA
A. Merge Sort (sortare prin interclasare)
-
se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie ordonată la un moment dat şi interclasată cu o altă secvenţă corespunzătoare din vector .
-
practic, interclasarea va începe când se ajunge la o secvenţă formată din două elemente. Aceasta, odată ordonată, se va interclasa cu o alta corespunzătoare(cu 2 elemente). Cele două secvenţe vor alcătui un subşir ordonat din vector mai mare(cu 4 elemente) care, la rândul lui, se va interclasa cu un subşir corespunzător(cu 4 elemente) ş.a.m.d.
7
38 27 43 3 9 82 10
30
17 34 22 11 6 56 23 68 54 2 87 54 25 20 3 66 89 4 44 21 53 12 44 73 15 80 61 62 59 38
O variantă on-line poate fi experimentată la 
sau la mergeSort
B. Quick Sort
Quicksort este un celebru algoritm de sortare, dezvoltat de C. A. R. Hoare și care, în medie, efectuează 
comparații pentru a sorta n elemente. În cazul cel mai defavorabil, se efectuează 
comparații. De obicei, în practică, quicksort este mai rapid decât ceilalți algoritmi de sortare de complexitate 
, deoarece bucla sa interioară are implementări eficiente pe majoritatea arhitecturilor și, în plus, în majoritatea implementărilor practice se pot lua, la proiectare, decizii ce ajută la evitarea cazului când complexitatea algoritmului este de 
.
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ă.
30
17 34 22 11 6 56 23 68 54 2 87 54 25 20 3 66 89 4 44 21 53 12 44 73 15 80 61 62 59 38
O variantă on-line poate fi experimentată la 
sau la divImpQuikSort
C. Problema tăieturilor (problema grădinii japoneze)
O frumoasă descriere a problemei grădinii japoneze este prezentată in clipul de mai jos de pe YouTube (click pe foto!)
3
3 12
6 7
12 9
15 15
O variantă on-line poate fi experimentată la 
sau la gradinaJaponeza
http://tpcg.io/dTRk6D
D. Determinarea rădăcinilor unei ecuaţii
O varianta online poate fi experimentata la 
si la divImpRadac
STUDIU DE CAZ
GRAFICA
Până acum, ne-am ocupat mai mult de găsirea unui algoritm pentru a rezolva problemele pe care ni le-am propus (sau pe care ni le-au propus alţii …), fără a ne preocupa, în majoritatea cazurilor, de eficienţa acestor algoritmi. Situaţia este normală, la început, căci, pentru a îmbunătăţi un lucru, trebuie să ai ce îmbunătăţi!
În aplicaţiile reale, se pune adesea problema “ameliorării” soluţiilor găsite. Fără a încerca o abordare exhaustivă, să discutăm un caz concret:
A. Fractali
B. Turnurile din Hanoi
Unul dintre jocurile aparent simple, dar cu un adânc substrat matematic, este binecunoscutul Turn din Hanoi. Acest joc a fost inventat de matematicianul francez Edouard Lucas şi a fost comercializat ca jucărie pentru toate vârstele încă din anul 1883. La început era confecţionat din lemn şi consta în câteva discuri de mărimi diferite şi 3 beţişoare. Provocarea este de a muta turnul format din discuri de pe un beţişor pe alt beţişor liber, urmând două reguli simple: la fiecare mutare se mută un singur disc şi niciodată nu se aşază un disc mai mare peste un disc mai mic. Bineînţeles, scopul este acela de a realiza mutarea turnului folosind cât mai puţine mutări .
Se spune că acest joc este inspirat de legenda Turnului lui Brahma, aflat într-un templu al oraşului indian Benares. Acest turn este format din 64 de discuri de aur, de a căror mutare se ocupă preoţii templului, respectând regulile de mai sus. Legenda spune că atunci când turnul discurilor de aur va fi complet transferat pe o altă tijă, templul se va prăbuşi iar lumea va lua sfârşit. Ceea ce ne face să ne întrebăm cu îngrijorare care este numărul minim de mutări în cazul turnului cu 64 de discuri… Conform calculelor , durata minima de rezolvare a acestui puzzle este de 584 942 417 355 de ani.
O frumoasă descriere a problemei turnurilor din Hanoi este prezentată in clipul de mai jos
posibilitatea 1
Posibilitatea 3
Initial
O situatie intermediara
Final
