În acest capitol vom studia o alta metoda fundamentala de elaborare a algoritmilor, numita Divide et Impera . Ca si Backtracking, Divide et Impera se bazeaza pe un principiu extrem de simplu: descompunem problema în doua (sau mai multe) subprobleme de dimensiuni mai mici; rezolvam subproblemele, iar solutia pentru problema initiala se obtine combinând 343e47d solutiile subproblemelor în care a fost descompusa. Rezolvarea subproblemelor se face în acelasi mod cu problema initiala. Procedeul se reia pâna când subproblemele devin atât de simple încât admit o rezolvare imediata.
Înca din descrierea globala a acestei tehnici s-au strecurat elemente de recursivitate. Pentru a putea întelege mai bine aceasta metoda de elaborare a algoritmilor care este eminamente recursiva, vom prezenta în sectiunea 6.1 câteva elemente fundamentale referitoare la recursivitate. Continuam apoi în sectiunea 6.2 cu prezentarea generala a metodei, urmata de rezolvarea anumitor probleme de Divide et Impera deosebit de importante: cautare binara, sortarea prin interclasare, sortarea rapida si evaluarea expresiilor aritmetice.
Recursivitatea este un concept care deriva în mod direct din notiunea de recurenta matematica. Recursivitatea este un instrument elegant si puternic pe care programatorii îl au la dispozitie pentru a descrie algoritmii. Este interesant de retinut faptul ca programatorii obisnuiau sa utilizeze recursivitatea pentru a descrie algoritmii cu mult înainte ca limbajele de programare sa suporte implementarea directa a acestui concept.
Din punct de vedere informatic, o subrutina (procedura sau functie) recursiva este o subrutina care se autoapeleaza. Sa luam ca exemplu functia factorial, a carei definitie matematica recurenta este:
Din exemplul de mai sus se observa ca factorialul este definit functie de el însusi, dar pentru o valoare a parametrului mai mica cu o unitate. Iata acum care este implementarea recursiva a factorialului, folosind o functie algoritmica:
functie fact(n)
daca n=0 sau n=1 atunci
fact
altfel
fact n*fact(n-1)
return
Se observa ca functia de mai sus nu este decât o "traducere" aproape directa a formulei matematice anterioare. Trebuie sa remarcam ca, asa cum vom vedea în continuarea acestui capitol, la baza functionarii acestor functii sta un mecanism foarte precis, care nu este atât de trivial cum ar parea la prima vedere.
Sa luam ca al doilea exemplu, calculul celebrului sir al ui Fibonacci, care este definit recurent astfel:
Implementarea în pseudocod a sirului lui Fibonacci este:
functie Fib(n)
daca n=0 sau n=1 atunci
Fib
altfel
Fib Fib(n-1) + Fib(n-2)
return
Se observa ca în ambele exemple am început cu asa numita conditie de terminare
daca n=0 sau n=1 atunci
Fib
care corespunde cazului în care nu se mai fac apeluri recursive. O functie recursiva care nu are conditie de terminare va genera apeluri recursive interminabile, care se soldeaza inevitabil (în Pascal) cu mesajul Stack overflow (depasire de stiva, deoarece asa cum vom vedea, fiecare apel recursiv presupune salvarea anumitor date pe stiva, iar stiva are o dimensiune finita). Conditia de terminare ne asigura de faptul ca atunci când parametrul functiei devine suficient de mic, nu se mai realizeaza apeluri recursive si functia este calculata direct.
Ideea fundamentala care sta la baza întelegerii profunde a mecanismului recursivitatii este aceea ca în esenta, un apel recursiv nu difera cu nimic de un apel de functie obisnuit. Pentru a veni în sprijinul acestei afirmatii trebuie sa studiem mai în amanuntime ce se petrece în cazul unui apel de functie.
Se cunoaste faptul ca în situatia în care compilatorul întâlneste un apel de functie sau procedura, acesta preda controlul executiei functiei sau procedurii respective, dupa care se revine la urmatoarea instructiune de dupa apel. Întrebarea care apare în mod firesc este: de unde stie compilatorul unde sa se întoarca la terminarea subrutinei? De unde stie care au fost valorile variabilelor înainte de a se preda controlul subrutinei? Raspunsul este simplu: înainte de a realiza un apel de functie sau de procedura compilatorul salveaza complet starea programului (linia de la care s-a realizat apelul, valorile variabilelor locale, valorile parametrilor de apel) pe stiva, urmând ca la revenirea din subrutina sa reîncarce starea care a fost înainte de apel de pe stiva.
Pentru exemplificare sa consideram urmatoarea procedura (nerecursiva) care afiseaza o linie a unei matrice. Atât linia care trebuie afisata, cât si matricea sunt transmise ca parametru:
procedura AfisLin(a: tmatrice; n,lin: integer)
pentru i = 1,n
scrie a[lin,i]
return
Procedura AfisLin este apelata de procedura AfisMat descrisa mai jos, care afiseaza linie cu linie o întreaga matrice pe care o primeste ca parametru:
procedura AfisMat(a: tmatrice; n: integer)
pentru i = 1,n
AfisLin(a,n,i)
return
Sa presupunem ca procedura AfisMat este apelata într-un program astfel:
AfisMat(a,5)
pentru a afisa o matrice de dimensiuni 5x5.
În momentul în care compilatorul întâlneste acest apel, el salveaza pe stiva linia de la care s-a facut apelul (sa spunem 2181), valoarea matricei a si alte variabile locale declarate în program:
Figura 6.1 Stiva programului dupa apelul procedurii AfisMat
Controlul va fi apoi preluat de catre procedura AfisMat, care intra în ciclul pentru de la linia 2197, dupa care întâlneste apelul:
AfisLin(a,n,i)
În acest moment controlul va fi preluat de catre procedura AfisLin, dar nu înainte de a adauga la vârful stivei linia de la care s-a facut apelul, valorile parametrilor si a variabilei locale i:
Figura 6.2 Continutul stivei programului dupa apelul procedurii AfisLin
Procedura AfisLin va tipari prima linie a matricei, dupa care executia ei se încheie. În acest moment compilatorul consulta vârful stivei pentru a vedea unde trebuie sa revina si care au fost valorile parametrilor si variabilelor locale înainte de apel. Variabila i devine 2, si din nou se apeleaza procedura AfisLin etc.
Remarcam aici faptul ca atât procedura AfisMat cât si procedura AfisLin utilizeaza o variabila locala numita i. Nu poate exista nici o confuzie între cele doua variabile, deoarece în momentul executiei lui AfisLin, valoarea variabilei i din AfisMat este salvata pe stiva.
Sa vedem acum evolutia stivei program în cazul calculului recursiv al lui Fact(5). În linia 2145 are loc apelul recursiv:
fact n*fact(n-1)
Pentru a realiza înmultirea respectiva, trebuie ca întâi sa se calculeze Fact(n-1). Cum n are valoarea 5, pe stiva se va depune Fact(4). Abia dupa ce valoarea lui Fact(4) va fi calculata se poate calcula valoarea lui Fact(5). Calculul lui Fact(4) implica însa calculul lui Fact(3), care implica la rândul lui calculul lui Fact(2), Fact(1). Calculul lui Fact(1) se realizeaza prin atribuire directa, fara nici un apel recursiv, în linia 2143:
daca n=0 sau n=1 atunci
fact
În acest moment, stiva programului contine toate apelurile recursive realizate pâna acum:
Figura 6.3 Continutul stivei programului când n devine 1, în cazul calcului lui Fact(5)
Fact(1) fiind calculat se poate reveni la calculul înmultirii 2*Fact(1)=2, apoi, Fact(2) fiind calculat se revine la calculul înmultirii 3*Fact(2)=6 s.a.m.d. pâna se calculeaza 5*Fact(4)=120 si se revine în programul apelant.
Sa vedem acum modul în care se realizeaza calculul recursiv al sirului lui Fibonacci. Vom vedea ca timpul de calcul al acestei recurente este incomparabil mai mare fata de calculul factorialului. Sa presupunem ca functia Fib se apeleaza cu parametrul n=3. În aceasta situatie, se depune pe stiva apelul Fib(3) împreuna cu linia de unde s-a realizat apelul. În linia 2160 a procedurii are loc apelul recursiv
Fib Fib(n-1) + Fib(n-2)
care în cazul nostru, n fiind 3, presupune calcularea sumei Fib(2)+Fib(1). Aceasta suma nu poate fi calculata înainte de a-l calcula pe Fib(2). Calculul lui Fib(2) presupune calcularea sumei Fib(1) + Fib(0). Fib(1) si Fib(0) se calculeaza direct la urmatorul apel recursiv, dupa care se calculeaza suma lor, Fib(2)=2. Abia acum se revine la suma Fib(2)+Fib(1)si se calculeaza Fib(1), dupa care se revine si se calculeaza Fib(3).
Modul de calcul al lui Fib(n) recursiv se poate reprezenta foarte sugestiv arborescent. Radacina arborelui este Fib(n), iar cei doi fii sunt apelurile recursive pe care Fib(n) le genereaza, si anume Fib(n-1) si Fib(n-2). Apoi se reprezinta apelurile recursive generate de Fib(n-2) s.a.m.d:
Figura 6.4 Reprezentarea arborescenta a apelurilor recursive din sirul lui Fibonacci
Din figura de mai sus se observa ca anumite valori ale sirului lui Fibonacci se recalculeaza de mai multe ori. Fib(n) si Fib(n-1) se calculeaza odata, Fib(n-2) se calculeaza de doua ori, Fib(n-3) de 3 ori s.a.m.d. Exercitiul 2 de la finalul acestui capitol va invita sa descoperiti de câte ori se calculeaza fiecare valoare Fib(k).
Implementarea recursiva a functiilor este oarecum usor de înteles, datorita analogiei care se poate realiza cu recurentele matematice. Totusi, recursivitatea nu este o tehnica specifica în exclusivitate functiilor. Putem defini la fel de bine si proceduri recursive. O functie recursiva calculeaza o valoare a ei functie de o valoare anterioara. Analog, o procedura recursiva realizeaza o operatie care se bazeaza pe aceeasi operatie, dar pentru o problema de dimensiune mai mica.
Exemplu. Sa se scrie o procedura care citeste o secventa de caractere pâna ce întâlneste caracterul ".", dupa care afiseaza caracterele în ordine inversa.
Rezolvarea acestei probleme se poate formula recursiv astfel: inversarea caracterelor unui sir implica inversarea caracterelor ramase dupa citirea primului caracter, si scrierea în final a primului caracter:
În consecinta procedura de inversare va avea forma (parametrul n a fost eliminat, el fiind dat în formula doar pentru claritate):
procedura inversare
citeste a
daca a <> '.' atunci inversare
scrie a
return
Este important de notat ca pentru ca procedura sa functioneze corect, variabila a trebuie declarata ca variabila locala a procedurii; astfel, toate valorile citite vor fi salvate pe stiva, de unde vor fi extrase succesiv (în ordinea inversa citirii) dupa întâlnirea caracterului ".".
Un alt exemplu elocvent de procedura recursiva este transformarea unui numar din baza 10 într-o baza b, mai mica decât 10. Sa ne reamintim algoritmul clasic de trecere din baza 10 în baza b. Numarul se împarte la b si se retine restul. Câtul se împarte din nou la b si se retine restul ... pâna când câtul devine mai mic decât b. Rezultatul se obtine prin scrierea în ordine inversa a resturilor obtinute.
Formularea recursiva a acestei rezolvari pentru trecerea unui numar n în baza b este:
Procedura care realizeaza acest cod este descrisa astfel:
procedura Transform(n : integer)
Rest n mod b
daca n<b atunci Transform(n div b)
scrie(Rest)
return
De remarcat ca in aceasta procedura variabila Rest trebuie sa fie declarata local, pentru a fi salvata pe stiva , în timp ce variabila b este bine sa fie declarata global, deoarece valoarea ei nu se modifica.
Divide et Impera este o metoda speciala prin care se pot aborda anumite categorii de probleme. Ca si celelalte metode de elaborare a algoritmilor, Divide et Impera se bazeaza pe un principiu extrem se simplu: se descompune problema initiala în doua subprobleme de dimensiune mai mica, care se rezolva, dupa care solutia problemei initiale se obtine combinând 343e47d solutiile subproblemelor în care a fost descompusa. Se presupune ca fiecare dintre problemele în care a fost descompusa problema initiala se poate descompune în alte subprobleme, la fel cum a fost descompusa si problema initiala. Procedeul de descompunere se repeta pâna când, dupa descompuneri succesive, se ajunge la probleme de dimensiune mica, pentru care exista rezolvare directa.
Evident, nu orice gen de problema se preteaza la a fi abordata cu Divide et Impera. Din descrierea de mai sus reiese ca o problema abordabila cu aceasta metoda trebuie sa aiba doua proprietati:
Sa se poata descompune în subprobleme
Solutia problemei initiale sa se poata construi simplu pe baza solutiei subproblemelor
Modul în care metoda a fost descrisa, conduce în mod natural la o implementare recursiva, având în vedere faptul ca si subproblemele se rezolva în acelasi mod cu problema initiala. Iata care este forma generala a unei functii Divide et Impera:
procedura DivImp(P: Problema)
daca Simplu(P) atunci
RezolvaDirect(P) ;
altfel
Descompune(P, P1, P2) ;
DivImp(P1) ;
DivImp(P2) ;
Combina(P1, P2) ;
return
În consecinta, putem spune ca abordarea Divide et Impera implica trei pasi la fiecare nivel de recursivitate:
Divide problema într-un numar de subprobleme.
Stapâneste (Cucereste) subproblemele prin rezolvarea acestora în mod recursiv.
Combina solutiile tuturor problemelor în solutia finala pentru problema initiala.
Cautarea binara este o metoda eficienta de regasire a unor valori într-o secventa ordonata. Desi este trecuta în acest capitol, cautarea binara nu este un exemplu tipic de problema Divide et Impera, deoarece în cazul ei se rezolva doar una din cele doua subprobleme, deci lipseste faza de recombinare a solutiilor. Enuntul problemei de cautare binara este:
Se da un vector cu n componente (întregi), ordonate crescator si un numar întreg p. Sa se decida daca p se gaseste în vectorul dat, si, în caz afirmativ, sa se furnizeze indicele pozitiei pe care se gaseste.
O rezolvare imediata a problemei presupune parcurgerea secventiala a vectorului dat, pâna când p este gasit, sau am ajuns la sfârsitul vectorului. Aceasta rezolvare însa nu foloseste nicaieri faptul ca vectorul este sortat.
Cautarea binara procedeaza în felul urmator: se compara p, cu elementul din mijlocul vectorului; daca p este egal cu acel element, cautarea s-a încheiat. Daca este mai mare, se cauta doar în prima jumatate, iar daca este mai mic, se cauta doar în a doua jumatate.
Cititorul atent a observat cu siguranta ca în aceasta situatie problema nu se descompune în doua subprobleme care se rezolva, dupa care se construieste solutia, ci se reduce la una sau la alta din subprobleme. Cei trei pasi ai lui Divide et Impera sunt în aceasta situatie:
Divide: Împarte sirul de n elemente în care se realizeaza cautarea în doua siruri cu n/2 elemente.
Stapâneste: Cauta în una dintre cele doua jumatati, functie de valoarea elementului din mijloc.
Combina: Nu exista.
Iata
care este functia care realizeaza cautarea elementului 
în sirul 
, între
indicii low si high
functie CautBin(low, high)
daca low<=high atunci //daca mai exista cel putin un element
mid (low + high)/2 //calculam mijlocul sirului
daca p = a[mid] atunci //daca elementul din mijloc este cel cautat
CautBin mid //returneaza pozitia pe care a fost gasit
altfel
daca p<a[mid] atunci //daca e mai mic atunci
CautBin CautBin(a,p,low,mid-1) //cauta în prima jumatate
altfel
CautBin CautBin(a,p, mid+1, high) //cauta în a doua jumatate
altfel CautBin
return
Pozitia pe care se gaseste elementul p în sirul a este data de apelul:
Poz CautBin(1,n)
Sortarea prin interclasare este, alaturi de sortarea rapida (QuickSort) si sortarea cu ansamble (HeapSort) una dintre metodele eficiente de ordonare a elementelor unui sir. Enuntul problemei este urmatorul:
Sa se ordoneze crescator un vector cu n componente întregi.
Principiul de rezolvare este urmatorul: se împarte vectorul în doua parti egale si se sorteaza fiecare jumatate, apoi se interclaseaza cele doua jumatati. Descompunerea în doua jumatati se realizeaza pâna când se ajunge la vectori cu un singur element, care nu mai necesita sortare. Algoritmul de sortare prin interclasare urmeaza îndeaproape paradigma Divide et Impera. În mare, modul ei de operare este:
Divide: Împarte sirul de n elemente care urmeaza a fi sortat în doua siruri cu n/2 elemente
Stapâneste: Sorteaza recursiv cele doua subsiruri utilizând sortarea prin interclasare
Combina: Interclaseaza subsirurile sortate pentru a obtine rezultatul final
Procedura MergeSort de mai jos implementeaza algoritmul de sortare prin interclasare. Apelul initial al functiei este
MergeSort(1,n)
unde n este numarul de elemente al tabloului a
procedura MergeSort(low, high)
daca low < high atunci
mid (low + high)/2
MergeSort(a,low, mid)
MergeSort(a,mid+1, high)
Intercls(low,mid, high, a)
return
Procedura de interclasare în acest caz este analoaga cu procedura de interclasare obisnuita a doua siruri propusa în capitolul 2, diferenta constând în faptul ca acum se interclaseaza doua jumatati ale aceluiasi sir, iar rezultatul se va depune în final tot în sirul interclasat. Lasam scrierea acestei proceduri ca exercitiu.
Sortarea rapida este, asa cum îi spune si numele, cea mai rapida metoda de sortare cunoscuta în prezent. Exista foarte multe variante ale acestei metode, o parte dintre ele având doar rolul de a micsora timpul de executie în cazul cel mai nefavorabil. Vom prezenta aici varianta clasica, despre care veti remarca cu surprindere ca este neasteptat de simpla. Enuntul problemei este identic cu cel de la sortarea prin interclasare.
Sa se ordoneze crescator un vector de numere întregi.
Metoda de sortare rapida prezentata în acest paragraf este dintr-un anumit punct de vedere complementara metodei Mergesort. Diferenta între cele doua metode este data de faptul ca în timp ce la MergeSort mai întâi vectorul se împartea în doua parti dupa care se sorta fiecare parte si apoi se interclasau cele doua jumatati, la QuickSort împartirea se face în asa fel încât cele doua siruri sa nu mai trebuiasca interclasate dupa sortare, adica primul sir sa contina doar elemente mai mici decât al doilea sir. Cu alte cuvinte, în cazul lui QuickSort etapa de recombinare este triviala, deoarece problema este astfel împartita în subprobleme încât nu mai este necesara interclasarea sirurilor. Etapele lui Divide et Impera pot fi descrise în aceasta situatie astfel:
Divide: Împarte sirul de n elemente care urmeaza a fi sortat în doua siruri cu n/2 elemente, astfel încât elementele din primul sir sa fie mai mici decât elementele din al doilea sir
Stapâneste: Sorteaza recursiv cele doua subsiruri utilizând sortarea rapida
Combina: sirul sortat este obtinut din concatenarea celor doua subsiruri sortate.
Functia care realizeaza împartirea în subprobleme (astfel încât elementele primului sir sa fie mai mici decât elementele celui de-al doilea) se datoreaza lui C. A. Hoare, care a gasit o metoda de a realiza aceasta împartire (numita partitionare) în timp liniar.
Procedura de partitionare rearanjeaza elementele tabloului functie de primul element, numit pivot, astfel încât elementele mai mici decât primul element sunt trecute în stânga lui, iar elementele mai mari decât primul element sunt trecute în dreapta lui. De exemplu, daca avem vectorul:
atunci procedura de partitionare va muta elementele 5,2 si 3 în stânga lui 7, iar 8 va fi în dreapta lui. Cum se realizeaza acest lucru? sirul este parcurs de doi indici: primul indice, low, pleaca de la primul element si este incrementat succesiv, al doilea indice, high, porneste de la ultimul element si este decrementat succesiv. În situatia în care a[low] este mai mare decât a[high], elementele se interschimba. Partitionarea este încheiata în momentul în care cei doi indici se întâlnesc (devin egali) undeva în interiorul sirului. La un pas al algoritmului, fie se incrementeaza low, fie se decrementeaza high; întotdeauna unul dintre cei doi indici, low sau high, este pozitionat pe pivot. Atunci când low indica pivotul, se decrementeaza high, iar atunci când high indica pivotul se incrementeaza low. Iata cum functioneaza partitionarea pe exemplul de mai sus. La început, low indica primul element, iar high indica ultimul element:
Deoarece a[low]>a[high] elementele 7 si 3 se vor interschimba. Dupa interschimbare, pivotul va fi indicat de high, deci low va fi incrementat:
Din nou avem a[low]>a[high], elementele 8 si 7 se vor interschimba. Dupa interschimbare, pivotul va fi indicat de low, deci high va fi decrementat:
Din nou avem a[low]>a[high], elementele 7 si 2 se vor interschimba. Dupa interschimbare, pivotul va fi indicat de high, deci low va fi incrementat:
De data aceasta avem a[low]<=a[high], deci low va fi incrementat din nou, fara a se realiza interschimbari.
În acest moment low si high s-au suprapus (au devenit egale), deci partitionarea s-a încheiat. Pivotul este pe pozitia a 4-a, care este de fapt si pozitia lui finala în sirul sortat.
Functia de partitionare de mai jos primeste ca parametri limitele inferioara, respectiv superioara ale sirului care se partitioneaza si returneaza pozitia pe care se afla pivotul în finalul partitionarii. Pozitia pivotului este importanta deoarece ne da locul în care sirul va fi despartit în doua subsiruri.
functie Partitionare(low, high)
PozPivot 0 //variabila care ne spune daca low indica pivotul
cât timp low<high //indicii de parcurgere nu s-au suprapus
daca a[low]>a[high] atunci
Interschimba(a[low], a[high])
PozPivot 1 - PozPivot //alt indice indica acum pivotul
daca PozPivot = 0 atunci high high-1 altfel low low + 1
Partitionare low //se returneaza pozitia pivotului
return
Doua observatii importante merita facute asupra acestei functii:
Variabila PozPivot poate lua valoarea 0 daca pivotul este indicat de low sau 1 daca pivotul este indicat de high. Atribuirea PozPivot 1 - PozPivot are ca efect schimbarea starii acestei variabile din 0 în 1 sau invers.
Functia se foloseste în mod inteligent de transmiterea prin valoare a parametrilor, deoarece modifica variabilele low si high, fara ca aceasta modificare sa afecteze programul principal.
Procedura de sortare propriu-zisa, respecta structura Divide et Impera obisnuita, doar ca functia de recombinare a solutiilor nu mai este necesara, deoarece am realizat partitionarea înainte de apel:
procedura QuickSort(low, high)
daca low<high atunci //daca subsirul mai are cel putin doua elemente
mid Partitionare(low, high) //partitioneaza
QuickSort(low, mid-1) //sorteaza prima jumatate
QuickSort(mid+1, high) //sorteaza a doua jumatate
return
Se da o expresie aritmetica în care operanzii sunt simbolizati prin litere mici (de la a la z), iar operatorii sunt '+', '-', '/',si '*' cu semnificatia cunoscuta. Se cere sa se scrie un program care transforma expresia în forma poloneza postfixata.
Reamintim faptul ca forma poloneza postfixata (Lukasiewicz) este obtinuta prin scrierea operatorului dupa cei doi operanzi, si nu între ei. Aceasta forma are avantajul ca nu necesita paranteze pentru a schimba prioritatea operatorilor. Ea este utilizata adeseori în informatica pentru a evalua expresii.
Exemple:
a) a+b se scrie a b +
b) a*(b+c) se scrie a b c + *
c) (a+b)*(c+d) se scrie ab+ cd+ *
Unul dintre cei mai simpli algoritmi de a trece o expresie în forma poloneza consta în a cauta care este operatorul din expresie cu prioritatea cea mai mica, si de a aseza acest operator în finalul expresiei, urmând ca prima parte a formei poloneze sa fie formata din transformarea expresiei din stânga operatorului, iar a doua parte a formei poloneze sa fie formata din transformarea expresiei din dreapta operatorului.
Cele doua subexpresii urmeaza a se trata în mod analog, pâna când se ajunge la o subexpresie de lungime 1, care va fi obligatoriu un operand si care nu mai necesita transformare.
Schematic, daca avem expresia
unde E1 si E2 sunt subexpresii, iar op este operatorul cu prioritatea cea mai mica (deci operatorul unde expresia se poate "rupe" în doua), atunci forma poloneza a lui E se obtine astfel:
Expresia de mai sus exprima faptul ca forma poloneza postfixata a lui E se obtine prin scrierea în forma poloneza postfixata a celor doua subexpresii, urmate de operatorul care le separa. Expresia de mai sus este o expresie recursiva specifica tehnicii Divide et Impera. Etapele sunt în aceasta situatie:
Divide: Împarte expresia aritmetica în doua subexpresii. Elimina parantezele exterioare inutile.
Stapâneste: Transforma recursiv în forma poloneza cele doua subexpresii.
Combina: Scrie cele doua subexpresii în forma poloneza urmate de operatorul care le leaga.
Functia de trecere în forma poloneza primeste ca parametru indicele inferior si superior reprezentând limitele între care se încadreaza subexpresia în expresia originala. sirul original este continut în tabloul x cu n elemente. Presupunem definita o constanta op, de tip matrice 2x2 care contine operatorii în ordinea inversa a prioritatilor: op = ( (+,-), (*, /) ) . Functia Parant verifica daca expresia este înconjurata de paranteze inutile si le elimina daca este cazul. Functia Polonez returneaza un sir de caractere care contine expresia în forma poloneza:
functie Polonez(low, high)
daca low=high atunci
Polonez x[low]
cât timp x[low]='(' si x[high]=')' si Parant(low,high)
low low +1; high high -1
pentru i=1,2 //pentru i=1 se cauta operatori aditivi, pentru i=2 se
//cauta operatori multiplicativi
nrp 0 //nrp este numarul de paranteze deschise si neînchise
pentru j=high, low, -1
daca x[j]='(' atunci nrp nrp+1
daca x[j]=')' atunci nrp nrp-1
daca nrp=0 si (x[j] = op[i][0] sau x[j] = op[i][1]) atunci
Polonez Polonez(low,j-1) + Polonez(j+1, high) + x[j]
i 2; j n //nu mai cautam alt operator
return
Prima linie a functiei testeaza daca nu s-a ajuns la o expresie care are un singur caracter. În caz afirmativ, valoarea functiei este chiar caracterul (operandul) respectiv. Ciclul cât timp din a treia linie are rolul de a elimina parantezele inutile care ar putea înconjura expresia. Eliminarea acestor paranteze este necesara, deoarece algoritmul cauta sa rupa expresia în doua la primul operator aditiv sau multiplicativ care se afla în afara oricarei paranteze. De exemplu, în cazul expresiei (a+b)*(c+d) primul operator aflat în afara oricarei paranteze (deci operatorul cu prioritatea cea mai mica) este '*'. Expresia va fi împartita astfel în subexpresiile (a+b) si (c+d) care nu au nici un operator în afara oricarei paranteze. Din acest motiv, eliminarea parantezelor inutile este necesara.
Expresia este parcursa de cel mult doua ori. La prima parcurgere se cauta un operator aditiv aflat în afara oricarei paranteze; în cazul în care un astfel de operator nu este gasit, se parcurge expresia pentru a cauta primul operator multiplicativ aflat în afara oricarei paranteze. Aceasta dubla parcurgere este realizata de ciclul pentru dupa i
Ciclul pentru dupa j parcurge sirul de la coada la cap în cautarea operatorului aflat în afara oricarei paranteze. Variabila nrp are rolul de a numara câte paranteze deschise si neînchise sunt de la capatul sirului pâna la punctul curent. Ruperea sirului se poate realiza numai în situatia în care parantezele deschise sunt egale cu cele închise, deci nrp=0. Daca se întâlneste operatorul cautat si acesta se afla în afara oricarei paranteze, atunci are loc împartirea expresiei în doua si transformarea celor doua subexpresii.
Functia Parant, definita mai jos, se bazeaza pe urmatoarea idee simpla: se parcurge expresia cu parantezele exterioare eliminate si se verifica daca dupa eliminare expresia mai este corecta. Daca exista o paranteza închisa careia nu îi corespunde nici o paranteza deschisa (nrp = -1) atunci expresia este incorecta si functia returneaza fals.
functie Parant(low, high)
Parant True
pentru i=low+1, high-1
daca x[i]= '(' atunci nrp nrp + 1
daca x[i]= ')' atunci nrp nrp - 1
daca nrp<0 atunci
Parant False
return
Reprezentati evolutia stivei pentru procedurile si functiile recursive din acest capitol.
Calculati de câte ori se recalculeaza valoarea Fk în cazul calcului recursiv al valorii Fn a sirului lui Fibonacci.
Sa se calculeze recursiv si iterativ cel mai mare divizor comun a doua numere dupa formulele (Euclid):
Sa se calculeze recursiv si iterativ functia lui Ackermann, data de formula:
Sa se
calculeze combinarile dupa formula de recurenta din
triunghiul lui Pascal: 
.
Calculati apoi combinarile dupa formula clasica: 
. Ce
constati? Cum explicati ceea ce ati constat? (daca ati
constat...)
Sa se calculeze recursiv si iterativ functia Manna-Pnueli, data de formula:
Sa se scrie o functie care calculeaza recursiv suma cifrelor unui numar dupa formula:
Se considera doua siruri definite recurent dupa formulele:
si 
, cu 
Sa se scrie un program recursiv care calculeaza aceste siruri.
(Partitiile
unui numar) Un numar natural n se poate descompune ca suma
descrescatoare de numere naturale. De exemplu, pentru numarul 4 avem
descompunerile 2+1+1 sau 3+1. Prin 
se noteaza numarul de
posibilitati de a-l descompune pe n ca suma
(descrescatoare) de k numere. De exemplu, P(4,2)=2 (4 = 3+1, 4=2+2).
Numerele verifica relatia de
recurenta:
Sa se
calculeze numarul total de descompuneri ale numarului 
Sa se scrie o functie care calculeaza maximul elementelor unui vector utilizând tehnica Divide et Impera. Sugestie: Se împarte vectorul în doua jumatati egale, se calculeaza recursiv maximul celor doua jumatati si se alege numarul mai mare.
(Turnurile din Hanoi) Se dau trei tije simbolizate prin literele A, B si C. Pe tija A se afla n discuri de diametre diferite asezate descrescator în ordinea diametrelor, cu diametrul maxim la baza. Se cere sa se mute discurile pe tija B respectând urmatoarele reguli:
a. la fiecare pas se muta un singur disc
b. nu este permisa asezarea unui disc cu diametru mai mare peste un disc cu diametrul mai mic
Sugestie: Formularea recursiva a solutiei este: se muta primele n-1 discuri pe tija C folosind ca tija intermediara tija B; se muta discul ramas pe A pe tija B; se muta discurile de pe tija C pe tija B folosind ca tija intermediara tija A.
Scrieti un program în care calculatorul sa ghiceasca cît se poate de repede un numar natural la care Dvs. v-ati gândit. Numarul este cuprins între 1 si 32.000. Atunci când calculatorul propune un numar i se va raspunde prin 1, daca numarul este prea mare, 2 daca numarul este prea mic si 0 daca numarul a fost ghicit.
Se
considera un vector cu n componente numere naturale. Definim plierea
vectorului ca fiind suprapunerea uneia dintre jumatati,
numita donatoare, peste o alta, numita receptoare. în
cazul în care numarul de elemente ale vectorului este impar, cel din
mijloc este eliminat. În acest mod se ajunge la un vector ale carui
elemente încep de la o pozitie lo si se termina la
o pozitie hi.
Exemplu: pentru n=7, putem obtine fie lo=1 si hi=3, fie lo=5 si hi=6.
Plierea se poate aplica în continuare în mod repetat pâna când se ajunge
la un subvector de lungime 1 (lo=hi) numit element final. Sa se precizeze
toate elementele finale posibile, precum si o serie de plieri prin care se
poate ajunge la ele.
(Problema taieturilor) Se da o bucata dreptunghiulara de tabla de dimensiune lxh, având pe suprafata ei n gauri de coordonate numere întregi (coltul din stânga jos al tablei este considerat centrul sistemului de coordonate). Sa se determine care este bucata de arie maxima fara gauri care poate fi decupata din suprafata originala. Sunt permise doar taieturi orizontale sau verticale. Sugestie: Se cauta în bucata curenta prima gaura. Daca o astfel de gaura exista, atunci problema se împarte în alte patru subprobleme de acelasi tip. Daca suprafata nu are nici o gaura, atunci se compara suprafata ei cu suprafetele obtinute pâna la acel moment. Daca suprafata este mai mare, atunci se retine.
(Fractali - Curba lui Koch). Se considera un triunghi echilateral ale carui laturi se transforma dupa cum se vede în figura urmatoare:
Fiecare latura a poligonului obtinut se transforma dupa aceeasi regula. Sa se vizualizeze grafic figura obtinuta dupa aplicarea succesiva a regulii de N ori.
16. (Fractali - Covorul lui Sierpinsky). Se porneste de la un patrat a carui suprafata se divide în 9 parti egale prin împartirea fiecarei laturi în 3 parti egale. Patratul din mijloc se elimina. Cu cele 8 patrate ramase se procedeaza în acelasi mod. Sa se vizualizeze figura obtinuta dupa N pasi.
|
