1. Algoritmică şi programare

Manual de Informatică pentru licenţă iulie și septembrie 2018

Specializarea Informatică

Tematica generală:

Partea 1. Algoritmică şi programare

1. Căutari (secvenţială şi binară), interclasare, sortări (selecţie, bubblesort, inserție, mergesort, quicksort). Metoda backtracking.

2. Concepte OOP în limbaje de programare (Python, C++, Java, C#): Clase şi obiecte.

Membrii unei clase şi specificatorii de acces. Constructori şi destructori.

3. Relaţii între clase. Clase derivate şi relaţia de moştenire. Suprascrierea metodelor.

Polimorfism. Legare dinamica. Clase abstracte şi interfeţe.

4. Diagrame de clase si de interacțiune ȋntre obiecte în UML: Pachete, clase şi interfețe.

Relații între clase şi interfețe. Obiecte. Mesaje

5. Liste. Dicţionare. Specificarea operaţiilor caracteristice (fără implementări)

6. Identificarea structurilor şi tipurilor de date potrivite pentru rezolvarea problemelor (doar dintre cele de la punctul 5.). Folosirea unor biblioteci existente pentru aceste structuri (Python, Java, C++, C#).

Partea 2. Baze de date

1. Baze de date relaţionale. Primele trei forme normale ale unei relaţii.

2. Interogarea bazelor de date cu operatori din algebra relaţională.

3. Interogarea bazelor de date relaţionale cu SQL (Select).

Partea 3. Sisteme de operare

1. Structura sistemelor de fișiere Unix.

2. Procese Unix: creare, funcţiile fork, exec, exit, wait; comunicare prin pipe şi FIFO.

3. Programare shell Unix. Comenzi Unix de bază: cat, cp, cut, echo, expr, file, find, grep, less, ls, mkdir, mv, ps, pwd, read, rm, sort, test, wc, who.

Cuprins

1. ALGORITMICĂ ŞI PROGRAMARE ... 3

1.1. CĂUTĂRI ŞI SORTĂRI ... 3

1.1.1. Căutări ... 3

1.1.2. Interclasare ... 5

1.1.3. Sortări ... 6

1.1.4. Metoda backtracking ... 11

1.2. CONCEPTE OOP ÎN LIMBAJE DE PROGRAMARE ... 15

1.2.1. Noţiunea de clasă ... 15

1.3. RELAŢII ÎNTRE CLASE ... 24

1.3.1. Bazele teoretice ... 24

1.3.2. Declararea claselor derivate ... 24

1.3.3. Funcţii virtuale... 26

1.3.4. Clase abstracte... 30

1.3.5. Interfeţe ... 32

1.4. DIAGRAME DE CLASE ŞI INTERACŢIUNI ÎNTRE OBIECTE ÎN UML:PACHETE, CLASE ŞI INTERFEȚE.RELAȚII ÎNTRE CLASE ŞI INTERFEȚE.OBIECTE.MESAJE ... 34

1.4.1. Diagrame de clase ... 37

1.4.2. Diagrame de interacţiune ... 44

1.5. LISTE ŞI DICŢIONARE ... 46

1.5.1. Liste ... 47

1.5.2. Dicţionare ... 51

1.6. PROBLEME PROPUSE ... 53

2. BAZE DE DATE ... 55

2.1. BAZE DE DATE RELAŢIONALE.PRIMELE TREI FORME NORMALE ALE UNEI RELAŢII ... 55

2.1.1. Modelul relaţional ... 55

2.1.2. Primele trei forme normale ale unei relaţii ... 58

2.2. INTEROGAREA BD CU OPERATORI DIN ALGEBRA RELAŢIONALĂ ... 65

2.3. INTEROGAREA BAZELOR DE DATE RELAŢIONALE CU SQL ... 68

2.4. PROBLEME PROPUSE ... 74

3. SISTEME DE OPERARE ... 77

3.1. STRUCTURA SISTEMELOR DE FIŞIERE UNIX ... 77

3.1.1. Structura Internă a Discului UNIX ... 77

3.1.2. Tipuri de fişiere şi sisteme de fişiere... 80

3.2. PROCESE UNIX ... 84

3.2.1. Principalele apeluri system de gestiune a proceselor ... 84

3.2.2. Comunicarea între procese prin pipe ... 88

3.2.3. Comunicarea între procese prin FIFO ... 90

3.3. INTERPRETOARE ALE FIŞIERELOR DE COMENZI ... 94

3.3.1. Funcţionarea unui interpretor de comenzi shell ... 94

3.3.2. Programarea în shell ... 95

3.4. PROBLEME PROPUSE ... 97

4. BIBLIOGRAFIE GENERALĂ ... 99

1. Algoritmică şi programare

1.1. Căutări şi sortări

1.1.1. Căutări

Datele se află în memoria internă, într-un şir de articole. Vom căuta un articol după un câmp al acestuia pe care îl vom considera cheie de căutare. În urma procesului de căutare va rezulta poziţia elementului căutat (dacă acesta există).

Notând cu k1, k2, ...., kn cheile corespunzătoare articolelor şi cu a cheia pe care o căutăm, problema revine la a găsi (dacă există) poziţia p cu proprietatea a = kp.

De obicei articolele sunt păstrate în ordinea crescătoare a cheilor, deci vom presupune că k1 < k2 < .... < kn .

Uneori este util să aflăm nu numai dacă există un articol cu cheia dorită ci şi să găsim în caz contrar locul în care ar trebui inserat un nou articol având cheia specificată, astfel încât să se păstreze ordinea existentă.

Deci problema căutării are următoarea specificare:

Date a,n,(ki, i=1,n);

Precondiţia: nN, n1 şi k1 < k2 < .... < kn ; Rezultate p;

Postcondiţia: (p=1 şi a  k1) sau (p=n+1 şi a > kn) sau (1<pn) şi (kp-1 < a  kp).

1.1.1.1. Căutare secvenţială

O primă metodă este căutarea secvenţială, în care sunt examinate succesiv toate cheile.

Sunt deosebite trei cazuri: a≤k1, a>kn, respectiv k1 < a ≤ kn, căutarea având loc în al treilea caz.

Subalgoritmul CautSecv(a, n, K, p) este: {nN, n1 şi k1 < k2 < .... < kn} {Se caută p astfel ca: (p=1 şi a  k1) sau}

{ (p=n+1 şi a>kn) sau (1<pn) şi (kp-1 < a  kp).

Fie p := 0; {Cazul "încă negasit"}

Dacă a k1 atunci p := 1 altfel

Dacă a > kn atunci p := n + 1 altfel Pentru i := 2; n execută

Dacă (p = 0) şi (a ki) atunci p := i sfdacă sfpentru

sfdacă sfdacă sf-CautSecv

Se observă că prin această metodă se vor executa în cel mai nefavorabil caz n-1 comparări, întrucât contorul i va lua toate valorile de la 2 la n. Cele n chei împart axa reală în n+1 intervale.

Tot atâtea comparări se vor efectua în n-1 din cele n+1 intervale în care se poate afla cheia căutată, deci complexitatea medie are acelaşi ordin de mărime ca şi complexitatea în cel mai rău caz.

Evident că în multe situaţii acest algoritm face calcule inutile. Atunci când a fost deja găsită cheia dorită este inutil a parcurge ciclul pentru celelalte valori ale lui i. Cu alte cuvinte este posibil să înlocuim ciclul PENTRU cu un ciclu CÂTTIMP. Ajungem la un al doilea algoritm, dat în continuare.

Subalgoritmul CautSucc(a, n, K, p) este: {nN, n1 şi k1 < k2 < .... < kn} {Se caută p astfel ca: p=1 şi a  k1) sau } {(p=n+1 şi a>kn) sau (1<pn) şi (kp-1 < a  kp).

Fie p:=1;

Dacă a>k1 atunci

Câttimp pn şi a>kp execută p:=p+1 sfcât sfdacă

sf-CautSucc

În cel mai rău caz şi acest algoritm face acelaşi număr de operaţii ca şi subalgoritmul Cautsecv. În medie numărul operaţiilor este jumătate din numărul mediu de operaţii efecuat de subalgoritmul Cautsecv deci complexitatea este aceeaşi.

1.1.1.2. Căutare binară

O altă metodă, numită căutare binară, care este mult mai eficientă, utilizează tehnica

"divide et impera" privitor la date. Se determină în ce relaţie se află cheia articolului aflat în mijlocul colecţiei cu cheia de căutare. În urma acestei verificări căutarea se continuă doar într-o jumătate a colecţiei. În acest mod, prin înjumătăţiri succesive se micşorează volumul colecţiei rămase pentru căutare. Căutarea binară se poate realiza practic prin apelul funcţiei

BinarySearch(a, n, K, 1, n), descrisă mai jos, folosită în subalgoritmul dat în continuare.

Subalgoritmul CautBin(a, n, K, p) este: {nN, n1 şi k1 < k2 < .... < kn} {Se caută p astfel ca: (p=1 şi a  k1) sau}

{(p=n+1 şi a>kn) sau (1<pn) şi (kp-1 < a  kp)}

Dacă a k1 atunci p := 1 altfel

Dacă a > kn atunci p := n+1 altfel P := BinarySearch(a, n, K, 1, n) sfdacă

sfdacă sf-CautBin

Funcţia CăutareBinară(a, n, K, St, Dr) este:

Dacă St Dr - 1

atunci CăutareBinară := Dr altfel m := (St+Dr) Div 2;

Dacă a km

atunci CăutareBinară := CăutareBinară(a, n, K, St, m) altfel CăutareBinară:= CăutareBinară(a, n, K, m, Dr) sfdacă

sfdacă

sf-CăutareBinară

În funcţia CăutareBinară descrisă mai sus, variabilele St şi Dr reprezintă capetele intervalului de căutare, iar m reprezintă mijlocul acestui interval. Prin această metodă, într-o colecţie având ⁿ elemente, rezultatul căutării se poate furniza după cel mult log2n comparări.

Deci complexitatea în cel mai rău caz este direct proporţională cu log2n. Fără a insista asupra demonstraţiei, menţionăm că ordinul de mărime al complexităţii medii este acelaşi.

Se observă că funcţia CăutareBinarăNerec se apelează recursiv. Se poate înlătura uşor recursivitatea, aşa cum se poate vedea în următoarea funcţie:

Funcţia CăutareBinarăNerec(a, n, K, St, Dr) este:

Câttimp Dr – St > 1 execută m := (St+Dr) Div 2;

Dacă a km atunci Dr := m altfel St := m sfdacă sfcât

CăutareBinarăNerec := Dr sf- CăutareBinarăNerec

1.1.2. Interclasare

Fiind date două secvențe de date, ordonate crescător (sau descrescător) după o cheie, se cere să se obţină o colecţie care să fie de asemenea ordonată crescător (respectiv descrescător) după aceeaşi cheie şi care să fie formată din elementele secvențelor date. Acest lucru se poate obţine direct (fără o sortare a secvenței finale) prin parcurgerea secvenţială a celor două secvențe, simultan cu generarea secvenței cerute. Prin compararea a două elemente din secvențele de intrare se va decide care element va fi adăugat în secvența de ieşire.

Menționăm că sunt două tipuri de interclasări: (1) interclasare cu păstrarea dublurilor (în acest caz se păstrează în colecția rezultat toate elementele din cele două secvențe inițiale, chiar dacă elementele se repetă) și (2) interclasare fără păstrarea dublurilor (în acest caz se păstrează în secvența rezultat toate elementele distincte din cele două secvențe).

În continuare vom prezenta interclasare cu păstrarea dublurilor. Lăsăm ca exercițiu varianta de interclasare fără păstrarea dublurilor

Deci ne interesează un algoritm de rezolvare a problemei ce are următoarea specificare:

Date m, (xi, i=1,m), n, (yi, i=1,n);

Precondiţia: {x1  x2  ...  xm} şi {y1  y2  ...  yn}

Rezultate k, (zi, i=1,k);

Postcondiţia: {k=m+n} şi {z1 z2 ... zk} şi (z1,z2,..., zk) este o permutare a valorilor (x1, ..., xm,y1,..., yn)

O soluţie posibilă ar fi depunerea componentelor vectorului X şi a componentelor vectorului Y în vectorul Z, realizând astfel a doua parte din postcondiţie. Ordonând apoi componentele vectorului Z obţinem soluţia dorită. Acest algoritm, deşi corect, este ineficient.

Este important ca la o singură trecere prin vectorii X şi Y să se obţină vectorul Z. Acest lucru este realizat de următorul algoritm de interclasare:

Subalgoritmul Interclasare(m,X,n,Y,k,Z) este: {X are cele m componente}

{ordonate crescător. La fel Y cu n componente}

{Cele m+n valori se depun în Z, tot ordonate crescător}

Fie i:=1; j:=1; k:=0;

Câttimp (i<=m) şi (j<=n) execută {Există componente}

Dacă xiyj

atunci Cheamă ADAUGĂ(xi,k,Z) {şi în X}

i:=i+1

altfel Cheamă ADAUGĂ (yj,k,Z) {şi în Y}

j:=j+1 sfdacă

sfcât

Câttimp (i<=m) execută {Există componente}

Cheamă ADAUGĂ (xi,k,Z) {numai în X}

i:=i+1 {avansează în vectorul X}

sfcât

Câttimp (j<=n) execută {Există componente}

Cheamă ADAUGĂ (yj,k,Z) {numai în Y}

j:=j+1 {avansează în vectorul Y}

sfcât

sf-Interclasare

Aici s-a folosit subalgoritmul ADAUGĂ(val,k,Z) care adaugă valoarea val la sfârșitul vectorului Z având k elemente, subalgoritm dat în continuare.

Subalgoritmul ADAUGĂ(val,k,Z) este: {Adaugă val}

k:=k+1; {la finalul vectorul Z cu}

zk:=val; {k componente}

sf-ADAUGĂ

Complexitatea subalgoritmului Interclasare descris anterior este (mn). Spațiul suplimentar de memorare necesar pentru subalgoritmul de interclasare este (1).

1.1.3. Sortări

Prin sortare internă vom înţelege o rearanjare a unei colecţii aflate în memoria internă astfel încât cheile articolelor să fie ordonate crescător (eventual descrescător).

Din punct de vedere al complexităţii algoritmilor problema revine la ordonarea cheilor.

Deci specificarea problemei de sortare internă este următoarea:

Date n,K; {K=(k1,k2,...,kn)}

Precondiţia: kiR, i=1,n Rezultate K';

Postcondiţia: K' este o permutare a lui K, dar ordonată crescător.

Deci k1  k2  ...  kn.

1.1.3.1. Sortare prin selecţie

O primă tehnică numită "Selecţie" se bazează pe următoarea idee: se determină poziţia elementului cu cheie de valoare minimă (respectiv maximă), după care acesta se va interschimba cu primul element. Acest procedeu se repetă pentru subcolecţia rămasă, până când mai rămâne doar elementul maxim.

Subalgoritmul Selectie(n, K) este: {Se face o permutare a celor}

{n componente ale vectorului K astfel}

{ca k1  k2  ....  kn } Pentru i := 1; n-1 execută

Fie ind := i;

Pentru j := i + 1; n execută

Dacă kj < kind atunci ind := j sfdacă sfpentru

Dacă i < ind atunci t := ki; ki := kind; kind := t sfdacă sfpentru

sf-Selectie

Se observă că numărul de comparări este:

(n-1)+(n-2)+...+2+1=n(n-1)/2

indiferent de natura datelor. Deci complexitatea medie, dar şi în cel mai rău caz este O(n²).

1.1.3.2. Bubble sort

Metoda "BubbleSort", compară două câte două elemente consecutive iar în cazul în care acestea nu se află în relaţia dorită, ele vor fi interschimbate. Procesul de comparare se va încheia în momentul în care toate perechile de elemente consecutive sunt în relaţia de ordine dorită.

Subalgoritmul BubbleSort(n, K) este:

Repetă

Fie kod := 0; {Ipoteza "este ordine"}

Pentru i := 2; n execută Dacă ki-1 > ki atunci

t := ki-1; ki-1 := ki;

ki := t;

kod := 1 {N-a fost ordine!}

sfdacă sfpentru

pânăcând kod = 0 sfrep {Ordonare}

sf-BubbleSort

Acest algoritm execută în cel mai nefavorabil caz (n-1)+(n-2)+ ... +2+1 = n(n-1)/2 comparări, deci complexitatea lui este O(n²).

O variantă optimizată a algoritmului "BubbleSort" este :

Subalgoritmul BubbleSort(n, K) este:

Fie s := 0 Repetă

Fie kod := 0; {Ipoteza "este ordine"}

Pentru i := 2; n-s execută Dacă ki-1 > ki atunci

t := ki-1; ki-1 := ki; ki := t;

kod := 1 {N-a fost ordine!}

sfdacă sfpentru s := s + 1

pânăcând kod = 0 sfrep {Ordonare}

sf-BubbleSort

1.1.3.3. Sortarea prin inserție

Ideea de bază a acestei metode de sortare este că, în timpul parcurgerii elementelor, inserăm elementul curent la poziția corectă în secvența de elemente deja sortată. Astfel, secvența conținând elementele deja prelucrate este păstrată sortată, iar la finalul parcurgerii, întreaga secvență va fi sortată. Acest algoritm se numește Sortare prin inserție (InsertionSort).

Subalgoritm SortareInserție(n, K) este:

Pentru i:=2; n execută Fie ind:=i-1; a:=ki;

Câttimp ind>0 și a<kind execută kind+1 := kind ;

ind:=ind-1 sfcât

kind+1:=a sfpentru

sf-SortareInserție

Acest algoritm execută în cel mai nefavorabil caz (n-1)+(n-2)+ ... +2+1 = n(n-1)/2 comparări, deci complexitatea lui este O(n²).

1.1.3.4. Sortare prin interclasare (Merge Sort)

Vom folosi în cele ce urmează o variantă ușor modificată a subalgoritmului Interclasare, (descris în Secțiunea 1.1.2) pentru a interclasa subsecvențe. Această versiune va interclasa X[sx,

…, dx] și Y[sy, …, dy] în Z[1,…,k].

Subalgoritm InterclasareSubSecv(sx,dx,X,sy,dy,Y,k,Z) este:

{X are componentele sx,…,dx ordonate crescător. Y are sy,…,dy ordonate}

{crescător. Toate aceste valori se adaugă în Z, ordonat crescător.}

Fie i:=sx; j:=sy; k:=0;

Câttimp (i<=dx) și (j<=dy) execută{Sunt componente de procesat}

Dacă xiyj

atunci Cheamă ADAUGĂ(xi,k,Z) {în X}

i:=i+1

altfel Cheamă ADAUGĂ(yj,k,Z) {în Y}

j:=j+1 sfdacă

sfcât

Câttimp (i<=dx) execută {Sunt componente}

Cheamă ADAUGĂ (xi,k,Z) {doar în X}

i:=i+1 sfcât

Câttimp (j<=dy) execută { Sunt componente } Cheamă ADAUGĂ (yj,k,Z) {doar în Y}

j:=j+1 sfcât

sf-InterclasareSubSecv

Algoritmul Sortare-Interclasare penrtu sortarea unei secvențe S cu n elemente se folosește strategia divide-et-impera:

1.

2

n elemente și S2 conține restul elementelor).

2.

3.

Subalgoritmul SortareInterclasare este descris mai jos.

Subalgoritm SortareInterclasare (n,A) este:

Cheamă SortareInterclasareRec (1,n,A);

Sf-SortareInterclasare

Subalgoritm SortareInterclasareRec (Stânga,Dreapta,A) este:

{Sortare prin interclasare a secvenței AStânga,AStânga+1,...,ADreapta} Dacă Stânga < Dreapta

atunci

Fie m:=(Stânga + Dreapta) div 2;

Cheamă SortareInterclasareRec (Stânga,m,A);

Cheamă SortareInterclasareRec (m+1, Dreapta,A);

Cheamă InterclasareSubSecv (Stânga,m,A,m+1,Dreapta,A,k,C);

Fie A[Stânga…Dreapta]=C[1…k];

sfdacă

sf-SortareInterclasareRec

Subalgoritmul de mai sus sortează recursiv cele două părtți ale unei secvențe si apoi le interclasează într-un vector extern C. La final,vectorul C este re-copiat în subsecvența A.

Complexitatatea timp pentru SortareInterclasare este (nlog₂ n)^.

Se observă faptul că subalgoritmul SortareInterclasare folosește spațiu suplimentare de memorare (n) necesar pentru interclasarea celor două subșiruri.

1.1.3.5. Quicksort

O metodă mai performantă de ordonare, care va fi prezentată în continuare, se numeşte

"QuickSort" şi se bazează pe tehnica "divide et impera" după cum se poate observa în continuare. Metoda este prezentată sub forma unei proceduri care realizează ordonarea unui subşir precizat prin limita inferioară şi limita superioară a indicilor acestuia. Apelul procedurii pentru ordonarea întregului şir este : QuickSort(n, K, 1, n), unde n reprezintă numărul de articole ale colecţiei date. Deci

Subalgoritmul SortareRapidă(n, K) este:

Cheamă QuickSort(n, K, 1, n) sf-SortareRapidă

Procedura QuickSort(n, K, St, Dr) va realiza ordonarea subşirului kSt, kSt+1, ..., kDr. Acest subşir va fi rearanjat astfel încât kSt să ocupe poziţia lui finală (când şirul este ordonat). Dacă ⁱ este această poziţie, şirul va fi rearanjat astfel încât următoarea condiţie să fie îndeplinită:

kj  ki  kl , pentru st  j < i < l dr (*)

Odată realizat acest lucru, în continuare va trebui doar să ordonăm subşirul ^kSt, kSt+1, ... ,ki-1 prin apelul recursiv al procedurii QuickSort(n, K, St, i-1) şi apoi subşirul ki+1, ...,kDr prin apelul QuickSort(n, K, i+1, Dr). Desigur ordonarea acestor două subşiruri (prin apelul recursiv al procedurii) mai este necesară doar dacă acestea conţin cel puţin două elemente.

Procedura ^QuickSort este prezentată în continuare :

Subalgoritmul QuickSort (n, K, St, Dr) este:

Fie i := St; j := Dr; a := ki; Repetă

Câttimp kj  a şi (i < j) execută j := j - 1 sfcât ki := kj;

Câttimp ki  a şi (i < j) execută i := i + 1 sfcât kj := ki ;

pânăcând i = j sfrep Fie ki := a;

Dacă St < i-1 atunci Cheamă QuickSort(n, K, St, i - 1) sfdacă Dacă i+1 < Dr atunci Cheamă QuickSort(n, K, i + 1, Dr) sfdacă sf-QuickSort

Complexitatea algoritmului prezentat este O(n²) în cel mai nefavorabil caz, dar complexitatea medie este de ordinul O(nlog2n).

1.1.4. Metoda backtracking

Metoda backtracking (căutare cu revenire) este aplicabilă in general unor probleme ce au mai multe soluţii.

Vom considera întâi un exemplu, după care vom indica câţiva algoritmi generali pentru această metodă.

Problema 1. (Generarea permutărilor) Fie n un număr natural. Determinaţi permutările numerelor 1, 2, ..., n.

O soluţie pentru generarea permutărilor, în cazul particular n = 3, ar putea fi:

Subalgoritmul Permutări1 este:

Pentru i1 := 1; 3 execută Pentru i2 := 1; 3 execută

Pentru i3 := 1; 3 execută

Fie posibil := (i1, i2, i3)

Dacă componentele vectorului posibil sunt distincte atunci

Tipăreşte posibil sfdacă

sfpentru sfpentru sfpentru sf-Permutări1

1

1

1 2 3 2

1 2 3 3

1 2 3

2

1

1 2 3 2

1 2 3 3

1 2 3

3

1

1 2 3 2

1 2 3 3

1 2 3

x₁

x₂

x₃

Figura 1.1 Reprezentare grafică a produsului cartezian {1, 2, 3}³

Observaţii privind subalgoritmul Permutări1:

 Pentru n oarecare nu putem descrie un algoritm care să conţină n cicluri în textul sursă.

 Numărul total de vectori verificaţi este 3³, iar în general nⁿ. Vectorii posibil verificaţi sunt reprezentaţi grafic în Figura 1.1 - fiecare vector este un drum de la rădăcină (de sus) spre frunze (baza arborelui).

 Algoritmul atribuie valori tuturor componentelor vectorului x, apoi verifică dacă vectorul este o permutare.

O îmbunătăţire a acestor algoritmi ar consta în a verifica anumite condiţii din problemă în timp ce se construiesc vectorii, evitând completarea inutilă a unor componente.

De exemplu, dacă prima componentă a vectorului construit (posibil) este 1, atunci este inutil să atribuim celei de a doua componente valoarea 1, iar componentei a treia oricare din valorile 1, 2 sau 3. Dacă n este mare se evită completarea multor vectori ce au prefixul (1, ...). În acest sens, (1, 3, ...) este un vector promiţător (pentru a fi o permutare), în schimb vectorul (1, 1, ...) nu este. Vectorul (1, 3, ...) satisface anumite condiţii de continuare (pentru a ajunge la soluţie) - are componente distincte. Nodurile haşurate din Figura 1.1 constituie valori care nu conduc la o soluţie.

Vom descrie un algoritm general pentru metoda Bactracking după care vom particulariza acest algoritm pentru problemele enunţate la începutul secţiunii. Pentru început vom face câteva observaţii şi notaţii privind metoda Backtracking aplicată unei probleme în care soluţiile se reprezintă pe vectori, nu neapărat de lungime fixă:

 spaţiul de căutare a soluţiilor (spaţiul soluţiilor posibile): S = S1 x S2 x ... x Sn;

 posibil este vectorul pe care se reprezintă soluţiile;

 posibil[1..k]  S1 x S2 x ... x Sk este un vector care poate conduce sau nu la o soluţie; k reprezintă indice pentru vectorul posibil, respectiv nivel în arborele care redă grafic procesul de căutare (Figura 1.2).

 posibil[1..k] este promiţător dacă satisface condiţii care pot conduce la o soluţie;

 soluţie(n, k, posibil) funcţie care verifică dacă vectorul (promiţător) posibil[1..k] este soluţie a problemei.

Figura 1.2. Spaţiul soluţiilor posibile pentru generarea permutărilor

Procesul de căutare poate fi urmărit în algoritmul care urmează:

Algoritmul Backtracking este: {varianta nefinisată}

Fie k := 1

@Iniţializează căutarea pe nivelul k (= 1)

Câttimp k > 0 execută {posibil[1..k-1] este promiţător}

@Caută (secvenţial) pe nivelul k o valoare v, pentru a completa în continuare vectorul posibil[1..k-1] astfel încât posibil[1..k] să fie promiţător

Dacă căutarea este cu succes

atunci Fie posibil[k] := v {posibil[1..k] este promiţător}

Dacă soluţie(n, k, posibil)

atunci {o soluţie! (rămânem pe nivelul k)}

Tipareşte posibil[1..k]

altfel {e doar un vector promiţător}

@Initializeaza cautarea pe nivelul k+1

Fie k := k + 1 {pas în faţă (pe nivelul k+1)}

sfdacă

altfel {pas în spate (revenire pe nivelul k-1)}

k := k - 1 sfdacă

sfcât

sf-Backtracking

Pentru a finisa acest algoritm trebuie să precizăm elementele nestandard prezente. Astfel, avem nevoie de funcţia booleană

condiţii-continuare(k, posibil, v)

funcţie care verifică dacă vectorul promiţător posibil[1..k-1] completat cu valoarea v conduce la un vector promiţător.

Apoi, pentru a iniţializa căutarea la nivelul j avem nevoie de a alege un element fictiv din mulţimea Sj, activitate realizată de funcţia

init(j)

care returnează acest element fictiv, care are rolul de a indica faptul că din mulţimea S încă nu s- a ales nici un element, deci după el urmează primul element propriu din această mulţime. Pentru a căuta o valoare pe nivelul j, în ipoteza că valoarea curentă nu e bună, avem nevoie de funcţia booleană

următor(j, v, nou)

care este True dacă poate alege o valoare din Sj care urmează după valoarea v, valoare notată prin nou şi False în cazul în care nu mai există alte valori în Sj, deci nu mai poate fi făcută alegerea. Cu aceste notaţii algoritmul devine:

Algoritmul Backtracking este: {versiune finală}

Fie k := 1;

posibil[1] := init(1);

Câttimp k > 0 execută {posibil[1..k-1] este promiţător}

Fie Găsit := false; v := posibil[k];

Câttimp Următor(k, v,urm) şi not Găsit execută Fie v := urm;

Dacă condiţii-continuare(k, posibil, v) atunci Găsit := true

sfdacă sfcât

Dacă Găsit

atunci Fie posibil[k] := v; {posibil[1..k] este promiţător}

Dacă soluţie(n, k, posibil)

atunci {o soluţie! (rămânem pe nivelul k)}

Tipareşte posibil[1..k]

altfel {e doar un vector promiţător}

Fie k := k + 1; {pas în faţă (pe nivelul k+1)}

posibil[k] := init(k) sfdacă

altfel {pas în spate (revenire pe nivelul k-1)}

k := k - 1;

sfdacă sfcât

sf-Backtracking

Procesul de căutare a unei valori pe nivelul k şi funcţiile condiţii-continuare şi soluţie sunt dependente de problema care se rezolvă. De exemplu, pentru generarea permutărilor funcţiile menţionate sunt:

Funcţia init(k) este:

Init := 0 sf-init;

Funcţia Următor(k, v, urm) este:

Dacă v < n

atunci Următor := True; urm := v + 1 altfel Următor := False

sfdacă sf-urmator

Funcţia conditii-continuare(k, posibil, v) este:

Kod := True; i := 1;

Câttimp kod şi (i < k) execută

Dacă posibil[i] = v atunci kod := False sfdacă i := i + 1;

sfcât

conditii-continuare:=kod sf-conditii

Funcţia soluţii(n, k, posibil) este:

Soluţii := (k = n) sf-solutii

În încheiere, menţionăm că explorarea backtracking poate fi descrisă de asemenea recursiv. Dăm în acest scop următoru subalgoritm:

Subalgoritmul Backtracking(k, posibil) este:

{posibil[1..k] este promiţător}

Dacă soluţie(n, k, posibil) atunci

{o soluţie! terminare apel recursiv, astfel}

Tipareste posibil[1..k]

{rămânem pe acelaşi nivel}

altfel

Pentru fiecare v valoare posibilă pentru posibil[k+1] execută Dacă condiţii-continuare(k + 1, posibil, v) atunci posibil[k + 1] := v

Backtracking(k + 1, posibil) {pas in faţă}

sfdacă sfpentru sfdacă

{terminare apel Backtracking(k, posibil)}

sf-Backtracking {deci, pas în spate (revenire)}

cu apelul iniţial Cheamă Backtracking(0, posibil).

1.2. Concepte OOP în limbaje de programare

1.2.1. Noţiunea de clasă

1.2.1.1. Realizarea protecţiei datelor prin metoda programării modulare

Dezvoltarea programelor prin programare procedurală înseamnă folosirea unor funcţii şi proceduri pentru scrierea programelor. În limbajul C lor le corespund funcţiile care returnează o valoare sau nu. Însă în cazul aplicaţiilor mai mari ar fi de dorit să putem realiza şi o protecţie corespunzătoare a datelor. Acest lucru ar însemna că numai o parte a funcţiilor să aibă acces la datele problemei, acelea care se referă la datele respective. Programarea modulară oferă o posibilitate de realizare a protecţiei datelor prin folosirea clasei de memorie static. Dacă într-un fişier se declară o dată aparţinând clasei de memorie statică în afara funcţiilor, atunci ea poate fi folosită începând cu locul declarării până la sfârşitul modulului respectiv, dar nu şi în afara lui.

Să considerăm următorul exemplu simplu referitor la prelucrarea vectorilor de numere întregi. Să se scrie un modul referitor la prelucrarea unui vector cu elemente întregi, cu funcţii corespunzătoare pentru iniţializarea vectorului, eliberarea zonei de memorie ocupate şi ridicarea la pătrat, respectiv afişarea elementelor vectorului. O posibilitate de implementare a modulului este prezentată în fişierul vector1.cpp:

#include <iostream>

using namespace std;

static int* e; //elementele vectorului static int d; //dimensiunea vectorului

void init(int* e1, int d1) //initializare {

d = d1;

e = new int[d];

for(int i = 0; i < d; i++) e[i] = e1[i];

}

void distr() //eliberarea zonei de memorie ocupata {

delete [] e;

}

