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 = 24a 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 = 192a 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 An procedăm astfel:
P, format din factori de forma A1, A2, A4, A8, …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 august 2025
La o centrală solară se monitorizează stocul zilnic de energie produsă și stocul total calculat pentru fiecare perioadă. Zilele de monitorizare sunt numerotate cu valori naturale consecutive, în ordine cronologică, începând cu ziua 1. O perioadă este formată din cel puțin două zile de monitorizare, consecutive, iar stocul total calculat pentru ea este suma stocurilor zilnice corespunzătoare. O zi este validată dacă stocul zilnic este cel puțin egal cu limita zilnică, minZ; o perioadă este validată dacă stocul total calculat pentru ea este cel puțin egal cu limita stabilită pentru perioade, minP, fiecare zi a perioadei este validată, iar perioada este maximală în raport cu această proprietate (nu i se mai poate adăuga nicio zi validată).
Fișierul text bac.in conține cel mult 106 numere naturale din intervalul [1,103]: pe prima linie minZ și minP, reprezentând limitele precizate pentru validare, iar pe a doua linie stocurile zilnice de energie produse în zile consecutive, în ordinea monitorizării. 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, pentru fiecare perioadă de producție validată, corespunzătoare datelor din fișier, câte un triplet de numere, reprezentând prima și ultima zi a perioadei, respectiv stocul total calculat pentru ea. Valorile din fiecare triplet se afișează pe câte o linie a ecranului, separate prin câte un spațiu, iar dacă nu există nicio astfel de perioadă, se afișează 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 valorile
10 40 65 9 20 25 12 14 7 3 11 15 12 8 19 50 21
se afișează pe ecran
3 6 71 13 15 90
Sunt validate perioadele 20 25 12 14 și 19 50 21.
Sesiunea iunie-iulie 2025, subiect de rezervă
La o loterie se generează aleatoriu un șir de numere naturale și pentru fiecare număr generat, se inversează ordinea cifrelor. Dintre valorile distincte obținute se extrag trei numere, în această ordine: cel mai mic, cel mai mare dintre cele rămase, apoi cel mai mic dintre cele rămase.
Fișierul text bac.in conține cel mult 106 numere naturale din intervalul [1001,9999], cu cifra unităților nenulă, separate prin câte un spațiu, reprezentând termenii șirului generat aleatoriu în vederea extragerii. Scrieți un program C/C++ care afișează pe ecran cele trei numere, în ordinea extragerii acestora. Numerele afișate sunt separate prin câte un spațiu, iar dacă nu există trei astfel de numere distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
*Exemplu:@ dacă fișierul conține numerele 1114 3212 3217 2855 7309 2131 2131 1238 7893 se afișează pe ecran, în această ordine, numerele 1312 9037 2123
Sesiunea iunie-iulie 2025
Un tânăr pasionat de călătorii are o listă cu muzee virtuale și, pentru fiecare, câte un singur interval orar, în care acesta poate fi vizitat online, gratuit. Tânărul dispune zilnic de același interval orar pentru vizite; un muzeu este convenabil dacă poate fi vizitat online gratuit în timpul disponibil și dacă pentru vizită îi poate aloca cel puțin o oră. Muzeele din listă sunt numerotate cu valori naturale consecutive, începând cu 1, și
cel puțin unul este convenabil.
Fișierul text bac.in conține cel mult 105 linii, iar pe fiecare linie câte o pereche de numere, reprezentând limitele câte unui interval orar: pe prima linie intervalul orar de care tânărul dispune zilnic, iar pe fiecare dintre următoarele linii, intervalul orar de vizitare gratuită pentru câte un muzeu, în ordinea din listă. Limitele intervalelor sunt ore fixe, numere naturale din intervalul [8,22], iar cele aflate pe aceeași linie a fișierului sunt în ordine strict crescătoare și sunt separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori, reprezentând numărul de muzee convenabile, respectiv numărul de ordine al ultimului astfel de muzeu din lista tânărului. Utilizați un algoritm eficient din punctul de vedere al timpului de executare şi al memoriei utilizate.
Exemplu: dacă fișierul conține valorile
16 19 15 18 17 21 19 21 18 20 12 13
atunci pe ecran se afișează numerele 3 4. (pot fi vizitate trei muzee cu numerele de ordine 1, 2 și 4, în intervalele 16-18, 1@7-19@, respectiv
18-19).
Sesiunea specială 2025
Fișierul text bac.txt conține un șir de cel mult 106 triplete de numere naturale din intervalul [1,102], numerele din fiecare triplet reprezentând lungimile laturilor câte unui triunghi. Fiecare triplet se află pe câte o linie a fișierului, iar numerele care îl compun sunt separate prin câte un spațiu. Într-un triunghi dreptunghic pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor
celor două catete.
Se cere să se afișeze pe ecran numărul maxim de triunghiuri dreptunghice din fișier care au aceeași lungime a ipotenuzei. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
6 10 6 7 24 25 7 25 24 25 14 13 8 6 10 15 20 25 4 5 3
pe ecran se afișează 3 (sunt trei triunghiuri de tipul cerut cu ipotenuza 25: două au catetele 7, respectiv 24, și unul are catetele 15, respectiv 20).
Simulare 2025
Pentru o paradă a modei sunt pregătite seturi de bijuterii, un set fiind format din cercei și pandantiv, cu câte cel puțin două pietre prețioase și semiprețioase. Sunt utilizate nouă tipuri de pietre, numerotate de la 1 la 9, iar orice bijuterie are o etichetă, număr natural în care fiecare cifră corespunde unei pietre din montură, în ordinea descrescătoare a importanței în cadrul modelului. Un set este potrivit dacă cele mai importante două pietre ale fiecărei bijuterii din set sunt de același tip, chiar dacă nu în aceeași ordine a importanței.
Fișierul bijuterii.in conține numere naturale din intervalul [10,999]: pe prima linie două numere nc și np, reprezentând numărul de cercei, respectiv de pandantive disponibile, pe a doua linie un șir de nc numere, reprezentând etichetele cerceilor, iar pe a treia linie un șir de np numere, reprezentând etichetele pandantivelor. 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 mesajul DA, dacă se poate forma cel puțin un set potrivit de bijuterii, 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
10 11 497 125 521 497 513 258 491 55 551 16 21 259 943 77 945 57 52 552 16 17 71
se afișează pe ecran mesajul DA; două dintre cele 14 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu
etichetele 259, respectiv 52, pentru toate aceste bijuterii pietrele de tipurile 2 și 5 fiind cele mai importante).
Model 2025
La o expoziție auto se află, în șir, mașini de epocă, fiecare având câte un cod, format prin alipirea, în această ordine, a două numere naturale nenule: identificatorul colecționarului care deține mașina, respectiv anul fabricației acesteia.
Fişierul bac.txt conţine numere naturale: pe prima linie un număr x (x∊[1880,1950]), reprezentând un an calendaristic, iar pe a doua linie cel mult 105 numere din intervalul [104,109], reprezentând codurile mașinilor, în ordinea din șirul în care sunt expuse. Numerele aflate pe aceeași linie în fișier sunt separate prin câte un spaţiu.
Se cere să se afișeze pe ecran identificatorii colecționarilor care dețin ultimele două mașini, din șirul celor expuse, ambele fiind fabricate în anul x și aflate în șir pe poziții consecutive, ca în exemplu. Numerele, nu neapărat distincte, sunt afișate în ordinea în care mașinile corespunzătoare apar în șir, separate printr-un spațiu, iar dacă nu există două astfel de mașini, 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
1925 31885 21925 8931925 31925 121900 11925 31925 151925 61950 201925 121880
atunci pe ecran se afișează 3 15
Sesiunea august 2024
Șirul 0, 0, 1, 4, 13, 38, 105, 280, 729 .... este definit astfel: f[1]=f[2]=0, f[3]=1, f[n]=4∙f[n-1]-3∙f[n-2]-2∙f[n-3] (unde n este un număr natural n≥4).
Se citesc de la tastatură trei numere naturale x, y și z (x≤y<z≤109), valorile a trei termeni aflați pe poziții consecutive în șirul dat, și se cere să se scrie în fișierul 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 z. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă se citesc numerele 38 105 280 fişierul conţine numerele 280 105 38 13 4 1 0 0
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 106 numere naturale din intervalul [10,104], 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 106 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 106 numere naturale din intervalul [1,103], 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,106], m și n, iar pe următoarele două linii numere naturale din intervalul [0,102): 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 106 numere naturale din intervalul [10,104), 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.in conține un șir de cel mult 106 numere întregi din intervalul [-109,109], 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 106 numere naturale din intervalul [0,104], 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 2i noduri.h conține cel mult 2h+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 61 2 4 7 3 5 67 4 2 5 6 3 1Deoarece 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);
Stars and bars (Stele și bare) este o metodă de rezolvare a unor probleme de combinatorică. Se poate folosi când trebuie să determinăm numărul de modalități de a grupa un număr dat de obiecte identice.
Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii este egal cu: \( C_{n+k-1}^{k-1} \).
Demonstrația implică separarea celor n obiecte (stele) în k cutii prin k-1 bare – de unde și numele. De exemplu, configurația următoare are n=7 stele și k=4 cutii: \( \star \vert \star \star \vert \vert \star \star \star \star \) și corespunde următoarei situații:
Configurația este echivalentă cu următoarea configurație de biți: 0100110000, în care bitul 1 corespunde obiectului, \( \star \), iar 1 corespunde barei, \( \vert \). Toate configurațiile convenabile au n-k+1 biți, dintre care n au valoarea 0 și k-1 au valoarea 1 și corespund submulțimilor cu k-1 elemente ale unei mulțimi cu n+k-1 elemente.
Astfel, numărul lor este \( C_{n+k-1}^{k-1} \).
Consecință Ecuația \(x_1 + x_2 + x_3 + \cdots + x_k = n\) are \( C_{n+k-1}^{k-1} \) soluții întregi nenegative (mai mari sau egale cu 0).
Afirmația este echivalentă cu teorema de mai sus, în care \(x_i\) fiind egal cu numărul de obiecte din cutia i.
Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect este egal cu: \( C_{n-1}^{k-1} \).
Demonstrația 1: Fixăm în fiecare cutie câte un obiect. Rămân \(n – k\) obiecte care trebuie plasate în \(k\) cutii, în condițiile teoremei de mai sus. Astfel, numărul de variante este \( C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} \).
Demonstrația 2: Folosim metoda Stars and bars. Separarea obiectelor în cutii se face plasând \(k\) bare în golurile dintre obiecte. Sunt \(n-1\) goluri în care putem plasa \(k\) bare în \( C_{n-1}^{k-1} \) moduri.
Pseudocod este un limbaj prin care sunt descriși pașii dintr-un algoritm. Limbajul pseudocod conține structurile specifice unui limbaj de programare obișnuit (precum Pascal, C/C++, Basic, etc) dar este destinat a fi citit de către oameni, nu de către calculatoare.
De obicei sunt omise detaliile vitale într-un limbaj de programare, precum declararea variabilelor sau secvențe specifice limbajului. Algoritmii pseudocod pot conține secvențe descrise în limbaj natural, precum și expresii matematice compacte, care lipsesc din limbajele de programare reale.
Conceptele care intervin in algoritmii pseudocod sunt similare cu cele din limbajele de programare:
Există mai multe variante ale limbajului pseudocod. Acest articol se referă la varianta folosită în subiectele pentru examenul de bacalaureat la informatică. Limba folosită este limba română.
În pseudocod variabilele nu se declară, iar numele lor respectă regula uzuală a identificatorilor – litere, cifre, caracterul de subliniere și să nu înceapă cu cifră.
Constantele care apar de regulă în algoritmii pseudocod sunt constante literale (valori numerice, întregi sau reale, caractere – delimitate prin apostrof ‘, șiruri de caractere – delimitate prin apostroafe (‘) sau ghilimele (“). De asemenea, pot să apară constante matematice, de exemplu \( \pi \).
Sunt prezente toate operațiile aritmetice uzuale:
a+b. În funcție de context, rezultatul este întreg sau real.a-b. În funcție de context, rezultatul este întreg sau real.a*b. În funcție de context, rezultatul este întreg sau real.a/b. Rezultatul se consideră real. Dacă se dorește determinarea câtului împărțirii a două numere naturale, se va folosi partea întreagă a rezultatului împărțirii: [a/b].a%b. Se aplică numai pentru date întregi, iar rezultatul este număr întreg.Notă: Unele variante pseudocod propun operațiile DIV și MOD pentru determinarea câtului și restului împărțirii a două numere întregi. De asemenea, pot să apară operații de ridicare la putere, în forma \( a ^ n\), sau de extragere a rădăcinii pătrate – \(\sqrt{x}\).
Operațiile relaționale sunt:
= – egalitatea≠ – neegalitatea< – mai mic≤ – mai mic sau egal> – mai mare≥ – mai mare sau egalOperanzii sunt de regulă numere, iar rezultatul este valoare de adevăr (adevărat sau fals).
Operațiile logice sunt NOT, ȘI, SAU – cu semnificațiile cunoscute. O descriere a operațiilor logice poate fi găsită aici: www.pbinfo.ro/articole/21315/operatii-logice.
Instrucțiunile sunt componentele algoritmului care au efect, atunci când se execută. Ele modifică valorile unor variabile, citesc sau afișează date, repetă anumite acțiuni, etc.
De regulă fiecare instrucțiune se scrie pe o linie (sau mai multe în cazul celor complexe), dar există situații când, pentru a economisi spațiu, două sau mai multe instrucțiuni simple se scriu pe același rând, separate prin ;.
Orice algoritm poate fi reprezentat prin intermediul a trei tipuri de structuri:
Pentru citirea datelor se folosește instrucțiunea citește <listă variabile>, unde <listă variabile> reprezintă un șir de variabile separate prin caracterul ,. Se preiau valori succesive de la tastatură și se memorează în variabilele din listă.
Exemplu
citeste a , b , c
Citirea datelor este frecvent însoțită de precizări privind datele citite (tip, valori posibile. etc.).
Pentru afișarea datelor se folosește instrucțiunea scrie <listă expresii>, unde <listă expresii> reprezintă un șir de expresii separate prin caracterul ,. Se evaluează în ordine expresiile din listă și se afisează pe ecran rezultatele lor.
Exemplu
scrie 'a + b = ' , a + b
Dacă a = 3 și b = 4 se va afișa:
a + b = 7
Pentru atribuire se folosește instructiunea <variabilă> ← <expresie>. Se evaluază expresia, iar valoarea obținută se memorează in variabilă.
Exemple
a ← 0 S ← a + b i ← i + 1
În pseudocod există instrucțiunea daca, cu următoarea sintaxă:
┌ daca <conditie> atunci │ <instructiuni1> │ altfel │ <instructiuni2> └■
sau
┌ daca <conditie> atunci │ <instructiuni1> └■
Modul de execuție este următorul:
<conditie><instructiuni1>, apoi se trece la următoarea instrucțiune<instructiuni2>, dacă există secțiunea altfel, apoi se trece la următoarea instrucțiune.Sintaxă
┌ pentru <variabila> ← <expresie initiala>, <expresie finala> , <pas> executa │ <instructiuni> └■
unde expresie initiala, expresie finala și pas sunt expresii cu rezultat (de regulă) întreg, iar pas poate fi 1 sau -1 și poate lipsi, caz în care se consideră că este 1.
variabila primește pe rând valori crescătoare (dacă pas = 1) sau descrescătoare (dacă pas = -1) începând de la expresie initiala până la expresie finala, și pentru fiecare valoare se execută secvența instructiuni.
Dacă pas = 1 și expresie initiala > expresie finala>, secvența instructiuni nu se va executa deloc. La fel se întâmplă când <pas = -1 și expresie initiala < expresie finala. În caz contrar numărul de pași este expresie initială - expresie finala + 1, dacă <pas = 1, respectiv expresie finală - expresie initiala + 1, dacă pas=-1.
Exemplu
Determinarea sumei și produsului primelor n numere naturale:
S ← 0; P ← 1 ┌ pentru i←1,n executa │ S ← S + i │ P ← P * i └■ scrie S, ' ' , P
Structura repetitivă cu număr necunoscut de pasi și test inițial
Sintaxă
┌ cat timp <conditie> executa │ <instructiuni> └■
Mod de execuție
Important: Dacă condiția este de la început falsă, instrucțiunile nu se vor executa deloc!
Exemplu
Determinarea sumei cifrelor unui număr natural:
citeste n S ← 0 ┌ cat timp n ≠ 0 executa │ S ← S + n % 10 │ n ← [n/10] └■ scrie S
Structura repetitivă cu număr necunoscut de pasi și test final
Sintaxă
┌ executa │ <instructiuni> └ cat timp <conditie>
Mod de execuție
Important: Chiar dacă condiția este de la început falsă, instrucțiunile s-au executat deja o dată!
Exemplu
Numărul cifrelor unui număr natural:
citeste n cnt ← 0 ┌ executa │ cnt ← cnt + 1 │ n ← [n/10] └ cat timp n ≠ 0 scrie cnt
Sintaxă
┌ repeta │ <instructiuni> └ pana cand <conditie>
Mod de execuție
Important: Chiar dacă condiția este de la început adevărată, instrucțiunile s-au executat deja o dată!
Exemplu
Numărul cifrelor unui număr natural:
citeste n cnt ← 0 ┌ repeta │ cnt ← cnt + 1 │ n ← [n/10] └ pana cand n = 0 scrie cnt
Numeroase exerciții propun un algoritm și se cere scrierea unui algoritm echivalent care să folosească o structură repetitivă de alt tip. Doi algoritmi sunt echivalenți dacă pentru orice set de date de intrare (conforme cu restricțiile problemei) ei obțin aceleași rezultate.
Această secțiune descrie câteva reguli de transformare a structurilor repetitive din algoritmii pseudocod.
PENTRU → CÂTTIMP
┌ pentru i←a,b executa │ <instructiuni> └■
i ← a ┌ cattimp i ≤ b executa │ <instructiuni> │ i ← i + 1 └■
PENTRU → EXECUTĂ … CÂTTIMP
┌ pentru i←a,b executa │ <instructiuni> └■
i ← a ┌ daca i ≤ b atunci │┌ executa ││ <instructiuni> ││ i ← i + 1 │└ cattimp i ≤ b └■
PENTRU → REPETĂ … PÂNÂCÂND
┌ pentru i←a,b executa │ <instructiuni> └■
i ← a ┌ daca i ≤ b atunci │┌ repeta ││ <instructiuni> ││ i ← i + 1 │└ panacand i > b └■
CÂTTIMP → EXECUTĂ … CÂTTIMP
┌ cattimp <conditie> executa │ <instructiuni> └■
┌ daca <conditie> atunci │┌ executa ││ <instructiuni> │└ cattimp <conditie> └■
CÂTTIMP → REPETĂ … PÂNÂCÂND
┌ cattimp <conditie> executa │ <instructiuni> └■
┌ daca <conditie> atunci │┌ repeta ││ <instructiuni> │└ panacand NOT <conditie> └■
REPETĂ … PÂNĂCÂND → CÂTTIMP
┌ repeta │ <instructiuni> └ panacand <conditie>
<instructiuni> ┌ cattimp NOT <conditie> executa │ <instructiuni> └■
Coada de priorități este o structură de date de tip coadă, în care se fac operații de inserare și eliminare, dar ordinea nu este cea a cozii obișnuite. Fiecare element are asociată o anumită prioritate (de exemplu chiar valoarea sa), iar elementul de la începutul cozii este cel cu prioritate maximă, el fiind și cel care va fi eliminat din coadă în cazul operației de eliminare a unui element.
Cozile de priorități pot fi implementate sub formă de heap-uri, iar STL contine containerul adaptor priority_queue. Tehnic priority_queue implementează în mod implicit un max-heap.
Operația de determinare a elementului maxim are complexitate constantă, in timp ce operațiile de inserare și eliminare au complexități logaritmice în raport cu numărul de elemente.
Clasa priority_queue este o clasă template definită în headerul queue:
#include <queue>
O putem declara ca în exemplul următor:
priority_queue<int> H;
Implicit, priority_queue-ul este un max-heap (elementul maxim are prioritate maximă) și se implementează pe baza operației < (less<int>)). Dacă dorim să gestionăm un min-heap (elementul minim să aibă prioritate maximă) vom folosi următoarea declarație:
priority_queue<int , vector<int> , greater<int> > H;
Similar, putem crea cozi de priorităti cu elemente de tipuri oarecare T. Condiția este să fie definit pentru tipul T operatorul < (functorul less<T>), sau să construim un functor de comparare.
struct fcmp
{ bool operator()(const T & a , const T & b)
{
//returneaza true daca si numai daca a este strict in fata lui b in ordinea dorita
}
};
priority_queue<T , vector<T> , fcmp > H;
Fie următoarea coadă de priorități:
priority_queue<T> H; T v;
priority_queue<T> H; T v; H.push(v);
Se adaugă în coadă elementul v. Elementele se reorganizează pentru se păstra proprietate de heap (elementul maxim să fie la început).
priority_queue<T> H; H.pop();
Se șterge din coadă elementul de la început. Elementele se reorganizează pentru se păstra proprietate de heap.
priority_queue<T> H; T v; v = H.top();
Returnează o referință la elementul de la începutul cozii. Elementul se va elimina numai la apelul metodei pop().
priority_queue<T> H; H.empty()
Returnează true dacă H este o coadă vidă și false în caz contrar.
priority_queue<T> H; H.size()
Returnează numărul de elemente din coada de priorități H.
Conținutul unei cozi de priorități poate fi copiat în altă coadă de același tip prin operatorul de atribuire =.
priority_queue<T> A , B; ... A = B;
Considerăm următoarea problemă;
Se dau coordonatele întregi ale unor puncte în plan. Să se afișeze coordonatele în ordinea crescătoare a absciselor, iar la abscise egale în ordinea crescătoare a ordonatelor.
Următoarele soluții se bazează pe o coadă de priorități în care adăugăm toate punctele, apoi le extragem și le afișăm.
Pentru memorarea unui punct folosim o structură (clasă) definită în mod adecvat. Pentru stabilirea ordinii între puncte folosim un functor, iar pentru afișarea coordonatelor folosim o funcție prietenă.
#include <iostream>
#include <queue>
using namespace std;
struct Punct{
int x , y;
Punct(int a = 0, int b = 0){ x = a , y = b;}
friend ostream & operator<<(ostream & os , Punct A)
{
os << "(" << A.x << "," << A.y << ")";
return os;
}
};
struct fcmp
{ bool operator()(const Punct & a , const Punct & b)
{
if(a.x > b.x)
return true;
if(a.x < b.x)
return false;
if(a.y > b.y)
return true;
return false;
}
};
int main()
{
priority_queue<Punct, vector<Punct>, fcmp> H;
H.push(Punct(6,1));
H.push(Punct(2,7));
H.push(Punct(2,4));
H.push(Punct(4,10));
H.push(Punct(7,4));
while(! H.empty())
cout << H.top() << '\n', H.pop();
return 0;
}
În acestă soluție nu folosim un functor pentru comparare, ci supraîncărcăm operatorul < printr-o functie prietenă.
#include <iostream>
#include <queue>
using namespace std;
struct Punct{
int x , y;
Punct(int a = 0, int b = 0){ x = a , y = b;}
friend ostream & operator<<(ostream & os , const Punct & A)
{
os << "(" << A.x << "," << A.y << ")";
return os;
}
friend bool operator<(const Punct & A , const Punct & B)
{
if(A.x > B.x)
return true;
if(A.x < B.x)
return false;
if(A.y > B.y)
return true;
return false;
}
};
int main()
{
priority_queue<Punct> H;
H.push(Punct(6,1));
H.push(Punct(2,7));
H.push(Punct(2,4));
H.push(Punct(4,10));
H.push(Punct(7,4));
while(! H.empty())
cout << H.top() << '\n', H.pop();
return 0;
}
Pentru memorare punctelor folosim clasa pair. Clasa pair are definit operatorul mai mic, acesta verificând ordinea lexicografică pentru membrii first și second.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue <
pair<int,int>,
vector<pair<int,int>>,
greater<pair<int,int>>
> H;
H.push({6,1});
H.push({2,7});
H.push({2,4});
H.push({4,10});
H.push({7,4});
while(! H.empty())
cout << "(" << H.top().first << "," << H.top().second << ")" << '\n', H.pop();
return 0;
}
Declararea de mai sus trebuie făcută în acest mod, pentru a obține un min-heap. Dacă am fi folosit declararea:
priority_queue <pair<int,int> > H;
s-ar fi implementat (pe baza functorului less<pair<int,int>>) un max-heap, în care elementele de prioritate maximă ar fi fost acela care au câmpul first mai mare.
bitset este un container special din STL care permite lucrul cu șiruri de biți. Aceștia sunt memorați eficient, pentru un bit din șir folosindu-se un bit în memorie. Astfel, spațiul de memorie ocupat de un bitset cu M biți este mai mic decât un tablou bool V[M]; sau un vector cu elemente de tip bool, dar numărul de biți M din bitset trebuie să fie cunoscut în momentul compilării, deci trebuie să fie o contantă.
Pot fi folosiți de exemplu pe post de vectori caracteristici, dar suportă și operațiile pe biți cunoscute pentru tipurile întregi.
Pentru a folosi containerul bitset trebuie inclus headerul bitset:
#include <bitset>
Declararea se face astfel:
const int M = 16; bitset<M> B = 30;
const int M = 16; bitset<M> B = 30; cout << B << endl;
Observații:
M este constantă. Lipsa modificatorului const duce la o eroare de compilare.M biți.Biții din bitset sunt indexați de la 0 și pot fi accesați prin operatorul []. Bitul cel mai nesemnificativ (cel mai din dreapta) este B[0], iar bitul cel mai semnificativ este B[M-1], unde M este dimensiunea bitsetului.
const int M = 16; bitset<M> B = 30; // 0000000000011110 B[6] = 1; cout << B; // 0000000001011110
Două containere bitset de aceeași dimensiune pot fi comparate cu operatorii == și !=.
Notă: operația != este eliminată în C++20.
Putem să-i atribuim unui bitset valoarea unui întreg sau valoarea unui alt bitset. Prin atribuirea unui întreg, biții din bitsetul B devin identici cu biții din reprezentarea în memorie a valorii întregi care se atribuie:
const int M = 16; bitset<M> B, A; B = -30; cout << B << endl; // 1111111111100010 B = 5; cout << B << endl; // 0000000000000101 A = B; cout << A << endl; // 0000000000000101
Pentru a afle câți biți din bitset sunt setați (au valoarea 1), folosim metoda count(). Pentru a determina numărul total de biți, folosim metoda size(). Numărul biților nesetați (cu valoarea 0), facem diferența celor două.
const int M = 16; bitset<M> B = 63; cout << B.count() << endl; // 6 cout << B.size() << endl; // 16
Se face cu metoda test(k), unde k reprezintă numărul de ordine al bitului dorit (de la dreapta spre stânga, incepând de la 0), iar rezultatul este 1 sau 0.
const int M = 16; bitset<M> B = 63; cout << B << endl; // 0000000000111111 cout << B.test(5) << endl; // 1 cout << B.test(6) << endl; // 0
Bitsetul oferă metode pentru:
B.set(k) dă valoarea 1 pentru B[k]B.set(k , r) dă valoarea r pentru B[k]B.set() dă valoarea 1 pentru toți biții din BB.reset(k) dă valoarea 0 pentru B[k]B.reset() dă valoarea 0 pentru toți biții din B1 devine 0, iar din 0 devine 1):
B.flip(k) schimbă valoarea lui B[k]B.flip() schimbă valorile pentru toți biții din Bbitset<M> B; B = 63; cout << B << endl; // 0000000000111111 //bitii se numeroteaza de la dreapta, incepand cu 0 B.reset(5); B.set(10); B.set(9 , 1); B.set(3 , 0); B.flip(2); cout << B << endl; // 0000011000010011 B.flip(); cout << B << endl; // 1111100111101100 B.set(); cout << B << endl; // 1111111111111111 B.reset(); cout << B << endl; // 0000000000000000
Clasa bitset suportă operatorii logici pe biți (~, &, |, ^).
bitset<M> B, A; B = -60; A = 5; cout << "A = " << A << endl; // 0000000000000101 cout << "B = " << B << endl; // 1111111111000100 cout << "~B = " << ~B << endl; // 0000000000111011 cout << "A & B = " << (A & B) << endl; // 0000000000000100 cout << "A | B = " << (A | B) << endl; // 1111111111000101 cout << "A ^ B = " << (A ^ B) << endl; // 1111111111000001
Clasa bitset suportă operatorii de deplasare a biților (<<, >>).
bitset<M> B; int n = 4; B = 7; cout << "B = " << B << endl; // 0000000000000111 cout << "B << n = " << (B << n) << endl; // 0000000001110000
Clasa bitset suportă atriburile scurte: &=, |=, ^=, precum și <<=, >>=.
Fie A , B două containere bitset de aceași dimensiune și n un întreg. Atunci:
A &= B este echivalent cu A = A & B;A |= B este echivalent cu A = A | B;A ^= B este echivalent cu A = A ^ B;A <<= n este echivalent cu A = A << n;A >>= n este echivalent cu A = A >> n;Bitset-ul poate fi convertit la
to_string
B.to_string() – returnează un string conținând reprezentarea binară a lui B, formată formată din caractere 0 și 1;B.to_string(c0) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 fiind înlocuite cu caracterul c0;B.to_string(c0 , c1) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 și 1 fiind înlocuite cu caracterul c0, respectiv c1;to_ulong(), to_uulong()
B.to_ulong() – retunează un întreg fără semn pe 32 de biți (unsingned int, unsigned long) cu reprezentarea binară echivalentă cu configurația bitsetului B;B.to_uulong() – retunează un întreg fără semn pe 64 de biți (unsigned long long) cu reprezentarea binară echivalentă cu configurația bitsetului B;overflow_error.Containerul C++ vector este, probabil, cel mai folosit container STL. Vectorii sunt tablouri dinamice cu elemente omogene care au proprietatea de a se redimensiona automat când se adaugă sau se șterge un element, gestionarea memoriei fiind realizată automat de către container.
Vectorii sunt stocați într-o zonă contiguă de memorie și pot fi traversați cu ajutorul iteratorilor. Elementele se adaugă, de regulă la sfârșit. Operația de adăugare ia, de regulă, timp constant, cu excepția cazului când spatiul de memorie alocat trebuie redimensionat (mărit). Ștergerea unui element ia întotdeauna timp constant. Inserarea și ștergerea la începutul sau în interiorul vectorului iau timp liniar.

