1. Metoda Divide et Impera Prezentarea metodei Implementri sugerate Probleme propuse Soluiile problemelor Capitolul 4 4.1. Prezentarea metodei Divide et Impera (mparte i Stpnete) este o metod de programare care se aplic problemelor care pot fi descompuse n subprobleme independente, similare problemei iniiale, de dimensiuni mai mici i care pot fi rezolvate foarte uor. Metoda presupune: Descompunerea problemei iniiale n subprobleme independente; Rezolvarea subproblemelor; Construirea rezultatului prin compunerea soluiilor problemelor de dimensiuni mici. Aceast metod se poate implementa att iterativ ct i recursiv. Datorit faptului c problemele se mpart n subprobleme n mod recursiv, de obicei mprirea se reali- zeaz pn cnd irul obinut prin mprire este de lungime 1, caz n care rezolvarea subproblemei este foarte uoar, chiar banal. Fie un vector X = (x1, x2, , xn) asupra cruia se aplic o prelucrare. Pentru orice i, j {1, 2, , n} astfel nct i < j, exist o valoare p, astfel nct prin prelucrarea sec- venelor {xi, xi+1, , xp} i {xp+1, xp+2, , xj} se obin soluiile corespunztoare subi- rurilor care prin combinare conduc la soluia prelucrrii secvenei {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) sfrit subalgoritm