void lapatrat() //ridicare la patrat {

for(int i = 0; i < d; i++) e[i] *= e[i];

}

void afiseaza() //afisare {

for(int i = 0; i < d; i++) cout << e[i] << ' ';

cout << endl;

}

Modulul se compilează separat obţinând un program obiect. Un exemplu de program principal este prezentat în fişierul vector2.cpp:

extern void init( int*, int); //extern poate fi omis extern void distr();

extern void lapatrat();

extern void afiseaza();

//extern int* e;

int main() {

int x[5] = {1, 2, 3, 4, 5};

init(x, 5);

lapatrat();

afiseaza();

distr();

int y[] = {1, 2, 3, 4, 5, 6};

init(y, 6);

//e[1]=10; eroare, datele sunt protejate lapatrat();

afiseaza();

distr();

return 0;

}

Observăm că deşi în programul principal se lucrează cu doi vectori nu putem să-i folosim împreună, deci de exemplu modulul vector1.cpp nu poate fi extins astfel încât să realizeze şi adunarea a doi vectori. În vederea înlăturării acestui neajuns s-au introdus tipurile abstracte de date.

1.2.1.2. Tipuri abstracte de date

Tipurile abstracte de date realizează o legătură mai strânsă între datele problemei şi operaţiile (funcţiile) care se referă la aceste date. Declararea unui tip abstract de date este asemănătoare cu declararea unei structuri, care în afară de date mai cuprinde şi declararea sau definirea funcţiilor referitoare la acestea.

