Cuvântul polimorfism se referă la proprietatea unor substanțe, ființe, obiecte de a avea mai multe forme.
În contextul programării orientate pe obiecte, polimorfismul se referă la posibilitatea claselor de a avea mai multe metode cu același nume, dar cu efecte și rezultate diferite.
În C++ polimorfismul poate fi implementat prin:
Supraîncărcarea funcțiilor și operatorilor sunt tratate în acest articol: www.pbinfo.ro/articole/25851/supraincarcarea-functiilor-si-a-operatorilor.
Suprascrierea funcțiilor (overriding) se referă la situația ca într-o ierarhie de clase să avem metode cu același nume, dar cu efecte diferite. Considerăm clasele Animal
și Caine
.
#include<iostream> using namespace std; class Animal{ public: void vorbeste() { cout << "Animalul vorbeste." << endl; } }; class Caine: public Animal{ public: void vorbeste() { cout << "Cainele latra." << endl; } }; int main(){ Caine C; Animal A; C.vorbeste(); A.vorbeste(); C.Animal::vorbeste(); // A.Caine::vorbeste(); // imposibil }
În exemplul anterior:
Caine
este derivată din clasa Animal
;C
este de tip Caine
, obiectul A
este de tip Animal
; ambele sunt obiecte statice;vorbeste()
este disponibilă în ambele clase, fiind suprascrisă în clasa derivatăvorbeste()
C.Animal::vorbeste();
– invers nu este posibil!Constatăm că pentru obiectele referite static accesarea metodelor suprascrise este rezolvată elegant, putând accesa orice metodă disponibilă în obiectul curent (proprie obiectului curent sau proprie aflate mai “sus” în ierarhie).
Să vedem cum putem accesa membri claselor de bază/derivată în cazul pointerilor. Folosind clasele definite mai sus, considerăm următorul exemplu:
Caine C; Animal A; Animal * p; p = & A; p->vorbeste(); // Animalul vorbeste. p = & C; p->vorbeste(); // Animalul vorbeste. (?!?) Caine * q; q = & C; q->vorbeste(); // q = & A; // imposibil
Constatăm că:
q
) poate memora doar adresa unui obiect al acesteia;p
) poate memora atât adresa unui obiect al clasei de bază, cât și adresa unui obiect al clasei derivate;C++ oferă un mecanism prin care se alege metoda accesată printr-un pointer dinamic, la execuția programului, în funcție de clasa din care face obiectul referit de pointer (de bază sau derivată). Acest mecanism este reprezentat de funcțiile virtuale.
Declararea unei funcții (metode) virtuale este precedată de cuvântul C++ rezervat virtual
în clasa de bază:
virtual tipRezultat metoda(parametri)
Exemplu:
#include<iostream> using namespace std; class Animal{ public: virtual void vorbeste() { cout << "Animalul vorbeste." << endl; } }; class Caine: public Animal{ public: void vorbeste() { cout << "Cainele latra." << endl; } }; int main(){ Caine C; Animal A; Animal * p; p = & A; p->vorbeste(); // Animalul vorbeste. p = & C; p->vorbeste(); // Cainele latra. (!) }
Constatăm că:
p
este declarat pointer la clasa de bază;p
poate memora fie adresa unui obiect din clasa de bază, fie adresa unui obiect din clasa derivată;Încapsularea presupune și ascunderea datelor sensibile ale unui obiect. Acest lucru este necesar din cel puțin două motive:
0
, într-un interval cunoscut – nu putem avea 157
sau 1204578
de ani!Astfel, datele membru ale unui clase sunt declarate private. Acest lucru duce la respectarea regulilor de mai sus, dar conduce totodată și la imposibilitatea de a vedea din afara clasei care este valoare unei date membru private sau de a o schimba. Aceste operații pot fi făcute prin intermediul metodelor GET și SET (getter-e și setter-e).
O metodă GET este o metodă publică a clasei care returnează valoarea ueni date membru private.
O metodă SET este o metodă publică a clasei care atribuie unei date membru private o anumită valoare.
void
sau este obiectul curent, pentru a putea înlănțui apelul metodelor.În exemplul de mai jos implementăm clasa Fractie
, înzestrând-o cu metode GET și SET. Folosim aceste metode la scrierea unei funcții care determină suma a două fracții.
#include <iostream> using namespace std; class Fractie{ private: int numarator, numitor; // proprietăți void Simplifica(); // metodă privată public: Fractie(int _numarator = 0, int _numitor = 1); // constructor Fractie(const Fractie &); // constructor de copiere Fractie & Citeste(); // metodă publică Fractie & Scrie(); // metodă publică // metode GET int Numarator(); int Numitor(); // metode SET Fractie & Numarator(int); Fractie & Numitor(int); }; Fractie::Fractie(const Fractie & F) { // constructor de copiere numarator = F.numarator; numitor = F.numitor; Simplifica(); } Fractie::Fractie(int _numarator /* = 0 */, int _numitor /* = 1 */) { // constructor numitor = _numitor, numarator = _numarator; Simplifica(); } int Fractie::Numarator() { //metoda GET return numarator; } int Fractie::Numitor() { //metoda GET return numitor; } Fractie & Fractie::Numarator(int x) { numarator = x; Simplifica(); return * this; } Fractie & Fractie::Numitor(int x) { // validam valoarea lui x if(x == 0) { cerr << "Numitor nul" << endl; return * this; } numitor = x; if(x < 0) numarator *= -1, numitor *= -1; Simplifica(); return * this; } Fractie & Fractie::Citeste() { // citeste numaratorul si numitorul obiectului curent // returnează obiectul curent int a , b; cin >> a >> b; // validam valorile citite if(b == 0) { cerr << "Numitor nul"<<endl; return * this; } if(b < 0) a = -a , b = -b; numarator = a, numitor = b; Simplifica(); return * this; } Fractie & Fractie::Scrie() { // afisează numaratorul si numitorul obiectului curent // returnează obiectul curent cout << numarator << " " << numitor <<endl; return * this; } void Fractie::Simplifica() { //metoda privata; realizeaza simplificarea fractiei merorate în obiectul curent int a = abs(numarator), b = abs(numitor); while(b) { int r = a % b; a = b; b = r; } numarator /= a; numitor /= a; } Fractie Suma(Fractie F, Fractie G) { // funcție oarecare. Accesam datele private ale obiectelor prin metodele GET si SET int x = F.Numarator() * G.Numitor() + F.Numitor() * G.Numarator(), y = F.Numitor() * G.Numitor(); Fractie R; R.Numarator(x).Numitor(y); // apelam metodele SET return R; // s-a apelat costructorul de copiere } int main() { Fractie a , b; a.Citeste(), b.Citeste(); Suma(a , b).Scrie(); return 0; }
Derivarea claselor (moștenirea) este unul dintre principiile fundamentale ale programării orientate pe obiecte. Ne permite să definim o clasă pornind de la altă clasă, creată anterior, și facilitează crearea și întreținerea aplicațiilor. Tototdată permite reutilizarea codului și micșorează timpul de implementare a programelor.
La crearea unei clase, în loc să scriem date și funcții membre complet noi, putem să precizăm că noua clasă va moșteni membri unei clase existente. Se obțin astfel ierarhii de clase.
Moștenirea are sens numai când obiectele din clasa moștenită fac parte din obiectele clasei de bază – relația dintre ele este de tipul Is A (este un/o). De exemplu:
Paralelogram
poate fi derivată din clasa Patrulater
.Caine
poate fi derivată din clasa Animal
.Fie B
o clasă care există deja, iar D
clasa care moștenește membrii clasei B
. Spunem că:
B
este clasa de bază;D
este clasa derivată;D
s-a obținut prin derivarea clasei B
;B
a fost derivată și s-a obținut clasa D
;D
moștenește clasa B
;În C++, o clasă poate fi derivată pornind de la mai multe clase de bază. Totodată, specificatorii de acces cunoscuți (public
, private
, protected
) sunt folosiți și pentru a preciza modul în care se face derivarea. Efectul lor este legat de vizibilitatea membrilor clasei de bază în clasa derivată.
Cea mai simplă formă de derivarea a unei clase este prezentată mai jos:
class D: public B{ // membri noi ai clasei derivate }
Observații:
B
este clasa de bază, care trebuie să fie deja definită;D
este clasa derivată;public
, face ca:
public
din clasa de bază B
rămân public
și în clasa derivată D
– pot fi accesați din afara clasei D
;protected
din clasa de bază B
rămân protected
și în clasa derivată D
– pot fi accesați din clasa derivata D
și vor putea fi acesați din alte clase vor moșteni clasa D
;private
din clasa de bază B
nu pot fi accesați din clasa derivată D
;public
putem folosi private
sau protected
. Semnificația lor va fi discutată ceva mai târziu!#include<iostream> using namespace std; class Animal{ private: protected: int varsta; public: Animal(){ varsta = 0; cout << "S-a nascut un animal." << endl; } ~Animal(){ cout << "Animalul a murit." << endl; } void creste() { ++ varsta; cout << "Animalul are " << varsta << (varsta == 1 ? " an":" ani") << endl; } }; class Caine: public Animal{ public: Caine(){ cout << "S-a nascut un caine." << endl; } ~Caine(){ cout << "Cainele a murit." << endl; } void latra() { for(int i = 1 ; i <= varsta ; i ++) cout << "Ham " ; cout << endl; } void creste() { ++ varsta; cout << "Cainele are " << varsta << (varsta == 1 ? " an":" ani") << endl; } }; int main(){ Caine X; X.creste(); X.Animal::creste(); X.latra(); X.creste(); X.latra(); }
S-a nascut un animal. S-a nascut un caine. Cainele are 1 an Animalul are 2 ani Ham Ham Cainele are 3 ani Ham Ham Ham Cainele a murit. Animalul a murit.
Animal
este clasa de bază, iar Caine
este clasa derivată;latra()
) am accesat proprietatea varsta
din clasa de bază:
varsta
a fost declarată protected
private
, nu putea fi accesată din clasa derivatămain()
, pentru obiectul X
de tip Caine
am accesat:
latra()
, disponibilă doar în clasa derivată;creste()
, moștenită din clasa de bază;X.creste(); // Cainele are 1 an
X.Animal::creste(); // Animalul are 2 ani
int main(){ Caine X; X.creste(); // Cainele are 1 an X.latra(); // Ham Animal A; A = X; A.creste(); // Animalul are 2 ani // X = A; eroare de sintaxă
}
A
este de tipul Animal
(clasa de bază), iar X
este de tipul Caine
(clasa derivată). Atunci:
A = X;
este corectă. În A
se vor copia doar membri din X
care fac parte din clasa de bază.X = A;
nu este corectă. Clasa derivată conține și membri care nu aparțin clasei de bază, ce nu pot fi inițializați prin această atribuire!Accesul la membrii (date sau funcții) clasei de bază în clasa derivată se face în funcție de regulile de acces la membrii clasei de bază și în funcție de modalitatea în care s-a făcut derivarea.
Sunt trei moduri de declarare a membrilor unei clase:
public
– pot fi accesați din afara clasei, dar și din interiorul eiprotected
– nu pot fi accesați din exteriorul clasei (de bază sau derivate). Pot fi accesați din interiorul clasei de bază și din interiorul claselor derivateprivate
– pot fi accesați numai din interiorul clasei.Modalitățile de derivarea ale unei clase sunt:
class D: public B{ … }
B
rămân publici și în clasa D
;B
rămân protejați în clasa D
;B
sunt inaccesibili în clasa D
;class D: protected B{ … }
B
devin protejați și în clasa D
;B
rămân protejați în clasa D
;B
sunt inaccesibili în clasa D
;class D: private B{ … }
B
devin privați și în clasa D
;B
devin privați în clasa D
;B
sunt inaccesibili în clasa D
;Supraîncărcarea funcțiilor (eng. functions overloading) se referă la posibilitatea ca în același program să fie declarate și definite mai multe funcții cu același nume, care să difere prin parametri. La apelul unei funcții supraîncărcate, compilatorul stabilește care dintre declarații se potrivește cu apelul respectiv, comparând numărul și tipul parametrilor actuali cu cel al parametrilor formali.
Metodele unei clase, fiind funcții, pot fi supraîncărcate. Totodată, în interiorul unei clase pot fi definiți și supraîncărcați operatori (+
, -
, *
, etc.), care permit utilizarea naturală a obiectelor, în raport cu înțelesul lor.
De exemplu, fracțiile pot fi adunate, scăzute, etc. O clasa care implementează fracții poate fi îmbogățită cu operațiile naturale de adunare, scădere, înmulțire, împărțire, dar și cu comparații, incrementări/decrementări, citire, afișare, etc.
În acest fel lucrul cu obiecte devine natural, evitând apelul explicit al unor metode care poate părea forțat, în anumite situații.
De știut:
În exemplul următor, definim pentru clasa Fracție
două metode creste()
:
1
;n
, care va mări valoarea fracției încapsulate în obiect cu n
.#include <iostream> using namespace std; class Fractie{ private: int numarator, numitor; public: void afiseaza() /// metodă pentru afișarea fractiei { cout << numarator << "/" << numitor << endl; } Fractie(int a , int b) /// constructor { if(b < 0) a = -a, b = -b; numarator = a, numitor = b; } Fractie & creste() { numarator += numitor; return *this; } Fractie & creste(int n) { numarator += n * numitor; return *this; } }; int main(){ Fractie x(1 , 4); x.afiseaza(); x.creste(); x.afiseaza(); x.creste(3); x.afiseaza(); return 0; }
Programul de mai sus va afișa:
1/4 5/4 17/4
Putem supraîncărca aproape toți operatorii C++ predefiniți. În acest mod putem folosi operatorii și pentru tipurile definite de noi, nu doar pentru cele predefinite.
Nu putem supraîncărca operatori pentru tipurile de bază: int
, double
, etc.
Nu putem supraîncărca operatori care nu există. De exemplu, nu putem adăuga operatorul #
.
Nu putem schimba prioritatea operatorilor.
Operatorii sunt funcții cu un nume special: cuvântul rezervat operator
, urmat de simbolul operatorului pe care îl definim. La fel ca orice altă funcție, și operatorii au tip al rezultatului și listă de parametri.
Operatorii care pot fi supraîncărcați sunt:
+
, -
, *
, /
, %
^
, &
, |
, ~
,,
=
<
, >
, <=
, >=
, ==
, !=
,!
, &&
, ||
++
, --
<<
, >>
,+=
, -=
, /=
, %=
, ^=
, &=
, |=
, *=
, <<=
, >>=
,[]
, ()
->
, ->*
new
, new []
, delete
, delete []
Următorii operatori nu pot fi supraîncărcați:
::
, .*
, .
, ?:
Sunt două modalități de defini operatori pentru o clasă:
Putem folosi metodele când operatorul este unar, sau când este binar și primul operand este obiect al clasei pentru care definim operatorul. Dacă operatorul este binar și primul operator nu este obiect al clasei, vom defini operatorul prin intermediul funcțiilor prietene.
În programul de mai jos definim o clasă Fractie
în care vom defini și supraîncărca operatorul +
pentru a implementa adunarea fracțiilor și adunarea fracțiilor cu întreg. Distingem următoarele cazuri:
F + G
, unde F
și G
sunt fracții, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;F + n
, unde F
este fracție și n
este număr întreg, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;n + F
, unde F
este fracție și n
este număr întreg, va fi implementată printr-o funcție prietenă.Situația de mai sus se datorează faptului că, la implementarea operatorului ca metodă, obiectul curent, pentru care se implementează metoda, este primul operand.
#include <iostream> using namespace std; class Fractie{ private: int numarator, numitor; public: void afiseaza() /// metodă pentru afișarea fractiei { cout << numarator << "/" << numitor << endl; } Fractie(int a = 0, int b = 1) /// constructor { if(b < 0) a = -a, b = -b; numarator = a, numitor = b; } Fractie operator+ (Fractie F) { Fractie R; R.numarator = numarator * F.numitor + numitor * F.numarator; R.numitor = numitor * F.numitor; return R; } Fractie operator+ (int n) { Fractie R; R.numarator = numarator + n * numitor; R.numitor = numitor; return R; } friend Fractie operator + (int n, Fractie F) { Fractie R; R.numarator = F.numarator + n * F.numitor; R.numitor = F.numitor; return R; } }; int main(){ Fractie X(1 , 4), Y(2, 3); Fractie R = X + Y; R.afiseaza(); R = X + 2; R.afiseaza(); R = 2 + X; R.afiseaza(); return 0; }
Programul de mai sus va afișa:
11/12 9/4 9/4
Considerăm următorul algoritm, aplicat pentru două numere naturale a
și b
:
R ← 0 ┌ cattimp a ≠ 0 executa │ ┌ daca a este impar atunci │ │ R ← R + b │ └■ │ a ← [a / 2] │ b ← b * 2 └■ scrie R
Dacă îl vom aplica pentru a = 18
și b = 12
vom constata că:
a |
b |
R |
Explicație | ||
---|---|---|---|---|---|
18 |
12 |
0 |
a este par => R nu se modificăa se înjumătățește, b se dublează |
||
9 |
24 |
0 + 24 = 24 |
a este impar => la R se adună b = 24 a se înjumătățește, b se dublează |
||
4 |
48 |
24 |
a este par => R nu se modificăa se înjumătățește, b se dublează |
||
2 |
96 |
24 |
a este par => R nu se modificăa se înjumătățește, b se dublează |
||
1 |
192 |
24 + 192 = 216 |
a este impar=> la R se adună b = 192 a se înjumătățește, b se dublează |
||
0 |
384 |
216 |
a a devenit 0 , ne oprim |
Observăm că rezultatul R = 216
este de fapt chiar 18 * 12
. Aceasta nu este o coincidență!
Algoritmul determină rezultatul înmulțirii dintre a
și b
și se numește înmulțirea a la russe (înmulțirea rusească). În ciuda numelui, se pare că metoda era cunoscută în Egiptul Antic și poate fi descrisă astfel:
a
și b
:
a
este impar, il adunăm pe b
la rezultat, care inițial este 0
;a
se înjumătățește, iar b
se dublează;a
devine 0
.Aparent ciudată, metoda se bazează de fapt pe scrierea unui număr ca sumă de puteri ale lui 2
( sau reprezentarea numerelor în baza 2
) – știm că orice număr natural are o unică reprezentare în baza 2
, poate fi scris în mod unic ca sumă de puteri ale lui 2
.
Să-l scrie pe \(a = 18\) ca sumă de puteri ale lui 2
: \(18 = 2 + 16 = 0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4\). 0 1 0 0 1
sunt cifrele reprezentării lui 18
în baza 2
, în ordine inversă (ordinea în care sunt determinate, prin metoda cunoscută ca resturi ale împărțirii la 2
).
Atunci:
$$\begin{align}
18 \cdot 12 & = \left(0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 \right) \cdot 12 \\
& = \left(0 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + 0 \cdot 8 + 1 \cdot 16 \right) \cdot 12 \\
& = 0 \cdot 12 + 1 \cdot 24 + 0 \cdot 48 + 0 \cdot 96 + 1 \cdot 192 \\
& = 24 + 192 \\
& = 216 \\
\end{align}$$
Observăm deci că valorile care se adună pentru a obține rezultatul sunt tocmai acele valori obținute prin dublările succesive ale lui b
când a
este impar – ceea ce corespunde cifrei binare 1
!!
Acest modalitate de înmulțire este interesantă, dar nu este neapărat utilă în practică. Mult mai interesant este următorul algoritm pentru ridicarea la putere, care poate fi utilizat în rezolvarea de probleme de informatică.
Să considerăm \(A^{25}\). Îl vom scrie pe \(25\) ca sumă de puteri ale lui \(2\): \(25 = 1 + 8 + 16\).
Atunci \( A^{25} = A^{1 + 8 + 16} = A^1 \cdot A^8 \cdot A^{16} = \underbrace{{(A^1)}^1}_{=A^1} \cdot \underbrace{{(A^2)}^0}_{=1} \cdot \underbrace{{(A^4)}^0}_{=1} \cdot \underbrace{{(A^8)}^1}_{=A^8} \cdot \underbrace{{(A^{16})}^1}_{=A^{16}}\). Observăm, desigur, că exponenții \(0\) și \(1\) sunt cifrele reprezentării în baza \(2\) a lui \(25\).
Pentru a determina A
n
procedăm astfel:
P
, format din factori de forma A
1
, A
2
, A
4
, A
8
, …2
a lui n
, începând cu cea mai nesemnificativă:
1
, înmulțim pe A
la P
, P ← P * A;
A
cu el însuși, A ← A * A;
, obținând următoarea putere din șirul de mai susUrmătorul program pseudocod descrie algoritmul de mai sus:
citeste A,n (baza, exponent) P ← 1 ┌ cattimp n ≠ 0 executa │ c ← n % 2 │ ┌ daca c = 1 atunci │ │ P ← P * A │ └■ │ n ← [n / 2] │ A ← A * A └■ scrie P
Observăm că algoritmul este foarte eficient! Numărul de iterații este egal cu numărul de cifre din reprezentarea în baza 2
a lui n
– mult mai mic decât n
!
Definiție: Se numește arbore binar de cautare un arbore binar în care fiecare nod are o cheie unică de identificare care respectă următoarele condiții:
Exemplu
Observații:
struct nod{ int info; nod * st, * dr;
};
Așa cum ma văzut mai sus, principalele operații sunt:
În implementarea acestor operații vom folosi metoda divide-et-impera. Principiul este:
Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL
dacă arborele este vid) și o valoare. Se cere să se insereze în arbore un nod care are drept cheie de identificare valoarea dată.
Inserarea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!
Procedăm astfel:
NULL
. Legarea nodului la subarbore se face automat, datorită transmiterii prin referință a parametrului care reprezintă adresa rădăcinii.Pentru a creea un arbore binar de căutare vom porni de la un arbore vid și vom aplica în mod repetat operația de inserare.
Funcție C++
void Inserare(nod * & R, int x) { if(R != NULL) { if(R->info == x) return; else if(R->info > x) Inserare(R->st , x); else Inserare(R->dr , x); } else { R = new nod; R->info = x; R->st = NULL; R->dr = NULL; } }
Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL
dacă arborele este vid) și o valoare. Se cere să se stabilească dacă există în arbore un nod care are cheia de identificare egală cu valoarea dată.
Procedăm astfel:
Funcție C++
Funcția de mai jos caută valoarea x
în arborele pentru care adresa rădăcinii este memorată în pointerul R
. Funcția returnează adresa nodului care are cheia egală cu x
sau NULL
dacă nu există un asemenea nod.
nod * Cautare(nod * R , int x) { if(R == NULL) return NULL; if(R->info == x) return R; if(R->info > x) return Cautare(R->st , x); else return Cautare(R->dr , x); }
Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL
dacă arborele este vid) și o valoare. Se cere să se șteargă din arbore nodul care are cheia de identificare egală cu valoarea dată.
Ștergerea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!
Procedăm astfel:
NULL
;Secvența C++
Mai jos sunt prezentate două funcții: Stergere
și StAux
. Funcția StAux
tratează cazul când nodul curent trebuie șters și are ambii subarbori.
void StergAux(nod * & p, nod * & R) { // R - nodul care trebuie sters // p - pointer cu care identificăm nodul cel mai din dreapta if(p->dr) StergAux(p -> dr , R); else { R->info = p->info; nod * aux = p; p = p->st; delete aux; } } void Stergere(nod * & R , int x) { if(R != NULL) { if(R->info == x) { // nodul trebuie șters if(R->st == NULL && R->dr == NULL) { delete R; R = NULL; } else if(R->dr == NULL) { nod * aux = R; R = R->st; delete aux; } else if(R->st == NULL) { nod * aux = R; R = R->dr; delete aux; } else StergAux(R->st, R); } else if(R->info > x) Stergere(R->st , x); else Stergere(R->dr , x); } else return; // valoarea x nu apare în arbore }
Arborii binari de căutare pot fi parcurși în orice mod: inordine, preordine, postordine. Datorită structurii interne a arborilor (pentru orice subarbore, cheia asociată rădăcinii este mai mare decât orice cheie din subarborele stâng și mai mică decât orice cheie din subarborele drept), parcurgerea în inordine (Stâng-Rădăcină-Drept)se face în ordinea crescătoare a cheilor!
Pentru a realiza o parcurgere în ordinea descrescătoare a cheilor, folosim tot o parcurgere în inordine, dar de tip Drept-Rădăcină-Stâng!
Secvență C++
void Afisare(nod * r) { if(r != NULL) { Afisare(r->st); cout << r->info << " "; Afisare(r->dr); } }
map
și set
sunt implementate cu ajutorul arborilor binari de căutare echilibrați – de regulă arbori roșu-negru.Acest articol conține o listă cu probleme propuse pentru examenul de bacalaureat la care se cer soluții eficiente din punct de vedere a memoriei utilizate și/sau a timpului de execuție (punctul III.3).
Problemele pot fi filtrate folosind butoanele din stânga!
Sesiunea iunie-iulie 2024
De-a lungul unui traseu montan este utilizată o succesiune de marcaje turistice, care trebuie urmate în acea ordine. Pentru fiecare marcaj se cunoaște cota (înălțimea, măsurată în metri) la care este plasat. Numim scară într-un traseu o secvență de marcaje aflate pe poziții consecutive în cadrul traseului, care au drept cote numere consecutive, ordonate strict crescător. O scară este formată din cel puțin două marcaje, iar lungimea acesteia este egală cu numărul de marcaje care o compun.
Fișierul bac.txt
conține un șir de cel mult 10
6
numere naturale din intervalul [10,10
4
]
, separate prin câte un spațiu, reprezentând cotele marcajelor turistice din cadrul unui traseu, în ordinea în care se succed în acesta. Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict crescătoare, cotele corespunzătoare marcajelor unei scări de lungime maximă pe acest traseu. Dacă în cadrul traseului există mai multe astfel de scări, se afișează doar cotele corespunzătoare marcajelor uneia dintre ele, iar dacă nu există nicio scară, pe ecran se afișează mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 500 600 601 405 569 570 700 701 625 626 627 520
atunci pe ecran se afișează 625 626 627
.
Sesiunea specială, mai 2024
Fișierul numere.in
conține un șir de cel mult 10
6
numere naturale din intervalul [0,99]
. Numerele din fișier sunt separate prin câte un spațiu.
Se cere să se determine primul și ultimul număr din șir care conțin cea mai mare cifră ce apare în scrierea numerelor din fișier. Numerele determinate se afișează pe ecran, în ordinea apariției lor în șir, separate printr-un spațiu. Dacă nu există două astfel de numere pe poziții distincte, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 34 5 38 30 87 70 11 8 82 25
se afișează pe ecran 38 82
, dacă fișierul conține numerele 34 5 38 30 87 70 11 8 38 25
se afişează pe ecran 38 38
, iar dacă fișierul conține numerele 34 5 38 30
se afișează pe ecran nu exista
.
Simulare martie 2024
Un șir se numește de tip api dacă numărul de apariții ale fiecărui termen este mai mic sau egal cu acel termen și are o paritate egală cu a acestuia.
Fișierul bac.in
conține un șir de cel mult 10
6
numere naturale din intervalul [1,10
3
]
, separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA
, dacă șirul este de tip api, sau mesajul NU
în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare
Exemplu: dacă fișierul conține numerele 6 27 2 6 27 6 6 14 14 2 27
se afișează pe ecran DA
(termenul par 6
apare de 4
ori, 4
fiind tot număr par și 4≤6
, termenii pari 2
și 14
apar de câte 2
ori, 2
fiind tot număr par și 2≤2
, respectiv 2≤14
, iar termenul impar 27
apare de 3
ori, 3
fiind tot număr impar și 3≤27
).
Sesiunea august 2023
Fișierul date.in
conține pe prima linie două numere naturale din intervalul [1,10
6
]
, m
și n
, iar pe următoarele două linii numere naturale din intervalul [0,10
2
)
: pe a doua linie un șir A
, de m
numere, iar pe a treia linie un șir B
, de n
numere. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul maxim de perechi de forma (pa,pb)
(pa∈[1,m]
, pb∈[1,n]
), cu proprietatea că termenul de pe poziția pa
din șirul A
are aceeași valoare cu termenul de pe poziția pb
din șirul B
și că fiecare poziție, corespunzătoare șirului A
, respectiv șirului B
, apare în cel mult o pereche, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
8 9 1 0 4 1 5 3 5 5 1 1 1 7 5 3 5 3 0
se afișează pe ecran numărul 6
, de exemplu, pentru perechile (1,1), (2,9), (4,2), (5,5), (6,6), (7,7)
sau pentru perechile (1,2), (2,9), (4,1), (5,7), (6,8), (8,5)
.
Sesiunea iunie-iulie 2023
Un număr natural x
este numit prefix al unui număr natural y
dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la dreapta sa, și este numit sufix al lui y
dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la stânga sa.
Exemplu: 15
este prefix pentru 154
sau 1521
, este sufix pentru 3415
sau 5115
, dar nu este nici prefix, nici sufix pentru 15
.
Fișierul bac.txt
conține maximum 10
6
numere naturale din intervalul [10,10
4
)
, separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix, respectiv ca prefix al numerelor din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul
342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310
se afișează pe ecran: 4
(pentru valorile 10
, 11
, 16
, 34
).
Sesiunea specială, mai 2023
Intervalul [x,y]
se numește p
-interval pentru un șir de valori întregi, dacă oricare dintre primii p
termeni ai șirului aparține intervalului, iar numărul de valori întregi distincte din interval este minim.
Exemplu: pentru șirul 2, 7, -1, 8, 3, 10
există [2,2]
ca 1
-interval, [-1,8]
ca 4
-interval și 5
-interval etc.
Fișierul bac.i
n conține un șir de cel mult 10
6
numere întregi din intervalul [-10
9
,10
9
]
, separate prin câte un spațiu. Se cere să se afișeze pe ecran cea mai mică și cea mai mare valoare a lui p
(p≥2
) cu proprietatea că (p-1)
-interval este identic cu p
-interval pentru șirul aflat în fișier. Valorile afișate pot fi egale, iar dacă nu există nicio astfel de valoare, pe ecran se afișează mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul bac.txt
conține numerele 2 7 1 8 3 10 6 -3 -2 13
se afișează pe ecran 5 9
(intervale conform cerinței se obțin pentru valorile 5
, 7
și 9
ale lui p
), iar dacă fișierul conține numerele 2 7 1 0 8 10 -3 13
, se afișează pe ecran nu exista
.
Simulare, martie 2023
Pentru a studia un metal, s-a urmărit comportamentul său într-o succesiune de pași, la fiecare pas metalul fiind supus unei anumite temperaturi. Pașii sunt numerotați cu valori naturale consecutive, începând de la 1
. Un pas se numește reprezentativ dacă la niciunul dintre pașii anteriori nu este utilizată o temperatură strict mai mare decât la acest pas. Dacă există o secvență de pași consecutivi la care se utilizează aceeași temperatură, se consideră reprezentativ doar primul pas din secvență.
Fișierul bac.txt
conține cel mult 10
6
numere naturale din intervalul [0,10
4
]
, separate prin câte un spațiu, reprezentând temperaturile la care este supus metalul, în ordinea pașilor corespunzători. Se cere să se afișeze pe ecran, separați prin câte un spațiu, pașii reprezentativi pentru datele din fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 7 4 9 10 10 10 3 9 2 10 10 8 2 30
se afișează pe ecran 1 3 4 10 14
Sesiunea august 2022
Numim secvență paritară a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași paritate, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt
conține un șir de cel puțin două și cel mult \(10^6\) numere naturale din intervalul \([0, 10^9]\). Numerele sunt separate prin câte un spațiu, iar în șir există cel puțin doi termeni cu aceeași paritate pe poziții consecutive.
Se cere să se afișeze pe ecran numărul secvențelor paritare de lungime maximă din șirul aflat în fișier, precum și această lungime maximă. Numerele afișate sunt separate printr-un spațiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fişierul conţine numerele 2
3 5 1 7 9
8 4 4
11 15 17 21 11
6
11 15 17 21 11
6 5
2 6 4 0 16
atunci pe ecran se afișează valorile 4 5
.
Sesiunea specială, mai 2022
Numim secvență progresivă a unui șir crescător de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că fiecare termen apare în subșir de un număr de ori egal cu valoarea sa. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt
conține un șir crescător de cel mult \(10^6\) numere naturale din intervalul \([1,10^6]\), astfel încât orice termen al șirului apare de un număr de ori cel mult egal cu valoarea sa. Numerele sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe progresive din șirul aflat în fișier.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fişierul conţine numerele 1 2 2
3
4 4 4 4 6 6 6 6 6 6
7 7 7
8 8 8 8 8 8 8 8
atunci pe ecran se afișează valoarea 10
.
Sesiunea iunie-iulie 2022
Fișierul bac.txt
conține numere naturale din intervalul\( [1,10^9]\), astfel: pe prima linie două numere, x
și y
(x<y
), iar pe a doua linie un șir de cel mult \(10^6\) numere, ordonate crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afişeze pe ecran numărul de valori distincte din șirul aflat pe a doua linie a fișierului care aparțin intervalului [x,y]
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fişierul conține numerele
2 9 1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21
atunci pe ecran se afișează valoarea 6
.
Simulare 2022
Se citește de la tastatură un număr natural, \(n\) ( \( n \in [1,10^9]\)), și se cere să se scrie în fișierul text bac.txt
cel mai mare număr natural p
cu proprietatea că numărul \(45^p\) este divizor al numărului obținut prin evaluarea produsului 1∙2∙3∙...∙n
.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă n=14
, fișierul conține numărul 2
(\(45^2=2025\) este divizor al lui 1∙2∙3∙..∙14=87178291200
).
Sesiunea august-septembrie 2021
Numim pereche asemenea (x,y)
două numere naturale cu cel puțin două cifre, x
și y
, cu proprietatea că ultimele două cifre ale lui x
sunt egale cu ultimele două cifre ale lui y
, dispuse eventual în altă ordine.
Fișierul numere.in
conține numere naturale din intervalul \(10,10^5\): pe prima linie două numere na
și nb
, pe a doua linie un șir A
de na
numere, iar pe a treia linie un șir B
de nb
numere. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de perechi asemenea (x,y)
, cu proprietatea că x
este un termen al șirului A
, iar y
este un termen al șirului B
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
9 7 112 20 42 112 5013 824 10012 55 155 402 1024 321 521 57 6542 255
se afișează pe ecran numărul
13
deoarece sunt 13
perechi asemenea: (112,321)
, (112,521)
, (20,402)
, (42,1024)
, (42,6542)
, (112,321)
, (112,521)
, (824,1024)
, (824,6542)
, (10012,321)
, (10012,521)
, (55,255)
, (155,255)
.
Sesiunea iunie-iulie 2021
Numărul natural a
se numește sufix al numărului natural b
dacă a
este egal cu b
sau dacă b
se poate obține din a
prin alipirea la stânga a unor noi cifre.
Fişierul bac.txt
conţine pe prima linie un număr natural x
(\( x \in [100,999] \)), iar pe a doua linie un şir de cel mult \(10^5\) numere naturale din intervalul \([0,10^9]\). Numerele din şir sunt separate prin câte un spaţiu. Se cere să se afișeze pe ecran ultimii doi termeni ai șirului, aflați pe poziții consecutive în acesta, care îl au drept sufix pe numărul x
. Numerele sunt afișate în ordinea în care apar în șir, separate printr-un spațiu, iar dacă nu există doi astfel de termeni, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul bac.txt
conține numerele
210 3445 210 893210 1245 1210 3210 15210 67120 20210 12
pe ecran se afișează 3210 15210
.
Subiecte antrenament, 2021, testul 12
Fișierul bac.txt
conține un șir de cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran cea mai mare poziție pe care ar putea-o ocupa primul termen al șirului aflat în fișier în șirul format cu aceleași valori, ordonat descrescător. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul bac.txt
conține numerele 15 7 15 17 6 4 21
seafișează pe ecran 4
(15
se află pe a treia și pe a patra poziție în șirul 21, 17, 15, 15, 7, 6, 4
).
Subiecte antrenament, 2021, testul 11
Se consideră șirul 1
, 3
, 7
, 13
, 21
, 31
, 43
… definit astfel: \(f_0=1\), iar \(f_n=f_{n-1} + 2 \cdot n\), dacă n≥1
(unde n
este un număr natural). Se citesc de la tastatură două numere naturale din intervalul \([1,10^9]\), x
și y
(x<y
), reprezentând doi termeni aflați pe poziții consecutive în șirul dat, și se cere să se scrie în fișierul text bac.out
, separați prin câte un spațiu, toți termenii șirului mai mici sau egali cu y
, în ordine inversă a apariției lor în șir. Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie și al timpului de executare.
Exemplu: dacă x=21
și y=31
, fişierul conţine valorile 31 21 13 7 3 1
Subiecte antrenament, 2021, testul 10
Fişierul bac.txt
conține un șir de cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran cea mai mică poziție pe care ar putea-o ocupa primul termen al șirului aflat în fișier în șirul format cu aceleași valori, ordonat crescător. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține 15 7 15 17 6 4
se afișează pe ecran 4
(15
se află pe a patra și pe a cincea poziție în șirul 4, 6, 7, 15, 15, 17
).
Subiecte antrenament, 2021, testul 9
Fișierul numere.txt
conține cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), câte unul pe fiecare linie.
Se cere să se afișeze pe ecran cel mai mare număr care se poate forma cu toate cifrele care apar în numerele din fișier, ca în exemplu.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține:
263 39628 79 887308
se afișează
9988887766333220
Subiecte antrenament, 2021, testul 8
Fișierul bac.txt
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\).
Se cere să se determine și să se afișeze pe ecran, separate printr-un spațiu, ultimele două numere impare (nu neapărat distincte) din șirul aflat în fișier, sau mesajul nu exista
, dacă nu există două astfel de numere.Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține valorile 122
1635
628
1413
1647
900
3001
4252
se afișează pe ecran 1647 3001
Subiecte antrenament, 2021, testul 7
Fișierul bac.txt
conține cel mult \(10^6\) cifre, separate prin câte un spațiu.
Se cere să se afișeze pe ecran, separate prin câte un spațiu, toate cifrele pare care apar în fișier sau mesajul nu exista
, dacă nu există astfel de cifre. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține cifrele 3 3 0 8 2 1 2 1 3 7 1 5 2 7 1 0 3 2 3
pe ecran se afișează, de exemplu în ordine crescătoare, cifrele 0 0 2 2 2 2 8
Subiecte antrenament, 2021, testul 6
Fișierul bac.in
conține un șir de cel puțin patru și cel mult \(10^5\) numere întregi nenule din intervalul \([-10^9,10^9]\), dintre care trei sunt negative, iar restul pozitive. Numerele sunt separate prin câte un spațiu. O secvență este formată din termeni aflați pe poziții consecutive în șir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia.
Se cere să se afișeze pe ecran lungimea unei secvențe din șirul aflat în fișier care conține o singură valoare negativă și un număr maxim de valori pozitive. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține numerele 15 21 -61 9 870 -23 11 5 8 -81 5 14
pe ecran se afișează 6
(corespunzător secvențelor 9 870 -23 11 5 8
sau 11 5 8 -81 5 14
).
Subiecte antrenament, 2021, testul 5
Fişierul bac.txt
conține numere naturale din intervalul \([2,10^6]\): pe prima linie \(n\), iar pe a doua linie un șir de \(n\) numere, separate prin câte un spațiu. Se cere să se afișeze pe ecran, pentru fiecare număr natural \(i\) (\(i ∊ [1,n]\)), cea mai mare dintre primele \(i\) valori ale șirului aflat în fișier. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă fișierul conține
12 4 6 3 7 8 1 6 2 7 9 10 8
se afișează pe ecran
4 6 6 7 8 8 8 8 8 9 10 10
Subiecte antrenament, 2021, testul 3
Două numere naturale sunt numite z-prietene dacă au aceeași cifră a zecilor.
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([10,10^9]\), separate prin câte un spațiu.
Se cere să se afișeze pe ecran pozițiile din șir pe care se află termeni precedați de un număr maxim de valori z-prietene cu ei. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 726 358 98 157 20 49 128 879 659 271
pe ecran se afișează numerele 7 9
(termenii 128
, respectiv 659
respectă proprietatea cerută).
Subiecte antrenament, 2021, testul 2
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^9,10^9]\), separate prin câte un spațiu. Cel puțin un număr din șir este pozitiv.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe a șirului care fie începe, fie se încheie cu un număr pozitiv. O secvență este formată din termeni aflați pe poziții consecutive în șir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține numerele -15 -7 4 -7 21-5 -200 -26 52 -24 -7 -9 -20
pe ecran se afișează 11
(corespunzător secvenței 4 -7 21 -5 -200 -26 52 -24 -7 -9 -20
).
Subiecte antrenament, 2021, testul 1
Fișierul bac.in
conține cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran, în ordine descrescătoare, cele mai mari două numere de două cifre distincte care NU se află în fișier. Numerele afișate sunt separate printr-un spațiu, iar dacă nu există două astfel de numere, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul bac.in
conține numerele 12 235 123 67 98 6 96 94 123 67 98 100
se afișează pe ecran, în această ordine,numerele 97 95
.
Subect simulare, 2021
La proiectarea unui site web se utilizează elemente grafice realizate pe baza unor modele. Fiecare model este de formă pătrată și oricare două modele distincte au dimensiuni diferite ale laturilor. Toate elementele grafice realizate pe baza unui anumit model au aceeași formă și aceleași dimensiuni ca ale acestuia. În vederea asigurării elementelor grafice necesare, pentru fiecare model dintre cele utilizate se plătește o taxă unică de proiectare, de 10
lei, iar pentru fiecare element grafic realizat pe baza acelui model se plătește o sumă în lei, egală cu valoarea suprafeței acestuia (aria pătratului), calculată în centimetri pătrați.
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([1,10]\), separate prin câte un spațiu, reprezentând dimensiunile laturilor tuturor elementelor grafice utilizate, date în centimetri; fiecare termen al șirului corespunde unui element grafic distinct. Se cere să se afișeze pe ecran suma totală plătită pentru asigurarea elementelor grafice necesare. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 1 7 2 1 1 2 1 7 2
se afișează pe ecran valoarea 144
(10
lei pentru modelul de lățime 1
cm și câte 1∙1
lei pentru fiecare dintre cele patru elemente grafice care îl au la bază, 10
lei pentru modelul de lățime 2
cm și câte 2∙2
lei pentru fiecare dintre cele trei elemente grafice care îl au la bază, respectiv 10
lei pentru modelul de lățime 7
cm și câte 7∙7
lei pentru fiecare dintre cele două elemente grafice care îl au la bază).
Model subiect, 2021
Fișierul cheltuieli.in
are cel mult \(10^6\) linii, fiecare linie conținând câte trei numere naturale din intervalul \([1,10^2]\), reprezentând, în această ordine, date despre câte o achiziție: tipul produsului cumpărat, numărul de produse de acest tip cumpărate, respectiv prețul unui astfel de produs la acel moment. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran cea mai mare sumă cheltuită pentru toate produsele de același tip, precum și numărul de tipuri de produse pentru care s-a obținut această sumă. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul cheltuieli.in
are conținutul următor
4 1 10 1 16 1 4 2 8 2 1 5 1 5 2
se afișează pe ecran: 26 2
(s-a cheltuit suma maximă 26
pentru produsele de tipul 1
și 4
: 26=16·1+5·2=1·10+2·8
)
Sesiunea august-septembrie 2020
Fișierul bac.txt
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran, separate printr-un spațiu, două numere naturale a
și b
(a<b
), astfel încât oricare termen al șirului care are exact două cifre să aparțină intervalului (a,b)
, iar valoarea expresiei b-a
să fie minimă. Dacă șirul nu are niciun termen de două cifre, pe ecran se afișează mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține valorile 7 2 40 5 11 15 10 122 18 350
se afișează pe ecran numerele 9 41
.
Sesiunea iunie-iulie 2020
Un șir finit se numește palindromic dacă parcurgându-l termen cu termen, de la stânga la dreapta sau de la dreapta la stânga se obține același șir de valori.
Exemplu:șirul 12
13
16
13
12
este palindromic.
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([1,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA
, dacă numerele din șir pot fi rearanjate, astfel încât să formeze un șir palindromic, sau mesajul NU
în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 100
30
100
30
500
30
30
se afișează pe ecran DA
Sesiunea specială 2020
Se numește vârf într-un șir de numere naturale un termen al șirului care este strict mai mare decât fiecare dintre cei doi termeni vecini cu el, aflați în șir pe poziția din stânga, respectiv din dreapta sa.
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran vârful din șirul aflat în fișier pentru care valoarea absolută a diferenței dintre cei doi vecini ai săi este minimă. Dacă există mai multe astfel de numere, se afișează cel mai mare dintre ele, iar dacă nu există niciun vârf, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține șirul 2
7
10
5
6
2
1
3
20
17
9
11
7
3
10
6
2
se afișează pe ecran 11
Subiecte antrenament, 2020, testul 1
Se consideră șirul 1
, 1
, 2
, 5
, 13
, 34
, 89
, 233
, 610
…. definit astfel: \(f_1=f_2=1\), \(f_n=3 \cdot f_{n-1}-f_{n-2}\)(unde \(n\) este un număr natural \(n≥3\)).
Se citesc de la tastatură două numere naturale \(x\) și \(y\) (\(x≤y≤10^9\)), valorile a doi termeni aflați pe poziții consecutive în şirul dat, şi se cere să se scrie în fişierul text bac.txt
, în ordine descrescătoare, separați prin câte un spațiu, toţi termenii şirului care sunt mai mici sau egali cu \(y\). Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă se citesc numerele 89 233
fişierul bac.txt
va conţine numerele 233 89 34 13 5 2 1 1
Subiecte antrenament, 2020, testul 2
Fişierul bac.in
conţine un şir de numere naturale distincte, din intervalul [\(1,10^9]\). Numerele din şir sunt separate prin câte un spaţiu şi cel puţin trei dintre ele au penultima cifră 2
și ultima cifră 0
. Se cere să se afișeze pe ecran cele mai mari trei numere din şir cu proprietatea că au penultima cifră 2
și ultima cifră 0
. Numerele determinate sunt afişate în ordine crescătoare, separate prin câte un spaţiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă fişierul conţine numerele 9731 50 112 20 8 16 8520 3 2520 1520
pe ecran se vor afişa, în această ordine, numerele: 1520 2520 8520
Subiecte antrenament, 2020, testul 3
Fişierul bac.in
conţine un şir de cel mult \(10^6\) numere întregi din intervalul \([-10^9,10^9]\), separate prin câte un spaţiu. Cel puţin un număr din șir este negativ.
Se cere să se afişeze pe ecran lungimea maximă a unei secvenţe a şirului care fie începe, fie se încheie cu un număr negativ. O secvenţă este formată din termeni aflaţi pe poziţii consecutive în şir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă fişierul conţine numerele 12
25
-6
7
80
-75
101
-6
52
-124
87
99
210
pe ecran se afişează 11
(corespunzător secvenţei -6
7
80
-75
101
-6
52
-124
87
99
210
).
Subiecte antrenament, 2020, testul 4
Fişierul bac.txt
conţine, în ordine descrescătoare, cel puţin două şi cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spaţiu. Se cere să se afişeze pe ecran, în ordine strict descrescătoare, separate prin câte un spaţiu, numai numerele care apar în fişier de exact două ori. Dacă nu există niciun astfel de număr, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă fişierul conţine numerele 100 50 50 50 49 49 36 16 16 12 10 10 9 7 7
pe ecran se afişează, în această ordine, numerele 49 16 10 7
Subiecte antrenament, 2020, testul 5
Fișierul bac.txt
conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^3,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran suma maximă obținută adunând numere de pe poziții consecutive în șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul bac.txt
conține valorile 4
-6
7
2
-1
4
-10
-3
9
2
-2
se afișează pe ecran numărul 12
Subiecte antrenament, 2020, testul 6
Se citesc de la tastatură două numere naturale din intervalul [1,81]
, p1
și p2
, și se cere scrierea în fișierul bac.out
a tuturor numerelor naturale cu exact 7
cifre, pentru care produsul primelor două cifre este egal cu p1
, cele trei cifre din mijloc sunt egale între ele, iar produsul ultimelor două cifre este egal cu p2
. Numerele apar în fișier în ordine strict descrescătoare, fiecare pe câte o linie. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă p1=12
, iar p2=8
, atunci 2633324
și 3400018
sunt două dintre cele 160
de numere cuproprietatea cerută (2∙6=3∙4=12
și 2∙4=1∙8=8
).
Subiecte antrenament, 2020, testul 7
Fișierul bac.txt
conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^3,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran suma minimă obținută adunând numere de pe poziții consecutive în șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul bac.txt
conține valorile -4
6
-7
-2
1
-4
10
3
-9
-2
2
se afișează pe ecran numărul -12
Subiecte antrenament, 2020, testul 8
Fișierul bac.in
conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran pozițiile din șir pe care se află termeni precedați de un număr maxim de valori care au cifra unităților egală cu cifra unităților lor. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul bac.in
conține numerele 112
12
5
25
88
15
2
19
32
179
35
621
pe ecran se afișează numerele de mai jos 9 11
(termenii 32
, respectiv 35
respectă proprietatea cerută).
Subiecte antrenament, 2020, testul 9
Numim k-secvență într-un șir de numere naturale, o succesiune de termeni aflați pe poziții consecutive în șir, cu proprietatea că sunt divizibili cu numărul natural nenul k
. Lungimea secvenței este egală cu numărul de termeni ai săi.
Fișierul bac.txt
conține numere naturale din intervalul \([0,10^9]\): pe prima linie un număr nenul k
, iar pe a doua linie un șir de cel mult \(10^6\) numere, separate prin câte un spațiu. Cel puțin un termen din șir este divizibil cu k
. Se cere să se afișeze pe ecran două valori, separate printr-un spațiu, reprezentând lungimea maximă a unei k-secvențe din șirul aflat în fișier, respectiv numărul de astfel de secvențe. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține
5 2 10 5 20 21 0 10 60 15 3 9 20 20 5 45
se afișează 4 2
Subiecte antrenament, 2020, testul 10
Un șir format din cel puțin trei termeni formează o progresie aritmetică de rație r
dacă diferența dintre oricare termen al acestuia și cel aflat pe poziția consecutivă în șir este egală cu r
.
Fișierul text bac.txt
conține un șir de cel puțin trei și cel mult \(10^6\) numere întregi din intervalul \([-10^8,10^8]\). Numerele sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran rația unei secvențe din șir cu număr maxim de termeni, secvență care formează o progresie aritmetică. Dacă există mai multe astfel de secvențe de lungime maximă se afișează rația cea mai mare, iar dacă nu există nicio astfel de secvență, se afișează pe ecran mesajul nu exista
. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține numerele 4
9
14
19
18
16
8
5
3
1
-1
-3
-5
-7
pe ecran se afișează valoarea -2
(corespunzătoare secvenței 5 3 1 -1 -3 -5 -7
).
Subiecte antrenament, 2020, testul 11
Fişierul bac.txt
conţine un şir crescător de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spaţiu. Se cere să se afişeze pe ecran fiecare număr distinct din şir, urmat de numărul de apariţii ale acestuia în şir. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fişierul bac.txt
conține numerele 0 0 0 5 5 5 5 7 7 11 20 20
se afișează 0 3 5 4 7 2 11 1 20 2
Definiție. Se numește arbore binar un arbore cu rădăcină în care fiecare nod are cel mult doi descendenți direcți: descendentul stâng și descendentul drept.
Exemplu.
În arborele de mai sus:
1
este rădăcina;2
este descendent stâng a lui 1
, iar 3
este descendent drept;2
are un singur descendent, pe 4
. Acesta este descendent stâng al lui 2
;7
este descendent drept al lui 4
;5
, 6
și 7
sunt noduri terminale (frunze).Observație. Dacă un nod are un singur descendent acesta va fi descendent stâng sau drept – acest lucru trebuie să fie precizat. Cei doi arbori de mai jos sunt considerați distincți.
O altă definiție, recursivă, a arborelui binar este următoarea: Un arbore binar este o mulțime finită de noduri, astfel:
Această definiție recursivă este utilă deoarece foarte multe probleme cu arbori binari constau în prelucrarea nodurilor din arbore: a rădăcinii și a celor doi subarbori, în mod recursiv, prin metoda Divide et Impera.
i=0,1,2,...
dintr-un arbore binar conține cel mult 2
i
noduri.h
conține cel mult 2
h+1
-1
noduri. Demonstrația se bazează pe afirmația anterioară.n
noduri și înâlțime h
avem relația \( h \geq \log_{2}{(n+1)} -1 \).a
, iar c
este numărul nodurilor care au exact 2
fii, atunci a = c + 1
.Definiție: Se numește arbore binar strict un arbore binar în care fiecare nod, cu excepția celor terminale, are exact doi descendenți.
Exemplu:
Proprietăți:
Definiție: Se numește arbore binar plin un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri.
Exemplu:
Proprietăți:
Definiție: Se numește arbore binar complet un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h – 1 \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri, iar nivelul \(k\) conține eventual mai puțin de \(2^h\) noduri, acestea fiind grupate de regulă în partea stângă.
Exemplu:
Observație: Arborele binar plin este și arbore binar complet.
Arborii binari se pot reprezenta fie prin referințe ascendente, fie prin referințe descendente, fie combinând cele două variante.
În cazul reprezentării prin referințe ascendente, pentru fiecare nod din arbore trebuie să se cunoască:
Pentru memorarea informațiilor, considerând nodurile numerotate începând cu 1
, putem folosi două tablouri: Tata[]
și Tip[]
, unde Tata[k]
reprezintă nodul părinte al lui k
sau 0
dacă k
este chiar rădăcina arborelui, iat Tip[k]
este 0
, dacă k
este rădăcina arborului (caz în care nu are părinte), respectiv -1
dacă k
este descendent stâng al lui Tata[k]
sau 1
dacă k
este descendent drept al lui Tata[k]
.
Exemplu.
Pentru arborele de mai sus, cele doua tablouri sunt:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Tata[k ] |
0 |
1 |
1 |
2 |
3 |
3 |
4 |
Tip[k ] |
0 |
-1 |
1 |
-1 |
-1 |
1 |
1 |
În cazul reprezentării prin referințe descendente, trebuie să fie cunoscută rădăcina arborelui binar, iar pentru celelalte noduri din arbore, trebuie să se cunoască fiul stâng și fiul drept.
Această reprezentare se poate face cu ajutorul tablourilor sau prin intermediul alocării dinamice.
Dacă folosim tablouri, vom avea nevoie de două tablouri, st[]
(de la stânga) și dr[]
(de la dreapta). Considerând nodurile numerotate de la 1
la n
:
st[k]
reprezintă numărul de ordine al nodului care este descendent stâng al lui k
, sau 0
dacă k
nu are descendent stâng;dr[k]
reprezintă numărul de ordine al nodului care este descendent drept al lui k
, sau 0
dacă k
nu are descendent drept.Exemplu.
Pentru arborele de mai sus, cele doua tablouri sunt:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
st[k ] |
2 |
4 |
5 |
0 |
0 |
0 |
0 |
dr[k ] |
3 |
0 |
6 |
7 |
0 |
0 |
0 |
Cunoscând valorile din cele două tablouri putem identifica rădăcina ca nodul care nu apare nici în st[]
, nici în dr[]
. În exemplul de mai sus acesta este 1
.
Pentru fiecare nod al arborelui se crează o variabilă dinamică de tip structură, în care se vor memora următoarele câmpuri:
NULL
dacă nodul nu are descendent stâng (sau drept).Următoarea secvență C/C++ definește structura:
struct nod{ int info; nod * st, * dr; };
Pentru operațiile cu arborele reprezentat astfel este necesar să cunoaștem adresa nodului rădăcină:
nod * R;
Pornind de la nodul rădăcină pot fi parcurse toate nodurile din arbore, pentru a efectua diverse operații cu acestea.
Pentru a crea un arbore binar trebuie cunoscute pentru fiecare nod:
În funcție de reprezentarea folosită, mecanismul creării poate avea mai multe forme.
În cazul reprezentării statice pot fi citite numărul de noduri n
și elementele tablourilor st[]
și dr[]
, ca în exemplul următor:
// variabilele n, st[] si dr[] sunt considerate globale void Citire() { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> st[i]; for(int i = 1 ; i <= n ; i ++) cin >> dr[i]; }
În numeroase probleme este necesară identificarea nodului rădăcină, folosind informațiile din cele două tablouri.
Determinarea rădăcinii se poate face ținând cont de faptul că ea nu este descendent al niciunui nod din arbore, deci nu va apărea în cele două tablouri:
int Radacina() { int v[101] = {0}; for(int i = 1 ; i <= n ; i ++) { if(st[i] != 0) v[st[i]] = 1; if(dr[i] != 0) v[dr[i]] = 1; } for(int i = 1 ; i <= n ; i ++) if(v[i] == 0) return i; return 0; }
Reprezentarea dinamică unui arbore impune ca operațiile cu nodurile arborelui, inclusiv crearea, să se realizeze pornind de la rădăcină și continuând pe rând cu cei doi subarbori. Tehnica folosită este recursivitatea: pentru toți arborii (arborele initial și subarborii) realizăm aceleași operații – prelucrăm rădăcina și continuăm cu cei doi subarbori.
Schema folosită în funcția Creare
din programul de mai jos este următoarea:
NULL
. Crează arborele (subarborele) și îl întoarce având ca valoare adresa rădăcinii;Pentru afișarea arborelui folosim funcția Afisare
care procedează similar:
NULL
#include <iostream> using namespace std; int n , st[101], dr[101]; struct nod { int info; nod * st, * dr; }; void Creare(nod * & r, int x) { if(x != 0) { r = new nod; r->info = x; r->st = r->dr = NULL; int y; cout << "st[" << x << "]="; cin >> y; Creare(r -> st , y); cout << "dr[" << x << "]="; cin >> y; Creare(r -> dr , y);; } } void Afisare(nod * r) { if(r != NULL) { cout << r->info << " "; Afisare(r->st); Afisare(r->dr); } } int main() { nod * R = NULL; int x; cout << "Eticheta radacinii: "; cin >> x; Creare(R , x); Afisare(R); return 0; }
Pentru a prelucra un arbore este necesar ca nodurile sale să fie vizitate. La fel ca în cazul grafurilor (ceea ce și sunt de fapt arborii binari), ei pot fi parcurși în lățime sau în adâncime, a doua metodă fiind de regulă folosită.
Parcurgerea începe din rădăcină.
În funcție de ordinea în care se vizitează nodurile avem următoarele parcurgeri:
Observație: În programul de mai sus, crearea și afișarea arborelui se fac cu ajutorul parcurgerii, mai precis a parcurgerii în preordine.
Exemplu
Pentru arborele de mai sus, ordinea de parcurgere este:
4 7 2 1 5 3 6
1 2 4 7 3 5 6
7 4 2 5 6 3 1
Deoarece parcurgerea începe din rădăcină și continuă cu nodurile descendent (cu subarborii stâng și drept), reprezentarea folosită este cea cu referințe descendente.
Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore. Reprezentarea arborelui este prin tablourile st[]
și dr[]
. Datele de intrare se citesc de la tastatură: mai întâi se citește numărul de noduri, n
, apoi elementele vectorului st[]
, apoi elementele vectorului dr[]
.
#include <iostream> using namespace std; int n , st[101], dr[101]; void Citire() { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> st[i]; for(int i = 1 ; i <= n ; i ++) cin >> dr[i]; } int Radacina() { // radacina este un nod intre 1 și n care nu apare în tablourile st[] și dr[] int v[101] = {0}; for(int i = 1 ; i <= n ; i ++) { if(st[i] != 0) v[st[i]] = 1; if(dr[i] != 0) v[dr[i]] = 1; } for(int i = 1 ; i <= n ; i ++) if(v[i] == 0) return i; return 0; } void Inordine(int x) { if(x != 0) { Inordine(st[x]); cout << x << " "; Inordine(dr[x]); } } void Preordine(int x) { if(x != 0) { cout << x << " "; Preordine(st[x]); Preordine(dr[x]); } } void Postordine(int x) { if(x != 0) { Postordine(st[x]); Postordine(dr[x]); cout << x << " "; } } int main() { Citire(); int R = Radacina(); Inordine(R); cout << endl; Preordine(R); cout << endl; Postordine(R); cout << endl; return 0; }
Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore, reprezentarea acestuia fiind cea dinamică.
#include <iostream> using namespace std; int n , st[101], dr[101]; struct nod { int info; nod * st, * dr; }; void Creare(nod * & r, int x) { if(x != 0) { r = new nod; r->info = x; r->st = r->dr = NULL; int y; cout << "st[" << x << "]="; cin >> y; Creare(r -> st , y); cout << "dr[" << x << "]="; cin >> y; Creare(r -> dr , y);; } } void Preordine(nod * r) { if(r != NULL) { cout << r->info << " "; Preordine(r->st); Preordine(r->dr); } } void Inordine(nod * r) { if(r != NULL) { Inordine(r->st); cout << r->info << " "; Inordine(r->dr); } } void Postordine(nod * r) { if(r != NULL) { Postordine(r->st); Postordine(r->dr); cout << r->info << " "; } } int main() { nod * R = NULL; int x; cout << "Eticheta radacinii: "; cin >> x; Creare(R , x); Preordine(R); cout << endl; Inordine(R); cout << endl; Postordine(R); cout << endl; return 0; }
Ștergerea arborilor binari este necesară cu precădere în cazul reprezentării dinamice a acestora.
Ștergerea se va face nod cu nod, folosind parcurgerea în postordine: parcurgem subarbore stâng, apoi subarborele drept, apoi prelucrăm rădăcina. În acest fel la ștergerea nodului rădăcină cei doi subarbori sunt deja șterși.
Funcția C++ de mai jos șterge arborele binar pentru care adresa rădăcinii este transmisă ca parametru. Acesta parametru este de intrare-ieșire: intră cu adresa rădăcinii și iese cu valoarea NULL
– arborele a fost șters.
void Stergere(nod * & R) { if(R != NULL) { Stergere(R->st); Stergere(R->dr); delete R; R = NULL; } }
Funcția de mai sus poate fi utilizată și pentru ștergerea unui subarbore dintr-un arbore dat. Este însă important ca parametrul să fie câmpul st
sau dr
din nodul părinte, nu un pointer oarecare care să memoreze adresa rădăcinii subarborelui.
Exemplu: Considerăm un arbore binar pentru care adresa rădăcinii este memorată în pointerul R
. Dorim să ștergem subarborele stâng al rădăcinii, care are adresa în R->st
.
Următoarea secvență este corectă.
Stergere(R->st);
Următoarea secvență este greșită. De ce?
nod * p = R->st; Stergere(p);
Să se afişeze cel mai mare număr format din cifrele numărului luate o singură dată.