Trebuie inclus header-ul vector:
#include <vector>;
Declararea se face astfel:
vector<T> V;
unde T este un tip de date. Acesta va fi tipul elementelor vectorului. Vectorul declarat mai sus este vid – are 0 elemente.
Alternativ, putem declara vectorul astfel:
vector<T> V(n);
n este un întreg. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt valorile implicite pentru datele de tip T. Pentru tipurile numerice, valoarea elementelor este 0.
vector<T> V(n, vT);
n este un întreg, iar vT este o dată de tip T. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt copii ale lui vT.
De exemplu:
vector<int> A; // se crează un vector A cu zero elemente cin >> n; vector<int> B(n); // se crează un vector B cu n elemente, egale cu 0 cin >> x; vector<int> C(n , x); // se crează un vector B cu n elemente, egale cu x
Spre deosebire de tablourile standard C, vectorilor li se pot atribui valori în orice moment. Exemplu:
vector<int> A , B = {2 , 4, 6 , 8};
A = B;
A = {1 , 2 , 3 , 4 , 5};
Numărul de elemente din vector poate fi determinat cu funcția size():
vector<int> A = {2 , 4 , 6 , 8};
cout << A.size(); // 4
De regulă, memoria alocată pentru un vector este mai mare decât memoria folosită. Acest lucru se întâmplă pentru a se evita realocarea memoriei (operație costisitoare, care presupune copierea tuturor elementelor) de fiecare dată când se adaugă elemente.
Funcția capacity() returnează numărul de elemnte pe care le poate avea vectorul la momentul curent, fără a se realoca memoria. Are loc relația capacity() >= size(), iar numărul de elemente care pot fi adăugate fără realocare este capacity() - size().
Funcția resize() permite redimensionarea unui vector și are următoarele forme:
V.resize(n); (1)V.resize(n , x); (2)Vectorul V se redimensionează încât să aibă n elemente:
n < V.size(), în vector vor rămâne primele n elemente, celelalte vor fi șterse.n > V.size(), în vector se vor adăuga n - V.size() elemente egale cu x , în cazul (2) sau egale cu valoarea implicită pentru tipul elementelor din vector, în cazul (1). Această valoare este 0 pentru tipurile numerice.Adăugarea unui nou element în vector se face la sfârșit, cu funcția push_back():
vector<int> A; for(int i = 1 ; i <= 5 ; i ++) A.push_back(2 * i); cout << A.size();
Elementele vectorilor pot fi accesate prin intermediul indicilor, cu operatorul []. Acesta nu verifică existență elementului cu un anumit indice, iar dacă acesta nu există, comportamentul programului este impredictibil.
vector<int> A; for(int i = 1 ; i <= 5 ; i ++) A.push_back(2 * i); for(int i = 0 ; i < A.size() ; i ++) cout << A[i] << ' '; // 0 2 4 6 8
De asemenea, este posibilă accesarea elementelor prin intermediul funcției at(). Aceasta returnează o referință la elementul de la poziția dată, iar dacă acesta nu există ridică o excepție care poate fi capturată prin mecanismul try … catch.
vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
for(auto x : A)
cout << x << " ";
Primul și ultimul element poate fi accesat prin intemediul funcțiilor front() și back(). Ele returnează referințe la primul, respectiv ultimul element al vectorului. Comportamentul este impredictibil dacă vectorul este vid.
vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
A.front() = 7; //A = {7 , 20 , 6 , 8 , 10}
A.back() = 5; //A = {7 , 20 , 6 , 8 , 5}
for(auto x : A)
cout << x << " ";
Iteratorii sunt similari cu pointerii. Cu ajutorul lor putem identifica adresa elementelor din vector. Iteratorii pot fi dereferențiați (obtinând referințe la elemente), pot fi incrementați/decrementați și pot fi adunați cu scalari.
Vectorii oferă prin intermediul funcției begin() un iterator la primul element al funcției, iar prin end() un iterator la elementul de după ultimul element al vectorului.
vector<int> A = {2 , 4 , 6 , 8 , 10};
vector<int>::iterator I;
for(I = A.begin() ; I < A.end() ; I ++)
cout << *I << " "; // 2 4 6 8 10
Observații:
*I;A.end() este un iterator, dar acestuia nu-i corespunde un element al vectorului. Valoarea sa este adresa de după ultimul element al vectorului.
Clasa vector conține și funcțiile rbegin() și rend(), care returnează iteratori de tip reverse iterator, care permit parcurgerea vectorului în ordien inversă:
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::reverse_iterator I = A.rbegin() ; I < A.rend() ; I ++)
cout << *I << " ";
Acești iteratori fac parte din categoria iteratorilor cu acces aleatoriu. Este cea mai puternică categorie de iteratori (cu cele mai multe operații definite). Aceste operații sunt:
| Expresie | Rezultat, efect |
|---|---|
*I |
Dereferențiere |
I->camp |
Acces la câmpurile structurii/membrii clasei memorate în elementele vectorului |
++I |
Preincrementare. Rezultatul este poziția următoare |
I++ |
Postincrementare. Rezultatul este poziția inițială |
--I |
Predecrementare. Rezultatul este poziția anterioară |
I-- |
Postdecrementare. Rezultatul este poziția inițială |
I == J |
Egalitate între doi iteratori |
I != J |
Neegalitate între doi iteratori |
<, >, <=, >= |
Operatori relaționali. Operanzii sunt iteratorii. Rezultatul este conform cu poziția în vector a elementelor adresate de cei doi iteratori |
I[k] |
Elementul de pe poziția k, începând de la I |
I += k |
k pași înainte |
I -= k |
k pași înapoi |
I + k |
iterator spre al k-lea element după cel curent |
I - k |
iterator spre al k-lea element înaintea celui curent |
I - J |
distanța în vector între iteratorii I și J |
O primă modalitate de parcurgere este folosind indicii, similar cu parcurgerea tablourilor standard C. Pentru determinarea numărului de elemnte există functia size():
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int i = 0 ; i < A.size(); i ++)
cout << A[i] << " ";
De asemenea, putem folosi iteratorii:
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::iterator I = A.begin() ; I < A.end() ; I ++)
cout << *I << " ";
Pentru ușurință, putem folosi specificatorul de tip auto pentru a stabili tipul iteratorului:
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(auto I = A.begin() ; I < A.end() ; I ++)
cout << *I << " ";
Începând de la versiunea 2011 a standardului C++ există o formă specială a instrucțiunii for, care permite parcurgerea elementelor unui container:
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int x : A)
cout << x << " ";
Specificatorul de tip auto poate fi folosit și aici. În secvența de mai sus, x reprezintă pe rând câte o copie a elementelor din A. Eventualele modificări ale lui x nu vor modifica valorile elementelor din A. Dacă se dorește modificare elemenelor din A, atunci x trebuie să fie o referință:
vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int & x : A)
x *= 2;
for(int x : A)
cout << x << " ";
Vectorii suportă iteratori reversibili, care permit parcurgerea containerului în ordine inversă. Clasa vector are metodele:
rbegin() – returnează un iterator reversibil la ultimul element din containerrend() – returnează un iterator reversibil la elementul din fața primuluiParcurgerea se poate face astfel:
for(vector<int>::reverse_iterator I = V.rbegin() ; I < V.rend() ; I ++) cout << *I << " ";
Pentru adăugarea la sfârșit se folosește metoda push_back(). Pentru inserarea de noi elemente în interiorul containerului se folosește metoda insert(), care are mai multe forme:
V.insert(pos , x) – inserează în vectorul V, în fața iteratorului pos un nou element cu valoarea x;V.insert(pos , cnt , x) inserează în vectorul V, în fața iteratorului pos, cnt noi elemente egale cu x;V.insert(pos , st , dr) inserează în vectorul V, în fața iteratorului pos, dr-st noi elemente, având valorile egale cu cele ale elementelor din secvența [st, dr) dintr-un container oarecare. Dacă vectorul V și secvența [st,dr) se suprapun rezultatul este impredictibil.Rezultatul apelurilor de mai sus este un iterator la primul element inserat.
Apelurile de mai sus invalidează toți iteratorii și referințele la elemente din V, dacă în urma inserării se realocă memorie, respectiv se invalidează iteratorii și referințele din dreapta lui pos, în caz contrar.
Mai multe detalii despre insert() aici: https://en.cppreference.com/w/cpp/container/vector/insert.
Pentru eliminarea tuturor elementelor intr-un vector există metoda clear().
V.clear();
În urma eliminării, rezultatul lui V.size() este 0.
Pentru eliminarea ultimului element al tabloului există metoda pop_back(). În urma apelului se invalidează iteratorii și referințele la ultimul element, precum și iteratorul end().
Pentru eliminarea unor elemente oarecare se folosește metoda erase(), cu următoarele forme:
V.erase(pos) – elimină elementul indicat de iteratorul pos. pos nu poate fi egal cu end()V.erase(st , dr) – elimină elementele din intervalul [st,dr), unde st și dr sunt iteratori la elemente din VRezultatul funcției erase() este un iterator la elementul de după ultimul element eliminat.
Se invalidează iteratorii și iteratorii din dreapta lui posm inclusiv iteratorul end().
Mai multe detalii aici: https://en.cppreference.com/w/cpp/container/vector/erase.