De exemplu în cazul vectorilor cu elemente numere întregi putem declara tipul abstract:

struct vect { int* e;

int d;

void init(int* e1, int d1);

void distr() { delete [] e; } void lapatrat();

void afiseaza();

};

Funcţiile declarate sau definite în interiorul structurii vor fi numite funcţii membru iar datele date membru. Dacă o funcţie membru este definită în interiorul structurii (ca şi funcţia distr din exemplul de mai sus), atunci ea se consideră funcţie inline. Dacă o funcţie membru se defineşte în afara structurii, atunci numele funcţiei se va înlocui cu numele tipului abstract urmat de operatorul de rezoluţie (::) şi numele funcţiei membru. Astfel funcţiile init, lapatrat şi afiseaza vor fi definite în modul următor:

void vect::init(int *e1, int d1) {

d = d1;

e = new int[d];

for(int i = 0; i < d; i++) e[i] = e1[i];

}

void vect::lapatrat() {

for(int i = 0; i < d; i++) e[i] *= e[i];

}

void vect::afiseaza() {

for(int i = 0; i < d; i++) cout << e[i] << ' ';

cout << endl;

}

Deşi prin metoda de mai sus s-a realizat o legătură între datele problemei şi funcţiile referitoare la aceste date, ele nu sunt protejate, deci pot fi accesate de orice funcţie utilizator, nu numai de funcţiile membru. Acest neajuns se poate înlătura cu ajutorul claselor.