2. 4. Metoda Divide et Impera 103 3.2. Implementri sugerate 1. recapitularea algoritmului cutrii binare i realizarea implementrii recursive; 2. calcularea produsului a n numere cu metoda Divide et Impera; 3. determinarea celui mai mare (celui mai mic) numr ntr-un ir dat cu metoda Divi- de et Impera; 4. plierea unui vector (Se consider un vector de lungime n. Definim plierea vectoru- lui prin suprapunerea unei jumti, numite donatoare peste cealalt jumtate, nu- mit receptoare. Dac numrul de elemente este impar, elementul din mijloc este eliminat. n acest mod se ajunge la un subir ale crui elemente au numerotarea corespunztoare jumtii receptoare. a) Fiind dat un indice i, s se determine dac al i-lea element poate fi element final ca rezultat al unor plieri succesive. b) S se precizeze toate elementele finale posibile. c) Fiind dat un element i final, s se de- termine o succesiune de plieri prin care se ajunge la el); 5. sortare prin interclasare (merge-sort); 6. sortare rapid (quick-sort); 7. determinarea minimului dintr-un ir, precum i a indicelelui uneia dintre valorile minime; 8. verificarea dac un ir de numere este ordonat cresctor; 9. determinarea celui mai mare divizor comun al elementelor unui ir; 10. determinarea celui mai mare numr par dintr-un ir dat; 11. nmulirea a dou polinoame folosind metoda Divide et Impera; 12. calcularea valorii unui polinom ntr-un punct dat; 13. Raftul de cri. Fie n cri de matematic, fizic, literatur i informatic (avnd ca simboluri M, F, L, i I) aezate pe raftul A ntr-o ordine oarecare. Exist, de asemenea, dou rafturi B i X la dispoziie. S se transfere crile pe rafturile LF, LMI, LL dup urmtoarele reguli: pe rafturile A i B se pot pune sau lua oricte cri; pe raftul X se poate pune sau lua o singur carte; pe rafturile LF, LMI, LL se pot pune cri i nu se pot lua; la orice mutare avem acces la o singur carte, i anume la cea din vrful teancu- lui de pe raftul A; tipul crii se poate citi numai pe raftul B i numai cnd aici se afl o singur carte; n final crile de pe rafturile LF, LMI, LL trebuie s fie n aceeai ordine n care erau pe raftul A. 14. Produsul a dou matrice. Produsul a dou matrice presupune un numr mare de operaii (n3 nmuliri i n2 (n 1) adunri, astfel nct complexitatea algoritmului clasic de nmulire este O(n3 ). Folosind metoda Divide et Impera se reduce complexitatea, dac se folosete urmtoarea formul: 3. 104 4. Metoda Divide et Impera = 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC , unde: C11 = A11 B11 + A12 B21, C12 = A11 B12 + A12 B22, C21 = A21 B11 + A22 B21, C22 = A21 B12 + A22 B22. Se obine astfel matricea rezultat n urma nmulirii a 8 matrice de ordin n/2. 4.3. Probleme propuse 4.3.1. Minim Determinai valoarea minim dintr-un ir de numere, folosind metoda Divide et Impera. Date de intrare Prima linie a fiierului de intrare MINIM.IN va conine un numr ntreg n, care repre- zint numrul de elemente din ir. Pe urmtoarea linie se afl n numere ntregi, separa- te prin cte un spaiu, reprezentnd valorile elementelor din ir. Date de ieire Fiierul de ieire MINIM.OUT va conine o linie pe care se va afla valoarea minim ca- re a fost gsit n ir. Restricii i precizri 1 n 10000; Valorile din ir sunt numere ntregi mai mici dect 30000. Exemplu MINIM.IN 7 720 212 10 13 150 15 17 MINIM.OUT 10 4.3.2. Produsul numerelor prin metoda Divide et Impera Calculai produsul a n numere folosind metoda Divide et Impera. Date de intrare Prima linie a fiierului de intrare PRODUS.IN va conine un numr ntreg n, care repre- zint numrul de elemente din ir. Pe urmtoarea linie se afl, separate prin spaii, n numere reale, reprezentnd valorile numerice ale elementelor din ir. 4. 4. Metoda Divide et Impera 105 Date de ieire Fiierul de ieire PRODUS.OUT va conine o linie pe care se va afla numrul real, cu dou zecimale exacte, reprezentnd produsul elementelor. Restricii i precizri 1 n 100. Exemplu PRODUS.IN 7 10 0.1 100 2 0.1 3 0.1 PRODUS.OUT 6.00 4.3.3. Turnurile din Hanoi Se dau trei tije verticale A, B i C. Pe tija A se gsesc discuri de diametre diferite, per- forate la mijloc, aranjate n ordine descresctoare a diametrelor discurilor, de la baz spre vrf. Celelalte tije sunt goale. Se cere s se gseasc o strategie de mutare a discurilor de pe tija A pe tija B res- pectnd urmtoarele reguli: La un moment dat se va muta un singur disc (cel care se afl deasupra celorlalte discuri pe o tij). Un disc poate fi aezat doar peste un alt disc avnd diametru mai mare dect al su, sau pe o tij goal. Date de intrare Fiierului de intrare HANOI.IN conine un singur numr natural n, care reprezint nu- mrul de discuri existente pe tija A. Date de ieire Fiierul de ieire HANOI.OUT va conine pe fiecare linie dou litere separate de un spa- iu. Aceste litere reprezint mutarea care se realizeaz la un moment dat, i anume pri- ma liter reprezint tija de pe care se ia discul, iar a doua liter reprezint tija pe care se aeaz discul respectiv. Restricii i precizri 0 < n 10. A B C 5. 106 4. Metoda Divide et Impera Exemplu HANOI.IN 3 HANOI.OUT A -> B A -> C B -> C A -> B C -> A C -> B A -> B 4.3.4. Sortare prin interclasare (merge-sort) Implementai metoda sortrii prin interclasare pentru un ir de numere dat. Date de intrare Fiierului de intrare MERGE.IN conine pe prima linie un numr natural n, care repre- zint numrul de elemente ale irului. Pe a doua linie, separate prin cte un spaiu, se afl cele n numere din ir. Date de ieire Fiierul de ieire MERGE.OUT va conine numerele din irul dat (separate prin cte un spaiu) n ordine cresctoare. Restricii i precizri 0 n 10000; Numerele sunt ntregi. Exemplu MERGE.IN 8 23 8 7 17 90 3 17 29 MERGE.OUT 3 7 8 17 17 23 29 90 4.3.5. Sortare rapid (quick-sort) Implementai metoda sortrii rapide pentru un ir de numere dat. Date de intrare Fiierul de intrare QUICK.IN conine pe prima linie numrul n al elementelor irului. Pe a doua linie se afl cele n numere din ir, separate prin cte un spaiu. Date de ieire Fiierul de ieire QUICK.OUT va conine numerele din ir n ordine cresctoare, sepa- rate de cte un spaiu. 6. 4. Metoda Divide et Impera 107 Restricii i precizri 0 n 10000; Numerele sunt ntregi. Exemplu QUICK.IN 9 8 5 4 10 12 6 3 9 7 QUICK.OUT 3 4 5 6 7 8 9 10 12 4.3.6. Serbare Pentru serbarea colii profesorul de dans a adus un costum de urs polar care poate fi mbrcat doar de un copil care are nlimea adecvat. El ncearc s gseasc elevul potrivit pentru a purta costumul. Profesorul, observnd c nu exist doi elevi cu ace- eai nlime, cere elevilor s se aeze n ordinea cresctoare a nlimii lor. Sper ast- fel ca s gseasc mai uor elevul potrivit. Cunoscnd numrul elevilor, precum i nlimile lor n ordine cresctoare, scriei un program care s determine dac exist un elev cu nlimea cerut i care este locul lui n irul elevilor. Dac nu exist un astfel de elev, determinai locul elevului care are cea mai mic nlime i este mai nalt dect nlimea cerut adic locul pe care ar sta un elev cu nlimea potrivit. Date de intrare Prima linie a fiierului de intrare SERBARE.IN va conine dou numere ntregi poziti- ve: nlimea cutat h n centimetri i numrul de elevi n. Aceste numere vor fi sepa- rate printr-un spaiu. Pe urmtoarea linie se afl n numere ntregi, separate prin cte un spaiu, n ordine strict cresctoare, reprezentnd nlimea elevilor n centimetri. Date de ieire Fiierul de ieire SERBARE.OUT va conine o linie pe care se va afla rspunsul 'NU', dac nu exist un elev de nlime potrivit, sau 'DA' dac acesta exist. Pe urmtoa- rea linie se va scrie poziia elevului n irul ordonat fie c este cel gsit, fie c este a elevului imediat mai mare. Restricii i precizri 60 h 200; 1 n 1000. Exemple SERBARE.IN 150 7 110 112 140 137 150 151 167 SERBARE.OUT DA 5 7. 108 4. Metoda Divide et Impera SERBARE.IN 131 9 110 112 120 137 153 151 155 158 167 SERBARE.OUT NU 4 4.3.7. Joc Ghicirea numrului ascuns Deseori o persoan cere alteia s ghiceasc un numr. Dup prima ncercare se poate ca cel care a ascuns numrul s zic este prea mare, sau este prea mic, sau chiar felicitri ai ghicit. Se cere s se scrie un program care simuleaz acest joc, i anume o bibliotec ex- tern genereaz numrul ascuns i programul l ajut pe cel care ncearc s ghiceasc numrul. La sfrit s se afieze numrul de pai n care s-a gsit numrul ascuns. Descrierea bibliotecii Pentru a utiliza biblioteca extern, n program va trebui s includei instruciunea uses nr; (pentru limbajul Pascal), respectiv #include "nr.h". Biblioteca v pune la dispoziie rutine pentru: iniializare ghicirea numrului Antetele funciilor i procedurilor: procedure Init; void Init(void); Acesta este folosit pentru iniializarea bibliotecii. function Incercare(nr:Integer):Integer; int Incercare(int nr); Aceasta se folosete pentru a testa nr. Dac s-a returnat 1, nseamn c nr este prea mare, 2 nseamn c nr este prea mic, 0 nseamn c s-a ghicit numrul ascuns. 4.3.8. Patinoarul Un patinoar de form dreptunghiular prezint defecte ale gheii datorit temperaturi- lor ridicate, dar i a antrenamentelor numeroase. Proprietarii doresc s evite accidente- le prin delimitarea unei zone fr probleme pentru patinatori, astfel nct s acopere o suprafa ct mai mare din cea iniial. Laturile zonei ngrdite pot fi realizate doar prin garduri paralele cu marginile patinoarului. Se cunosc coordonatele n plan ale patinoarului, precum i ale zonelor care pot pro- voca accidente, considerate punctiforme. Suntei rugai s ajutai proprietarii s deter- mine coordonatele unei zone dreptunghiulare de arie maxim care nu prezint nici un risc, precum i aria acestei zone. 8. 4. Metoda Divide et Impera 109 Date de intrare Prima linie a fiierului de intrare PATINA.IN va conine coordonatele patinoarului (ordonata i abscisa colului stnga-sus, respectiv dreapta-jos), separate prin cte un spaiu. Pe urmtoarea linie se afl numrul n a punctelor cu probleme de pe suprafaa patinoarului. Pe urmtoarele n linii se afl cte dou numere ntregi, separate de un spaiu, reprezentnd coordonatele punctelor nesigure din zon. Date de ieire Fiierul de ieire PATINA.OUT va conine o linie pe care se vor afla cinci numere, re- prezentnd aria i coordonatele (ordonata i abscisa) colului stnga-sus, respectiv col- ului dreapta-jos a zonei sigure. Aceste numere vor fi separate printr-un spaiu. Restricii i precizri Coordonatele sunt numere naturale; 0 n 200; Dac exist mai multe soluii, n fiier se va scrie una singur; Zonele cu probleme se consider punctiforme i pot fi pe marginea mprejmuirii. Exemplu PATINA.IN 0 0 10 10 3 3 5 3 8 6 6 PATINA.OUT 42 3 0 10 6 (0,0) (10,10) (3,0) (3,8) (3,5) (6,6) (10,6) 4.3.9. Ora de sport Profesorul de sport dorete s aleag un elev care s conduc un grup dintr-o clas de n elevi la nclzirea de la ora de sport. Deoarece el ar vrea ca la fiecare or, n princi- piu, s fie alt elev care are acest rol, la nceputul orei i aranjeaz pe elevi la ntmplare i le mparte tricouri numerotate de la 1 la n. Apoi d comenzi una dup alta, rostind cuvintele stnga sau dreapta, urmnd ca dup fiecare comand jumtatea opus comenzii date din irul de elevi s plece spre zona de nclzire, iar dintre cei rmai s aleag mai departe. Dac numrul grupului de elevi mprit la un moment dat este impar, elevul din mijloc pleac i el la nclzire. Alegerea se repet pn cnd rmne un singur elev pe care profesorul l numete conductor pentru ziua respectiv. ntr-o zi profesorul se ntreab oare ci elevi au ansa s devin conductori i care ar fi acetia? Dar el ar vrea s mai tie i dac un elev purtnd un tricou cu un anumit 9. 110 4. Metoda Divide et Impera numr poate sau nu deveni conductor i, n caz afirmativ, ce comenzi trebuie s spu- n pentru ca acesta s ajung conductor? Scriei un program care determin elevii care pot fi conductori, cunoscnd num- rul total al elevilor din clas. Apoi, pe baza numrului de pe tricoul unui elev dat, sta- bilii dac acesta poate fi n ziua respectiv conductor sau nu. n caz afirmativ, deter- minai o succesiune de comenzi stnga-dreapta n urma crora el devine conductor. Date de intrare Fiierul de intrare SPORT.IN conine dou numere naturale n i t, separate printr-un spaiu, reprezentnd numrul de elevi din clas, respectiv numrul de ordine de pe tri- coul unui elev. Date de ieire Fiierul de ieire SPORT.OUT va conine pe prima linie numerele de pe tricourile ele- vilor care pot deveni conductori, separate prin cte un spaiu. Pe a doua linie se va afla cuvntul 'DA' sau cuvntul 'NU', dup cum elevul cu numrul t pe tricou poate s fie conductor sau nu. n caz afirmativ, pe a treia linie vei scrie un ir de caractere format din literele mici 's' i 'd' care reprezint succesiunea de comenzi necesar. Dac pe al doilea rnd ai scris 'NU', n fiier nu se mai scrie nimic. Restricii i precizri 0 < n 10000: 0 < t n. Exemple SPORT.IN 7 3 SPORT.IN 7 4 SPORT.OUT 1 3 5 7 DA sd SPORT.OUT 1 3 5 7 NU 4.4. Soluiile problemelor propuse 4.4.1. Minim Din enunul problemei se deduce clar care sunt cerinele i cum trebuie determinat soluia. Dac nu s-ar fi specificat metoda de rezolvare, probabil c o parcurgere a iru- lui de la primul element la ultimul, cu determinarea minimului local ar fi fost o soluie care nu ridica nici un fel de probleme. Dar metoda este impus, i anume Divide et Impera. 10. 4. Metoda Divide et Impera 111 Metoda presupune mprirea problemei n subprobleme care se rezolv, iar apoi rezultatele subproblemelor se combin i se obine soluia problemei date. n cazul determinrii minimului dintr-un ir de numere, descompunerea problemei revine la a mpri irul n dou subiruri. De exemplu, dac avem irul (x1, x2, , xn) el poate fi mprit n subirul (x1, , xm) i n (xm+1, , xn), unde n este numrul de elemente din ir, iar m = [(1 + n) / 2] este indicele elementului din mijloc. Dup deter- minarea minimului pentru fiecare dintre cele dou subiruri (min1 respectiv min2), combinarea rezultatelor se realizeaz prin compararea valorilor celor dou minimuri (min1 < min2). n funcie de rezultat se obine rezultatul final al valorii minime din ir, i anume dac min1 este mai mic dect min2, vom avea min = min1, respectiv min = min2, dac min1 este mai mare sau egal cu min2. Rezultatul obinut este corect, deoarece, dac min1 este valoarea minim dintre ele- mentele irului (x1, , xm), nseamn c orice alt valoare din acest ir este mai mare sau egal cu min1. Analog se poate raiona pentru min2 i irul (xm+1, , xn). Atunci, dac min1 < min2, acest lucru implic min1 < xj, pentru j {m+1, , n}, n plus prin rezolvarea subproblemelor, min1 este determinat ca fiind mai mic sau egal dect ele- mentele xk, unde k {1, , m}. Deci min1 conine valoarea minim din ntreg irul. Analog, dac rezultatul comparaiei min1 < min2 este fals, se obine c min2 conine va- loarea minim din ntreg irul. Dar determinarea lui min1 pentru primul subir, respectiv a lui min2 pentru al doilea subir este o problem de rezolvat la fel ca problema iniial pentru ntreg irul. Se va mpri subirul {x1, , xm} n alte dou subiruri i, la rndul lor, cele dou subiruri n altele, pn cnd subirul care se obine este de dimensiune 1, adic are un singur element, care este valoarea minim din acest subir de lungime 1. Subalgoritm Minim(st,dr): dac st < dr atunci mij (st+dr) div 2 { se determin indicele elementului din mijloc } min1 Minim(st,mij) min2 Minim(mij+1,dr) dac min1 < min2 atunci minim min1 altfel Minim min2 sfrit dac altfel Minim x[st] { dac st=dr atunci minimul este singurul element din ir } sfrit dac sfrit subalgoritm 11. 112 4. Metoda Divide et Impera 4.4.2. Produsul numerelor prin metoda Divide et Impera Din enunul problemei se deduce clar care sunt cerinele i cum trebuie determinat soluia. Dac nu s-ar fi specificat metoda de rezolvare, o parcurgere a irului de la pri- mul element la ultimul ar fi fost o soluie care nu ridic nici un fel de probleme, dar trebuie s lucrm cu metoda Divide et Impera. Metoda presupune mprirea problemei n subprobleme care se rezolv, apoi re- zultatele subproblemelor se combin i se obine soluia. Pentru a calcula produsul a n numere, se calculeaz produsul numerelor din prima jumtate a irului, produsul numerelor din a doua jumtate i apoi rezultatul final se obine prin nmulirea celor dou produse calculate. De exemplu, irul (x1, x2, , xn) poate fi mprit n subirurile (x1, , xm) i (xm+1, , xn), unde n este numrul de elemente din ir, iar m = [(1 + n) / 2]. Calculul produsului numerelor din prima jumtate se poate realiza de asemenea fo- losind metoda Divide et Impera i astfel primul subir se mparte n dou subiruri, i aa mai departe pn cnd, prin mprirea n subiruri, se obin iruri de lungime 1. Aceste subiruri conin un singur element i n acest caz produsul numerelor este egal cu numrul respectiv. Subalgoritm Produs(st,dr): dac st=dr atunci Produs x[st] altfel m (st+dr) div 2 { se determin indicele elementului din mijloc } p1 Produs(st,mij) p2 Produs(mij+1,dr) Produs p1 * p2 sfrit dac sfrit subalgoritm 4.4.3. Turnurile din Hanoi 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 ne- cesar ar fi A B. Pentru dou discuri existente pe tija A, mutrile ar fi: A C, A B i C B. Pentru un numr mai mare de discuri, evident va fi un numr mult mai mare de mutri. mprim 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. 12. 4. Metoda Divide et Impera 113 Acum au aprut 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 rndul lor, aceste operaii se pot mpri n subprobleme pn cnd rmne de mutat un singur disc. Astfel, problema se rezolv folosind metoda Divide et Impera. La un transfer al unui disc acesta este n vrful tijei i este aezat tot n vrful unei tije, astfel c o mutare este definit prin numele tijelor de pe care se ia un disc, respec- tiv cea pe care se aeaz. Pentru a asigura precizarea lor pentru fiecare subproblem care trebuie rezolvat, vom folosi trei parametri (pentru tija surs, tija destinaie i tija auxiliar) care vor primi valori n momentul autoapelrii subalgoritmului. Subalgoritm Hanoi(n,A,B,C): dac n=1 Mut un disc de pe tija A pe tija B Hanoi(n-1,A,C,B) Mut un disc de pe tija A pe tija B Hanoi(n-1,C,B,A) sfrit dac sfrit subalgoritm Combinarea soluiilor subproblemelor nu este necesar n cazul rezolvrii acestei probleme. 4.4.4. Sortare prin interclasare (merge-sort) Un ir de valori poate fi ordonat cu diverse metode (n celebra carte a lui D. Knuth, Arta programrii calculatoarelor sunt prezentate peste 30 de metode de ordonare). A B C n-1 A B C n-1 A B C n-1 13. 114 4. Metoda Divide et Impera De data aceasta se cere explicit s se rezolve aceast problem cu metoda de sorta- re prin interclasare. Metoda presupune mprirea irului n subiruri ordonate i apoi interclasarea lor, obinndu-se astfel un ir ordonat. Prima etap, i anume mprirea irului n ubiruri ordonate, ncepe prin mpri- rea irului iniial n dou subiruri (cu atenie, astfel nct elementul din mijloc s nu apar n ambele). Este foarte posibil ca cele dou subiruri obinute s nu fie ordonate, dar la rndul lor i acestea vor fi mprite n dou subiruri i aa mai departe. Subi- rurile se vor mpri pn cnd subirul obinut are un singur element, i acesta este sigur ordonat. Urmeaz etapa a doua n care interclasm subirurile. O astfel de rezolvare se ncadreaz n metoda Divide et Impera. mprirea proble- mei n subprobleme este realizat prin divizarea unui ir n subiruri, iar combinarea rezultatelor pariale se realizeaz prin interclasarea celor dou subiruri ordonate. Astfel, la un pas al prelucrrii vom avea subirul (xst, , xdr) care se va mpri n dou subiruri (xst, , xm) i (xm+1, , xdr), unde m = [(st + dr) / 2 ]. Aceste subiruri se ordoneaz, apoi urmeaz interclasarea lor pentru a obine subirul iniial cu elemen- tele n ordinea cerut. Subalgoritm Ordonare(st,dr): dac st = dr atunci ieire forat din subalgoritm { subirul conine un singur element } altfel m (st+dr) div 2 Apel prelucrare pentru irul de indici st, m Apel prelucrare pentru irul de indici m+1, dr Interclasare(st,m,dr) { interclasarea irurilor (xst, , xm) i (xm+1, , xdr) } sfrit dac sfrit subalgoritm Interclasarea a dou iruri ordonate nseamn crearea unui nou ir care conine ele- mentele primelor dou i, n plus, acest nou ir este de asemenea ordonat dup acelai criteriu ca irurile iniiale. Trebuie menionat c cele dou iruri iniiale trebuie s fie ordonate dup acelai criteriu, de exemplu ambele s fie ordonate cresctor. Exemplu Fie dou iruri ordonate: a = (1, 3, 5, 17, 21) i b = (3, 3, 8, 11, 23, 27). Prin inter- clasarea lor se obine irul ordonat c = (1, 3, 3, 3, 5, 11, 17, 21, 23, 27). Pentru cele dou subiruri (xst, , xm) i (xm+1, , xdr) care sunt ordonate cresctor, interclasarea presupune parcurgerea lor relativ simultan cu ajutorul a doi indici i tre- cerea n al treilea ir a elementului minim dintre cele dou elemente comparate la un moment dat. 14. 4. Metoda Divide et Impera 115 Reamintim subalgoritmul de interclasare, sub forma clasic, actualizat pentru ordo- nare prin interclasare prezint cteva modificri. Acum toate elementele fac parte din acelai ir x. n cadrul algoritmului clasic se consuma pe rnd cte un element din ce- le dou iruri i se trecea n al treilea ir cel care coninea irurile interclasate. Acum al treilea ir trebuie s fie unul auxiliar, altfel s-ar suprascrie valori din irul iniial. La sfritul subalgoritmului vom copia n x (de fapt n subirul (xst, , xdr) valorile din irul auxiliar. Subalgoritm Interclasare(st,m,dr): i st j m + 1 k 0 ct timp (i m) i (j dr) execut: dac xi < xj atunci { dac xi (i m) este mai mic dect xj (j dr) } k k + 1 { l copiem n irul auxiliar a pe poziia curent k } ak xi i i + 1 { avansm n subirul din stnga } altfel { dac xj (j dr) este mai mic sau egal cu xi (i m) } k k + 1 { l copiem n irul auxiliar a pe poziia curent k } ak xj j j + 1 { avansm n subirul din dreapta } sfrit dac sfrit ct timp ct timp i m execut: { dac n subirul din stnga mai exist elemente } k k + 1 { le copiem n a } ak xi i i + 1 sfrit ct timp ct timp j dr execut: { dac n subirul din dreapta mai exist elemente } k k + 1 { le copiem n a } ak xj j j + 1 sfrit ct timp pentru i=1,k execut: { n irul a avem k = dr st + 1 elemente care trebuie copiate n xst, ..., xdr } xst+i-1 ai sfrit subalgoritm 4.4.5. Sortare rapid (quicksort) Problema ordonrii unui ir poate fi soluionat prin diverse metode de ordonare. Acum se cere explicit rezolvarea cu ajutorul metodei de sortare rapid. 15. 116 4. Metoda Divide et Impera Exemplu Fie urmtorul ir de numere: 8, 7, 6, 10, 4, 11, 2, 5, 9. Ne propunem s-l ordonm cresctor. Primul element se compar cu toate celelalte din ir. Ordonarea pornete prin com- pararea primului element cu ultimul din ir. 8, 7, 6, 10, 4, 11, 2, 5, 9 Aceste dou elemente sunt n ordinea cerut. n aceast situaie se trece la compa- rarea primului numr cu penultimul. 8, 7, 6, 10, 4, 11, 2, 5, 9 Cele dou elemente nu sunt n ordinea cerut, deci vor fi interschimbate i se obi- ne irul: 5, 7, 6, 10, 4, 11, 2, 8, 9 Deoarece a avut loc o interschimbare, se va continua compararea lui 8 (aflat acum pe penultima poziie) cu numrul 7 (al doilea, situat dup elementul care la pasul ante- rior a participat la interschimbare), i avnd n vedere c 7 este pe o poziie anterioar lui 8 n ir i este adevrat relaia 7 < 8 cele dou numere rmn neschimbate. 5, 7, 6, 10, 4, 11, 2, 8, 9 Din aceleai considerente i numerele 6 i 8 rmn n locaiile lor dup comparare. 5, 7, 6, 10, 4, 11, 2, 8, 9 Urmeaz s se compare 10 cu 8 i, datorit faptului c nu sunt n relaia de ordine cerut, (adic n ordine cresctoare) cele dou valori se interschimb. 5, 7, 6, 10, 4, 11, 2, 8, 9 devine: 5, 7, 6, 8, 4, 11, 2, 10, 9 Urmeaz s se compare tot numrul 8, dar cu 2. Datorit faptului c 8 > 2, cele dou numere trebuie schimbate ntre ele. 5, 7, 6, 8, 4, 11, 2, 10, 9 devine: 5, 7, 6, 2, 4, 11, 8, 10, 9 Urmtoarea comparaie se va face ntre 8 i 4. Cele dou numere rmn la locurile lor. 5, 7, 6, 2, 4, 11, 8, 10, 9 O ultim comparaie se realizeaz ntre 8 i 11. Cele dou numere trebuie inter- schimbate i se obine: 5, 7, 6, 2, 4, 8, 11, 10, 9 Dup aceast parcurgere, numrul 8, cel care a fost n irul iniial pe prima poziie, se afl acum pe poziia sa final n ir. Toate elementele din subirul din stnga lui 8 sunt mai mici dect acesta i toate cele din subirul din dreapta lui 8 sunt mai mari de- 16. 4. Metoda Divide et Impera 117 ct el. Primul numr din ir, n cazul de fa 8, a fost comparat cu toate elementele din ir i prin interschimbri cu cele care sunt mai mici dect el au ajuns n stnga sa, iar cele mai mari au ajuns n subirul din partea dreapt. Se obin astfel dou subiruri (care trebuie ordonate) i un element care se afl pe poziia sa final n ir. (5, 7, 6, 2, 4), 8, (11, 10, 9) Cele dou subiruri obinute se mpart la rndul lor dup cum urmeaz: (5, 7, 6, 2, 4) (4, 7, 6, 2, 5) (4, 5, 6, 2, 7) (4, 5, 6, 2, 7) (4, 2, 6, 5, 7) (4, 2, 6, 5, 7) (4, 2, 5, 6, 7) (4, 2), 5, (6, 7) (11, 10, 9) (9, 10, 11) (9, 10, 11) (9, 10), 11 Metoda presupune mprirea irului n dou subiruri, astfel nct toate elementele din primul subir s fie mai mici dect toate elementele din al doilea subir. mprirea irului n subiruri se realizeaz pn cnd se obin subiruri de lungime 1, caz n care se consider c acel subir este ordonat. Metoda sortrii rapide lucreaz cu metoda Divide et Impera, deoarece problema iniial se mparte n subprobleme independente unele de altele, care se rezolv mai uor. Datorit faptului c subirurile se ordoneaz direct, combinarea rezultatelor par- iale nu se mai realizeaz. Astfel, la o mprire a unui subir [xst, , xdr] se poate scrie algoritmul: Subalgoritm Quick(st,dr): dac st < dr atunci mparte(st,dr,p){ se determin poziia p care reprezint locul unde se taie irul n } { dou subiruri dup ce un element a ajuns pe poziia sa final p } Quick(st,p-1) { se procedeaz similar pentru subirul (xst, ..., xp-1) } Quick(p+1,dr) { i pentru subirul (xp+1, ..., xdr) } sfrit dac sfrit subalgoritm Cea mai important parte a algoritmului o reprezint cea n care se mparte irul n subiruri, procedur n care se realizeaz i o ordonare a elementelor fa de primul numr din ir. Trebuie ca n fiecare moment s se pstreze cei doi indici ai elementelor care se compar. La fiecare pas se modific unul dintre cei doi indici, fie cel din dreapta, fie cel din stnga. Se vor folosi dou variabile auxiliare ii i jj (deplasamente), cu ajutorul crora se va ti n fiecare moment care este indicele care crete (respectiv scade). Pentru nceput primul numr se compar cu elemente luate de la sfritul irului avansnd spre nce- put. Deci primul indice (i) rmne constant i al doilea (j) scade. Astfel ii 0, iar jj 1. Dup prima interschimbare de valori, primul indice (i) crete i al doilea (j) 17. 118 4. Metoda Divide et Impera rmne constant, adic ii 1 i jj 0. Operaiile de comparare i trecerea la pasul urmtor se realizeaz pn cnd i devine egal cu j. n situaia i = j, elementul care a fost iniial pe prima poziie din ir este acum pe poziia i, care este poziia sa final n ir, i s-au obinut cele dou subiruri. Subalgoritm mparte(st,dr,p): i st j dr ii 0 jj -1 ct timp i < j execut: dac xi > xj atunci { dac elementele nu sunt n ordinea dorit } aux xi { se interschimb elementele } xi xj xj aux aux ii { totodat se schimb i sensul de comparare } ii -jj jj -aux sfrit dac i i + ii j j + jj sfrit ct timp sfrit subalgoritm Comparativ cu alte metode de ordonare, n cazul sortrii rapide, un singur element este comparat cu toate celelalte, dup care se obin dou subiruri mai scurte ca lungi- me i acest fapt conduce la un timp mai mic de execuie a algoritmului. 4.4.6. Serbare Dac irul nu ar fi ordonat, profesorul ar fi nevoit s ncerce s gseasc elevul potrivit lund elev dup elev i verificnd nlimea sa. n momentul n care a gsit elevul c- ruia i se potrivete costumul, cutarea profesorului ar lua sfrit. Copilul cutat poate fi primul, dar tot aa de bine poate fi i ultimul. Avnd n vedere faptul c nlimea elevilor este dat n ordine cresctoare, o solu- ie prin care se gsete elevul potrivit ar trebui s in cont de acest fapt. O strategie posibil este ca profesorul s ncerce s gseasc elevul potrivit studiind nlimea elevului aflat pe poziia din mijloc al irului. Dac elevul cutat nu este cel din mijloc, profesorul i poate da seama dac elevul este n prima sau n cea de-a doua jumtate a irului. irul este ordonat cresctor, iar dac elevul din mijloc este mai mic dect cel cutat, este sigur c elevul cutat nu se gsete n prima jumtate a iru- 18. 4. Metoda Divide et Impera 119 lui. Dac elevul din mijloc este mai mare dect cel cutat, este de asemenea sigur c elevul cutat nu se gsete n cea de-a doua jumtate. n cele ce urmeaz, profesorul trebuie s continue cutarea doar n grupul format din jumtate dintre elevi, grup care la rndul lui este un ir ordonat. Acest subir va fi mprit n dou (la fel ca irul iniial) i eventual (dac elevul c- utat nu este cel din mijlocul subirului) se continu cutarea n jumtatea corespunz- toare a subirului. Aceast metod se repet pn cnd este gsit elevul cu nlimea potrivit sau n cazul n care nu exist un astfel de elev pn cnd lungimea subirului este egal cu 1. n acest caz rspunsul la problema profesorului este: Nu se afl n ir nici un elev cu nlimea potrivit. Aceast strategie aplic algoritmul de cutare binar. Algoritmul const n cuta- rea unei valori val ntr-un ir ordonat de elemente. Astfel, dac trebuie gsit valoarea val n irul x1, x2, , xn, se testeaz dac val este egal cu xm, unde m = [(n + 1)/2]. Dac cele dou valori sunt egale, cutarea se oprete cu succes. Dac cele dou valori nu sunt egale, nu nseamn c nu vom gsi n viitor valoarea val. S-ar putea ca valoarea cutat s se gseasc ntr-unul dintre cele dou subiruri obinute: n subirul x1, , xm-1 n situaia n care xm > val sau n subirul xm+1, , xn, n situaia n care xm < val. mprirea irului n dou subiruri arat c problema face parte din categoria celor rezolvate cu ajutorul metodei Divide et Impera, deoarece mprirea unui astfel de sub- ir se poate realiza independent de mprirea celorlalte subiruri. n concluzie, proble- ma se mparte n subprobleme independente. Metoda de rezolvare Divide et Impera n majoritatea cazurilor conduce la algoritmi avnd complexitate logaritmic. Problemele care se rezolv folosind aceast metod presupun posibilitatea de a le mpri n subprobleme distincte care se pot rezolva mai uor i soluiile acestor sub- probleme se combin pentru a obine rezultatul final al problemei de rezolvat. n cazul cutrii binare mprirea problemei n subprobleme se realizeaz prin de- terminarea celor dou subiruri. Astfel, dac se caut o valoare n irul (xst, , xdr), mprirea problemei const n stabilirea subirurilor (xst, , xm-1) i (xm+1, , xdr), unde m = [(st + dr) / 2]. Subalgoritm CutareBinar(st,dr,h): mij (st + dr) div 2 { stabilirea mijlocului subirului curent } dac h = x[mij] atunci scrie DA, mij altfel dac h < x[mij] atunci CutareBinar(st,mij-1,h) altfel CutareBinar(mij+1,dr,h) sfrit subalgoritm 19. 120 4. Metoda Divide et Impera n rezolvarea acestei probleme nu exist compunerea soluiilor subproblemelor pentru a obine soluia final. Practic gsim valoarea cutat n ultima clip sau aflm c nu exist soluie. 4.4.7. Joc Ghicirea numrului ascuns Pentru a ghici un numr dintr-un anume interval, prima tendin este de a ncerca va- loarea din mijloc. Dac este prea mare se va reduce intervalul n care se caut la prima jumtate. De exemplu, dac intervalul iniial este [0, 200] se va ncerca cu valoarea 100. Apoi se ncearc cu 50 i la fel se obine jumtate din ultimul interval considerat, dac 50 nu a fost cumva numrul ascuns. Dup cte se observ strategia de gsire a numrului ascuns se bazeaz pe metoda Divide et Impera. n cazul de fa metoda este folosit de persoana care utilizeaz pro- gramul (ncearc s ghiceasc numrul). Algoritmul de gsire a numrului ascuns se numete cutare binar i este cel mai rapid algoritm de cutare a unei valori ntr-un ir ordonat de numere. Numrul maxim de cutri va fi de ordinul log2n, unde n este numrul valorilor din ir. 4.4.8. Patinoarul Dac patinoarul nu are zone punctiforme cu probleme n interiorul su, atunci zona maxim coincide cu patinoarul iniial. Dac ar avea un singur punct problem de coordonate (x, y), problema s-ar reduce la a mpri patinoarul n zone mai mici, delimitate de punctul respectiv ca n figura 2, respectiv ca n figura 3, dreptunghiuri care nu conin acest punct, el fiind pe marginea zonei. Se obin astfel 4 zone dreptunghiulare. Zona cutat este una dintre cele patru zone, cea de arie maxim. n situaia n care patinoarul conine mai multe zone nesigure este foarte probabil ca ntre cele patru dreptunghiuri obinute prin mprire, s existe unele care au la rn- dul lor puncte cu probleme. Aceste noi dreptunghiuri, care au puncte cu probleme se vor trata la fel ca dreptunghiul iniial i vor fi mprite n alte zone mai mici. mpri- rea se repet pn cnd dreptunghiurile obinute nu conin nici un punct interior i din- tre acestea soluia este dat de dreptunghiul de arie maxim. (a, b) (x, y) (c, d) Fig. 1 (a, b) (c, d) Z1 Z2 Fig. 2 (a, b) Z3 (c, d) Z4 Fig. 3 20. 4. Metoda Divide et Impera 121 Dac se cunosc coordonatele dreptunghiului de mprit ((a, b), (c, d)) i coordona- tele punctului curent (x, y), se pot calcula foarte uor coordonatele noilor dreptunghiuri care se formeaz: Z1: colul stnga-sus rmne (a, b), colul dreapta-jos devine (c, y) Z2: colul stnga-sus devine (a, y), colul dreapta-jos rmne (c, d) Z3: colul stnga-sus rmne (a, b), colul dreapta-jos devine (x, d) Z4: colul stnga-sus devine (x, b), colul dreapta-jos rmne (c, d) Aria unei zone de coordonate (a, b), (c, d) se calculeaz cu formula: A = (c a)(d b). Pentru a determina dac un dreptunghi conine puncte cu probleme se poate folosi o funcie care returneaz indicele unui punct din tabloul n care sunt memorate, punct cu probleme din interiorul dreptunghiului ales la un moment dat. Dac acesta nu exist returneaz 0. Condiia ca un punct de coordonate (x, y) s se afle n interiorul unui dreptunghi avnd coordonatele colurilor n (a, b), respectiv (c, d) este ca (a < x, x < c, b < y i y < d). Subalgoritm Exist(a1,b1,c1,d1,i): { caut un punct interior dreptunghiului de coordonate (a1, b1) } i 1 { i (c1, d1) (nu i pe margini) } gsit fals ct timp (i n) i nu gsit execut: dac (a1 < x[i]) i (x[i] < c1) i (b1 < y[i]) i (y[i] < d1) atunci gsit adevrat { se va returna indicele i a punctului gsit } altfel i i + 1 sfrit dac sfrit ct timp dac nu gsit atunci { dac nici un punct nu se afl n interior } i 0 sfrit dac sfrit subalgoritm Rezolvarea este realizat astfel prin metoda Divide et Impera. mprirea problemei n subprobleme se realizeaz prin determinarea a patru dreptunghiuri. Rezolvarea sub- problemelor revine la a cuta dac exist puncte nesigure n fiecare dintre dreptun- ghiurile nou obinute. Dac exist astfel de puncte se trece la o nou mprire. Pentru un dreptunghi fr puncte cu probleme se calculeaz aria sa i se compar cu aria maxim obinut deja. Subalgoritm mpart(a1,b1,c1,d1): Exist(a1,b1,c1,d1,i) { se caut un punct n interiorul dreptunghiului } 21. 122 4. Metoda Divide et Impera dac i = 0 atunci { dac n zon nu exist nici un punct nesigur } aria (c1-a1)*(d1-b1) { se calculeaz aria } { dac aria este mai mare dect maximul gsit pn acum } dac aria > max atunci max aria { se pstreaz aria i coordonatele dreptunghiului respectiv } am a1 bm b1 cm c1 dm d1 altfel { se mparte terenul n cele patru dreptunghiuri noi } mpart(a1,b1,x[t],d1) mpart(x[t],b1,c1,d1) mpart(a1,b1,c1,y[t]) mpart(a1,y[t],c1,d1) sfrit dac sfrit dac sfrit subalgoritm 4.4.9. Ora de sport S observm c enunul precizeaz explicit modelul dup care se desfoar activitatea profesorului care urmrete descoperirea/stabilirea conductorului grupului de elevi. Nu exist criterii de inteligen (profesorul ar putea fi subiectiv...); Nu exist considerente privind nlimea, greutatea sau culoarea ochilor... (irul nu este ordonat dup nici un criteriu), ci doar dup numrul de pe tricouri. Rezult c aceste numere vor fi considerate numere de ordine (indici) n ir. Ceea ce alege profesorul este jumtatea care rmne (de aici rezultnd i jumta- tea care pleac)! Rezult c rezolvarea, adic stabilirea rspunsului la cerina proble- mei este dirijat de comenzile profesorului. Se observ c profesorul d comenzi pn cnd n irul (grupul) de elevi rmne unul singur! n concluzie, n urma comenzilor profesorului, grupul se njumtete, rmnnd n continuare de mprit jumtatea preferat, adic cea care nu a plecat. Se observ c faptul c dac la un moment dat pleac, de exemplu, jumtatea din stnga din ir, nu are nici o legtur cu o comand viitoare imediat sau ulterioar a profesorului; el alege s plece o parte sau alta din grupul existent la momentul respec- tiv. Altfel spus, faptul c dintre copiii c1, c2, ..., cn la un moment dat vor rmne copiii c1, c2, ..., cq, unde q = [(1 + n)/2] sau, n funcie de paritatea lui n, q = [(1 + n)/2] 1, nu are nici o legtur cu faptul c la un pas viitor se va alege jumtate dintr-un ir cp, cp+1, ..., cr. Rezult c mprirea unui astfel de subir se poate face independent de mprirea celorlalte subiruri. n concluzie, problema se mparte n subprobleme independente. n astfel de probleme metoda de rezolvare recomandat este Divide et Impera. 22. 4. Metoda Divide et Impera 123 Stabilit fiind metoda, s definim o subproblem: la un moment dat avem elevii cu numerele de ordine st, st + 1, ..., dr ntr-un subir care urmeaz s fie mprit. La co- manda profesorului, acest ir se mparte n dou subiruri, n funcie de paritatea lungi- mii irului (st dr + 1): 1. Dac st dr + 1 este numr par, rezult subirurile formate din copiii avnd numerele de ordine st + 1, st + 2, , mij i mij + 1, mij + 2, , dr, unde mij este [(st + dr)/2] 2. Dac st dr + 1 este numr impar, vor rezulta subirurile (st + 1, st + 2, , mij 1) i (mij + 1, mij + 2,, dr), urmnd ca cel cu numrul de ordine mij s mearg di- rect la nclzire. n funcie de comand rmne n continuare n prelucrare fie subirul din stnga, fie cel din dreapta. S observm c dac numrul n este putere a lui 2, vor putea deveni conductori toi copiii. Adic, dac n = 2k , la prima mprire obinem dou subiruri, ambele de lungimi puteri ale lui 2, (care, evident, sunt numere pare) i aa mai departe, fiecare mprire d natere la subiruri avnd numr par de elevi. De exemplu, dac n = 16, prima mprire conduce la subirurile formate din elementele avnd indice ntre 1..8 i 9..16, Dac s-a comandat stnga, se reine primul subir (1..4). Dac urmeaz din nou o comand stnga, rmn copiii cu numerele de ordine 1 i 2. n funcie de urmtoarea comand conductor va fi fie 1 fie 2. Dar la fel s-ar mpri i celelalte subiruri n funcie de comenzile profesorului. S vedem ce se ntmpl dac n nu este putere a lui 2, dar este numr par. Evident, mprind un astfel de numr la 2, putem obine, fie un numr par fie unul impar. De exemplu, dac n = 10, i prima comand este dreapta, rmne subirul 6..10. O co- mand nou dreapta d natere subirului 9..10, deoarece mij ar avea valoarea 8, dar copilul care are acest numr de ordine pleac la nclzire deoarece n subirul 6..10 au fost 5 (un numr impar) de elevi. Rezult c dac avem subirul st, st + 1, ..., dr, unde numrul de elevi (dr st +1) este impar, elevul avnd numrul de ordine mij = [(st + dr)/2] nu poate s fie conduc- tor. Aa pare, c mprind pur i simplu numrul n n mod repetat la 2, am putea rs- punde la prima ntrebare (oare ci elevi au ansa s fie conductorii i care ar fi acetia?). Dar nu este aa! Trebuie s rezolvm aceeai subproblem pentru subiruri rezultate att n partea stng, ct i n partea dreapt! Cea de-a doua ntrebare (un elev purtnd un tricou cu un anumit numr poate sau nu deveni conductor?) ntr-un fel este inversa primei ntrebri. Adic, ndeprtnd dintre cei n elevi pe cei care nu pot fi conductori, rmn cei care pot fi. Rezult c vom pstra numerele de ordine care n urma divizrii repetate rmn singure ntr-un subir. Din cauz c irul nu se mparte exact n dou, ci n funcie de paritatea ele- mentelor, cel din mijloc se elimin din prelucrare, este nevoie de o variabil suplimen- tar mij1 n care pstrm numrul de ordine al mijlocului irului, urmnd ca n funcie de paritatea elementelor n subirul actual s stabilim limitele subirurilor rezultate. 23. 124 4. Metoda Divide et Impera Subalgoritm Com1(st,dr): { afieaz toate numerele elevilor care pot deveni conductori } dac st < dr atunci mij (st+dr) div 2 { se determin numrul de ordine din mijloc } mij1 mij + 1 dac (dr-st+1) este numr impar atunci mij mij - 1 { elevul din mijloc este eliminat } sfrit dac Com1(st,mij) { repetarea comenzii pentru prima jumtate } Com1(mij1,dr) { repetarea comenzii pentru a doua jumtate } altfel scrie st { st=dr, adic n ir a rmas un singur elev, acesta se afieaz } sfrit dac sfrit subalgoritm n a treia ntrebare ni se cer comenzile care trebuie spuse pentru ca un anumit elev s ajung conductor. Pentru aceasta vom determina mijlocul subirului, apoi n funcie de valoare, vom elimina (depi) sau nu acest punct de mijloc. Dac numrul de ordine este mai mic, l vom cuta n continuare n stnga, ceea ce necesit comanda stnga, altfel n dreapta, corespunztor unei comenzi dreapta. Comenzile (caracterele corespunztoare) le vom pstra concatenate ntr-o variabil de tip string. Subalgoritm Com2(st,dr):{ se determin dac numrul cutat este conductor } { i succesiunea de comenzi necesar pentru ca acesta s devin conductor } dac st < dr atunci mij (st+dr) div { se determin numrul de ordine din mijloc } t1 mij mij1 mij + 1 dac (dr-st+1) este numr impar atunci mij mij - 1 { elevul din mijloc este eliminat } sfrit dac dac t t1 atunci comanda comanda+'s' { cutm numrul de ordine n stnga } Com2(st,mij) altfel comanda comanda+'d' { cutm numrul de ordine n dreapta } Com2(mij1,dr) sfrit dac altfel dac t = st atunci gsit adevrat { t este un posibil conductor } sfrit dac sfrit dac sfrit subalgoritm