algoritmi fundamentali - cwu.edu · v cuvânt înainte evolu ția rapid ă și spectaculoas ă a...

of 294 /294
ALGORITMI FUNDAMENTALI O PERSPECTIVĂ C++

Author: others

Post on 30-Aug-2019

3 views

Category:

Documents


1 download

Embed Size (px)

TRANSCRIPT

  • ALGORITMI FUNDAMENTALI O PERSPECTIV C++

  • ALGORITMI FUNDAMENTALI

    O PERSPECTIV C++

    RZVAN ANDONIE ILIE GRBACEA

    Editura Libris Cluj-Napoca, 1995

  • Referent: Leon Livovschi

    Coperta: Zoltn Albert

    Copyright 1995 Editura Libris Universitii 8/8, 3400 Cluj-Napoca

    ISBN 973-96494-5-9

  • v

    Cuvnt nainte

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

    Un concept nou, care s-a dovedit foarte eficient, este cel al programrii orientate pe obiect, prin obiect nelegndu-se o entitate ce cuprinde att datele, ct i procedurile ce opereaz cu ele. Dintre limbajele orientate pe obiect, limbajul C++ prezint printre multe altele avantajul unei exprimri concise, fapt ce uureaz transcrierea n acest limbaj a algoritmilor redactai n pseudo-cod i motiveaz folosirea lui n cartea de fa. Cu toate c nu este descris n detaliu, este demn de menionat faptul c descrierea din Capitolul 2, mpreun cu completrile din celelalte capitole, constituie o prezentare aproape integral a limbajului C++.

    O preocupare meritorie a acestei lucrri este problema analizei eficienei algoritmilor. Prezentarea acestei probleme ncepe n Capitolul 1 i continu n Capitolul 5. Tehnicile de analiz expuse se bazeaz pe diferite metode, prezentate ntr-un mod riguros i accesibil. Subliniem contribuia autorilor n expunerea detailat a induciei constructive i a tehnicilor de rezolvare a recurenelor liniare.

    Diferitele metode clasice de elaborare a algoritmilor sunt descrise n Capitolele 68 prin probleme ce ilustreaz foarte clar ideile de baz i detaliile metodelor expuse. Pentru majoritatea problemelor tratate, este analizat i eficiena algoritmului folosit. Capitolul 9 este consacrat tehnicilor de explorri n grafuri. n primele seciuni sunt prezentate diferite probleme privind parcurgerea grafurilor. Partea final a capitolului este dedicat jocurilor i cuprinde algoritmi ce reprezint de fapt soluii ale unor probleme de inteligen artificial.

    Cartea este redactat clar i riguros, tratnd o arie larg de probleme din domeniul elaborrii i analizei algoritmilor. Exerciiile din ncheierea fiecrui capitol sunt foarte bine alese, multe din ele fiind nsoite de soluii. De asemenea, merit menionate referirile interesante la istoria algoritmilor i a gndirii algoritmice.

    Considerm c aceast carte va fi apreciat i cutat de ctre toi cei ce lucreaz n domeniul abordat i doresc s-l cunoasc mai bine.

    Leon Livovschi

  • vii

    n clipa 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 analiza eficienei algoritmilor, cartea se concentreaz pe principiile fundamentale de elaborare a algoritmilor: greedy, divide et impera, programare dinamic, backtracking. Interesul nostru pentru inteligena artificial a fcut ca penultimul capitol s fie, de fapt, o introducere din punct de vedere al algoritmilor n acest domeniu.

    Majoritatea algoritmilor selectai au o conotaie estetic. Efortul necesar pentru nelegerea elementelor mai subtile este uneori considerabil. Ce este ns un algoritm estetic? Putem rspunde foarte simplu: un algoritm este estetic dac exprim mult n cuvinte puine. Un algoritm estetic este oare n mod necesar i eficient? Cartea rspunde i acestor ntrebri.

    n al doilea rnd, cartea prezint mecanismele interne eseniale ale limbajului C++ (moteniri, legturi dinamice, clase parametrice, excepii) i trateaz implementarea algoritmilor n conceptul programrii orientate pe obiect. Totui, aceast carte nu este un curs complet de C++.

    Algoritmii nu sunt pur i simplu transcrii din pseudo-cod n limbajul C++, ci sunt regndii din punct de vedere al programrii orientate pe obiect. Sperm c, dup citirea crii, vei dezvolta aplicaii de programare orientat pe obiect i vei elabora implementri ale altor structuri de date. Programele* au fost scrise pentru limbajul C++ descris de Ellis i Stroustrup n The Annotated C++ Reference Manual. Acest limbaj se caracterizeaz, n principal, prin introducerea claselor parametrice i a unui mecanism de tratare a excepiilor foarte avansat, faciliti deosebit de importante pentru dezvoltarea de biblioteci C++. Compilatoarele GNU C++ 2.5.8 (UNIX/Linux) i Borland C++ 3.1 (DOS) suport destul de bine clasele parametrice. Pentru tratarea excepiilor se pot utiliza compilatoarele Borland C++ 4.0 i, n viitorul apropiat, GNU C++ 2.7.1.

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

    * Fiierele surs ale tuturor exemplelor aproximativ 3400 de linii n 50 de fiiere pot fi obinute

    pe o dischet MS-DOS, printr-o comand adresat editurii.

  • viii Principii de algoritmi i C++ Cuprins

    spre disperarea ne-matematicienilor cu celebrul Fie ... , sau cu o definiie. Am ncercat, pe de alt parte, s evitm situaia cnd totul este evident, sau se poate demonstra. Fiecare capitol este conceput fluid, ca o mic poveste, cu puine referine i note. Multe rezultate mai tehnice sunt obinute 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 cu soluii.

    Presupunem c cititorul are la baz cel puin un curs introductiv n programare, nefiindu-i strini termeni precum algoritm, recursivitate, funcie, procedur i pseudo-cod. Exist mai multe modaliti de parcurgere a crii. n funcie de interesul i pregtirea cititorului, acesta poate alege oricare din prile referitoare la elaborarea, analiza, sau implementarea algoritmilor. Cu excepia prilor de analiz a eficienei algoritmilor (unde sunt necesare elemente de matematici superioare), cartea poate fi parcurs i de ctre un elev de liceu. Pentru parcurgerea seciunilor de implementare, este recomandabil cunoaterea limbajului C.

    Cartea noastr se bazeaz pe cursurile pe care le inem, ncepnd cu 1991, la Secia de electronic i calculatoare a Universitii Transilvania din Braov. S-a dovedit util i experiena noastr de peste zece ani n dezvoltarea produselor software. Colectivul de procesare a imaginilor din ITC Braov a fost un excelent mediu n care am putut s ne dezvoltm profesional. Le mulumim pentru aceasta celor care au fcut parte, alturi de noi, din acest grup: Sorin Cisma, tefan Jozsa, Eugen Carai. Nu putem s nu ne amintim cu nostalgie de compilatorul C al firmei DEC (pentru minicalculatoarele din seria PDP-11) pe care l-am descoperit mpreun, cu zece ani n urm.

    Ca de obicei n astfel de situaii, numrul celor care au contribuit ntr-un fel sau altul la realizarea acestei cri este foarte mare, cuprinznd profesorii notri, colegii de catedr, studenii pe care am testat cursurile, prietenii. Le mulumim tuturor. De asemenea, apreciem rbdarea celor care ne-au suportat n cei peste doi ani de elaborare a crii.

    Sperm s citii aceast carte cu aceeai plcere cu care ea a fost scris.

    Braov, ianuarie 1995

    Rzvan Andonie

    Ilie Grbacea*

    * Autorii pot fi contactai prin pot, la adresa: Universitatea Transilvania, Catedra de electronic i

    calculatoare, Politehnicii 1-3, 2200 Braov, sau prin E-mail, la adresa: algoritmi&[email protected]

  • ix

    Cuprins

    1. PRELIMINARII 1 1.1 Ce este un algoritm? 1

    1.2 Eficiena algoritmilor 5

    1.3 Cazul mediu i cazul cel mai nefavorabil 6

    1.4 Operaie elementar 8

    1.5 De ce avem nevoie de algoritmi eficieni? 9

    1.6 Exemple 10 1.6.1 Sortare 10 1.6.2 Calculul determinanilor 10 1.6.3 Cel mai mare divizor comun 11 1.6.4 Numerele lui Fibonacci 12

    1.7 Exerciii 13

    2. PROGRAMARE ORIENTAT PE OBIECT 14 2.1 Conceptul de obiect 14

    2.2 Limbajul C++++++++ 15 2.2.1 Diferenele dintre limbajele C i C++ 16 2.2.2 Intrri/ieiri n limbajul C++ 20

    2.3 Clase n limbajul C++++++++ 22 2.3.1 Tipul intErval n limbajul C 23 2.3.2 Tipul intErval n limbajul C++ 25

    2.4 Exerciii 34

    3. STRUCTURI ELEMENTARE DE DATE 37 3.1 Liste 37

    3.1.1 Stive 38 3.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

  • x Principii de algoritmi i C++ Cuprins

    4. TIPURI ABSTRACTE DE DATE 56 4.1 Tablouri 56

    4.1.1 Alocarea dinamic a memoriei 57 4.1.2 Clasa tablou 60 4.1.3 Clasa parametric tablou 63

    4.2 Stive, cozi, heap-uri 68 4.2.1 Clasele stiva i coada 69 4.2.2 Clasa heap 73

    4.3 Clasa lista 78

    4.4 Exerciii 84

    5. ANALIZA EFICIENEI ALGORITMILOR 89 5.1 Notaia asimptotic 89

    5.1.1 O notaie pentru ordinul lui 89 5.1.2 Notaia asimptotic condiionat 91

    5.2 Tehnici de analiz a algoritmilor 94 5.2.1 Sortarea prin selecie 94 5.2.2 Sortarea prin inserie 94 5.2.3 Heapsort 95 5.2.4 Turnurile din Hanoi 97

    5.3 Analiza algoritmilor recursivi 98 5.3.1 Metoda iteraiei 98 5.3.2 Inducia constructiv 98 5.3.3 Recurene liniare omogene 99 5.3.4 Recurene liniare neomogene 101 5.3.5 Schimbarea variabilei 103

    5.4 Exerciii 105

    6. ALGORITMI GREEDY 113 6.1 Tehnica greedy 113

    6.2 Minimizarea timpului mediu de ateptare 115

    6.3 Interclasarea optim a irurilor ordonate 116

    6.4 Implementarea arborilor de interclasare 119

    6.5 Coduri Huffman 122

    6.6 Arbori pariali de cost minim 124 6.6.1 Algoritmul lui Kruskal 125 6.6.2 Algoritmul lui Prim 128

    6.7 Implementarea algoritmului lui Kruskal 130

  • Cuprins Principii de algoritmi i C++ xi

    6.8 Cele mai scurte drumuri care pleac din acelai punct 134

    6.9 Implementarea algoritmului lui Dijkstra 137

    6.10 Euristica greedy 143 6.10.1 Colorarea unui graf 143 6.10.2 Problema comis-voiajorului 144

    6.11 Exerciii 145

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

    7.2 Cutarea binar 151

    7.3 Mergesort (sortarea prin interclasare) 153

    7.4 Mergesort n clasele tablou i lista 154 7.4.1 O soluie neinspirat 154 7.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 problem de criptologie 169

    7.8 nmulirea matricilor 172

    7.9 nmulirea numerelor ntregi mari 174

    7.10 Exerciii 177

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

    8.2 O competiie 187

    8.3 nmulirea nlnuit a 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 204 8.7.1 Arborele optim 206 8.7.2 Cutarea n arbore 211 8.7.3 Modificarea arborelui 215

    8.8 Programarea dinamic comparat cu tehnica greedy 219

    8.9 Exerciii 221

  • xii Principii de algoritmi i C++ Cuprins

    9. EXPLORRI N GRAFURI 227 9.1 Parcurgerea arborilor 227

    9.2 Operaii de parcurgere n clasa arbore 229

    9.3 Parcurgerea grafurilor n adncime 231 9.3.1 Puncte de articulare 233 9.3.2 Sortarea topologic 234

    9.4 Parcurgerea grafurilor n lime 235

    9.5 Salvarea i restaurarea arborilor binari de cutare 237

    9.6 Backtracking 239

    9.7 Grafuri i jocuri 243 9.7.1 Jocul nim 243 9.7.2 ahul i tehnica minimax 247

    9.8 Grafuri AND/OR 249

    9.9 Exerciii 251

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

    10.2 Tablouri iniializate virtual 260 10.2.1 Structura 261 10.2.2 Implementarea (o variant de nota ase) 262 10.2.3 tablouVI ca subtip al tipului tablou 266

    10.3 Exerciii 269

    EPILOG 271

    BIBLIOGRAFIE SELECTIV 273

  • xiii

    Lista de notaii

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

    i .. j interval de ntregi: {k N | i k j}

    m mod n restul mpririi ntregi a lui m la n

    div mprirea ntreag

    | x | mrimea cazului x

    log logaritm ntr-o baz oarecare (n contextul notaiei

    asimptotice)

    lg logaritm n baza 2

    ln logaritm natural

    lg logaritm iterat (vezi Seciunea 3.5)

    n

    k

    combinri de n luate cte k

    R mulimea numerelor reale nenegative

    N+, R+ mulimea numerelor naturale (reale) strict pozitive

    B mulimea constantelor booleene {true, false}

    (x) | [P(x)] exist un x astfel nct P(x)

    (x) | [P(x)] pentru orice x astfel 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

  • 1

    1. Preliminarii

    1.1 Ce este un algoritm?

    Abu Ja`far Mohammed ibn Mus al-Khowrizm (autor persan, sec. VIII-IX), a scris o carte de matematic cunoscut n traducere latin ca Algorithmi de numero indorum, iar apoi ca Liber algorithmi, unde algorithm provine de la al-Khowrizm, ceea ce literal nseamn din oraul Khowrizm. n prezent, acest ora se numete Khiva i se afl n Uzbechistan. Att al-Khowrizm, ct i ali matematicieni din Evul Mediu, nelegeau prin algoritm o regul pe baza creia se efectuau calcule aritmetice. Astfel, n timpul lui Adam Riese (sec. XVI), algoritmii foloseau la: dublri, njumtiri, nmuliri de numere. Ali algoritmi apar n lucrrile lui Stifer (Arithmetica integra, Nrnberg, 1544) i Cardano (Ars magna sive de reguli algebraicis, Nrnberg, 1545). Chiar i Leibniz vorbete 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 teoriei funciilor recursive. Conceptul de recursivitate devine indisolubil legat de cel de algoritm. Dar abia n deceniile al treilea i al patrulea ale secolului nostru, teoria recursivitii i algoritmilor ncepe s se constituie ca atare, prin lucrrile lui Skolem, Ackermann, Sudan, Gdel, Church, Kleene, Turing, Peter i alii.

    Este surprinztoare transformarea gndirii algoritmice, dintr-un instrument matematic particular, ntr-o modalitate fundamental de abordare a problemelor n domenii care aparent nu au nimic comun cu matematica. Aceast universalitate a gndirii algoritmice este rezultatul conexiunii dintre algoritm i calculator. Astzi, nelegem prin algoritm o metod general de rezolvare a unui anumit tip de problem, metod care se poate implementa pe calculator. n acest context, un algoritm este esena absolut a unei rutine.

    Cel mai faimos algoritm este desigur algoritmul lui Euclid pentru aflarea celui mai mare divizor comun a dou numere ntregi. Alte exemple de algoritmi sunt metodele nvate n coal pentru a nmuli/mpri dou numere. Ceea ce d ns generalitate noiunii de algoritm este faptul c el 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 c nu exist nici un domeniu, orict ar prea el de imprecis i de fluctuant, n care s nu putem descoperi sectoare funcionnd algoritmic.

  • 2 Preliminarii Capitolul 1

    Un algoritm este compus dintr-o mulime finit de pai, fiecare necesitnd una sau mai multe operaii. Pentru a fi implementabile pe calculator, aceste operaii trebuie s fie n primul rnd definite, adic s fie foarte clar ce anume trebuie executat. n al doilea rnd, operaiile trebuie s fie efective, ceea ce nseamn c n principiu, cel puin o persoan dotat cu creion i hrtie trebuie s poat efectua orice pas ntr-un timp finit. De exemplu, aritmetica cu numere ntregi este efectiv. Aritmetica cu numere reale nu este ns efectiv, deoarece unele numere sunt exprimabile prin secvene infinite. Vom considera c un algoritm trebuie s se termine dup un numr finit de operaii, ntr-un timp rezonabil de lung.

    Programul este exprimarea unui algoritm ntr-un limbaj de programare. Este bine ca nainte de a nva concepte generale, s fi acumulat deja o anumit experien practic n domeniul respectiv. Presupunnd c ai scris deja programe ntr-un limbaj de nivel nalt, probabil c ai avut uneori dificulti n a formula soluia pentru o problem. Alteori, poate c nu ai putut decide care dintre algoritmii care rezolvau aceeai problem este mai bun. Aceast carte v va nva cum s evitai aceste situaii nedorite.

    Studiul algoritmilor cuprinde mai multe aspecte:

    i) Elaborarea algoritmilor. Actul de creare a unui algoritm este o art care nu va putea fi niciodat pe deplin automatizat. Este n fond vorba de mecanismul universal al creativitii umane, care produce noul printr-o sintez extrem de complex de tipul:

    tehnici de elaborare (reguli) + creativitate (intuiie) = soluie. Un obiectiv major al acestei cri este de a prezenta diverse tehnici

    fundamentale de elaborare a algoritmilor. Utiliznd aceste tehnici, acumulnd i o anumit experien, vei fi capabili s concepei algoritmi eficieni.

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

    iii) Validarea algoritmilor. Un algoritm, dup elaborare, nu trebuie n mod necesar s fie programat pentru a demonstra c funcioneaz corect n orice situaie. El poate fi scris iniial ntr-o form precis oarecare. n aceast form, 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 problem este mai bun, este nevoie s definim un criteriu de apreciere a valorii unui algoritm. n general, acest criteriu se refer la timpul de calcul i la memoria necesar unui algoritm. Vom analiza din acest punct de vedere toi algoritmii prezentai.

  • Seciunea 1.1 Ce este un algoritm? 3

    v) Testarea programelor. Aceasta const din dou faze: depanare (debugging) i trasare (profiling). Depanarea este procesul executrii unui program pe date de test i corectarea eventualelor erori. Dup cum afirma ns E. W. Dijkstra, prin depanare putem evidenia prezena erorilor, dar nu i absena lor. O demonstrare a faptului c un program este corect este mai valoroas dect o mie de teste, deoarece garanteaz c programul va funciona corect n orice situaie. Trasarea este procesul executrii unui program corect pe diferite date de test, pentru a-i determina timpul de calcul i memoria necesar. Rezultatele obinute pot fi apoi comparate cu analiza anterioar a algoritmului.

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

    Vom ncepe cu un exemplu de algoritm. Este vorba de o metod, cam ciudat la prima vedere, de nmulire a dou numere. 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 mparte numrul de sub denmulit la 2, ignornd fraciile, apoi se nmulete cu 2 numrul

    de sub nmulitor. Se aplic regula, pn cnd numrul de sub denmulit este 1. n final, adunm toate numerele din coloana nmulitorului 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 multor calculatoare. Ea prezint avantajul c nu este necesar s se memoreze tabla de nmulire. Totul se rezum la adunri i nmuliri/mpriri cu 2 (acestea din urm fiind rezolvate printr-o simpl decalare).

    Pentru a reprezenta algoritmul, vom utiliza un limbaj simplificat, numit pseudo-cod, care este un compromis ntre precizia unui limbaj de programare i uurina n exprimare a unui limbaj natural. Astfel, elementele eseniale ale algoritmului nu vor fi ascunse de detalii de programare neimportante n aceast faz. Dac suntei familiarizat cu un limbaj uzual de programare, nu vei avea nici

    45 19 19

    22 38

    11 76 76

    5 152 152

    2 304

    1 608 608

    855

  • 4 Preliminarii Capitolul 1

    o dificultate n a nelege notaiile folosite i n a scrie programul respectiv. Cunoatei atunci i diferena dintre o funcie i o procedur. n notaia pe care o folosim, o funcie va returna uneori un tablou, o mulime, sau un mesaj. Vei nelege c este vorba de o scriere mai compact i n funcie de context vei putea alege implementarea convenabil. Vom conveni ca parametrii funciilor (procedurilor) s fie transmii prin valoare, exceptnd tablourile, care vor fi transmise prin adresa primului element. Notaia folosit pentru specificarea unui parametru de tip tablou va fi diferit, de la caz la caz. Uneori vom scrie, de exemplu:

    procedure proc1(T)

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

    procedure proc2(T[1 .. n])

    sau, mai general:

    procedure proc3(T[a .. b])

    n aceste cazuri, n, a i b vor fi considerai parametri formali.

    De multe ori, vom atribui unor elemente ale unui tablou T valorile , nelegnd prin acestea dou valori numerice extreme, astfel nct pentru oricare alt element T[i] avem < T[i] < +.

    Pentru simplitate, vom considera uneori c anumite variabile sunt globale, astfel nct s le putem folosi n mod direct n proceduri.

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

  • Seciunea 1.1 Ce este un algoritm? 5

    function russe(A, B) arrays X, Y {iniializare} X[1] A; Y[1] B i 1 {se construiesc cele dou coloane} while X[i] > 1 do X[i+1] X[i] div 2 {div reprezint mprirea ntreag} Y[i+1] Y[i]+Y[i] i i+1 {adun numerele Y[i] corespunztoare numerelor X[i] impare} prod 0 while i > 0 do if X[i] este impar then prod prod+Y[i] i i1 return prod

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

    Pe lng algoritmul de nmulire nvat n coal, iat c mai avem un algoritm care face acelai lucru. Exist mai muli algoritmi care rezolv o problem, dar i mai multe programe care pot descrie un algoritm.

    Acest algoritm poate fi folosit nu doar pentru a nmuli pe 45 cu 19, dar i pentru a nmuli orice numere ntregi pozitive. Vom numi (45, 19) un caz (instance). Pentru fiecare algoritm exist un domeniu de definiie al cazurilor pentru care algoritmul funcioneaz corect. Orice calculator limiteaz mrimea cazurilor cu care poate opera. Aceast limitare nu poate fi ns atribuit algoritmului respectiv. nc o dat, observm c exist o diferen esenial ntre programe i algoritmi.

    1.2 Eficiena algoritmilor

    Ideal este ca, pentru o problem dat, s gsim mai muli algoritmi, iar apoi s-l alegem 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 pe calculator a unor cazuri diferite. Sau, putem analiza a priori (teoretic) algoritmul, naintea programrii lui, prin determinarea cantitativ a resurselor (timp, memorie etc) necesare ca o funcie de mrimea cazului considerat.

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

  • 6 Preliminarii Capitolul 1

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

    Avantajul analizei teoretice este faptul c ea nu depinde de calculatorul folosit, de limbajul de programare ales, sau de ndemnarea programatorului. Ea salveaz timpul pierdut cu programarea i rularea unui algoritm care se dovedete n final ineficient. Din motive practice, un algoritm nu poate fi testat pe calculator pentru cazuri orict de mari. Analiza teoretic ne permite ns studiul eficienei algoritmului 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, iar valorile numerice ale parametrilor sunt apoi determinate empiric. Aceast metod permite o predicie asupra comportrii algoritmului pentru cazuri foarte mari, care nu pot fi testate. O extrapolare doar pe baza testelor empirice este foarte imprecis.

    Este natural s ntrebm ce unitate trebuie folosit pentru a exprima eficiena teoretic a unui algoritm. Un rspuns la aceast problem este dat de principiul invarianei, potrivit cruia dou implementri diferite ale aceluiai algoritm nu difer n eficien cu mai mult de o constant multiplicativ. Adic, presupunnd c avem dou implementri care necesit t1(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 este valabil indiferent de calculatorul (de construcie convenional) folosit, indiferent de limbajul de programare ales i indiferent de ndemnarea programatorului (presupunnd c acesta nu modific algoritmul!). Deci, schimbarea calculatorului ne poate permite s rezolvm o problem de 100 de ori mai repede, dar numai modificarea algoritmului ne poate aduce o mbuntire care s devin din ce n ce mai marcant pe msur ce mrimea cazului soluionat crete.

    Revenind la problema unitii de msur a eficienei teoretice a unui algoritm, ajungem la concluzia c nici nu avem nevoie de o astfel de unitate: vom exprima eficiena n limitele unei constante multiplicative. Vom spune c un algoritm necesit timp n ordinul lui t, pentru o funcie t dat, dac exist o constant pozitiv 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 cazului considerat. Utilizarea secundelor n aceast definiie este arbitrar, deoarece trebuie s modificm doar constanta pentru a mrgini timpul la at(n) ore, sau bt(n) microsecunde. Datorit principiului invarianei, orice alt implementare a algoritmului va avea aceeai proprietate, cu toate c de la o implementare la alta se poate modifica constanta multiplicativ. n Capitolul 5 vom reveni mai riguros asupra acestui important concept, numit notaie asimptotic.

  • Seciunea 1.2 Eficiena algoritmilor 7

    Dac un algoritm necesit timp n ordinul lui n, vom spune c necesit timp liniar, iar algoritmul respectiv putem s-l numim algoritm liniar. Similar, un algoritm este ptratic, cubic, polinomial, sau exponenial dac necesit timp n ordinul lui

    n2, n3, nk, respectiv cn, unde k i c sunt constante.

    Un obiectiv major al acestei cri este analiza teoretic a eficienei algoritmilor. Ne vom concentra asupra criteriului timpului de execuie. Alte resurse necesare (cum ar fi memoria) pot fi estimate teoretic ntr-un mod similar. Se pot pune i probleme 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 cazuri de mrime identic. Pentru a ilustra aceasta, vom considera doi algoritmi elementari de sortare a unui tablou T de n elemente:

    procedure insert(T[1 .. n]) for i 2 to n do x T[i]; j i1 while j > 0 and x < T[ j] do T[ j+1] T[ j] j j1 T[ j+1] x

    procedure select (T[1 .. n]) for i 1 to n1 do minj i; minx T[i] for j i+1 to n do if T[ j] < minx then minj j minx T[ j] T[minj] T[i] T[i] minx

    Ideea general a sortrii prin inserie este s considerm pe rnd fiecare element al irului i s l inserm n subirul ordonat creat anterior din elementele precedente. Operaia de inserare implic deplasarea spre dreapta a unei secvene. Sortarea prin selecie lucreaz altfel, plasnd la fiecare pas cte un element direct pe poziia lui final.

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

  • 8 Preliminarii Capitolul 1

    Vom vedea mai trziu c timpul de execuie pentru sortarea prin selecie este ptratic, independent de ordonarea iniial a elementelor. Testul if T[ j] < minx este executat de tot attea ori pentru oricare dintre cazuri. Relativ micile variaii ale timpului de execuie se datoreaz doar numrului de executri ale atribuirilor din ramura then a testului.

    La sortarea prin inserie, situaia este diferit. Pe de o parte, insert(U) este foarte rapid, deoarece condiia care controleaz bucla while este mereu fals. Timpul necesar este liniar. Pe de alt parte, insert(V) necesit timp ptratic, deoarece bucla while este executat de i1 ori pentru fiecare valoare a lui i. (Vom analiza acest lucru n Capitolul 5).

    Dac apar astfel de variaii mari, atunci cum putem vorbi de un timp de execuie care s depind doar de mrimea cazului considerat? De obicei considerm analiza pentru cel mai nefavorabil caz. Acest tip de analiz este bun atunci cnd timpul de execuie al unui algoritm este critic (de exemplu, la controlul unei centrale nucleare). Pe de alt parte ns, este bine uneori s cunoatem timpul mediu de execuie al unui algoritm, atunci cnd el este folosit foarte des pentru cazuri diferite. Vom vedea c timpul mediu pentru sortarea prin inserie este tot ptratic. n anumite cazuri ns, acest algoritm poate fi mai rapid. Exist un algoritm de sortare (quicksort) cu timp ptratic pentru cel mai nefavorabil caz, dar cu timpul mediu n ordinul lui n log n. (Prin log notm logaritmul ntr-o baz oarecare, lg este logaritmul n baza 2, iar ln este logaritmul natural). Deci, pentru cazul mediu, quicksort este foarte rapid.

    Analiza comportrii n medie a unui algoritm presupune cunoaterea a priori a distribuiei probabiliste a cazurilor considerate. Din aceast cauz, analiza pentru cazul mediu este, n general, mai greu de efecuat dect pentru cazul cel mai nefavorabil.

    Atunci cnd nu vom specifica pentru ce caz analizm un algoritm, nseamn c eficiena algoritmului nu depinde de acest aspect (ci doar de mrimea cazului).

    1.4 Operaie elementar

    O operaie elementar este o operaie al crei timp de execuie poate fi mrginit superior de o constant depinznd doar de particularitatea implementrii (calculator, limbaj de programare etc). Deoarece ne intereseaz timpul de execuie n limita unei constante multiplicative, vom considera doar numrul operaiilor elementare executate ntr-un algoritm, nu i timpul exact de execuie al operaiilor respective.

    Urmtorul exemplu este testul lui Wilson de primalitate (teorema care st la baza acestui test a fost formulat iniial de Leibniz n 1682, reluat de Wilson n 1770 i demonstrat imediat dup aceea de Lagrange):

  • Seciunea 1.4 Operaie elementar 9

    function Wilson(n) {returneaz true dac i numai dac n este prim} if n divide ((n1)! + 1) then return true else return false

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

    Deci, este foarte important ce anume definim ca operaie elementar. Este oare adunarea o operaie elementar? n teorie, nu, deoarece i ea depinde de lungimea operanzilor. Practic, pentru operanzi de lungime rezonabil (determinat de modul de reprezentare intern), putem s considerm c adunarea este o operaie elementar. 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 sens atunci s investim n obinerea unor algoritmi eficieni? Nu este oare mai simplu s ateptm urmtoarea generaie de calculatoare?

  • 10 Preliminarii Capitolul 1

    S presupunem c pentru rezolvarea unei anumite probleme avem un algoritm exponenial 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. Pentru n = 20, sunt necesare aproape 2 minute. Pentru n = 30, o zi nu este de ajuns, iar pentru n = 38, chiar i un an ar fi insuficient. Cumprm un calculator de 100 de

    ori mai rapid, cu timpul de rulare de 106 2n secunde. Dar i acum, pentru n = 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 calculatorul

    vechi, cazul de mrime n n 102 n3 secunde. n Figura 1.1, putem urmri cum evolueaz 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 putea rezolva chiar cazul n = 1500. Este mai profitabil s investim n noul algoritm dect ntr-un nou hardware. Desigur, dac ne permitem s investim att n software ct i n hardware, noul algoritm poate fi rulat i pe noua main. Curba

    104 n3 reprezint aceast din urm situaie.

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

    Figura 1.1 Algoritmi sau hardware?

  • 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 dect algoritmul vechi. Pe vechiul calculator, algoritmul nou devine mai performant doar pentru cazuri mai mari sau egale cu 20.

    1.6 Exemple

    Poate c v ntrebai dac este ntr-adevr posibil s accelerm 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 n cazul mediu, ct i n cazul cel mai nefavorabil. Cu toate c aceti algoritmi sunt exceleni pentru cazuri mici, pentru cazuri mari avem algoritmi mai eficieni. n capitolele urmtoare vom analiza i ali algoritmi de sortare: heapsort, mergesort, quicksort. Toi acetia necesit un timp mediu n ordinul lui n log n, iar heapsort i mergesort necesit timp n ordinul lui n log n i 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 reuit s sorteze n 30 de secunde 100.000 de elemente, n timp ce sortarea prin inserie ar fi durat, pentru acelai caz, peste nou ore. Pentru un numr mic de elemente ns, eficiena celor dou sortri 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 definiie recursiv

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

    n

    = += 1 1 1 1

    1

    Dac folosim aceast relaie pentru a evalua determinantul, obinem un algoritm cu timp n ordinul lui n!, ceea ce este mai ru dect exponenial. O alt metod clasic, eliminarea Gauss-Jordan, necesit timp cubic. Pentru o anumit

  • 12 Preliminarii Capitolul 1

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

    Nu trebuie tras de aici concluzia c algoritmii recursivi sunt n mod necesar neperformani. Cu ajutorul algoritmului recursiv al lui Strassen, pe care l vom studia 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 ntregilor pozitivi m i n, notat cu cmmdc(m, n), se bazeaz pe definiie:

    function cmmdc-def (m, n) i min(m, n) + 1 repeat i i1 until i divide pe m i n return 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 celebrul algoritm al lui Euclid.

    function Euclid(m, n) if n = 0 then return m else return Euclid(n, m mod n)

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

    cmmdc(m, n) = cmmdc(n, m mod n)

    Timpul este n ordinul logaritmului lui min(m, n), chiar i n cazul cel mai nefavorabil, ceea ce reprezint o mbuntire substanial fa de algoritmul precedent. Pentru a fi exaci, trebuie s menionm c algoritmul originar al lui Euclid (descris n Elemente, aprox. 300 a.Ch.) opereaz prin 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:

  • 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 (Leonardo din Pisa), cunoscut sub numele de Leonardo Fibonacci. Cel de-al n-lea termen al irului se poate obine direct din definiie:

    function fib1(n) if n < 2 then return n else return fib1(n1) + fib1(n2)

    Aceast metod este foarte ineficient, deoarece recalculeaz de mai multe ori

    aceleai 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-un timp liniar.

    function fib2(n) i 1; j 0 for k 1 to n do j i + j i j i return j

    Mai mult, exist i un algoritm cu timp n ordinul lui log n, algoritm pe care l vom argumenta ns abia n Capitolul 7:

    function fib3(n) i 1; j 0; k 0; h 1 while n > 0 do if n este impar then t jh j ih+jk+t i ik+t t h2 h 2kh+t k k2+t n n div 2 return j

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

  • 14 Preliminarii Capitolul 1

    1.7 Exerciii

    1.1 Aplicai algoritmii insert i select pentru cazurile T = [1, 2, 3, 4, 5, 6] i U = [6, 5, 4, 3, 2, 1]. Asigurai-v c ai 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. ncercai s nelegei raionamentul care st la baza acestui algoritm de nmulire.

    Indicaie: Facei legtura cu reprezentarea binar.

    1.3 n algoritmul Euclid, este important ca n m ?

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

    Soluie:

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

    1.5 Programai algoritmul fib1 n dou limbaje diferite i rulai comparativ cele dou programe, pe mai multe cazuri. Verificai dac este valabil principiul invarianei.

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

    Indicaie: Un algoritm eficient se obine folosind urmtoarea proprietate*, valabil pentru 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 M m, unde fn1 i fn sunt doi termeni consecutivi oarecare ai irului lui

    Fibonacci.

    * Aceast surprinztoare proprietate a fost descoperit n 1876 de Lucas.

  • 14

    2. Programare orientat pe 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 pretext pentru introducerea elementelor de baz ale programrii orientate pe obiect n limbajul C++. Vom prezenta n capitolul de fa noiuni fundamentale legate de obiecte, limbajul C++ i de abstractizarea datelor n C++, urmnd ca, pe baza unor exemple detaliate, s conturm n capitolele urmtoare din ce n ce mai clar tehnica programrii orientate pe obiect. Scopul urmrit este de a surprinde acele aspecte strict necesare formrii unei impresii juste asupra programrii orientate pe obiect n limbajul C++, i nu de a substitui cartea de fa unui curs complet de C++.

    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 de programare au evoluat apoi n mod natural spre o tot mai net separare ntre conceptele manipulate de programe i reprezentrile acestor concepte n calculator.

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

    algoritmi + structuri de date = programe

    un program este format din dou pri total separate: un ansamblu de proceduri i un ansamblu de date asupra crora acioneaz procedurile. Procedurile sunt privite ca i cutii negre, fiecare avnd de rezolvat o anumit sarcin (de fcut anumite prelucrri). Aceast modalitate de programare se numete programare dirijat de prelucrri. Evoluia calculatoarelor i a problemelor de programare a fcut ca n aproximativ zece ani programarea dirijat de prelucrri s devin ineficient. Astfel, chiar dac un limbaj ca Pascal-ul permite o bun structurare a programului n proceduri, este posibil ca o schimbare relativ minor n structura datelor s provoace o dezorganizare major a procedurilor.

  • Seciunea 2.1 Conceptul de obiect 15

    Inconvenientele programrii dirijate de prelucrri sunt eliminate prin ncapsularea datelor i a procedurilor care le manipuleaz ntr-o singur entitate numit obiect. Lumea exterioar obiectului are acces la datele sau procedurile lui doar prin intermediul unor operaii care constituie interfaa obiectului. Programatorul nu este obligat s cunoasc reprezentarea fizic a datelor i procedurilor utilizate, motiv pentru care poate trata obiectul ca pe o cutie neagr cu un comportament bine precizat. Aceast caracteristic permite realizarea unor tipuri abstracte de date. Este vorba de obiecte nzestrate cu o interfa prin care se specific interaciunile cu exteriorul, singura modalitate de a comunica cu un astfel de obiect fiind invocarea interfeei sale. n terminologia specific programrii orientate pe obiect, procedurile care formeaz interfaa unui obiect se numesc metode. Obiectul este singurul responsabil de maniera n care se efectueaz operaiile asupra lui. Apelul unei metode este doar o cerere, un mesaj al apelantului care solicit executarea unei anumite aciuni. Obiectul poate refuza s o execute, sau, la fel de bine, o poate transmite unui alt obiect. n acest context, programarea devine dirijat de date, i nu de prelucrrile care trebuie realizate.

    Utilizarea consecvent a obiectelor confer programrii urmtoarele caliti:

    Abstractizarea datelor. Nu este nevoie de a cunoate implementarea i reprezentarea intern a unui obiect pentru a-i adresa mesaje. Obiectul decide singur maniera de execuie a operaiei cerute n functie de implementarea fizic. Este posibil suprancrcarea metodelor, n sensul c la aceleai mesaje, obiecte diferite rspund n mod diferit. De exemplu, este foarte comod de a desemna printr-un simbol unic, +, adunarea ntregilor, concatenarea irurilor de caractere, reuniunea mulimilor etc.

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

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

    Claritate. ncapsularea, posibilitatea de suprancrcare i modularitatea ntresc claritatea programelor. Detaliile de implementare sunt izolate de lumea exterioar, numele metodelor pot fi alese ct mai natural posibil, iar interfeele specific precis i detaliat modul de utilizare al obiectului.

    2.2 Limbajul C++++++++

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

  • 16 Programare orientat pe obiect Capitolul 2

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

    Limbaje care ofer doar faciliti de abstractizarea datelor i ncapsulare, cum sunt Ada i Modula-2. De exemplu, n Ada, datele i procedurile care le manipuleaz pot fi grupate ntr-un pachet (package).

    Limbaje orientate pe obiect, care adaug abstractizrii datelor noiunea de motenire.

    Dei definiiile de mai sus restrng mult mulimea limbajelor calificabile ca orientate pe obiect, aceste limbaje rmn totui foarte diverse, att din punct de vedere al conceptelor folosite, ct i datorit modului de implementare. S-au conturat trei mari familii, fiecare accentund un anumit aspect al noiunii de obiect: 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 date care descrie un ansamblu de obiecte cu aceeai structur i acelai comportament. Clasele pot fi mbogite i completate pentru a defini alte familii de obiecte. n acest mod se obin ierarhii de clase din ce n ce mai specializate, care motenesc datele i metodele claselor din care au fost create. Din punct de vedere istoric primele limbaje de clase au fost Simula (1973) i Smalltalk-80 (1983). Limbajul Simula a servit ca model pentru o ntreg linie de limbaje caracterizate printr-o organizare static a tipurilor de date.

    S vedem acum care sunt principalele deosebiri dintre limbajele C i C++, precum i 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, las programatorului o libertate deplin. Aceast libertate este o surs permanent de erori i de efecte colaterale foarte dificil de depanat. Limbajul C++ a introdus o verificare foarte strict a tipurilor de date. n particular, apelul oricarei funcii trebuie precedat de declararea funciei respective. Pe baza declaraiilor, prin care se specific numrul i tipul parametrilor formali, parametrii efectivi poat fi verificai n momentul compilrii apelului. n cazul unor nepotriviri de tipuri, compilatorul ncearc realizarea corespondenei (matching) prin invocarea unor conversii, semnalnd eroare doar dac nu 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 la

    AT&T, ca o extindere orientat pe obiect a limbajului C.

  • Seciunea 2.2 Limbajul C++ 17

    n acest exemplu, funcia maxim() este declarat ca o funcie de tip float cu doi parametri tot de tip float, motiv pentru care constanta ntreag 3 este convertit n momentul apelului la tipul float. Declaraia unei funcii const n prototipul funciei, care conine tipul valorii returnate, numele funciei, numrul i tipul parametrilor. Diferena dintre definiie i declaraie noiuni valabile i pentru variabile const n faptul c definiia este o declaraie care provoac i rezervare de spaiu sau generare de cod. Declararea unei variabile se face prin precedarea obligatorie a definiiei de cuvntul cheie extern. i o declaraie de funcie poate fi precedat de cuvntul cheie extern, accentund astfel c funcia este definit altundeva.

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

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

    Specificarea inline este doar orientativ i indic compilatorului c este preferabil de a nlocui fiecare apel cu corpul funciei apelate. Expandarea unei funcii inline nu este o simpl substituie de text n progamul surs, deoarece se realizeaz prin pstrarea semanticii apelului, deci inclusiv a verificrii corespondenei tipurilor parametrilor efectivi.

    Mecanismul de verificare a tipului lucreaz ntr-un mod foarte flexibil, permind att existena funciilor cu un numr variabil de argumente, ct i a celor suprancrcate. Suprancrcarea permite existena mai multor funcii cu acelai nume, dar cu paremetri diferii. Eliminarea ambiguitii care apare n momentul apelului se rezolv pe baza numrului i tipului parametrilor efectivi. Iat, de exemplu, o alt funcie 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 nceputul blocului de instruciuni. n exemplul de mai jos, tabloul buf i ntregul i pot fi utilizate din momentul definirii i pn la sfritul blocului n care au fost definite.

  • 18 Programare orientat pe 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, s mai notm i faptul c instruciunea for permite chiar definirea unor variabile (variabila i n cazul nostru). Variabilele definite n instruciunea for pot fi utilizate la nivelul blocului acestei instruciuni i dup terminarea executrii ei.

    Dei transmiterea parametrilor n limbajul C se face numai prin valoare, limbajul C++ autorizeaz n egal msur i transmiterea prin referin. Referinele, indicate prin caracterul &, permit accesarea n scriere a parametrilor efectivi, fr transmiterea 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 evit duplicarea provocat de transmiterea parametrilor prin valoare i sunt utile mai ales n cazul transmiterii unor structuri. De exemplu, presupunnd existena unei structuri de tip struct punct,

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

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

    void sim2( struct punct& p ) { swap( p.x, p.y ); // p.x si p.y se transmit prin // referinta si nu prin valoare p.x = -p.x; p.y = -p.y; }

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

  • Seciunea 2.2 Limbajul C++ 19

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

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

    Atributul const poate fi asociat nu numai parametrilor formali, ci i unor definiii de variabile, a cror valoare este specificat n momentul compilrii. Aceste variabile sunt variabile read-only (constante), deoarece nu mai pot fi modificate ulterior. 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 ntreag dim este o variabil propriu-zis accesibil doar n funcia g(). Dac ar fi fost definit prin #define (vezi simbolul DIM utilizat n funcia f() de mai sus) atunci orice identificator dim, care apare dup directiva de definire i pn la sfritul fiierului surs, este nlocuit cu valoarea respectiv, fr nici 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 s adugm obinuitul #include

    precum i funcia main() int main( ) { puts( "\n main." ); puts( "\n f( )" ); f( ); puts( "\n g( )" ); g( );

  • 20 Programare orientat pe obiect Capitolul 2

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

    Rezultatele obinute n urma rulrii acestui program: r main. f( ) iiiii 4 3 3 4 g( ) (-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 invocat naintea funciei main(). Acest lucru este normal, deoarece variabila x trebuie iniializat naintea lansrii n execuie a funciei main().

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

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

    Cele mai utilizate clase C++ sunt cele prin care se realizeaz intrrile i ieirile. Reamintim c n limbajul C, intrrile i ieirile se fac prin intermediul unor funcii de bibliotec cum sunt scanf() i printf(), funcii care permit citirea sau scrierea numai a datelor (variabilelor) de tipuri predefinite (char, int, float etc.). Biblioteca standard asociat oricrui compilator C++, conine ca suport pentru operaiile de intrare i ieire nu simple funcii, ci un set de clase adaptabile chiar i unor tipuri noi, definite de utilizator. Aceast bibliotec este un exemplu tipic pentru avantajele oferite de programarea orientat pe obiect. Pentru fixarea ideilor, vom folosi un program care determin termenul de rang n al irului lui Fibonacci prin algoritmul fib2 din Seciunea 1.6.4.

  • 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

  • 22 Programare orientat pe obiect Capitolul 2

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

  • Seciunea 2.3 Clase n limbajul C++ 23

    2.3.1 Tipul intErval n limbajul C

    Reprezentarea intern a tipului conine trei membri de tip ntreg: marginile intervalului i valoarea propriu-zis. Le vom grupa ntr-o structur care, prin intermediul instruciunii typedef, devine sinonim cu intErval.

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

  • 24 Programare orientat pe obiect Capitolul 2

    funcia de citire val() pur i simplu returneaz valoarea v. Practic, aceste dou funcii implementeaz o form de ncapsulare, izolnd reprezentarea intern a obiectului 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, obinem obiecte ale cror valori sunt cu certitudine ntre limitele admisibile. De exemplu, utiliznd metodele 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 depirea domeniului variabilei indice i provoac terminarea executrii programului.

    Aceast implementare este departe de a fi complet i comod de utilizat. Nu ne referim acum la aspecte cum ar fi citirea (sau scrierea) obiectelor de tip intErval, operaie rezolvabil printr-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:

  • Seciunea 2.3 Clase n limbajul C++ 25

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

    intErval numar = {80,32,64}; // obiect incorect initializat intErval 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 de programare, mai mult a complicat-o. Cauza nu este ns conceperea greit a tipului intErval, ci lipsa facilitilor de manipulare a obiectelor din limbajul C.

    2.3.2 Tipul intErval n limbajul C++++++++

    Clasele se obin prin completarea structurilor uzuale din limbajul C cu setul de funcii necesar implementrii interfeei obiectului. n plus, pentru realizarea izolrii reprezentrii interne de restul programului, fiecrui membru i se asociaz nivelul de ncapsulare public sau private. Un membru public corespunde, din punct de vedere al nivelului de accesibilitate, membrilor structurilor din limbajul C. Membrii private sunt accesibili doar n domeniul clasei, adic n clasa propriu-zis i n toate funciile membre. n clasa intErval, membrii publici sunt doar funciile atr() i val(), iar membrii verDom(), min, max i v sunt privai.

    class intErval { public: int atr( int ); int val( ) { return v; } private: int verDom( int ); int min, max; int v; };

    Obiectele de tip intErval se definesc ca i n limbajul C.

  • 26 Programare orientat pe obiect Capitolul 2

    intErval numar; intErval indice, limita;

    Aceste obiecte pot fi atribuite ntre ele (fiind structuri atribuirea se va face membru 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 notaiile utilizate pentru structuri. De exemplu, dup executarea instruciunii

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

    valoarea obiectului indice va fi valoarea obiectului numar, incrementat cu 1. Aceast operaie poate fi descris i prin intruciunea

    indice.v = numar.v + 1;

    care, dei corect din punct de vedere sintactic, este incorect semantic, deoarece v este un membru private, deci inaccesibil prin intermediul obiectelor indice i numar.

    Dup cum se observ, au disprut argumentele de tip intErval* i intErval ale funciilor atr(), respectiv val(). Cauza este faptul c funciile membre au un argument implicit, concretizat n obiectul invocator, adic obiectul care selecteaz funcia. Este o convenie care ntrete i mai mult atributul de funcie membr (metod) deoarece permite invocarea unei astfel de funcii numai prin obiectul respectiv.

    Definirea funciilor membre se poate face fie n corpul clasei, fie n exteriorul acestuia. Funciile definite n corpul clasei sunt considerate implicit inline, iar pentru cele definite n exteriorul corpului se impune precizarea statutului de funcie membr. nainte de a defini funciile atr() i verDom(), s observm c funcia val(), definit n corpul clasei intErval, ncalc de dou ori cele precizate pn aici. n primul rnd, nu selecteaz membrul v prin intermediul unui obiect, iar n al doilea rnd, v este privat! Dac funcia val() ar fi fost o funcie obinuit, atunci observaia ar fi fost ct se poate de corect. Dar val() este funcie membr i atunci:

    Nu poate fi apelat dect prin intermediul unui obiect invocator i toi membrii utilizai sunt membrii obiectului invocator.

  • 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 toi membrii, indiferent de nivelul lor de ncapsulare.

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

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

  • 28 Programare orientat pe 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 indice i 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 este nimic miraculos n aceast invocare automat, deoarece operatorul + nu este definit pentru argumente de tip intErval i int, dar este definit pentru int i int. Altfel spus, expresia numar + 1 poate fi evaluat printr-o simpl conversie a primului operand de la intErval la int.

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

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

    istream& operator >>( istream& is, intErval& n ) { int i; if ( is >> i ) // se citeste valoarea n = i; // se invoca operatorul de atribuire return is; }

    Sunt dou ntrebri la care trebuie s rspundem referitor la funcia de mai sus:

    Care este semnificaia testului if ( is >> i )? De ce se returneaz istream-ul?

  • Seciunea 2.3 Clase n limbajul C++ 29

    n testul if ( is >> i ) se invoc de fapt operatorul de conversie de la istream la int, rezultatul fiind valoarea logic true (valoare diferit de zero) sau false (valoarea zero), dup cum operaia a decurs normal sau nu.

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

    cin >> numar >> indice;

    De asemenea, remarcm i utilizarea absolut justificat a argumentelor de tip referin. n lipsa lor, obiectul numar ar fi putut s fie modificat doar dac i-am fi transmis adresa. n plus, utilizarea sintaxei de concatenare provoac, n lipsa referinelor, multiplicarea argumentului de tip istream de dou ori pentru fiecare apel: prima dat ca argument efectiv, iar a doua oar ca valoare returnat.

    Clasa intErval a devenit o clas comod de utilizat, foarte bine ncapsulat i cu un comportament similar ntregilor. ncapsularea este ns att de bun, nct, practic, nu avem nici o modalitate de a iniializa limitele superioar i inferioar ale domeniului admisibil. De fapt, am revenit la inconvenientul I1 menionat n finalul Seciunii 2.3.1. Problema iniializrii datelor membre n momentul definirii 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 invocai automat de ctre compilator, dup rezervarea spaiului pentru datele obiectului definit.

    Constructorul necesar clasei intErval are ca argumente limitele domeniului admisibil. Transmiterea lor se poate face implicit, prin notaia

    intErval numar( 80, 32 );

    sau explicit, prin specificarea constructorului intErval numar = intErval( 80, 32 );

    Definiia acestui constructor este

  • 30 Programare orientat pe obiect Capitolul 2

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

  • Seciunea 2.3 Clase n limbajul C++ 31

    Dup aceste ultime precizri, definiia clasei intErval este: 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 corp este vid. Ea se numete destructor, nu are tip i nici argumente, iar numele ei este obinut prin precedarea numelui clasei de caracterul ~. Rolul destructorului este opus celui al constructorului, n sensul c realizeaz operaiile necesare distrugerii corecte a obiectului. Destructorul este invocat automat, nainte de a elibera spaiul alocat datelor membre ale obiectului care nceteaz s mai existe. Un obiect nceteaz s mai 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 blocului respectiv.

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

    Obiectele alocate dinamic prin operatorul new (obiecte cu existen dinamic) nceteaz s mai 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 inclus n toate fiierele surs n care este utilizat, definiia unei clase se introduce ntr-un fiier header (prefix). n scopul evitrii includerii de mai multe ori a aceluiai fiier (includeri multiple), se recomand ca fiierele header s aib structura

  • 32 Programare orientat pe obiect Capitolul 2

    #ifndef simbol #define simbol // continutul fisierului #endif

    unde simbol este un identificator unic n program. Dac fiierul 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, care conine definiia clasei intErval, identificatorul simbol ar putea fi __INTeRVAL_H. Iat coninutul 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 dup compilare de programul executabil. Pentru clasa intErval, acest fiier este:

    #include "intErval.h" #include intErval::intErval( int sup, int inf ) { if ( inf >= sup ) { cerr

  • 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

  • 34 Programare orientat pe obiect Capitolul 2

    Neconcordana dintre argumentul formal de tip int din fib2() i argumentul efectiv (actual) de tip intErval se rezolv, de ctre compilator, prin invocarea operatorului de conversie de la intErval la int.

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

    n primul rnd, este posibilitatea dezvoltrii unor tipuri noi, definite exclusiv prin comportament i nu prin structur. Codul surs este mai compact, dar n nici un caz mai rapid dect n situaia n care nu am fi folosit obiecte. S reinem c programarea orientat pe obiect nu este o modalitate de a micora timpul de execuie, ci de a spori eficiena activitii de programare.

    n al doilea rnd, se remarc posibilitile de a suprancrca operatori, inclusiv pe cei de conversie. Efectul este foarte spectaculos, deoarece utilizarea noilor tipuri este la fel de comod ca i utilizarea tipurilor predefinite. Pentru tipul intErval, aceste avantaje se concretizeaz n faptul c obiectele de tip intErval se comport exact ca i cele de tip int, ncadrarea lor n limitele domeniului admisibil fiind absolut garantat.

    2.4 Exerciii *

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

    2.2 Care sunt valorile maxime ale lui n pentru care algoritmii fib1, fib2 i fib3 returneaz valori corecte? Cum pot fi mrite aceste valori?

    Soluie: Presupunnd c un long este reprezentat pe 4 octei, atunci cel mai mare numr Fibonacci reprezentabil pe long este cel cu rangul 46. Lucrnd pe unsigned long, se poate ajunge pn la termenul de rang 47. Pentru aceste ranguri, timpii de execuie ai algoritmului fib1 difer semnificativ de cei ai algoritmilor fib2 i fib3.

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

    * Chiar dac nu se precizeaz explicit, toate implementrile se vor realiza n limbajul C++.

  • Seciunea 2.4 Exerciii 35

    constructorul i destructorul astfel nct s iniializeze, respectiv s afieze, aceste valori.

    2.4 Implementai testul de primalitate al lui Wilson prezentat n Seciunea 1.4.

    2.5 Scriei un program pentru calculul recursiv al coeficienilor binomiali dup formula dat de triunghiul lui Pascal:

    n

    k

    n

    k

    n

    k

    =

    +

    1

    1

    1

    1

    pentru 0 < k < n

    altfel

    Analizai avantajele i dezavantajele acestui program n raport cu programul care calculeaz coeficientul conform definiiei:

    n

    m

    n

    m n m

    =

    !

    !( )!

    Soluie: Utilizarea definiiei pentru calculul combinrilor este o idee total neinspirat, nu numai n ceea ce privete eficiena, ci i pentru faptul c nu poate fi aplicat dect pentru valori foarte mici ale lui n. De exemplu, ntr-un long de 4 octei, valoarea 13! nu mai poate fi calculat. Funcia recursiv este 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 (vezi Exerciiul 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 )

  • 36 Programare orientat pe 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

  • 37

    3. Structuri elementare de date

    nainte de a elabora un algoritm, trebuie s ne gndim la modul n care reprezentm datele. n acest capitol vom trece n revist structurile fundamentale de date cu care vom opera. Presupunem n continuare c suntei deja familiarizai cu noiunile de fiier, tablou, list, graf, arbore i ne vom concentra mai ales pe prezentarea unor concepte mai particulare: heap-uri i structuri de mulimi disjuncte.

    3.1 Liste

    O list este o colecie de elemente de informaie (noduri) aranjate ntr-o anumit ordine. Lungimea unei liste este numrul de noduri din list. Structura corespunztoare de date trebuie s ne permit s determinm eficient care este primul/ultimul nod n structur i care este predecesorul/succesorul (dac exist) unui nod dat. Iat cum arat cea mai simpl list, lista liniar:

    O list circular este o list n care, dup ultimul nod, urmeaz primul, deci fiecare 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 liste etc. Implementarea unei liste se poate face n principal n dou moduri:

    Implementarea secvenial, n locaii succesive de memorie, conform ordinii nodurilor n list. Avantajele acestei tehnici sunt accesul rapid la predecesorul/succesorul unui nod i gsirea rapid a primului/ultimului nod. Dezavantajele sunt inserarea/tergerea relativ complicat a unui nod i faptul c, n general, nu se folosete ntreaga memorie alocat listei.

    Implementarea nlnuit. n acest caz, fiecare nod conine dou pri: informaia propriu-zis i adresa nodului succesor. Alocarea memoriei fiecrui nod se poate face n mod dinamic, n timpul rulrii programului. Accesul la un nod necesit parcurgerea tuturor predecesorilor si, ceea ce poate lua ceva mai

    alpha beta gamma deltacapullistei

    coadalistei

  • 38 Structuri elementare de date Capitolul 3

    mult timp. Inserarea/tergerea unui nod este n schimb foarte rapid. Se pot folosi dou adrese n loc de una, astfel nct un nod s conin pe lng adresa nodului succesor i adresa nodului predecesor. Obinem astfel o list dublu nlnuit, care poate fi traversat n ambele direcii.

    Listele implementate nlnuit pot fi reprezentate cel mai simplu prin tablouri. n acest caz, adresele sunt de fapt indici de tablou. O alternativ este s folosim tablouri paralele: s memorm informaia fiecrui nod (valoarea) ntr-o locaie VAL[i] a tabloului VAL[1 .. n], iar adresa (indicele) nodului su succesor ntr-o locaie LINK[i] a tabloului LINK[1 .. n]. Indicele de tablou al locaiei primului nod 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 o problem esenial: cea a gestionrii locaiilor libere. O soluie elegant este s reprezentm locaiile libere tot sub forma unei liste nlnuite. Atunci, tergerea unui nod din lista iniial implic inserarea sa n lista cu locaii libere, iar inserarea unui nod n lista iniial implic tergerea sa din lista cu locaii libere. Aspectul cel mai interesant este c, pentru implementarea listei de locaii libere, putem folosi aceleai tablouri. Avem nevoie de o alt variabil, freehead, care va conine indicele primei locaii libere din VAL i LINK. Folosim aceleai convenii: dac freehead = 0 nseamn c nu mai avem locaii libere, iar LINK[ultima locaie liber] = 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 de inserare/extragere a nodurilor se fac n/din coada listei. Dac nodurile A, B, C, D sunt inserate ntr-o stiv n aceast ordine, atunci primul nod care poate fi extras este D. n mod echivalent, spunem c ultimul nod inserat va fi i primul ters. Din acest motiv, stivele se mai numesc i liste LIFO (Last In First Out), sau liste pushdown.

    Cel mai natural mod de reprezentare pentru o stiv este implementarea secvenial ntr-un tablou S[1 .. n], unde n este numrul maxim de noduri. Primul nod va fi memorat n S[1], al doilea n S[2], iar ultimul n S[top], unde top este o variabil care conine adresa (indicele) ultimului nod inserat. Iniial, cnd stiva este vid, avem top = 0. Iat algoritmii de inserare i de tergere (extragere) a unui nod:

  • Seciunea 3.1 Liste 39

    function push(x, S[1 .. n]) {adaug nodul x n stiv} if top n then return stiv plin top top+1 S[top] x return succes

    function pop(S[1 .. n]) {terge ultimul nod inserat din stiv i l returneaz} if top 0 then return stiv vid x S[top] top top1 return x

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

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

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

    putem folosi o stiv pentru a memora rezultatele intermediare. ntr-o scriere simplificat, iat cum 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 fie deja n stiv atunci cnd ntlnim operatorul. Orice expresie aritmetic poate fi transformat astfel nct s ndeplineasc aceast condiie. Prin aceast transformare se obine binecunoscuta notaie postfixat (sau polonez invers), care se bucur de o proprietate remarcabil: nu sunt necesare paranteze pentru a indica ordinea operaiilor. Pentru exemplul de mai sus, notaia postfixat este:

    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 First Out).

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

  • 40 Structuri elementare de date Capitolul 3

    predecesoare primei locaii ocupate i fie head variabila care conine indicele locaiei ocupate ultima oar. Variabilele head i tail au aceeai valoare atunci i numai atunci cnd coada este vid. Iniial, avem head = tail = 0. Inserarea i tergerea (extragerea) unui nod necesit timp constant.

    function insert-queue(x, C[0 .. n1]) {adaug nodul x n capul cozii} head (head+1) mod n if head = tail then return coad plin C[head] x return succes

    function delete-queue(C[0 .. n1]) {terge nodul din coada listei i l returneaz} if head = tail then return coad vid tail (tail+1) mod n x C[tail] return x

    Este surprinztor faptul c testul de coad vid este acelai cu testul de coad plin. Dac am folosi toate cele n locaii, atunci nu am putea distinge ntre situaia de coad plin i cea de coad vid, deoarece n ambele situaii am avea head = tail. n consecin, se folosesc efectiv numai n1 locaii din cele n ale tabloului 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, iar M V V este o mulime de muchii. O muchie de la vrful a la vrful b este notat cu perechea ordonat (a, b), dac graful este orientat, i cu mulimea {a, b}, dac graful este neorientat. n cele ce urmeaz vom presupune c vrfurile a i b sunt diferite. Dou vrfuri unite printr-o muchie se numesc adiacente. Un drum 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 cu numrul muchiilor care l constituie. Un drum simplu este un drum n care nici un vrf nu se repet. Un ciclu este un drum care este simplu, cu excepia primului i ultimului vrf, care coincid. Un graf aciclic este un graf fr cicluri. Un subgraf al lui G este un graf , unde V' V, iar M' este format din muchiile din M care unesc vrfuri din V'. Un graf parial este un graf

  • Seciunea 3.2 Grafuri 41

    Un graf neorientat este conex, dac ntre oricare dou vrfuri exist un drum. Pentru grafuri orientate, aceast noiune este ntrit: un graf orientat este tare conex, dac ntre oricare dou vrfuri i i j exist un drum de la i la j i un drum de la j la i.

    n cazul unui graf neconex, se pune problema determinrii componentelor sale conexe. O component conex este un subgraf conex maximal, adic un subgraf conex n care nici un vrf din subgraf nu este unit cu unul din afar printr-o muchie a grafului iniial. mprirea unui graf G = n componentele sale conexe determin o partiie a lui V i una a lui M.

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

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

    Exist cel puin trei moduri evidente de reprezentare ale unui graf:

    Printr-o matrice de adiacen A, n care A[i, j] = true dac vrfurile i i j sunt adiacente, iar A[i, j] = false n caz contrar. O variant alternativ este s-i dm lui A[i, j] valoarea lungimii muchiei dintre vrfurile i i j, considernd A[i, j] = + atunci cnd cele dou vrfuri 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 vrfurile adiacente 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 conecteaz vrful respectiv.

    Prin liste de adiacen, adic prin ataarea la fiecare vrf i a listei de vrfuri adiacente 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, dac graful este neorientat, respectiv m, dac graful este orientat. Dac numrul muchiilor n graf este mic, aceast reprezentare este preferabil din punct de vedere al memoriei necesare. Este posibil s examinm toi vecinii unui vrf dat, n medie, n mai puin de n operaii. Pe de alt parte, pentru a determina dac dou vrfuri i i 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 dect consultarea unei valori logice n matricea de adiacen.

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

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

  • 42 Structuri elementare de date Capitolul 3

    3.3 Arbori cu rdcin

    Fie G un graf orientat. G este un arbore cu rdcina r, dac exist n G un vrf r din care oricare alt vrf poate fi ajuns printr-un drum unic.

    Definiia este valabil i pentru cazul unui graf neorientat, alegerea unei rdcini fiind ns n acest caz arbitrar: orice arbore este un arbore cu rdcin, iar rdcina poate fi fixat n oricare vrf al su. Aceasta, deoarece dintr-un vrf oarecare se poate ajunge n oricare alt vrf printr-un drum unic.

    Cnd nu va fi pericol de confuzie, vom folosi termenul arbore, n loc de termenul corect arbore cu rdcin. Cel mai intuitiv este s reprezentm un arbore cu rdcin, ca pe un arbore propriu-zis. n Figura 3.1, vom spune c beta este tatl lui delta i fiul lui alpha, c beta i gamma sunt frai, c delta este un descendent al lui alpha, iar alpha este un ascendent al 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 aceluiai printe: 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 din vrful respectiv i toi descendenii si. O mulime de arbori disjunci formeaz o pdure.

    ntr-un arbore cu rdcin vom adopta urmtoarele notaii. Adncimea unui vrf este lungimea drumului dintre rdcin i acest vrf; nlimea unui vrf este lungimea 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.

  • 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 cazul listelor nlnuite. Fiecare vrf va fi memorat n trei locaii diferite, reprezentnd informaia propriu-zis a vrfului (valoarea vrfului), adresa celui mai vrstnic fiu i adresa urmtorului frate. Pstrnd analogia cu listele nlnuite, dac se cunoate de la nceput numrul maxim de vrfuri, atunci implementarea arborilor cu rdcin se poate face prin tablouri paralele.

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

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

    binar de nlime i are cel mult 2i+11 vrfuri, iar dac are exact 2i+11 vrfuri, se numete arbore plin. Vrfurile unui arbore plin se numeroteaz n ordinea adncimii. Pentru aceeai adncime, numerotarea se face n arbore de la stnga la dreapta (Figura 3.3).

    Un arbore binar cu n vrfuri i de nlime i este complet, dac se obine din arborele 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 reprezenta secvenial folosind un tablou T, punnd vrfurile de adncime k, de la stnga la

    dreapta, n poziiile T[2k], T[2k+1], , T[2k+11] (cu posibila excepie a nivelului 0, 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.

  • 44 Structuri elementare de date Capitolul 3

    reprezentat un arbore binar complet cu zece vrfuri, obinut din arborele plin din Figura 3.3, prin eliminarea vrfurilor 11, 12, 13, 14 i 15. Tatl unui vrf reprezentat n T[i], i > 1, se afl n T[i div 2]. Fiii unui vrf reprezentat n T[i] se afl, dac exist, n T[2i] i T[2i+1].

    Facem acum o scurt incursiune n matematica elementar, pentru a stabili cteva rezultate de care vom avea nevoie n capitolele urmtoare. Pentru un numr real oarecare x, definim

    x = max{n n x, n este ntreg} i x = min{n n x,