1.2.1.3. Declararea claselor

Un tip abstract de date clasă se declară ca şi o structură, dar cuvântul cheie struct se înlocuieşte cu class. Ca şi în cazul structurilor referirea la tipul de dată clasă se face cu numele după cuvântul cheie class (numele clasei). Protecţia datelor se realizează cu modificatorii de protecţie: private, protected şi public. După modificatorul de protecţie se pune caracterul ‘:’. Modificatorul private şi protected reprezintă date protejate, iar public date neprotejate. Domeniul de valabilitate a modificatorilor de protecţie este până la următorul modificator din interiorul clasei, modificatorul implicit fiind private. Menţionăm că şi în cazul structurilor putem să folosim modificatori de protecţie, dar în acest caz modificatorul implicit este public.

De exemplu clasa vector se poate declara în modul următor:

class vector {

int* e; //elementele vectorului int d; //dimensiunea vectorului public:

vector(int* e1, int d1);

~vector() { delete [] e; } void lapatrat();

void afiseaza();

};

Se observă că datele membru e şi d au fost declarate ca date de tip private (protejate), iar funcţiile membru au fost declarate publice (neprotejate). Bineînţeles, o parte din datele membru pot fi declarate publice, şi unele funcţii membru pot fi declarate protejate, dacă natura problemei cere acest lucru. În general, datele membru protejate pot fi accesate numai de funcţiile membru ale clasei respective şi eventual de alte funcţii numite funcţii prietene (sau funcţii friend).

