Cartea de Algoritmi (Avansati)

download Cartea de Algoritmi (Avansati)

of 294

Transcript of Cartea de Algoritmi (Avansati)

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    1/294

    ALGORITMIFUNDAMENTALIO PERSPECTIVC++

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    2/294

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    3/294

    ALGORITMIFUNDAMENTALIO PERSPECTIVC++

    RZVAN ANDONIE ILIE GRBACEA

    Editura LibrisCluj-Napoca, 1995

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    4/294

    Referent: Leon Livovschi

    Coperta: Zoltn Albert

    Copyright 1995 Editura LibrisUniversitii 8/8, 3400 Cluj-Napoca

    ISBN 973-96494-5-9

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    5/294

    v

    Cuvnt nainte

    Evoluia rapid i spectaculoas a informaticii n ultimile decenii se reflect attn apariia a numeroase limbaje de programare, ct i n metodele de elaborare iredactare a unor algoritmi performani.

    Un concept nou, care s-a dovedit foarte eficient, este cel al program rii orientate

    pe obiect, prin obiect nelegndu-se o entitate ce cuprinde att datele, ct iprocedurile ce opereaz cu ele. Dintre limbajele orientate pe obiect, limbajul C++prezint printre multe altele avantajul unei exprimri concise, fapt ce uureaztranscrierea n acest limbaj a algoritmilor redacta i n pseudo-cod i motiveazfolosirea lui n cartea de fa . Cu toate cnu este descris n detaliu, este demn demen ionat faptul c descrierea din Capitolul 2, mpreun cu completrile dincelelalte capitole, constituie o prezentare aproape integrala limbajului C++.

    O preocupare meritorie a acestei lucrri este problema analizei eficieneialgoritmilor. Prezentarea acestei probleme ncepe n Capitolul 1 i continu nCapitolul 5. Tehnicile de analizexpuse se bazeazpe diferite metode, prezentate

    ntr-un mod riguros i accesibil. Subliniem contribuia autorilor n expunereadetailata induciei constructive i a tehnicilor de rezolvare a recurenelor liniare.

    Diferitele metode clasice de elaborare a algoritmilor sunt descrise n Capitolele68 prin probleme ce ilustreaz foarte clar ideile de baz i detaliile metodelorexpuse. Pentru majoritatea problemelor tratate, este analizat i eficienaalgoritmului folosit. Capitolul 9 este consacrat tehnicilor de explorri n grafuri.n primele seciuni sunt prezentate diferite probleme privind parcurgereagrafurilor. Partea final a capitolului este dedicat jocurilor i cuprinde algoritmice reprezint de fapt soluii ale unor probleme de inteligen artificial.

    Cartea este redactatclar i riguros, tratnd o arie largde probleme din domeniulelaborrii i analizei algoritmilor. Exerciiile din ncheierea fiecrui capitol suntfoarte bine alese, multe din ele fiind nsoite de soluii. De asemenea, meritmen ionate referirile interesante la istoria algoritmilor i a gndirii algoritmice.

    Considerm c aceast carte va fi apreciati cutatde ctre toi cei ce lucreazn domeniul abordat i doresc s-l cunoascmai bine.

    Leon Livovschi

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    6/294

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    7/294

    vii

    n cl ipa cnd exprimm un lucru, reuim,n mod bizar, s-l i depreciem.

    Maeterlinck

    Prefa

    Cartea noastr i propune n primul rnd s fie un curs i nu o enciclopedie de

    algoritmi. Pornind de la structurile de date cele mai uzuale i de la analizaeficienei algoritmilor, cartea se concentreaz pe principiile fundamentale deelaborare a algoritmilor: greedy, divide et impera, programare dinamic ,backtracking. Interesul nostru pentru inteligena artificial a fcut ca penultimulcapitol s fie, de fapt, o introducere din punct de vedere al algoritmilor nacest domeniu.

    Majoritatea algoritmilor selectai au o conotaie estetic. Efortul necesar pentrun elegerea elementelor mai subtile este uneori considerabil. Ce este ns unalgoritm estetic? Putem rspunde foarte simplu: un algoritm este estetic dacexprim mult n cuvinte puine. Un algoritm estetic este oare n mod necesar ieficient? Cartea rspunde i acestor ntrebri.

    n al doilea rnd, cartea prezintmecanismele interne eseniale ale limbajului C++

    (moteniri, legturi dinamice, clase parametrice, excepii) i trateazimplementarea algoritmilor n conceptul programrii orientate pe obiect. Totui,aceastcarte nu este un curs complet de C++ .

    Algoritmii nu sunt pur i simplu transcrii din pseudo-cod n limbajul C++ , cisunt regndii din punct de vedere al programrii orientate pe obiect. Sperm c,dupcitirea crii, vei dezvolta aplicaii de programare orientatpe obiect i ve ielabora implementri ale altor structuri de date. Programele* au fost scrise pentrulimbajul C++ descris de Ellis i Stroustrup n The Annotated C++ Reference

    Manual. Acest limbaj se caracterizeaz, n principal, prin introducerea claselorparametrice i a unui mecanism de tratare a excepiilor foarte avansat, facilit ideosebit de importante pentru dezvoltarea de biblioteci C++. Compilatoarele

    GNU C++ 2.5.8 (UNIX/Linux) i Borland C++

    3.1 (DOS) suport destul de bineclasele parametrice. Pentru tratarea excep iilor se pot utiliza compilatoareleBorland C++ 4.0 i, n viitorul apropiat, GNU C++ 2.7.1.

    Fr a face concesii rigorii matematice, prezentarea este intuitiv, cu numeroaseexemple. Am evitat, pe ct posibil, situa ia n care o carte de informatic ncepe

    * Fiierele sursale tuturor exemplelor aproximativ 3400 de linii n 50 de fiiere pot fi obinutepe o dischetMS-DOS, printr-o comandadresatediturii.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    8/294

    viii Principii de algoritmi i C++ Cuprins

    spre disperarea ne-matematicienilor cu celebrul Fie ... , sau cu o defini ie. Amncercat, pe de alt parte, s evitm situaia cnd totul este evident, sau sepoate demonstra. Fiecare capitol este conceput fluid, ca o mic poveste, cupu ine referine i note. Multe rezultate mai tehnice sunt ob inute ca exerciii.Algoritmii sunt prezentai ntr-un limbaj pseudo-cod compact, fr detalii inutile.Am adugat la sfritul fiecrui capitol numeroase exerciii, multe din ele cusoluii.

    Presupunem c cititorul are la baz cel puin un curs introductiv n programare,nefiindu-i strini termeni precum algoritm, recursivitate, funcie, procedur ipseudo-cod. Exist mai multe modalit i de parcurgere a crii. n funcie deinteresul i pregtirea cititorului, acesta poate alege oricare din prile referitoarela elaborarea, analiza, sau implementarea algoritmilor. Cu excep ia prilor deanaliz a eficienei algoritmilor (unde sunt necesare elemente de matematicisuperioare), cartea poate fi parcurs i de ctre un elev de liceu. Pentruparcurgerea seciunilor de implementare, este recomandabil cunoaterealimbajului C.

    Cartea noastr se bazeaz pe cursurile pe care le inem, ncepnd cu 1991, laSecia de electronic i calculatoare a Universit ii Transilvania din Braov. S-adovedit util i experiena noastr de peste zece ani n dezvoltarea produselorsoftware. Colectivul de procesare a imaginilor din ITC Bra ov a fost un excelentmediu n care am putut s ne dezvoltm profesional. Le mulumim pentru aceastacelor care au fcut parte, alturi de noi, din acest grup: Sorin Cisma, tefanJozsa, Eugen Carai. Nu putem snu ne amintim cu nostalgie de compilatorul C alfirmei DEC (pentru minicalculatoarele din seria PDP-11) pe care l-amdescoperit mpreun, cu zece ani n urm.

    Ca de obicei n astfel de situa ii, numrul celor care au contribuit ntr-un fel saualtul la realizarea acestei cri este foarte mare, cuprinznd profesorii notri,colegii de catedr, studenii pe care am testat cursurile, prietenii. Le mulumimtuturor. De asemenea, apreciem rbdarea celor care ne-au suportat n cei peste doiani de elaborare a crii.

    Sperm scitii aceastcarte cu aceeai plcere cu care ea a fost scris.

    Braov, ianuarie 1995Rzvan Andonie

    Ilie Grbacea*

    * Autorii pot fi contactai prin pot, la adresa: Universitatea Transilvania, Catedra de electronicicalculatoare, Politehnicii 1-3, 2200 Braov, sau prin E-mail, la adresa: algoritmi&[email protected]

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    9/294

    ix

    Cuprins

    1. PRELIMINARII 11.1 Ce este un algoritm? 1

    1.2 Eficiena algoritmilor 5

    1.3 Cazul mediu i cazul cel mai nefavorabil 61.4 Operaie elementar 8

    1.5 De ce avem nevoie de algoritmi eficieni? 9

    1.6 Exemple 101.6.1 Sortare 101.6.2 Calculul determinanilor 101.6.3 Cel mai mare divizor comun 111.6.4 Numerele lui Fibonacci 12

    1.7 Exerciii 13

    2. PROGRAMARE ORIENTATPE OBIECT 14

    2.1 Conceptul de obiect 142.2 Limbajul C++++++++ 15

    2.2.1 Diferenele dintre limbajele C i C++ 162.2.2 Intrri/ieiri n limbajul C++ 20

    2.3 Clase n limbajul C++++++++ 222.3.1 Tipul intErvaln limbajul C 232.3.2 Tipul intErvaln limbajul C++ 25

    2.4 Exerciii 34

    3. STRUCTURI ELEMENTARE DE DATE 373.1 Liste 37

    3.1.1 Stive 383.1.2 Cozi 39

    3.2 Grafuri 40

    3.3 Arbori cu rdcin 42

    3.4 Heap-uri 45

    3.5 Structuri de mulimi disjuncte 49

    3.6 Exerciii 53

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    10/294

    x Principii de algoritmi i C++ Cuprins

    4. TIPURI ABSTRACTE DE DATE 564.1 Tablouri 56

    4.1.1 Alocarea dinamica memoriei 574.1.2 Clasa tablou 604.1.3 Clasa parametrictablou 63

    4.2 Stive, cozi, heap-uri 684.2.1 Clasele stivai coada 694.2.2 Clasa heap 73

    4.3 Clasalista

    784.4 Exerciii 84

    5. ANALIZA EFICIENEI ALGORITMILOR 895.1 Notaia asimptotic 89

    5.1.1 O notaie pentru ordinul lui 895.1.2 Notaia asimptoticcondiionat 91

    5.2 Tehnici de analiza algoritmilor 945.2.1 Sortarea prin selecie 945.2.2 Sortarea prin inserie 945.2.3 Heapsort 955.2.4 Turnurile din Hanoi 97

    5.3 Analiza algoritmilor recursivi 985.3.1 Metoda iteraiei 985.3.2 Inducia constructiv 985.3.3 Recurene liniare omogene 995.3.4 Recurene liniare neomogene 1015.3.5 Schimbarea variabilei 103

    5.4 Exerciii 105

    6. ALGORITMI GREEDY 1136.1 Tehnica greedy 113

    6.2 Minimizarea timpului mediu de ateptare 115

    6.3 Interclasarea optima irurilor ordonate 116

    6.4 Implementarea arborilor de interclasare 119

    6.5 Coduri Huffman 122

    6.6 Arbori pariali de cost minim 1246.6.1 Algoritmul lui Kruskal 1256.6.2 Algoritmul lui Prim 128

    6.7 Implementarea algoritmului lui Kruskal 130

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    11/294

    Cuprins Principii de algoritmi i C++ xi

    6.8 Cele mai scurte drumuri care pleacdin acelai punct 134

    6.9 Implementarea algoritmului lui Dijkstra 137

    6.10 Euristica greedy 1436.10.1 Colorarea unui graf 1436.10.2 Problema comis-voiajorului 144

    6.11 Exerciii 145

    7. ALGORITMI DIVIDE ET IMPERA 1497.1 Tehnica divide et impera 149

    7.2 Cutarea binar 151

    7.3 Mergesort (sortarea prin interclasare) 153

    7.4 Mergesort n clasele tabloui lista 1547.4.1 O soluie neinspirat 1547.4.2 Tablouri sortabile i liste sortabile 159

    7.5 Quicksort (sortarea rapid) 161

    7.6 Selecia unui element dintr-un tablou 164

    7.7 O problemde criptologie 169

    7.8 nmulirea matricilor 172

    7.9 nmulirea numerelor ntregi mari 174

    7.10 Exerciii 177

    8. ALGORITMI DE PROGRAMARE DINAMIC 1858.1 Trei principii fundamentale ale programrii dinamice 185

    8.2 O competiie 187

    8.3 nmulirea nlnuita matricilor 189

    8.4 Tablouri multidimensionale 193

    8.5 Determinarea celor mai scurte drumuri ntr-un graf 198

    8.6 Arbori binari optimi de cutare 200

    8.7 Arborii binari de cutare ca tip de dat 2048.7.1 Arborele optim 2068.7.2 Cutarea n arbore 2118.7.3 Modificarea arborelui 215

    8.8 Programarea dinamiccomparatcu tehnica greedy 219

    8.9 Exerciii 221

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    12/294

    xii Principii de algoritmi i C++ Cuprins

    9. EXPLORRI N GRAFURI 2279.1 Parcurgerea arborilor 227

    9.2 Operaii de parcurgere n clasa arbore 229

    9.3 Parcurgerea grafurilor n adncime 2319.3.1 Puncte de articulare 2339.3.2 Sortarea topologic 234

    9.4 Parcurgerea grafurilor n lime 235

    9.5 Salvarea i restaurarea arborilor binari de cutare 2379.6 Backtracking 239

    9.7 Grafuri i jocuri 2439.7.1 Jocul nim 2439.7.2 ahul i tehnica minimax 247

    9.8 Grafuri AND/OR 249

    9.9 Exerciii 251

    10. DERIVARE PUBLIC, FUNCII VIRTUALE 25510.1 Ciurul lui Eratostene 255

    10.2 Tablouri iniializate virtual 260

    10.2.1 Structura 26110.2.2 Implementarea (o variantde nota ase) 26210.2.3 tablouVIca subtip al tipului tablou 266

    10.3 Exerciii 269

    EPILOG 271

    BIBLIOGRAFIE SELECTIV 273

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    13/294

    xiii

    Lista de notaii

    #T numrul de elemente din tabloul (sau mulimea) T

    i. . j interval de ntregi: {kN| ikj}

    mmod n restul mpririi ntregi a lui mla n

    div mprirea ntreag| x | mrimea cazului x

    log logaritm ntr-o bazoarecare (n contextul notaiei

    asimptotice)

    lg logaritm n baza 2

    ln logaritm natural

    lg logaritm iterat (vezi Seciunea 3.5)

    n

    k

    combinri de nluate cte k

    R mul imea numerelor reale nenegative

    N+, R+ mul imea numerelor naturale (reale) strict pozitive

    B mul imea constantelor booleene {true, false}

    (x) | [P(x)] existun xastfel nct P(x)

    (x) | [P(x)] pentru orice xastfel nct P(x)

    x cel mai mare ntreg mai mic sau egal cu x

    x cel mai mic ntreg mai mare sau egal cu x

    O, , notaie asimptotic(vezi Seciunea 5.1.1) atribuire

    (a, b) muchia unui graf orientat

    {a, b} muchia unui graf neorientat

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    14/294

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    15/294

    1

    1. Preliminarii

    1.1 Ce este un algoritm?

    Abu Ja`far Mohammed ibn Mus al-Khowrizm (autor persan, sec. VIII-IX), ascris o carte de matematic cunoscut n traducere latin ca Algorithmi denumero indorum, iar apoi ca Liber algorithmi, unde algorithm provine de laal-Khowrizm, ceea ce literal nseamn din oraul Khowrizm. n prezent,acest ora se numete Khiva i se afl n Uzbechistan. Att al-Khowrizm, ct ial i matematicieni din Evul Mediu, n elegeau prin algoritm o regul pe bazacreia se efectuau calcule aritmetice. Astfel, n timpul lui Adam Riese (sec. XVI),algoritmii foloseau la: dublri, njumt iri, nmuliri de numere. Ali algoritmiapar n lucrrile lui Stifer (Arithmetica integra, Nrnberg, 1544) i Cardano(Ars magna sive de reguli algebraicis, Nrnberg, 1545). Chiar i Leibnizvorbete de algoritmi de nmulire. Termenul a rmas totui mult vreme cu o

    ntrebuinare destul de restrns, chiar i n domeniul matematicii.

    Kronecker (n 1886) i Dedekind (n 1888) semneaz actul de natere al teorieifunciilor recursive. Conceptul de recursivitate devine indisolubil legat de cel dealgoritm. Dar abia n deceniile al treilea i al patrulea ale secolului nostru, teoriarecursivit ii i algoritmilor ncepe s se constituie ca atare, prin lucrrile luiSkolem, Ackermann, Sudan, Gdel, Church, Kleene, Turing, Peter i al ii.

    Este surprinztoare transformarea gndirii algoritmice, dintr-un instrumentmatematic particular, ntr-o modalitate fundamentalde abordare a problemelor ndomenii care aparent nu au nimic comun cu matematica. Aceast universalitate agndirii algoritmice este rezultatul conexiunii dintre algoritm i calculator. Astzi,

    n elegem prin algoritm o metod general de rezolvare a unui anumit tip deproblem, metod care se poate implementa pe calculator. n acest context, unalgoritm este esena absoluta unei rutine.

    Cel mai faimos algoritm este desigur algoritmul lui Euclid pentru aflarea celui maimare divizor comun a dou numere ntregi. Alte exemple de algoritmi suntmetodele nvate n coalpentru a nmuli/mpri dounumere. Ceea ce d nsgeneralitate noiunii de algoritm este faptul cel poate opera nu numai cu numere.Exist astfel algoritmi algebrici i algoritmi logici. Pn i o reet culinar este

    n esen un algoritm. Practic, s-a constatat cnu existnici un domeniu, orict arprea el de imprecis i de fluctuant, n care s nu putem descoperi sectoarefuncionnd algoritmic.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    16/294

    2 Preliminarii Capitolul 1

    Un algoritm este compus dintr-o mulime finitde pai, fiecare necesitnd una saumai multe operaii. Pentru a fi implementabile pe calculator, aceste operaiitrebuie s fie n primul rnd definite, adic s fie foarte clar ce anume trebuieexecutat. n al doilea rnd, opera iile trebuie sfie efective , ceea ce nseamnc

    n pr incipiu, cel pu in o persoan dotat cu creion i hrtie trebuie s poatefectua orice pas ntr-un timp finit. De exemplu, aritmetica cu numere ntregi esteefectiv. Aritmetica cu numere reale nu este ns efectiv, deoarece unele numeresunt exprimabile prin secvene infinite. Vom considera c un algoritm trebuie sse termine dupun numr finit de operaii, ntr-un timp rezonabil de lung.

    Programul este exprimarea unui algoritm ntr-un limbaj de programare. Este bineca nainte de a nva concepte generale, s fi acumulat deja o anumitexperien practic n domeniul respectiv. Presupunnd c ai scris deja programe ntr-unlimbaj de nivel nalt, probabil c ai avut uneori dificult i n a formula soluiapentru o problem. Alteori, poate cnu ai putut decide care dintre algoritmii carerezolvau aceeai problemeste mai bun. Aceastcarte vva nva cum sevitaiaceste situaii nedorite.

    Studiul algoritmilor cuprinde mai multe aspecte:

    i) Elaborarea algoritmilor. Actul de creare a unui algoritm este o art care nuva putea fi niciodat pe deplin automatizat. Este n fond vorba demecanismul universal al creativit ii umane, care produce noul printr-osintezextrem de complexde tipul:

    tehnici de elaborare (reguli) + creativitate (intuiie) = soluie.Un obiectiv major al acestei cri este de a prezenta diverse tehnicifundamentale de elaborare a algoritmilor. Utiliznd aceste tehnici, acumulndi o anumitexperien , vei fi capabili sconcepei algoritmi eficieni.

    ii) Exprimarea algoritmilor. Forma pe care o ia un algoritm ntr-un programtrebuie s fie clar i concis, ceea ce implic utilizarea unui anumit stil deprogramare. Acest stil nu este n mod obligatoriu legat de un anumit limbaj deprogramare, ci, mai curnd, de tipul limbajului i de modul de abordare.Astfel, ncepnd cu anii 80, standardul unanim acceptat este cel deprogramare structurat. n prezent, se impune standardul programriiorientate pe obiect.

    iii) Validarea algoritmilor. Un algoritm, dup elaborare, nu trebuie n modnecesar s fie programat pentru a demonstra c funcioneaz corect n oricesituaie. El poate fi scris iniial ntr-o form precis oarecare. n aceastform, algoritmul va fi validat, pentru a ne asigura c algoritmul este corect,independent de limbajul n care va fi apoi programat.

    iv) Analiza algoritmilor. Pentru a putea decide care dintre algoritmii ce rezolv aceeai problemeste mai bun, este nevoie sdefinim un criteriu de aprecierea valorii unui algoritm. n general, acest criteriu se refer la timpul de calculi la memoria necesar unui algoritm. Vom analiza din acest punct de vedereto i algoritmii prezentai.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    17/294

    Seciunea 1.1 Ce este un algoritm? 3

    v) Testarea programelor. Aceasta constdin dou faze: depanare (debugging) itrasare (profiling). Depanarea este procesul executrii unui program pe datede test i corectarea eventualelor erori. Dupcum afirma nsE. W. Dijkstra,prin depanare putem evidenia prezena erorilor, dar nu i absena lor. Odemonstrare a faptului c un program este corect este mai valoroas dect omie de teste, deoarece garanteaz c programul va funciona corect n oricesituaie. Trasarea este procesul executrii unui program corect pe diferitedate de test, pentru a-i determina timpul de calcul i memoria necesar.Rezultatele obinute pot fi apoi comparate cu analiza anterioar aalgoritmului.

    Aceast enumerare servete fixrii cadrului general pentru problemele abordate ncarte: ne vom concentra pe domeniile i) , ii)i iv).

    Vom ncepe cu un exemplu de algoritm. Este vorba de o metod, cam ciudat laprima vedere, de nmulire a dounumere. Se numete nmulirea a la russe.

    Vom scrie denmulitul i nmulitorul (de exemplu 45 i 19) unul lng altul,formnd sub fiecare cte o coloan, conform urmtoarei reguli: se mpartenumrul de sub denmulit la 2, ignornd fraciile, apoi se nmulete cu 2 numrul

    de sub nmulitor. Se aplicregula, pncnd numrul de sub denmulit este 1. nfinal, adunm toate numerele din coloana nmul itorului care corespund, pe linie,unor numere impare n coloana denmulitului. n cazul nostru, obinem:19 +76 +152 +608 = 855.

    Cu toate c pare ciudat, aceasta este tehnica folosit de hardware-ul multorcalculatoare. Ea prezint avantajul c nu este necesar s se memoreze tabla de

    nmul ire. Totul se rezum la adunri i nmuliri/mpriri cu 2 (acestea din urmfiind rezolvate printr-o simpldecalare).

    Pentru a reprezenta algoritmul, vom utiliza un limbaj simplificat, numitpseudo-cod, care este un compromis ntre precizia unui limbaj de programare iuurina n exprimare a unui limbaj natural. Astfel, elementele eseniale alealgoritmului nu vor fi ascunse de detalii de programare neimportante n aceastfaz. Dacsuntei familiarizat cu un limbaj uzual de programare, nu ve i avea nici

    45 19 19

    22 38

    11 76 765 152 152

    2 304

    1 608 608

    855

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    18/294

    4 Preliminarii Capitolul 1

    o dificultate n a nelege notaiile folosite i n a scrie programul respectiv.Cunoate i atunci i diferena dintre o funcie i o procedur. n notaia pe care ofolosim, o funcie va returna uneori un tablou, o mulime, sau un mesaj. Vei

    n elege ceste vorba de o scriere mai compacti n funcie de context vei puteaalege implementarea convenabil. Vom conveni ca parametrii funciilor(procedurilor) s fie transmii prin valoare, exceptnd tablourile, care vor fitransmise prin adresa primului element. Notaia folosit pentru specificarea unuiparametru de tip tablou va fi diferit, de la caz la caz. Uneori vom scrie, deexemplu:

    procedure proc1(T)

    atunci cnd tipul i dimensiunile tabloului T sunt neimportante, sau cnd acesteasunt evidente din context. ntr-un astfel de caz, vom nota cu #T numrul deelemente din tabloului T. Dac limitele sau tipul tabloului sunt importante, vomscrie:

    procedure proc2(T[1 .. n])

    sau, mai general:

    procedure proc3(T[a .. b])

    n aceste cazuri, n, aib vor fi considerai parametri formali.

    De multe ori, vom atribui unor elemente ale unui tablou Tvalorile , n elegnd

    prin acestea dou valori numerice extreme, astfel nct pentru oricare alt elementT[i] avem < T[i] < + .

    Pentru simplitate, vom considera uneori c anumite variabile sunt globale, astfelnct sle putem folosi n mod direct n proceduri.

    Iatacum i primul nostru algoritm, cel al nmulirii a la russe:

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    19/294

    Seciunea 1.1 Ce este un algoritm? 5

    functionrusse(A, B)arraysX, Y{iniializare}

    X[1] A; Y[1] Bi1 {se construiesc cele doucoloane}whileX[i] > 1 do

    X[i+1] X[i] div2 {divreprezintmprirea ntreag}Y[i+1] Y[i]+Y[i]ii+1

    {adunnumerele Y[i] corespunztoare numerelor X[i] impare}prod 0whilei> 0 do

    if X[i] este impar thenprod prod+Y[i]i i1

    return prod

    Un programator cu experien va observa desigur c tablourile X i Y nu sunt defapt necesare i c programul poate fi simplificat cu uurin . Acest algoritmpoate fi programat deci n mai multe feluri, chiar folosind acelai limbaj deprogramare.

    Pe lng algoritmul de nmulire nvat n coal, iat c mai avem un algoritmcare face acelai lucru. Existmai muli algoritmi care rezolvo problem, dar i

    mai multe programe care pot descrie un algoritm.Acest algoritm poate fi folosit nu doar pentru a nmul i pe 45 cu 19, dar i pentrua nmuli orice numere ntregi pozitive. Vom numi (45, 19) un caz (instance).Pentru fiecare algoritm exist un domeniu de definiie al cazurilor pentru carealgoritmul funcioneaz corect. Orice calculator limiteaz mrimea cazurilor cucare poate opera. Aceastlimitare nu poate fi nsatribuitalgoritmului respectiv.nco dat, observm cexisto diferen esenia lntre programe i algoritmi.

    1.2 Eficiena algoritmilor

    Ideal este ca, pentru o problem dat, s gsim mai muli algoritmi, iar apoi s-lalegem dintre acetia pe cel optim. Care este ns criteriul de comparaie?Eficiena unui algoritm poate fi exprimat n mai multe moduri. Putem analiza a

    posteriori (empiric) comportarea algoritmului dup implementare, prin rularea pecalculator a unor cazuri diferite. Sau, putem analiza a priori(teoretic) algoritmul,

    naintea programrii lui, prin determinarea cantitativa resurselor (timp, memorieetc) necesare ca o funcie de mrimea cazului considerat.

    Mrimea unui caz x, notat cu |x |, corespunde formal numrului de bii necesaripentru reprezentarea lui x, folosind o codificare precis definit i rezonabil de

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    20/294

    6 Preliminarii Capitolul 1

    compact. Astfel, cnd vom vorbi despre sortare, |x | va fi numrul de elementede sortat. La un algoritm numeric, |x| poate fi chiar valoarea numeric a cazului

    x.

    Avantajul analizei teoretice este faptul cea nu depinde de calculatorul folosit, delimbajul de programare ales, sau de ndemnarea programatorului. Ea salveaztimpul pierdut cu programarea i rularea unui algoritm care se dovedete n finalineficient. Din motive practice, un algoritm nu poate fi testat pe calculator pentrucazuri orict de mari. Analiza teoretic ne permite ns studiul eficieneialgoritmului pentru cazuri de orice mrime.

    Este posibil s analizm un algoritm i printr-o metod hibrid. n acest caz,forma funciei care descrie eficiena algoritmului este determinat teoretic, iarvalorile numerice ale parametrilor sunt apoi determinate empiric. Aceastmetodpermite o predicie asupra comportrii algoritmului pentru cazuri foarte mari, carenu pot fi testate. O extrapolare doar pe baza testelor empirice este foarteimprecis.

    Este natural s ntrebm ce unitate trebuie folosit pentru a exprima eficienateoretic a unui algoritm. Un rspuns la aceast problem este dat de principiulinvarianei , potrivit cruia dou implementri diferite ale aceluiai algoritm nudifer n eficien cu mai mult de o constant multiplicativ. Adic, presupunndcavem douimplementri care necesitt1(n) i, respectiv, t2(n) secunde pentru a

    rezolva un caz de mrime n, atunci exist ntotdeauna o constant pozitiv c,

    astfel nct t1(n) ct2(n) pentru orice n suficient de mare. Acest principiu estevalabil indiferent de calculatorul (de construcie convenional) folosit, indiferentde limbajul de programare ales i indiferent de ndemnarea programatorului(presupunnd c acesta nu modific algoritmul!). Deci, schimbarea calculatoruluine poate permite s rezolvm o problem de 100 de ori mai repede, dar numaimodificarea algoritmului ne poate aduce o mbuntire care sdevindin ce n cemai marcantpe msurce mrimea cazului soluionat crete.

    Revenind la problema unit ii de msur a eficienei teoretice a unui algoritm,ajungem la concluzia c nici nu avem nevoie de o astfel de unitate: vom exprimaeficiena n limitele unei constante multiplicative. Vom spune c un algoritmnecesit timp n ordinul lu i t, pentru o funcie t dat, dac exist o constantpozitiv c i o implementare a algoritmului capabil s rezolve fiecare caz al

    problemei ntr-un timp de cel mult ct(n) secunde, unde n este mrimea cazuluiconsiderat. Utilizarea secundelor n aceast definiie este arbitrar, deoarecetrebuie smodificm doar constanta pentru a mrgini timpul la at(n) ore, sau bt(n)microsecunde. Datorit principiului invarianei, orice alt implementare aalgoritmului va avea aceeai proprietate, cu toate c de la o implementare la altase poate modifica constanta multiplicativ. n Capitolul 5 vom reveni mai rigurosasupra acestui important concept, numit notaie asimptotic.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    21/294

    Seciunea 1.2 Eficiena algoritmilor 7

    Dacun algoritm necesittimp n ordinul lui n, vom spune cnecesittimp liniar,iar algoritmul respectiv putem s-l numim algoritm liniar. Similar, un algoritmeste ptratic, cubic, polinomial , sau exponenia ldac necesit timp n ordinul lui

    n2, n3, nk, respectiv cn, unde ki csunt constante.

    Un obiectiv major al acestei cri este analiza teoretic a eficienei algoritmilor.Ne vom concentra asupra criteriului timpului de execu ie. Alte resurse necesare(cum ar fi memoria) pot fi estimate teoretic ntr-un mod similar. Se pot pune iprobleme de compromis memorie - timp de execuie.

    1.3 Cazul mediu i cazul cel mai nefavorabil

    Timpul de execuie al unui algoritm poate varia considerabil chiar i pentru cazuride mrime identic. Pentru a ilustra aceasta, vom considera doi algoritmielementari de sortare a unui tablou Tde nelemente:

    procedure insert(T[1 .. n])fori 2 to n do

    x T[i]; ji1whilej > 0and x < T[ j] do

    T[ j+1] T[ j]

    jj1T[ j+1] x

    procedure select (T[1 .. n])fori 1 to n1 do

    minji;minxT[i]for ji+1 to ndo

    ifT[ j] < minxthen minj jminx T[ j]

    T[minj] T[i]T[i] minx

    Ideea general a sortri iprin inserie este s considerm pe rnd fiecare elemental

    irului

    i s

    l inser

    m n sub

    irul ordonat creat anterior din elementele

    precedente. Operaia de inserare implic deplasarea spre dreapta a unei secven e.Sortarea prin selecie lucreazaltfel, plasnd la fiecare pas cte un element directpe poziia lui final.

    Fie U i V dou tablouri de n elemente, unde U este deja sortat cresctor, iar Veste sortat descresctor. Din punct de vedere al timpului de execuie, Vreprezintcazul cel mai nefavorabil iar Ucazul cel mai favorabil.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    22/294

    8 Preliminarii Capitolul 1

    Vom vedea mai trziu c timpul de execuie pentru sortarea prin selecie esteptratic, independent de ordonarea iniia l a elementelor. Testul ifT[ j]

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    23/294

    Seciunea 1.4 Operaie elementar 9

    function Wilson(n){returneaztruedaci numai dacneste prim}if ndivide ((n1)! +1) then returntrue

    else returnfalse

    Dac considerm calculul factorialului i testul de divizibilitate ca opera iielementare, atunci eficiena testului de primalitate este foarte mare. Dacconsiderm c factorialul se calculeaz n funcie de mrimea lui n, atuncieficiena testului este mai slab. La fel i cu testul de divizibilitate.

    Deci, este foarte important ce anume definim ca opera ie elementar. Este oare

    adunarea o operaie elementar? n teorie, nu, deoarece i ea depinde de lungimeaoperanzilor. Practic, pentru operanzi de lungime rezonabil (determinatde modulde reprezentare intern), putem s considerm c adunarea este o operaieelementar. Vom considera n continuare c adunrile, scderile, nmulirile,

    mpririle, operaiile modulo (restul mpririi ntregi), operaiile booleene,comparaiile i atribuirile sunt operaii elementare.

    1.5 De ce avem nevoie de algoritmi eficieni?

    Performanele hardware-ului se dubleaz la aproximativ doi ani. Mai are sensatunci s investim n obinerea unor algoritmi eficieni? Nu este oare mai simplusateptm urmtoarea generaie de calculatoare?

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    24/294

    10 Preliminarii Capitolul 1

    S presupunem c pentru rezolvarea unei anumite probleme avem un algoritmexponenial i un calculator pe care, pentru cazuri de mrime n, timpul de rulare

    este de 104 2n secunde. Pentru n = 10, este nevoie de 1/10 secunde. Pentrun = 20, sunt necesare aproape 2 minute. Pentru n = 30, o zi nu este de ajuns, iarpentru n= 38, chiar i un an ar fi insuficient. Cumprm un calculator de 100 de

    ori mai rapid, cu timpul de rulare de 10 6 2n secunde. Dar i acum, pentrun= 45, este nevoie de mai mult de un an! n general, dac n cazul mainii vechi

    ntr-un timp anumit se putea rezolva problema pentru cazul n, pe noul calculator,n acest timp, se poate rezolva cazul n+7.

    S presupunem acum c am gsit un algoritm cubic care rezolv, pe calculatorulvechi, cazul de mrime n n 102 n3 secunde. n Figura 1.1, putem urmri cumevolueaz timpul de rulare n funcie de mrimea cazului. Pe durata unei zile,rezolvm acum cazuri mai mari dect 200, iar n aproximativ un an am putearezolva chiar cazul n = 1500. Este mai profitabil s investim n noul algoritmdect ntr-un nou hardware. Desigur, dac ne permitem s investim att nsoftware ct i n hardware, noul algoritm poate fi rulat i pe noua main. Curba

    104 n3reprezintaceastdin urmsituaie.

    Pentru cazuri de mrime mic, uneori este totui mai rentabil s investim ntr-o

    Figura 1.1Algoritmi sau hardware?

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    25/294

    Seciunea 1.5 De ce avem nevoie de algoritmi eficieni? 11

    nou main, nu i ntr-un nou algoritm. Astfel, pentru n= 10, pe maina veche,algoritmul nou necesit 10 secunde, adic de o sut de ori mai mult dectalgoritmul vechi. Pe vechiul calculator, algoritmul nou devine mai performantdoar pentru cazuri mai mari sau egale cu 20.

    1.6 Exemple

    Poate cvntrebai daceste ntr-adevr posibil saccelerm att de spectaculos

    un algoritm. Rspunsul este afirmativ i vom da cteva exemple.

    1.6.1 Sortare

    Algoritmii de sortare prin inserie i prin selecie necesit timp ptratic, att ncazul mediu, ct i n cazul cel mai nefavorabil. Cu toate c aceti algoritmi suntexceleni pentru cazuri mici, pentru cazuri mari avem algoritmi mai eficieni. ncapitolele urmtoare vom analiza i al i algoritmi de sortare: heapsort, mergesort,quicksort. To i acetia necesit un timp mediu n ordinul lui n log n, iar heapsorti mergesortnecesittimp n ordinul lui n log ni n cazul cel mai nefavorabil.

    Pentru a ne face o idee asupra diferenei dintre un timp ptratic i un timp n

    ordinul lui n log n, vom meniona c, pe un anumit calculator, quicksort a reuits sorteze n 30 de secunde 100.000 de elemente, n timp ce sortarea prin inser iear fi durat, pentru acelai caz, peste nou ore. Pentru un numr mic de elemente

    ns, eficiena celor dousortri este asemntoare.

    1.6.2 Calculul determinanilor

    Fie det( M ) determinantul matricii

    M= (aij)i, j = 1, , n

    i fie Mij submatricea de (n1) (n1) elemente, obinut din M prin tergerea

    celei de-a i-a linii i celei de-a j-a coloane. Avem binecunoscuta defini ierecursiv

    det( ) ( ) det( )M a Mj j jj

    n

    = +

    =

    1 1 1 11

    Dac folosim aceast relaie pentru a evalua determinantul, ob inem un algoritmcu timp n ordinul lui n!, ceea ce este mai ru dect exponenial. O alt metodclasic, eliminarea Gauss-Jordan, necesit timp cubic. Pentru o anumit

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    26/294

    12 Preliminarii Capitolul 1

    implementare s-a estimat c, n cazul unei matrici de 20 20 elemente, n timp cealgoritmul Gauss-Jordan dureaz 1/20 secunde, algoritmul recursiv ar dura maimult de 10 milioane de ani!

    Nu trebuie tras de aici concluzia c algoritmii recursivi sunt n mod necesarneperforman i. Cu ajutorul algoritmului recursiv al lui Strassen, pe care l vomstudia i noi n Seciunea 7.8, se poate calcula det( M ) ntr-un timp n ordinul lui

    nlg 7, unde lg 7 2,81, deci mai eficient dect prin eliminarea Gauss-Jordan.

    1.6.3

    Cel mai mare divizor comun

    Un prim algoritm pentru aflarea celui mai mare divizor comun al ntregilorpozitivi mi n, notat cu cmmdc(m, n), se bazeazpe definiie:

    functioncmmdc-def (m, n)i min(m, n) +1repeat i i1 untilidivide pe mi nreturn i

    Timpul este n ordinul diferenei dintre min(m, n) i cmmdc(m, n).

    Exist, din fericire, un algoritm mult mai eficient, care nu este altul dect celebrulalgoritm al lui Euclid.

    functionEuclid(m, n)ifn= 0 then returnm

    else returnEuclid(n, mmod n)

    Prin m mod n notm restul mpririi ntregi a lui m la n. Algoritmul funcioneazpentru orice ntregi nenuli mi n, avnd la baz cunoscuta proprietate

    cmmdc(m, n) = cmmdc(n, mmodn)

    Timpul este n ordinul logaritmului lui min(m, n), chiar i n cazul cel mainefavorabil, ceea ce reprezint o mbunt ire substania l fa de algoritmulprecedent. Pentru a fi exaci, trebuie s men ionm c algoritmul originar al luiEuclid (descris n Elemente, aprox. 300 a.Ch.) opereazprin scderi succesive,i nu prin mprire. Interesant este faptul c acest algoritm se pare c provine

    dintr-un algoritm i mai vechi, datorat lui Eudoxus (aprox. 375 a.Ch.).

    1.6.4 Numerele lui Fibonacci

    irul lui Fibonacci este definit prin urmtoarea recuren :

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    27/294

    Seciunea 1.6 Exemple 13

    f f

    f f f nn n n

    0 1

    1 2

    0 1

    2

    = =

    = +

    ;

    pentru

    Acest celebru ir a fost descoperit n 1202 de ctre Leonardo Pisano (Leonardodin Pisa), cunoscut sub numele de Leonardo Fibonacci. Cel de-al n- lea termen alirului se poate obine direct din definiie:

    functionfib1(n)ifn < 2 then returnn

    else returnfib1(n1) +fib1(n2)

    Aceast metod este foarte ineficient, deoarece recalculeaz de mai multe oriaceleai valori. Vom arta n Seciunea 5.3.1 c timpul este n ordinul lui n, unde

    = (1+ 5 )/2 este seciunea de aur, deci este un timp exponenial.

    Iat acum o alt metod, mai performant, care rezolv aceeai problem ntr-untimp liniar.

    functionfib2(n)i1 ; j 0fork 1 to ndo j i + j

    ij ireturnj

    Mai mult, exist i un algoritm cu timp n ordinul lui log n, algoritm pe care lvom argumenta nsabia n Capitolul 7:

    functionfib3(n)i1 ; j 0; k 0; h1whilen > 0 do

    ifneste impar then tjhjih+jk+tiik+t

    t h2h 2kh+t

    k k2+t

    nn div2return j

    V recomandm s comparai aceti trei algoritmi, pe calculator, pentru diferitevalori ale lui n.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    28/294

    14 Preliminarii Capitolul 1

    1.7 Exerciii

    1.1 Aplicai algoritmii insert i select pentru cazurile T = [1, 2, 3, 4, 5, 6] iU = [6, 5, 4, 3, 2, 1]. Asigurai-vca i neles cum funcioneaz.

    1.2 nmulirea a la russe este cunoscut nc din timpul Egiptului antic,fiind probabil un algoritm mai vechi dect cel al lui Euclid. ncerca i s nelegei

    ra ionamentul care stla baza acestui algoritm de nmulire.

    Indicaie:Facei legtura cu reprezentarea binar.

    1.3 n algoritmul Euclid, este important ca nm?

    1.4 Elaborai un algoritm care s returneze cel mai mare divizor comun a treintregi nenuli .

    Soluie:

    functionEuclid-trei(m, n, p)return Euclid(m, Euclid(n, p))

    1.5 Programai algoritmul fib1 n dou limbaje diferite i rulai comparativcele dou programe, pe mai multe cazuri. Verifica i dac este valabil principiulinvarianei.

    1.6 Elaborai un algoritm care returneaz cel mai mare divizor comun a doitermeni de rang oarecare din irul lui Fibonacci.

    Indicaie: Un algoritm eficient se ob ine folosind urmtoarea proprietate*,valabilpentru oricare doi termeni ai irului lui Fibonacci:

    cmmdc( fm, fn) = fcmmdc(m, n)

    1.7 Fie matricea M=

    0 1

    1 1. Calculai produsul vectorului ( fn1, fn) cu

    matricea Mm , unde fn1 i fn sunt doi termeni consecutivi oarecare ai irului lui

    Fibonacci.

    * Aceastsurprinztoare proprietate a fost descoperitn 1876 de Lucas.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    29/294

    14

    2. Programareorientatpe obiect

    Dei aceast carte este dedicat n primul rnd analizei i elaborrii algoritmilor,am considerat util s folosim numeroii algoritmi care sunt studiai ca un pretextpentru introducerea elementelor de baz ale programrii orientate pe obiect n

    limbajul C++ . Vom prezenta n capitolul de fa noiuni fundamentale legate deobiecte, limbajul C++ i de abstractizarea datelor n C++ , urmnd ca, pe bazaunor exemple detaliate, s conturm n capitolele urmtoare din ce n ce mai clartehnica programrii orientate pe obiect. Scopul urmrit este de a surprinde aceleaspecte strict necesare formrii unei impresii juste asupra programrii orientate peobiect n limbajul C++ , i nu de a substitui cartea de fa unui curs complet deC++ .

    2.1 Conceptul de obiect

    Activitatea de programare a calculatoarelor a aprut la sfritul anilor 40.Primele programe au fost scrise n limbaj main i de aceea depindeau n

    ntregime de arhitectura calculatorului pentru care erau concepute. Tehnicile deprogramare au evoluat apoi n mod natural spre o tot mai net separare ntreconceptele manipulate de programe i reprezentrile acestor concepte ncalculator.

    n faa complexit ii crescnde a problemelor care se cereau soluionate,structurarea programelor a devenit indispensabil. coala de programare Algol apropus la nceputul anilor 60 o abordare devenit ntre timp clasic. Conformcelebrei ecuaii a lui Niklaus Wirth:

    algoritmi+structuri de date= programe

    un program este format din doupri total separate: un ansamblu de proceduri iun ansamblu de date asupra crora acioneazprocedurile. Procedurile sunt priviteca i cutii negre, fiecare avnd de rezolvat o anumit sarcin (de fcut anumiteprelucrri). Aceast modalitate de programare se numete programare dirijatdeprelucrri . Evoluia calculatoarelor i a problemelor de programare a fcut ca naproximativ zece ani programarea dirijat de prelucrri s devin ineficient.Astfel, chiar dacun limbaj ca Pascal-ul permite o bunstructurare a programului

    n proceduri, este posibil ca o schimbare relativ minor n structura datelor sprovoace o dezorganizare majora procedurilor.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    30/294

    Seciunea 2.1 Conceptul de obiect 15

    Inconvenientele programrii dirijate de prelucrri sunt eliminate prinncapsularea datelor i a procedurilor care le manipuleaz ntr-o singur entitatenumitobiect. Lumea exterioar obiectului are acces la datele sau procedurile luidoar prin intermediul unor operaii care constituie interfaa obiectului.Programatorul nu este obligat s cunoasc reprezentarea fizic a datelor iprocedurilor utilizate, motiv pentru care poate trata obiectul ca pe o cutie neagr cu un comportament bine precizat. Aceast caracteristic permite realizarea unortipuri abstracte de date. Este vorba de obiecte nzestrate cu o interfa prin carese specific interaciunile cu exteriorul, singura modalitate de a comunica cu unastfel de obiect fiind invocarea interfeei sale. n terminologia specific

    programrii orientate pe obiect, procedurile care formeazinterfaa unui obiect senumesc metode. Obiectul este singurul responsabil de maniera n care seefectueaz operaiile asupra lui. Apelul unei metode este doar o cerere, un mesajal apelantului care solicit executarea unei anumite aciuni. Obiectul poate refuzas o execute, sau, la fel de bine, o poate transmite unui alt obiect. n acestcontext, programarea devine dirijat de date, i nu de prelucrrile care trebuierealizate.

    Utilizarea consecventa obiectelor conferprogramrii urmtoarele calit i:

    Abstractizarea datelor. Nu este nevoie de a cunoate implementarea ireprezentarea intern a unui obiect pentru a-i adresa mesaje. Obiectul decidesingur maniera de execuie a operaiei cerute n functie de implementareafizic. Este posibil suprancrcarea metodelor, n sensul c la aceleai mesaje,

    obiecte diferite rspund n mod diferit. De exemplu, este foarte comod de adesemna printr-un simbol unic, +, adunarea ntregilor, concatenarea irurilorde caractere, reuniunea mulimilor etc.

    Modularitate . Structura programului este determinat n mare msur deobiectele utilizate. Schimbarea definiiilor unor obiecte se poate face cu unminim de implicaii asupra celorlalte obiecte utilizate n program.

    Flexibilitate. Un obiect este definit prin comportamentul su graie existeneiunei interfee explicite. El poate fi foarte uor introdus ntr-o bibliotecpentrua fi utilizat ca atare, sau pentru a construi noi tipuri prin motenire, adicprinspecializare i compunere cu obiecte existente.

    Claritate. ncapsularea, posibilitatea de suprancrcare i modularitateantresc claritatea programelor. Detaliile de implementare sunt izolate de

    lumea exterioar, numele metodelor pot fi alese ct mai natural posibil, iarinterfeele specificprecis i detaliat modul de utilizare al obiectului.

    2.2 Limbajul C++++++++

    Toate limbajele de nivel nalt, de la FORTRAN la LISP, permit adaptarea unui stilde programare orientat pe obiect, dar numai cteva ofer mecanismele pentru

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    31/294

    16 Programare orientatpe obiect Capitolul 2

    utilizarea direct a obiectelor. Din acest punct de vedere, menionm dou maricategorii de limbaje:

    Limbaje care oferdoar facilit i de abstractizarea datelor i ncapsulare, cumsunt Ada i Modula-2. De exemplu, n Ada, datele i procedurile care lemanipuleazpot fi grupate ntr-un pachet (package).

    Limbaje orientate pe obiect, care adaug abstractizrii datelor noiunea demotenire.

    Dei definiiile de mai sus restrng mult mulimea limbajelor calificabile caorientate pe obiect, aceste limbaje rmn totui foarte diverse, att din punct de

    vedere al conceptelor folosite, ct i datorit modului de implementare. S-auconturat trei mari familii, fiecare accentund un anumit aspect al no iunii deobiect: limbaje de clase, limbaje de cadre (frames) i limbaje de tip actor.

    Limbajul C++* aparine familiei limbajelor de clase. O clas este un tip de datecare descrie un ansamblu de obiecte cu aceeai structuri acelai comportament.Clasele pot fi mbogite i completate pentru a defini alte familii de obiecte. nacest mod se obin ierarhii de clase din ce n ce mai specializate, care motenescdatele i metodele claselor din care au fost create. Din punct de vedere istoricprimele limbaje de clase au fost Simula (1973) i Smalltalk-80 (1983). LimbajulSimula a servit ca model pentru o ntreg linie de limbaje caracterizate printr-oorganizare statica tipurilor de date.

    Svedem acum care sunt principalele deosebiri dintre limbajele C i C++ , precumi modul n care s-au implementat intrrile/ieirile n limbajul C++ .

    2.2.1 Diferenele dintre limbajele C i C++++++++

    Limbajul C, foarte lejer n privina verificrii tipurilor de date, lasprogramatorului o libertate deplin. Aceast libertate este o surs permanent deerori i de efecte colaterale foarte dificil de depanat. Limbajul C++ a introdus overificare foarte strict a tipurilor de date. n particular, apelul oricarei funciitrebuie precedat de declararea funciei respective. Pe baza declaraiilor, prin carese specific numrul i tipul parametrilor formali, parametrii efectivi poat fiverificai n momentul compilrii apelului. n cazul unor nepotriviri de tipuri,

    compilatorul ncearc realizarea corespondenei (matching) prin invocarea unorconversii, semnalnd eroare doar dacnu gsete nici o posibilitate.

    float maxim( float, float );float x = maxim( 3, 2.5 );

    * Limbaj dezvoltat de Bjarne Stroustrup la nceputul anilor 80, n cadrul laboratoarelor Bell de laAT&T, ca o extindere orientatpe obiect a limbajului C.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    32/294

    Seciunea 2.2 Limbajul C++ 17

    n acest exemplu, funcia maxim() este declarat ca o funcie de tip floatcu doiparametri tot de tip float, motiv pentru care constanta ntreag3 este convertit

    n momentul apelului la tipul float. Declaraia unei funcii const n protot ipulfunciei, care conine tipul valorii returnate, numele funciei, numrul i tipulparametrilor. Diferena dintre definiie i declaraie noiuni valabile i pentruvariabile const n faptul c definiia este o declaraie care provoac irezervare de spaiu sau generare de cod. Declararea unei variabile se face prinprecedarea obligatorie a definiiei de cuvntul cheie extern. i o declaraie defuncie poate fi precedat de cuvntul cheie extern, accentund astfel c funciaeste definitaltundeva.

    Definirea unor funcii foarte mici, pentru care procedura de apel tinde s durezemai mult dect executarea propriu-zis, se realizeaz n limbajul C++ prinfunciile inline.

    inline float maxim( float x, float y ) {putchar( 'r' ); return x > y? x: y;

    }

    Specificarea inline este doar orientativ i indic compilatorului c estepreferabil de a nlocui fiecare apel cu corpul func iei apelate. Expandarea uneifuncii inlinenu este o simpl substituie de text n progamul surs, deoarece serealizeaz prin pstrarea semanticii apelului, deci inclusiv a verificrii

    corespondenei tipurilor parametrilor efectivi.Mecanismul de verificare a tipului lucreaz ntr-un mod foarte flexibil, permindatt existena funciilor cu un numr variabil de argumente, ct i a celorsuprancrcate. Suprancrcarea permite existena mai multor funcii cu acelainume, dar cu paremetri diferi i. Eliminarea ambiguit ii care apare n momentulapelului se rezolv pe baza numrului i tipului parametrilor efectivi. Iat, deexemplu, o altfuncie maxim():

    inline int maxim( int x, int y ) {putchar( 'i' ); return x > y? x: y;

    }

    (Prin apelarea funciei putchar(), putem afla care din cele dou funcii maxim()

    este efectiv invocat).

    n limbajul C++ nu este obligatorie definirea variabilelor locale strict la nceputulblocului de instruciuni. n exemplul de mai jos, tabloul buf i ntregul i pot fiutilizate din momentul definirii i pn la sfritul blocului n care au fostdefinite.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    33/294

    18 Programare orientatpe obiect Capitolul 2

    #define DIM 5

    void f( ) {int buf[ DIM ];

    for ( int i = 0; i < DIM; )buf[ i++ ] = maxim( i, DIM - i );

    while ( --i )printf( "%3d ", buf[ i ] );

    }

    n legtur cu acest exemplu, smai notm i faptul c instruciunea for permite

    chiar definirea unor variabile (variabila i n cazul nostru). Variabilele definite ninstruciunea for pot fi utilizate la nivelul blocului acestei instruciuni i dupterminarea executrii ei.

    Dei transmiterea parametrilor n limbajul C se face numai prin valoare, limbajulC++ autorizeaz n egal msur i transmiterea prin referin . Referinele,indicate prin caracterul &, permit accesarea n scriere a parametrilor efectivi, frtransmiterea lor prin adrese. Iat un exemplu n care o procedur interschimb(swap) valorile argumentelor.

    void swap( float& a, float& b ) {float tmp = a; a = b; b = tmp;

    }

    Referinele evitduplicarea provocatde transmiterea parametrilor prin valoare isunt utile mai ales n cazul transmiterii unor structuri. De exemplu, presupunndexistena unei structuri de tip structpunct,

    struct punct {float x; /* coordonatele unui */float y; /* punct din plan */

    };

    urmtoarea funcie transform un punct n simetricul lui fa de cea de a douabisectoare.

    void sim2( struct punct& p ) {swap( p.x, p.y ); // p.x si p.y se transmit prin

    // referinta si nu prin valoarep.x = -p.x; p.y = -p.y;

    }

    Parametrii de tip referin pot fi protejai de modificri accidentale prindeclararea lor const.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    34/294

    Seciunea 2.2 Limbajul C++ 19

    void print( const struct punct& p ) {// compilatorul interzice orice tentativa// de a modifica variabila pprintf( "(%4.1f, %4.1f) ", p.x, p.y );

    }

    Caracterele // indic faptul c restul liniei curente este un comentariu. Pe lngaceast modalitate nou de a introduce comentarii, limbajul C++ a preluat dinlimbajul C i posibiliatea ncadrrii lor ntre /*i */.

    Atributulconst

    poate fi asociat nu numai parametrilor formali, ci i unor definiiide variabile, a cror valoare este specificat n momentul compilrii. Acestevariabile sunt variabile read-only (constante), deoarece nu mai pot fi modificateulterior. n limbajul C, constantele pot fi definite doar prin intermediul directivei#define, care este o surs foarte puternic de erori. Astfel, n exemplul de mai

    jos, constanta ntreagdim este o variabilpropriu-zis accesibildoar n funciag(). Dac ar fi fost definit prin #define (vezi simbolul DIM utilizat n funciaf() de mai sus) atunci orice identificator dim, care apare dup directiva dedefinire i pn la sfritul fiierului surs, este nlocuit cu valoarea respectiv,frnici un fel de verificri sintactice.

    void g( ) {const int dim = 5;struct punct buf[ dim ];

    for ( int i = 0; i < dim; i++ ) {buf[ i ].x = i;buf[ i ].y = dim / 2. - i;

    sim2( buf[ i ] );print( buf[ i ] );

    }}

    Pentru a obine un prim program n C++, nu avem dect sadugm obinuitul

    #include

    precum i funcia main()

    int main( ) {puts( "\n main." );

    puts( "\n f( )" ); f( );puts( "\n g( )" ); g( );

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    35/294

    20 Programare orientatpe obiect Capitolul 2

    puts( "\n ---\n" );return 0;

    }

    Rezultatele obinute n urma rulrii acestui program:

    rmain.

    f( )iiiii 4 3 3 4g( )

    (-2.5, -0.0) (-1.5, -1.0) (-0.5, -2.0)( 0.5, -3.0) ( 1.5, -4.0)---

    suprind prin faptul c funcia float maxim( float, float ) este invocatnaintea funciei main(). Acest lucru este normal, deoarece variabila x trebuieiniializatnaintea lansrii n execuie a funciei main().

    2.2.2 Intrri/ieiri n limbajul C++++++++

    Limbajul C++ permite definirea tipurilor abstracte de date prin intermediulclaselor. Clasele nu sunt altceva dect generalizri ale structurilor din limbajul C.Ele conin date membre, adic variabile de tipuri predefinite sau definite deutilizator prin intermediul altor clase, precum i funcii membre, reprezentndmetodele clasei.

    Cele mai utilizate clase C++ sunt cele prin care se realizeaz intrrile i ieirile.Reamintim cn limbajul C, intrrile i ieirile se fac prin intermediul unor func iide bibliotec cum sunt scanf() i printf(), funcii care permit citirea sauscrierea numai a datelor (variabilelor) de tipuri predefinite (char, int, floatetc.). Biblioteca standard asociat oricrui compilator C++ , conine ca suportpentru operaiile de intrare i ieire nu simple funcii, ci un set de clase adaptabilechiar i unor tipuri noi, definite de utilizator. Aceastbibliotec este un exemplutipic pentru avantajele oferite de programarea orientatpe obiect. Pentru fixareaideilor, vom folosi un program care determin termenul de rang n al irului luiFibonacci prin algoritmul fib2 din Seciunea 1.6.4.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    36/294

    Seciunea 2.2 Limbajul C++ 21

    #include

    long fib2( int n ) {long i = 1, j = 0;

    for ( int k = 0; k++ < n; j = i + j, i = j - i );return j;

    }

    int main( ) {cout > n;

    cout

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    37/294

    22 Programare orientatpe obiect Capitolul 2

    comenzii de lansare n execuie a programului, argumente de forma >nume-fisier-iesire, sau

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    38/294

    Seciunea 2.3 Clase n limbajul C++ 23

    2.3.1 Tipul intErvaln limbajul C

    Reprezentarea intern a tipului conine trei membri de tip ntreg: marginileintervalului i valoarea propriu-zis. Le vom grupa ntr-o structur care, prinintermediul instruciunii typedef,devine sinonimcu intErval.

    typedef struct {int min; /* marginea inferioara a intervalului */int max; /* marginea superioara a intervalului */int v; /* valoarea, min

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    39/294

    24 Programare orientatpe obiect Capitolul 2

    funcia de citire val() pur i simplu returneaz valoarea v. Practic, aceste doufuncii implementeaz o form de ncapsulare, izolnd reprezentarea intern aobiectului de restul programului.

    int atr( intErval *pn, int i ) {return pn->v = verDom( *pn, i );

    }

    int val( intErval n ) {return n.v;

    }

    Funcia verDom()verific ncadrarea n domeniul admisibil:

    int verDom( intErval n, int i ) {if ( i < n.min || i >= n.max ) {fputs( "\n\nintErval -- valoare exterioara.\n\n", stderr);exit( 1 );

    }return i;

    }

    Utiliznd consecvent cele dou metode ale tipului intErval, ob inem obiecte alecror valori sunt cu certitudine ntre limitele admisibile. De exemplu, utilizndmetodele atr()i val(), instruciunea

    indice.v = numar.v + 1;

    devine

    atr( &indice, val( numar ) + 1 );

    Deoarece numar are valoarea 64, iar domeniul indice-lui este 32, ..., 64,instruciunea de mai sus semnaleaz dep irea domeniului variabilei indice iprovoac terminarea executrii programului.

    Aceast implementare este departe de a fi complet i comod de utilizat. Nu nereferim acum la aspecte cum ar fi citirea (sau scrierea) obiectelor de tip

    intErval, operaie rezolvabilprintr-o funcie de genul

    void cit( intErval *pn ) {int i;scanf( "%d", &i );atr( pn, i );

    }

    ci la altele, mult mai delicate, cum ar fi:

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    40/294

    Seciunea 2.3 Clase n limbajul C++ 25

    I1 Evitarea unor iniializri eronate din punct de vedere semantic i interzicereautilizrii obiectelor neiniializate:

    intErval numar = {80,32,64}; // obiect incorect initializatintErval indice, limita; // obiecte neinitializate

    I2 Interzicerea modificrii necontrolate a datelor membre:

    indice.v = numar.v + 1;

    I3 Sintaxa foarte ncrcat, diferit de sintaxa obinuit n manipularea tipurilor

    ntregi predefinite.n concluzie, aceast implementare, n loc s ne simplifice activitatea deprogramare, mai mult a complicat-o. Cauza nu este ns conceperea greit atipului intErval, ci lipsa facilit ilor de manipulare a obiectelor din limbajul C.

    2.3.2 Tipul intErvaln limbajul C++++++++

    Clasele se obin prin completarea structurilor uzuale din limbajul C cu setul defuncii necesar implementrii interfeei obiectului. n plus, pentru realizareaizolrii reprezentrii interne de restul programului, fiecrui membru i se asociaznivelul de ncapsulare public sau private. Un membru public corespunde, din

    punct de vedere al nivelului de accesibilitate, membrilor structurilor din limbajulC. Membrii private sunt accesibili doar n domeniul clasei, adic n clasapropriu-zisi n toate funciile membre. n clasa intErval, membrii publici suntdoar funciile atr()i val(), iar membrii verDom(), min, maxi vsunt privai.

    class intErval {public:int atr( int );int val( ) { return v; }

    private:int verDom( int );

    int min, max;

    int v;};

    Obiectele de tip intErvalse definesc ca i n limbajul C.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    41/294

    26 Programare orientatpe obiect Capitolul 2

    intErval numar;intErval indice, limita;

    Aceste obiecte pot fi atribuite ntre ele (fiind structuri atribuirea se va facemembru cu membru):

    limita = numar;

    i pot fi iniializate (tot membru cu membru) cu un obiect de acelai tip:

    intErval cod = numar;

    Selectarea membrilor se face prin nota iile utilizate pentru structuri. De exemplu,dupexecutarea instruciunii

    indice.atr( numar.val( ) + 1 );

    valoarea obiectului indice va fi valoarea obiectului numar, incrementat cu 1.Aceastoperaie poate fi descrisi prin intruciunea

    indice.v = numar.v + 1;

    care, dei corect din punct de vedere sintactic, este incorect semantic, deoarece

    veste un membru private, deci inaccesibil prin intermediul obiectelor indiceinumar.

    Dup cum se observ, au disprut argumentele de tip intErval*i intErval alefunciilor atr(), respectiv val(). Cauza este faptul c funciile membre au unargument implicit, concretizat n obiectul invocator, adic obiectul careselecteaz funcia. Este o convenie care ntrete i mai mult atributul de funciemembr (metod) deoarece permite invocarea unei astfel de funcii numai prinobiectul respectiv.

    Definirea funciilor membre se poate face fie n corpul clasei, fie n exteriorulacestuia. Funciile definite n corpul clasei sunt considerate implicit inline, iarpentru cele definite n exteriorul corpului se impune precizarea statutului defuncie membr. nainte de a defini funciile atr() i verDom(), s observm cfuncia val(), definit n corpul clasei intErval, ncalc de dou ori celeprecizate pnaici. n primul rnd, nu selecteazmembrul vprin intermediul unuiobiect, iar n al doilea rnd, v este privat! Dac funcia val() ar fi fost o funcieobinuit, atunci observaia ar fi fost ct se poate de corect. Dar val() estefuncie membri atunci:

    Nu poate fi apelatdect prin intermediul unui obiect invocator i to i membriiutilizai sunt membrii obiectului invocator.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    42/294

    Seciunea 2.3 Clase n limbajul C++ 27

    ncapsularea unui membru funcioneaz doar n exteriorul domeniului clasei.Funciile membre fac parte din acest domeniu i au acces la to i membrii,indiferent de nivelul lor de ncapsulare.

    Specificarea atributului de funcie membr se face precednd numele funciei deoperatorul domeniu :: i de numele domeniului, care este chiar numele clasei.Pentru asigurarea consistenei clasei, funciile membre definite n exterior trebuieobligatoriu declarate n corpul clasei.

    int intErval::verDom( int i ) {if ( i < min || i >= max ) {

    cerr

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    43/294

    28 Programare orientatpe obiect Capitolul 2

    class intErval {public:// operatorul de atribuire corespunzator functiei atr()int operator =( int i ) { return v = verDom( i ); }

    // operatorul de conversie corespunzator functiei val()operator int( ) { return v; }

    private:int verDom( int );

    int min, max;int v;

    };

    Revenind la obiectele indicei numar, putem scrie acum

    indice = (int)numar + 1;

    sau direct

    indice = numar + 1;

    conversia numar-ului la int fiind invocat automat de ctre compilator. Nu estenimic miraculos n aceast invocare automat, deoarece operatorul + nu este

    definit pentru argumente de tip intErval i int, dar este definit pentru int iint. Altfel spus, expresia numar + 1poate fi evaluatprintr-o simplconversie aprimului operand de la intErvalla int.

    O alt funcie util tipului intErval este cea de citire a valorii v, funciedenumit n paragraful precedent cit(). Ne propunem s o nlocuim cuoperatorul de extragere >>, pentru a putea scrie direct cin >> numar.Suprancrcarea operatorului >> ca funcie membr nu este posibil, deoareceargumentul stng este obiectul invocator i atunci ar trebui sscriem n >> cin.

    Operatorul de extragere necesar pentru citirea valorii obiectelor de tip intErvalse poate defini astfel:

    istream& operator >>( istream& is, intErval& n ) {

    int i;if ( is >> i ) // se citeste valoarean = i; // se invoca operatorul de atribuire

    return is;}

    Sunt dountrebri la care trebuie srspundem referitor la funcia de mai sus:

    Care este semnificaia testului if ( is >> i )?

    De ce se returneazistream-ul?

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    44/294

    Seciunea 2.3 Clase n limbajul C++ 29

    n testul if ( is >> i ) se invoc de fapt operatorul de conversie de laistreaml a int, rezultatul fiind valoarea logictrue(valoare diferitde zero) saufalse(valoarea zero), dupcum operaia a decurs normal sau nu.

    Returnarea istream-ului este o modalitate de a aplica operatorului >> sintaxa deconcatenare, sintax utilizat n expresii de forma i = j = 0. De exemplu,obiectele numar i indice de tip intErval, pot fi citite printr-o singurinstruciune

    cin >> numar >> indice;

    De asemenea, remarcm i utilizarea absolut justificat a argumentelor de tipreferin . n lipsa lor, obiectul numarar fi putut s fie modificat doar daci-am fitransmis adresa. n plus, utilizarea sintaxei de concatenare provoac, n lipsareferinelor, multiplicarea argumentului de tip istreamde douori pentru fiecareapel: prima datca argument efectiv, iar a doua oarca valoare returnat.

    Clasa intErval a devenit o clas comod de utilizat, foarte bine ncapsulat i cuun comportament similar ntregilor. ncapsularea este ns att de bun, nct,practic, nu avem nici o modalitate de a iniializa limitele superioar i inferioarale domeniului admisibil. De fapt, am revenit la inconvenientul I 1 menionat nfinalul Seciunii 2.3.1. Problema iniializrii datelor membre n momentuldefinirii obiectelor nu este specific doar clasei intErval. Pentru rezolvarea ei,

    limbajul C++

    ofer o categorie special de funcii membre, numite constructori .Constructorii nu au tip, au numele identic cu numele clasei i sunt invocaiautomat de ctre compilator, dup rezervarea spaiului pentru datele obiectuluidefinit.

    Constructorul necesar clasei intErval are ca argumente limitele domeniuluiadmisibil. Transmiterea lor se poate face implicit, prin nota ia

    intErval numar( 80, 32 );

    sau explicit, prin specificarea constructorului

    intErval numar = intErval( 80, 32 );

    Definiia acestui constructor este

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    45/294

    30 Programare orientatpe obiect Capitolul 2

    intErval::intErval( int sup, int inf ) {if ( inf >= sup ) {cerr

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    46/294

    Seciunea 2.3 Clase n limbajul C++ 31

    Dupaceste ultime precizri, definiia clasei intErvaleste:

    class intErval {public:intErval( int = 1, int = 0 );~intErval( ) { }

    int operator =( int i ) { return v = verDom( i ); }operator int( ) { return v; }

    private:int verDom( int );

    int min, max;int v;

    };

    Se observ apariia unei noi funcii membre, numit~intErval(), al crui corpeste vid. Ea se numete destructor, nu are tip i nici argumente, iar numele ei esteob inut prin precedarea numelui clasei de caracterul ~. Rolul destructorului esteopus celui al constructorului, n sensul c realizeaz operaiile necesaredistrugerii corecte a obiectului. Destructorul este invocat automat, nainte de aelibera spaiul alocat datelor membre ale obiectului care nceteaz s mai existe.Un obiect nceteazsmai existe n urmtoarele situaii:

    Obiectele definite ntr-o funcie sau bloc de instruciuni (obiecte cu existen local) nceteaz s mai existe la terminarea executrii funciei sau bloculuirespectiv.

    Obiectele definite global, n exteriorul oricrei funcii, sau cele definitestatic (obiecte cu existen static) nceteaz s mai existe la terminareaprogramului.

    Obiectele alocate dinamic prin operatorul new(obiecte cu existen dinamic)nceteazsmai existe la invocarea operatorului delete.

    Ca i n cazul constructorilor, prezena destructorului ntr-o clas este opional,fiind lsat la latitudinea proiectantului clasei.

    Pentru a putea fi inclusn toate fiierele sursn care este utilizat, definiia uneiclase se introduce ntr-un fiier header (prefix). n scopul evitrii includerii de

    mai multe ori a aceluiai fiier (includeri multiple), se recomand ca fiiereleheader sa ib structura

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    47/294

    32 Programare orientatpe obiect Capitolul 2

    #ifndef simbol#define simbol

    // continutul fisierului

    #endif

    unde simboleste un identificator unic n program. Dacf iierul a fost deja inclus,atunci identificatorul simbol este deja definit, i deci, toate liniile situate ntre#ifndef i #endif vor fi ignorate. De exemplu, n fiierul intErval.h, careconine definiia clasei intErval, identificatorul simbol ar putea fi

    __INTeRVAL_H. Iatcon inutul acestui fiier:

    #ifndef __INTeRVAL_H#define __INTeRVAL_H

    #include

    class intErval {public:intErval( int = 1, int = 0 );~intErval( ) { }

    int operator =( int i ) { return v = verDom( i ); }operator int( ) { return v; }

    private:int verDom( int );

    int min, max;int v;

    };

    istream& operator >>( istream&, intErval& );

    #endif

    Funciile membre se introduc ntr-un fiier surs obinuit, care este legat dupcompilare de programul executabil. Pentru clasa intErval, acest fiier este:

    #include "intErval.h"#include

    intErval::intErval( int sup, int inf ) {if ( inf >= sup ) {cerr

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    48/294

    Seciunea 2.3 Clase n limbajul C++ 33

    exit( 1 );}min = v = inf;max = sup;

    }

    int intErval::verDom( int i ) {if ( i < min || i >= max ) {cerr

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    49/294

    34 Programare orientatpe obiect Capitolul 2

    Neconcordana dintre argumentul formal de tip int din fib2() i argumentulefectiv (actual) de tip intErval se rezolv, de ctre compilator, prin invocareaoperatorului de conversie de la intErvalla int.

    Programarea orientat pe obiect este deosebit de avantajoas n cazul aplicaiilormari, dezvoltate de echipe ntregi de programatori pe parcursul ctorva luni, sauchiar ani. Aplicaia prezentat aici este mult prea mic pentru a putea fi folositca un argument n favoarea acestei tehnici de programare. Cu toate acestea,comparnd cele dou implementri ale clasei intErval (n limbajele C, respectivC++), sunt deja evidente douavantaje ale programrii orientate pe obiect:

    n primul rnd, este posibilitatea dezvoltrii unor tipuri noi, definite exclusivprin comportament i nu prin structur. Codul surs este mai compact, dar nnici un caz mai rapid dect n situa ia n care nu am fi folosit obiecte. Sre inem c programarea orientat pe obiect nu este o modalitate de a micoratimpul de execuie, ci de a spori eficiena activit ii de programare.

    n al doilea rnd, se remarcposibilit ile de a suprancrca operatori, inclusivpe cei de conversie. Efectul este foarte spectaculos, deoarece utilizarea noilortipuri este la fel de comod ca i utilizarea tipurilor predefinite. Pentru tipulintErval, aceste avantaje se concretizeaz n faptul c obiectele de tipintErval se comport exact ca i cele de tip int, ncadrarea lor n limiteledomeniului admisibil fiind absolut garantat.

    2.4 Exerciii *

    2.1 Scriei un program care determin termenul de rang n al irului luiFibonacci prin algoritmii fib1 i fib3.

    2.2 Care sunt valorile maxime ale lui npentru care algoritmii fib1, fib2 i fib3returneazvalori corecte? Cum pot fi mrite aceste valori?

    Soluie:Presupunnd cun longeste reprezentat pe 4 octei, atunci cel mai marenumr Fibonacci reprezentabil pe long este cel cu rangul 46. Lucrnd peunsigned long, se poate ajunge pn la termenul de rang 47. Pentru aceste

    ranguri, timpii de execuie ai algoritmului fib1 difer semnificativ de cei aialgoritmilorfib2 i fib3.

    2.3 Introducei n clasa intErval nc dou date membre prin care scontorizai numrul de apeluri ale celor doi operatori definii. Completai

    * Chiar dacnu se precizeazexplicit, toate implementrile se vor realiza n limbajul C++.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    50/294

    Seciunea 2.4 Exerciii 35

    constructorul i destructorul astfel nct siniializeze, respectiv safieze, acestevalori.

    2.4 Implementai testul de primalitate al lui Wilson prezentat n Seciunea1.4.

    2.5 Scriei un program pentru calculul recursiv al coeficienilor binomialidupformula datde triunghiul lui Pascal:

    n

    k

    nk

    nk

    =

    +

    11

    1

    1

    pentru 0 < k < n

    altfel

    Analizai avantajele i dezavantajele acestui program n raport cu programul carecalculeazcoeficientul conform definiiei:

    n

    m

    n

    m n m

    =

    !

    !( )!

    Soluie: Utilizarea definiiei pentru calculul combinrilor este o idee totalneinspirat, nu numai n ceea ce privete eficiena, ci i pentru faptul cnu poatefi aplicatdect pentru valori foarte mici ale lui n. De exemplu, ntr-un longde 4octei, valoarea 13! nu mai poate fi calculat. Funcia recursiveste simpl:

    int C( int n, int m) {return m == 0 ||

    m == n? 1: C( n - 1, m - 1 ) + C( n - 1, m );}

    dar i ineficient, deoarece numrul apelurilor recursive este foarte mare (veziExerciiul 8.1). Programul complet este:

    #include

    const int N = 16, M = 17;

    int r[N][M]; // contorizeaza numarul de apeluri ale// functiei C( int, int ) separat,// pentru toate valorile argumentelor

    long tr; // numarul total de apeluri ale// functiei C( int, int )

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    51/294

    36 Programare orientatpe obiect Capitolul 2

    int C( int n, int m ) {r[n][m]++; tr++;return m == 0 || m == n?1: C( n - 1, m - 1 ) + C( n - 1, m );

    }

    void main( ) {int n, m;for ( n = 0; n < N; n++ )for ( m = 0; m < M; m++ ) r[n][m] = 0;

    tr = 0;

    cout m;cout

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    52/294

    37

    3. Structuri elementare

    de date

    nainte de a elabora un algoritm, trebuie s ne gndim la modul n carereprezentm datele. n acest capitol vom trece n revist structurile fundamentalede date cu care vom opera. Presupunem n continuare csuntei deja familiarizai

    cu noiunile de fiier, tablou, list, graf, arbore i ne vom concentra mai ales peprezentarea unor concepte mai particulare: heap-uri i structuri de mulimidisjuncte.

    3.1 Liste

    O list este o colecie de elemente de informaie (noduri) aranjate ntr-o anumitordine. Lungimea unei liste este numrul de noduri din list. Structuracorespunztoare de date trebuie s ne permit s determinm eficient care esteprimul/ultimul nod n structur i care este predecesorul/succesorul (dac exist)unui nod dat. Iatcum aratcea mai simpllist, lista liniar:

    O list circular este o list n care, dup ultimul nod, urmeaz primul, decifiecare nod are succesor i predecesor.

    Operaii curente care se fac n liste sunt: inserarea unui nod, tergerea(extragerea) unui nod, concatenarea unor liste, numrarea elementelor unei listeetc. Implementarea unei liste se poate face n principal n doumoduri:

    Implementarea secvenial, n locaii succesive de memorie, conform ordinii

    nodurilor n list. Avantajele acestei tehnici sunt accesul rapid lapredecesorul/succesorul unui nod i gsirea rapid a primului/ultimului nod.Dezavantajele sunt inserarea/tergerea relativ complicat a unui nod i faptulc, n general, nu se folosete ntreaga memorie alocat listei.

    Implementarea n lnuit. n acest caz, fiecare nod con ine dou pri:informaia propriu-zisi adresa nodului succesor. Alocarea memoriei fiecruinod se poate face n mod dinamic, n timpul rul rii programului. Accesul la unnod necesitparcurgerea tuturor predecesorilor si, ceea ce poate lua ceva mai

    alpha beta gamma deltacapullistei

    coadalistei

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    53/294

    38 Structuri elementare de date Capitolul 3

    mult timp. Inserarea/tergerea unui nod este n schimb foarte rapid. Se potfolosi douadrese n loc de una, astfel nct un nod sconinpe lng adresanodului succesor i adresa nodului predecesor. Obinem astfel o list dublunlnuit, care poate fi traversatn ambele direcii.

    Listele implementate nlnuit pot fi reprezentate cel mai simplu prin tablouri. nacest caz, adresele sunt de fapt indici de tablou. O alternativ este s folosimtablouri paralele: s memorm informaia fiecrui nod (valoarea) ntr-o locaieVAL[i] a tabloului VAL[1 .. n], iar adresa (indicele) nodului su succesor ntr-olocaie LINK[i] a tabloului LINK[1 .. n]. Indicele de tablou al loca iei primuluinod este memorat n variabila head. Vom conveni ca, pentru cazul listei vide, s

    avem head = 0. Convenim de asemenea ca LINK[ultimul nod din list] = 0.Atunci, VAL[head] va conine informaia primului nod al listei, LINK[head]adresa celui de-al doilea nod, VAL[LINK[head]] informaia din al doilea nod,

    LINK[LINK[head]] adresa celui de-al treilea nod etc.

    Acest mod de reprezentare este simplu dar, la o analiz mai atent, apare oproblem esenia l: cea a gestionrii locaiilor libere. O soluie elegant este sreprezentm locaiile libere tot sub forma unei liste nlnuite. Atunci, tergereaunui nod din lista ini ia l implic inserarea sa n lista cu loca ii libere, iarinserarea unui nod n lista iniia l implic tergerea sa din lista cu loca ii libere.Aspectul cel mai interesant este c, pentru implementarea listei de locaii libere,putem folosi aceleai tablouri. Avem nevoie de o altvariabil, freehead, care vaconine indicele primei locaii libere din VALi LINK. Folosim aceleai convenii:

    dacfreehead = 0 nseamncnu mai avem loca ii libere, iar LINK[ultima locaieliber] = 0.

    Vom descrie n continuare dou tipuri de liste particulare foarte des folosite.

    3.1.1 Stive

    O stiv (stack) este o list liniar cu proprietatea c operaiile deinserare/extragere a nodurilor se fac n/din coada listei. Dac nodurile A, B, C, Dsunt inserate ntr-o stiv n aceast ordine, atunci primul nod care poate fi extraseste D. n mod echivalent, spunem cultimul nod inserat va fi i primul ters. Dinacest motiv, stivele se mai numesc i liste LIFO (Last In First Out), sau liste

    pushdown .Cel mai natural mod de reprezentare pentru o stiveste implementarea secvenia l

    ntr-un tablou S[1 .. n], unde n este numrul maxim de noduri. Primul nod va fimemorat n S[1], al doilea n S[2], iar ultimul n S[top], unde topeste o variabilcare conine adresa (indicele) ultimului nod inserat. Ini ial, cnd stiva este vid,avem top = 0. Iatalgoritmii de inserare i de tergere (extragere) a unui nod:

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    54/294

    Seciunea 3.1 Liste 39

    functionpush(x, S[1 .. n]){adaugnodul xn stiv}iftopnthen returnstivplin

    toptop+1

    S[top] xreturnsucces

    functionpop(S[1 .. n]){terge ultimul nod inserat din stivi l returneaz}iftop0 then returnstivv id

    xS[top]toptop1returnx

    Cei doi algoritmi necesittimp constant, deci nu depind de mrimea stivei.

    Vom da un exemplu elementar de utilizare a unei stive. Dac avem de calculatexpresia aritmetic

    5(((9+8)(46))+7)

    putem folosi o stiv pentru a memora rezultatele intermediare. ntr-o scrieresimplificat, iatcum se poate calcula expresia de mai sus:

    push(5); push(9); push(8); push(pop +pop); push(4); push(6);push(pop pop); push(pop pop); push(7); push(pop +pop);push(pop pop); write(pop);

    Observm c, pentru a efectua o operaie aritmetic, trebuie ca operanzii s fiedeja n stiv atunci cnd ntlnim operatorul. Orice expresie aritmetic poate fitransformat astfel nct s ndeplineasc aceast condiie. Prin aceasttransformare se obine binecunoscuta notaie postfixat (sau polonez invers),care se bucurde o proprietate remarcabil: nu sunt necesare paranteze pentru aindica ordinea operaiilor. Pentru exemplul de mai sus, nota ia postfixateste:

    5 9 8 + 4 6 7 +

    3.1.2 Cozi

    O coad (queue) este o list liniar n care inserrile se fac doar n capul listei,iar extragerile doar din coada listei. Cozile se numesc i liste FIFO(First In FirstOut).

    O reprezentare secvenia l interesant pentru o coad se obine prin utilizareaunui tablou C[0 .. n1], pe care l tratm ca i cum ar fi circular: dup locaiaC[n1] urmeaz locaia C[0]. Fie tail variabila care conine indicele locaiei

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    55/294

    40 Structuri elementare de date Capitolul 3

    predecesoare primei locaii ocupate i fie head variabila care conine indicelelocaiei ocupate ultima oar. Variabilele head i tail au aceeai valoare atunci inumai atunci cnd coada este vid. Iniial, avem head = tail = 0. Inserarea itergerea (extragerea) unui nod necesittimp constant.

    functioninsert-queue (x, C[0 .. n1]){adaugnodul xn capul cozii}head(head+1) mod nifhead= tail then returncoadplinC[head] x

    returnsuccesfunctiondelete-queue(C[0 .. n1])

    {terge nodul din coada listei i l returneaz}ifhead= tailthen returncoadvidtail( tail+1) mod n

    xC[tail]returnx

    Este surprinztor faptul c testul de coad vid este acelai cu testul de coadplin. Dacam folosi toate cele nlocaii, atunci nu am putea distinge ntre situaiade coad plin i cea de coad vid, deoarece n ambele situaii am aveahead = tail. n consecin , se folosesc efectiv numai n1 locaii din cele n aletabloului C, deci se pot implementa astfel cozi cu cel mult n1 noduri.

    3.2 Grafuri

    Un graf este o pereche G= , unde V este o mulime de vrfuri, iarMVV este o mulime de muchii. O muchie de la vrful a la vrful b estenotat cu perechea ordonat (a, b), dac graful este orientat, i cu mulimea{a, b}, dacgraful este neorientat. n cele ce urmeazvom presupune cvrfurilea i b sunt diferite. Dou vrfuri unite printr-o muchie se numesc adiacente. Undrum este o succesiune de muchii de forma

    (a1, a2), (a2, a3), , (an1, an)

    sau de forma{a1, a2}, {a2, a3}, , {an1, an}

    dup cum graful este orientat sau neorientat. Lungimea drumului este egal cunumrul muchiilor care l constituie. Un drumsimplueste un drum n care nici unvrf nu se repet. Un ciclu este un drum care este simplu, cu excepia primului iultimului vrf, care coincid. Un grafaciclic este un graf fr cicluri. Un subgrafal luiG este un graf , unde V'V, iar M'este formatdin muchiile din Mcare unesc vrfuri din V'. Un graf parialeste un graf

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    56/294

    Seciunea 3.2 Grafuri 41

    Un graf neorientat este conex, dac ntre oricare dou vrfuri exist un drum.Pentru grafuri orientate, aceast no iune este ntri t: un graf orientat este tareconex, dac ntre oricare dou vrfuri i i j exist un drum de la i la ji un drumde la jla i.

    n cazul unui graf neconex, se pune problema determinrii componentelor saleconexe. O component conex este un subgraf conex maximal, adic un subgrafconex n care nici un vrf din subgraf nu este unit cu unul din afar printr-omuchie a grafului iniial. mprirea unui graf G= n componentele saleconexe determino partiie a lui Vi una a lui M.

    Un arboreeste un graf neorientat aciclic conex. Sau, echivalent, un arbore este ungraf neorientat n care exist exact un drum ntre oricare dou vrfuri*. Un grafparial care este arbore se numete arbore parial.

    Vrfurilor unui graf li se pot ataa informaii numite uneori valori , iar muchiilor lise pot ataa informaii numite uneori lungimisau costuri .

    Existcel puin trei moduri evidente de reprezentare ale unui graf:

    Printr-o matrice de adiacen A, n care A[i, j] = truedac vrfurile ii jsuntadiacente, iar A[i, j] = false n caz contrar. O variant alternativeste s-i dmlui A[i, j] valoarea lungimii muchiei dintre vrfurile i i j, considernd

    A[i, j] = + atunci cnd cele douvrfuri nu sunt adiacente. Memoria necesar

    este n ordinul lui n2. Cu aceast reprezentare, putem verifica uor dac dou

    vrfuri sunt adiacente. Pe de alt parte, dac dorim s aflm toate vrfurileadiacente unui vrf dat, trebuie s analizm o ntreag linie din matrice.Aceasta necesit n operaii (unde n este numrul de vrfuri n graf),independent de numrul de muchii care conecteazvrful respectiv.

    Prin liste de adiacen , adic prin ataarea la fiecare vrf i a listei de vrfuriadiacente lui (pentru grafuri orientate, este necesar ca muchia s plece din i).ntr-un graf cu m muchii, suma lungimilor listelor de adiacen este 2m, dacgraful este neorientat, respectiv m, dac graful este orientat. Dac numrulmuchiilor n graf este mic, aceast reprezentare este preferabil din punct devedere al memoriei necesare. Este posibil s examinm to i vecinii unui vrfdat, n medie, n mai puin de n operaii. Pe de alt parte, pentru a determinadacdou vrfuri ii j sunt adiacente, trebuie s analizm lista de adiacen a

    lui i(i, posibil, lista de adiacen a lui j), ceea ce este mai puin eficient dectconsultarea unei valori logice n matricea de adiacen .

    Printr-o list de muchii. Aceast reprezentare este eficient atunci cnd avemde examinat toate muchiile grafului.

    * n Exerciiul 3.2 sunt date i alte propoziii echivalente care caracterizeazun arbore.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    57/294

    42 Structuri elementare de date Capitolul 3

    3.3 Arbori cu rdcin

    Fie G un graf orientat. Geste un arbore cu rdcina r, dacexist n Gun vrf rdin care oricare alt vrf poate fi ajuns printr-un drum unic.

    Definiia este valabili pentru cazul unui graf neorientat, alegerea unei rdcinifiind ns n acest caz arbitrar: orice arbore este un arbore cu rdcin, iarrdcina poate fi fixat n oricare vrf al su. Aceasta, deoarece dintr-un vrfoarecare se poate ajunge n oricare alt vrf printr-un drum unic.

    Cnd nu va fi pericol de confuzie, vom folosi termenul arbore, n loc determenul corect arbore cu rdcin. Cel mai intuitiv este s reprezentm unarbore cu rdcin, ca pe un arbore propriu-zis. n Figura 3.1, vom spune cbetaeste ta tl lui delta i fiul lui alpha, cbeta i gamma sunt frai, cdelta este undescendental lui alpha, iar alphaeste un ascendental lui delta. Un vrf terminal este un vrf fr descendeni. Vrfurile care nu sunt terminale sunt neterminale .De multe ori, vom considera c exist o ordonare a descendenilor aceluiaiprinte: beta este situat la stnga lui gamma, adic beta este fratele mai vrstnic

    al lui gamma.Orice vrf al unui arbore cu rdcin este rdcina unui subarbore constnd dinvrful respectiv i to i descendenii si. O mulime de arbori disjunci formeazo

    pdure.

    ntr-un arbore cu rdcin vom adopta urmtoarele notaii. Adncimea unui vrfeste lungimea drumului dintre rdcin i acest vrf; nlimea unui vrf estelungimea celui mai lung drum dintre acest vrf i un vrf terminal; nlimea

    delta omega

    adncimea

    0

    1 1

    0 2

    gamma

    alpha

    zeta

    beta

    nivelul

    2

    Figura 3.1 Un arbore cu rdcin.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    58/294

    Seciunea 3.3 Arbori cu rdcin 43

    arborelui este nlimea rdcinii; nivelul unui vrf este nlimea arborelui,minus adncimea acestui vrf.

    Reprezentarea unui arbore cu rdcin se poate face prin adrese, ca i n cazullistelor nlnuite. Fiecare vrf va fi memorat n trei locaii diferite, reprezentnd

    informaia propriu-zisa vrfului (valoarea vrfului), adresa celui mai vrstnic fiui adresa urmtorului frate. Pstrnd analogia cu listele nlnuite, dac secunoate de la nceput numrul maxim de vrfuri, atunci implementarea arborilorcu rdcinse poate face prin tablouri paralele.

    Dac fiecare vrf al unui arbore cu rdcin are pn la n fii, arborele respectiveste n-ar. Un arbore binar poate fi reprezentat prin adrese, ca n Figura 3.2.Observm cpoziiile pe care le ocup cei doi fii ai unui vrf sunt semnificative:lui ai lipsete fiul drept, iar beste fiul stngal lui a.

    ntr-un arbore binar, numrul maxim de vrfuri de adncime k este 2k. Un arbore

    binar de nlime iare cel mult 2 i+11 vrfuri, iar dacare exact 2 i+11 vrfuri, senumete arbore plin. Vrfurile unui arbore plin se numeroteaz n ordinea

    adncimii. Pentru aceeai adncime, numerotarea se face n arbore de la stnga ladreapta (Figura 3.3).

    Un arbore binar cu n vrfuri i de nlime i este complet, dac se obine dinarborele binar plin de nlime i, prin eliminarea, dac este cazul, a vrfurilor

    numerotate cu n+1, n+2, , 2i+11. Acest tip de arbore se poate reprezentasecvenial folosind un tablou T, punnd vrfurile de adncime k, de la stnga la

    dreapta, n poziiile T[2 k], T[2 k+1], , T[2 k+11] (cu posibila excepie a nivelului0, care poate fi incomplet). De exemplu, Figura 3.4 exemplific cum poate fi

    a

    valoarea vrfuluiadresa fiului stngadresa fiului drept

    b

    dc

    Figura 3.2 Reprezentarea prin adrese a unui arbore binar.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    59/294

    44 Structuri elementare de date Capitolul 3

    reprezentat un arbore binar complet cu zece vrfuri, ob inut din arborele plin dinFigura 3.3, prin eliminarea vrfurilor 11, 12, 13, 14 i 15. Tatl unui vrfreprezentat n T[i], i> 1, se afl n T[idiv2]. Fiii unui vrf reprezentat n T[i] seafl, dacexist, n T[2 i] i T[2 i+1].

    Facem acum o scurt incursiune n matematica elementar, pentru a stabili ctevarezultate de care vom avea nevoie n capitolele urmtoare. Pentru un numr realoarecarex , definim

    x= max{n nx, neste ntreg} i x= min{n nx, neste ntreg}

    Putei demonstra cu uurin urmtoarele propriet i:

    4

    98

    5

    1110

    6

    1312

    7

    1514

    2 3

    1

    Figura 3.3 Numerotarea vrfurilor ntr-un arbore binar de nlime 3.

    T[4]

    T[9]T[8]

    T[5]

    T[10]

    T[2]

    T[6] T[7]

    T[3]

    T[1]

    Figura 3.4Un arbore binar complet.

  • 7/22/2019 Cartea de Algoritmi (Avansati)

    60/294

    Seciunea 3.3 Arbori cu rdcin 45

    i) x1 < xxx< x+1pentru orice xreal

    ii) n/2+n/2= npentru orice n ntreg

    iii) n/a/b= n/ab i n/a/b= n/abpentru orice n, a, bntregi (a, b 0)

    iv) n/m= (nm+1)/m i n/m= (n+m1)/mpentru orice numere ntregi pozitive ni m

    n fine, arta i cun arbore binar complet cu nvrfuri are nlimea lg n.

    3.4 Heap-uri

    Un heap (n traducere aproximativ, grmad ordonat) este un arbore binarcomplet, cu urmtoarea proprietate, numitproprietatede heap: valoarea fiecruivrf este mai mare sau egalcu valoarea fiecrui fiu al su. Figura 3.5 prezintunexemplu de heap.

    Acelai heap poate fi reprezentat secvenial prin urmtorul tablou:

    10 7 9 4 7 5 2 2 1 6T[1] T[2] T[3] T[4] T[5] T[6] T[7] T[8] T[9] T[10]

    Caracteristica de baz a acestei structuri de dat este c modificarea valorii unuivrf se face foarte eficient, pstrndu-se proprietatea de heap. Dacvaloarea unuivrf crete, astfel nct depete valoarea tatlui, este suficient sschimbm ntreele aceste dou valori i s continum procedeul n mod ascendent, pn cndproprietatea