O altă observaţie importantă referitoare la exemplul de mai sus este că iniţializarea datelor membru şi eliberarea zonei de memorie ocupată s-a făcut prin funcţii membru specifice.

Datele declarate cu ajutorul tipului de dată clasă se numesc obiectele clasei, sau simplu obiecte. Ele se declară în mod obişnuit în forma:

nume_clasă listă_de_obiecte;

De exemplu, un obiect de tip vector se declară în modul următor:

vector v;

Iniţializarea obiectelor se face cu o funcţie membru specifică numită constructor. În cazul distrugerii unui obiect se apelează automat o altă funcţie membru specifică numită destructor.

În cazul exemplului de mai sus

vector(int* e1, int d1);

este un constructor, iar

~vector() { delete [] e; }

este un destructor.

Tipurile abstracte de date de tip struct pot fi şi ele considerate clase cu toate elementele neprotejate. Constructorul de mai sus este declarat în interiorul clasei, dar nu este definit, iar destructorul este definit în interiorul clasei. Rezultă că destructorul este o funcţie inline.

Definirea funcţiilor membru care sunt declarate, dar nu sunt definite în interiorul clasei se face ca şi în cazul tipurilor abstracte de date de tip struct, folosind operatorul de rezoluţie.

1.2.1.4. Membrii unei clase. Pointerul this

Referirea la datele respectiv funcţiile membru ale claselor se face cu ajutorul operatorilor punct (.) sau săgeată (->) ca şi în cazul referirii la elementele unei structuri. De exemplu, dacă se declară:

vector v;

vector* p;

atunci afişarea vectorului v respectiv a vectorului referit de pointerul p se face prin:

v.afiseaza();

p->afiseaza();

În interiorul funcţiilor membru însă referirea la datele respectiv funcţiile membru ale clasei se face simplu prin numele acestora fără a fi nevoie de operatorul punct (.) sau săgeată (->). De fapt compilatorul generează automat un pointer special, pointerul this, la fiecare apel de funcţie membru, şi foloseşte acest pointer pentru identificarea datelor şi funcţiilor membru.

Pointerul this va fi declarat automat ca pointer către obiectul curent. În cazul exemplului de mai sus pointerul this este adresa vectorului v respectiv adresa referită de pointerul p.

Dacă în interiorul corpului funcţiei membru afiseaza se utilizează de exemplu data membru d, atunci ea este interpretată de către compilator ca şi this->d.

Pointerul this poate fi folosit şi în mod explicit de către programator, dacă natura problemei necesită acest lucru.

1.2.1.5. Constructorul

Iniţializarea obiectelor se face cu o funcţie membru specifică numită constructor. Numele constructorului trebuie să coincidă cu numele clasei. O clasă poate să aibă mai mulţi constructori. În acest caz aceste funcţii membru au numele comun, ceea ce se poate face datorită posibilităţii de supraîncărcare a funcţiilor. Bineînţeles, în acest caz numărul şi/sau

tipul parametrilor formali trebuie să fie diferit, altfel compilatorul nu poate să aleagă constructorul corespunzător.

Constructorul nu returnează o valoare. În acest caz nu este permis nici folosirea cuvântului cheie void.

Prezentăm în continuare un exemplu de tip clasa cu mai mulţi constructori, având ca date membru numele şi prenumele unei persoane, şi cu o funcţie membru pentru afişarea numelui complet.

Fişierul persoana.h:

class persoana { char* nume;

char* prenume;

public:

persoana(); //constructor implicit persoana(char* n, char* p); //constructor

persoana(const persoana& p1); //constructor de copiere ~persoana(); //destructor

void afiseaza();

};

Fişierul persoana.cpp:

#include <iostream>

#include <cstring>

#include "persoana.h"

using namespace std;

persoana::persoana() {

nume = new char[1];

*nume = 0;

prenume = new char[1];

*prenume = 0;

cout << "Apelarea constructorului implicit." << endl;

}

persoana::persoana(char* n, char* p) {

nume = new char[strlen(n)+1];

prenume = new char[strlen(p)+1];

strcpy(nume, n);

strcpy(prenume, p);

cout << "Apelare constructor (nume, prenume).\n";

}

persoana::persoana(const persoana& p1) {

nume = new char[strlen(p1.nume)+1];

strcpy(nume, p1.nume);

prenume = new char[strlen(p1.prenume)+1];

strcpy(prenume, p1.prenume);

cout << "Apelarea constructorului de copiere." << endl;

}

persoana::~persoana() {

delete[] nume;

delete[] prenume;

}

void persoana::afiseaza() {

cout << prenume << ' ' << nume << endl;

}

Fişierul persoanaTest.cpp:

#include "persoana.h"

int main() {

persoana A; //se apeleaza constructorul implicit A.afiseaza();

persoana B("Stroustrup", "Bjarne");

B.afiseaza();

persoana *C = new persoana("Kernighan","Brian");

C->afiseaza();

delete C;

persoana D(B); //echivalent cu persoana D = B;

//se apeleaza constructorul de copire D.afiseaza();

return 0;

}

Observăm prezenţa a doi constructori specifici: constructorul implicit şi constructorul de copiere. Dacă o clasă are constructor fără parametri atunci el se va numi constructor implicit.

Constructorul de copiere se foloseşte la iniţializarea obiectelor folosind un obiect de acelaşi tip (în exemplul de mai sus o persoană cu numele şi prenumele identic). Constructorul de copiere se declară în general în forma:

nume_clasă(const nume_clasă& obiect);

Cuvântul cheie const exprimă faptul că argumentul constructorului de copiere nu se modifică.

O clasă poate să conţină ca date membru obiecte ale unei alte clase. Declarând clasa sub forma:

class nume_clasa { nume_clasa_1 ob_1;

nume_clasa_2 ob_2;

...

nume_clasa_n ob_n;

...

};

antetul constructorului clasei nume_clasa va fi de forma:

nume_clasa(lista_de_argumente):

ob_1(l_arg_1), ob_2(l_arg_2), ..., ob_n(l_arg_n)

unde lista_de_argumente respectiv l_arg_i reprezintă lista parametrilor formali ai constructorului clasei nume_clasa respectiv ai obiectului ob_i.

Din lista ob_1(l_arg_1), ob_2(l_arg_2), ..., ob_n(l_arg_n) pot să lipsească obiectele care nu au constructori definiţi de programator, sau obiectul care se iniţializează cu un constructor implicit, sau cu toţi parametrii impliciţi.

Dacă clasa conţine date membru de tip obiect atunci se vor apela mai întâi constructorii datelor membru, iar după aceea corpul de instrucţiuni al constructorului clasei respective.

Fişierul pereche.cpp:

#include <iostream>

#include "persoana.h"

using namespace std;

class pereche { persoana sot;

persoana sotie;

public:

pereche() //definitia constructorului implicit { //se vor apela constructorii impliciti } //pentru obiectele sot si sotie

pereche(persoana& sotul, persoana& sotia);

pereche(char* nume_sot, char* prenume_sot, char* nume_sotie, char* prenume_sotie):

sot(nume_sot, prenume_sot), sotie(nume_sotie, prenume_sotie) {

}

void afiseaza();

};

inline pereche::pereche(persoana& sotul, persoana& sotia):

sot(sotul), sotie(sotia) {

}

void pereche::afiseaza() {

cout << "Sot: ";

sot.afiseaza();

cout << "Sotie: ";

sotie.afiseaza();

}

int main() {

persoana A("Pop", "Ion");

persoana B("Popa", "Ioana");

pereche AB(A, B);

AB.afiseaza();

pereche CD("C","C","D","D");

CD.afiseaza();

pereche EF;

EF.afiseaza();

return 0;

}

Observăm că în cazul celui de al doilea constructor, parametrii formali sot şi sotie au fost declaraţi ca şi referinţe la tipul persoana. Dacă ar fi fost declaraţi ca parametri formali de tip persoana, atunci în cazul declaraţiei:

pereche AB(A, B);

constructorul de copiere s-ar fi apelat de patru ori. În astfel de situaţii se creează mai întâi obiecte temporale folosind constructorul de copiere (două apeluri în cazul de faţă), după care se execută constructorii datelor membru de tip obiect (încă două apeluri).

1.2.1.6. Destructorul

Destructorul este funcţia membru care se apelează în cazul distrugerii obiectului. Destructorul obiectelor globale se apelează automat la sfârşitul funcţiei main ca parte a funcţiei exit. Deci, nu este indicată folosirea funcţiei exit într-un destructor, pentru că acest lucru duce la un ciclu infinit. Destructorul obiectelor locale se execută automat la terminarea blocului în care s-au definit. În cazul obiectelor alocate dinamic, de obicei destructorul se apelează indirect prin operatorul delete (obiectul trebuie să fi fost creat cu operatorul new). Există şi un mod explicit de apelare a destructorului, în acest caz numele destructorului trebuie precedat de numele clasei şi operatorul de rezoluţie.

Numele destructorului începe cu caracterul ~ după care urmează numele clasei. Ca şi în cazul constructorului, destructorul nu returnează o valoare şi nu este permisă nici folosirea cuvântului cheie void. Apelarea destructorului în diferite situaţii este ilustrată de următorul exemplu. Fişierul destruct.cpp:

#include <iostream>

#include <cstring>

using namespace std;

class scrie { //scrie pe stdout ce face.

char* nume;

public:

scrie(char* n);

~scrie();

};

scrie::scrie(char* n) {

nume = new char[strlen(n)+1];

strcpy(nume, n);

cout << "Am creat obiectul: " << nume << '\n';

}

scrie::~scrie() {

cout << "Am distrus obiectul: " << nume << '\n';

delete nume;

}

void functie() {

cout << "Apelare functie" << '\n';

scrie local("Local");

}

scrie global("Global");

int main() {

scrie* dinamic = new scrie("Dinamic");

functie();

cout << "Se continua programul principal" << '\n';

delete dinamic;

return 0;

}

1.3. Relaţii între clase

1.3.1. Bazele teoretice

Prin folosirea tipurilor abstracte de date, se creează un tot unitar pentru gestionarea datelor şi a operaţiilor referitoare la aceste date. Cu ajutorul tipului abstract clasă se realizează şi protecţia datelor, deci în general elementele protejate nu pot fi accesate decât de funcţiile membru ale clasei respective. Această proprietate a obiectelor se numeşte încapsulare (encapsulation).

În viaţa de zi cu zi însă ne întâlnim nu numai cu obiecte separate, dar şi cu diferite legături între aceste obiecte, respectiv între clasele din care obiectele fac parte. Astfel se formează o ierarhie de clase. Rezultă a doua proprietate a obiectelor: moştenirea (inheritance). Acest lucru înseamnă că se moştenesc toate datele şi funcţiile membru ale clasei de bază de către clasa derivată, dar se pot adăuga elemente noi (date membru şi funcţii membru) în clasa derivată. În cazul în care o clasă derivată are mai multe clase de bază se vorbeşte despre moştenire multiplă.

O altă proprietate importantă a obiectelor care aparţin clasei derivate este că funcţiile membru moştenite pot fi supraîncărcate. Acest lucru înseamnă că o operaţie referitoare la obiectele care aparţin ierarhiei are un singur identificator, dar funcţiile care descriu această operaţie pot fi diferite. Deci, numele funcţiei şi lista parametrilor formali este aceeaşi în clasa de bază şi în clasa derivată, dar descrierea funcţiilor diferă între ele. Astfel, în clasa derivată funcţiile membru pot fi specifice clasei respective, deşi operaţia se identifică prin acelaşi nume.

Această proprietate se numeşte polimorfism.

1.3.2. Declararea claselor derivate O clasă derivată se declară în felul următor:

class nume_clasă_derivată : lista_claselor_de_bază { //date membru noi şi funcţii membru noi

};

unde lista_claselor_de_bază este de forma:

elem_1, elem_2, ..., elem_n

şi ^elem_i pentru orice 1 ≤ i ≤ n poate fi

public clasă_de_bază_i

sau

protected clasă_de_bază_i

sau

private clasă_de_bază_i

Cuvintele cheie public, protected şi private se numesc şi de această dată modificatori de protecţie. Ei pot să lipsească, în acest caz modificatorul implicit fiind private. Accesul la elementele din clasa derivată este prezentat în tabelul 1.

Accesul la elementele din clasa

de bază

Modificatorii de protecţie referitoare

la clasa de bază

Accesul la elementele din clasa

derivată

public public public

protected public protected

private public inaccesibil

public protected protected

protected protected protected

private protected inaccesibil

public private private

protected private private

private private inaccesibil

Tabelul 1: accesul la elementele din clasa derivată

Observăm că elementele de tip private ale clasei de bază sunt inaccesibile în clasa derivată.

Elementele de tip protected şi public devin de tip protected, respectiv private dacă modificatorul de protecţie referitor la clasa de bază este protected respectiv private, şi rămân neschimbate dacă modificatorul de protecţie referitor la clasa de bază este public. Din acest motiv în general datele membru se declară de tip protected şi modificatorul de protecţie referitor la clasa de bază este public. Astfel datele membru pot fi accesate, dar rămân protejate şi în clasa derivată.

1.3.3. Funcţii virtuale

Noţiunea de polimorfism ne conduce în mod firesc la problematica determinării funcţiei membru care se va apela în cazul unui obiect concret. Să considerăm următorul exemplu. Declarăm clasa de bază baza, şi o clasă derivată din acestă clasă de bază, clasa derivata. Clasa de bază are două funcţii membru: functia_1 şi functia_2. În interiorul funcţiei membru functia_2 se apelează functia_1. În clasa derivată se supraîncarcă funcţia membru functia_1, dar funcţia membru functia_2 nu se supraîncarcă. În programul principal se declară un obiect al clasei derivate şi se apelează funcţia membru functia_2 moştenită de la clasa de bază. În limbajul C++ acest exemplu se scrie în următoarea formă.

Fişierul virtual1.cpp:

#include <iostream>

using namespace std;

class baza { public:

void functia_1();

void functia_2();

};

class derivata : public baza { public:

void functia_1();

};

void baza::functia_1() {

cout << "S-a apelat functia membru functia_1"

<< " a clasei de baza" << endl;

}

void baza::functia_2() {

cout << "S-a apelat functia membru functia_2"

<< " a clasei de baza" << endl;

functia_1();

}

void derivata::functia_1() {

cout << "S-a apelat functia membru functia_1"

<< " a clasei derivate" << endl;

}

int main() { derivata D;

D.functia_2();

}

Prin execuţie se obţine următorul rezultat:

S-a apelat functia membru functia_2 a clasei de baza S-a apelat functia membru functia_1 a clasei de baza