Articolele lui Candale Silviu (silviu)

La concursul Mate Info UBB, ediția 2021 a fost dat următorul exercițiu:

Fie \(b_nb_{n-1}…b_0\) reprezentarea binară a numărului natural \(B\), \(2021 ≤ B ≤ 2021^{2021}\). Care dintre următoarele afirmații sunt adevărate?

A. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este zero, atunci \(B\) este divizibil cu \(3\)
B. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\), atunci \(B\) este divizibil cu \(3\)
C. \(B\) este divizibil cu \(3\) dacă suma cifrelor binare este divizibilă cu \(3\), dar nu cu \(9\)
D. Dacă \(B\) este divizibil cu \(3\), atunci valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\)

Răspunsul corect este: A, B, D.

Varianta C. se elimină imediat, deoarece reprezentarea binară a lui 3 este 11, iar suma cifrelor binare este 2, nedivizibil cu 3.

Pentru a demonstra că afirmațiile A., B. și D. sunt adevărate vom demonstra următoarea afirmație, mai generală.

Teoremă: Fie \(N\) un număr natural a cărui reprezentare în baza \(B\) este \(b_nb_{n-1}…b_0\). Numărul \(N\) este divizibil cu \(B+1\) dacă și numai dacă expresia \(E = b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă \(B+1\).

Pentru a demonstra teorema de mai sus, vom demonstra mai întâi următoarea lemă:

Lemă: Fie \(P\) un număr natural. Atunci \(P^{2k}\) este de forma \(X \cdot (P+1)+1\), iar \(P^{2k+1}\) este de forma \(Y \cdot (P+1)-1\)

Demonstrația lemei se face prin inducție. Mai întâi să observăm că \(P^{0} = 1 = 0 \cdot (P+1) + 1\), iar \(P^{1} = P = 1 \cdot (P+1) – 1\).

Dacă \(P^{2k} = X \cdot (P+1)+1\), atunci \(P^{2k+1} = P \cdot P^{2p} \\= P \cdot (X \cdot (P+1)+1) \\= P \cdot X \cdot (P+1)+P \\= P \cdot X \cdot (P+1)+P + 1 – 1 \\= (P \cdot X+1)\cdot(P+1)-1 \\= Y \cdot (P+1) -1\)

Similar, dacă \(P^{2k+1} = Y \cdot (P+1)-1\), atunci \(P^{2k+2} = P \cdot P^{2k+1} \\= P \cdot (Y \cdot (P+1) -1) \\= P \cdot Y \cdot (P + 1) – P \\= P \cdot Y \cdot (P + 1) – P – 1 + 1 \\= P \cdot Y \cdot (P + 1) – (P + 1) + 1 \\= (P \cdot Y -1) \cdot (P + 1) + 1 \\= X \cdot (P+1) + 1\)

Demonstrația teoremei Dacă \(b_nb_{n-1}…b_0\) este reprezentarea în baza \(B\) a lui \(N\), atunci

$$N=b_0 \cdot B^0 + b_1 \cdot B^1 + b_2 \cdot B^2 + b_3 \cdot B^3 + … + b_n \cdot B^n$$

Deoarece puterile lui \(B\) sunt de forma precizată în lemă, obținem:

$$\begin{aligned} N &= b_0 \cdot ((B+1) \cdot f_0 + 1) + b_1 \cdot ((B+1) \cdot f_1 – 1) + b_2 \cdot ((B+1) \cdot f_2 + 1) + b_3 \cdot ((B+1) \cdot f_3 – 1) + \cdots + b_n \cdot ((B+1) \cdot f_n + (-1)^n) \\
& = ((B+1) \cdot b_0 \cdot f_0 + b_0) + ((B+1) \cdot b_1 \cdot f_1 – b_1) + ((B+1) \cdot b_2 \cdot f_2 + b_2) + ((B+1) \cdot b_3 \cdot f_3 – b_3) + \cdots + ((B+1) \cdot b_n \cdot f_n + (-1)^n \cdot b_n)\\
& = (B+1) \cdot b_0 \cdot f_0 + (B+1) \cdot b_1 \cdot f_1 + (B+1) \cdot b_2 \cdot f_2 + (B+1) \cdot b_3 \cdot f_3 + \cdots + (B+1) \cdot b_n \cdot f_n + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot ( b_0 \cdot f_0 + \cdot f_1 + b_2 \cdot f_2 + \cdot b_3 \cdot f_3 + \cdots + \cdot b_n \cdot f_n) + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot M + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
\end{aligned}$$

Deoarece \((B+1) \cdot M\) este divizibil cu \(B+1\), deducem că \(N\) este divizibil cu \(B+1\) dacă și numai dacă \(b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\) este divizibil cu \(B+1\)!

Observații:

Exercițiul de mai sus este un caz particular al teoremei, în care \(B = 2\).

Expresia \(E\) poate fi scrisă și \(E = (b_0 + b_2 + …) – (b_1 + b_3 + …)\) – diferența dintre suma cifrelor de rang par și suma cifrelor de rang impar. Dacă \(B=10\), proprietatea de mai sus este “Criteriul de divizibilitate cu 11”.

Acest articol conține o listă cu subiecte date la examenul de bacalaureat, clasificate în funcție de problema ce presupune analiza algoritmilor pseudocod. Lista poate fi filtrată după an, categoria problemei și tipul structurii repetitive utilizate.

Citiți mai întâi Generarea aranjamentelor!

Introducere

Consideram o mulțime cu A cu n elemente. Prin combinări de k elemente din A înțelegem submulțimile cu k elemente ale multimii A. Numărul acestor combinări este \(C_n^k = \frac{A_n^k}{P_k}\). Mai multe formule pentru calculul numărului de combinări pot fi găsite în acest articol.

Acest articol prezintă un algoritm backtracking pentru determinarea în ordine lexicografică a combinărilor de k elemente ale mulțimii A={1 , 2 , ... , n}, elemente dintr-o combinare fiind generate în ordine crescătoare. El poate fi adaptat pentru determinarea combinărilor de k elemente ale unei mulțimi oarecare de n elemente.

Deoarece în algoritmul recursiv general apare funcția Back() cu parametrul k, pentru a păstra notațiile din algoritm vom considera în continuare combinările de k elemente luate câte p.

Soluția 1

Condiții

Ca orice rezolvare cu algoritmul backtracking, începem prin a preciza semnificația vectorului soluție. Astfel, x[] reprezintă o combinare. În consecință, el va respecta următoarele condiții:

• elemenele vectorului sunt valori între 1 și n;
• elementele nu se repetă;
• elementele sunt ordonate crescător
• vectorul se completează element cu element. Când va avea p elemente, reprezintă o combinare completă, care urmează a fi afișată.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne:
  • \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
  • \(x[k] > x[k-1]\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Observăm (din nou) că în verificarea condițiilor interne intervine doar elementul x[k] (cel care este verificat) și elementele deja generate (x[1], x[2], … , x[k-1]).

Observăm că aceste condiții sunt cele de la generarea aranjamentelor, la care se adaugă condiția internă legată de ordinea elementelor din vector. În consecință, programul va fi cel de la aranjamente, cu completarea funcției OK().

Sursa C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    if(k > 1)
		if(x[k] <= x[k-1])
			return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    back(1);
    return 0;
}

Soluția 2

Rafinarea condițiilor

Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:

1. cele două condiții interne pot fi reduse la una singură. Dacă pentru fiecare \( k \) are loc relația \(x[k] > x[k-1]\) atunci are loc și condiția \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\);
   Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
   • condiții interne: \(x[k] > x[k-1]\), pentru \( k > 1 \)
   • condiții de existență a soluției: \(k = p\)
2. condiția internă poate fi transformată în condiție externă. Dacă \(x[k] > x[k-1]\) atunci valorile pe care le poate lua \(x[k]\) (condiții externe) sunt \( \left\{ x[k-1] + 1, \ldots, n \right\} \). Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ x[k-1] +1 , x[k-1] +2, \ldots, n \right\} \);
   • condiții interne: nu există
   • condiții de existență a soluției: \(k = p\)

Cazul \(k = 1\) este unul special. Valorile pe care le poate lua sunt \(\left\{ 1 , 2 , 3 , \ldots \right\} \). Pentru a fi condițiile externe de mai sus corecte în în acest caz, este necesară inițializarea x[ 0 ] = 0, înaintea începerii generării.

Sursă C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

void back(int k){
    for(int i = x[k-1] + 1 ; i <= n ; ++ i)
    {
        x[k] = i;
		if(k == p)
			Afis(k);
		else
			back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    x[0] = 0;
    back(1);
    return 0;
}

Probleme

combinari combinari2 siruri SubmDiv cifre_c subimp2

Citește și

• Prezentare generală
• Generarea permutărilor
• Generarea aranjamentelor

• Generarea submulțimilor

Citiți mai întâi Generarea permutărilor!

Introducere

Considerăm o mulțime cu n elemente. Prin aranjamente de k elemente din acea mulțime înțelegem șirurile de k elemente din ea. Două șiruri diferă prin valorile elementelor sau prin ordinea acestora.

Numărul acestor șiruri este aranjamente de n luate câte k, adică \(A_n^k = n \cdot (n-1) \cdot \ldots \cdot(n – k +1) \).

Acest articol prezintă algoritmul de generare în ordine lexicografică a aranjamentelor de k elemente ale mulțimii {1, 2, ..., n}. El poate fi ușor modificat pentru a genera aranjamentele unei mulțimi cu elemente oarecare.

Metoda folosită va fi backtracking, varianta recursivă. Deoarece în algoritmul de generare folosit intervine variabila k, ca parametru al funcției Back(), vom considera în continuare aranjamentele de n elemente luate câte p.

Exemplu

Pentru n = 4 și p = 3 vom avea 4 * 3 * 2 = 24 de aranajamente. Lista completă a acestora este:

1 2 3		2 1 3		3 1 2		4 1 2
1 2 4		2 1 4		3 1 4		4 1 3
1 3 2		2 3 1		3 2 1		4 2 1
1 3 4		2 3 4		3 2 4		4 2 3
1 4 2		2 4 1		3 4 1		4 3 1
1 4 3		2 4 3		3 4 2		4 3 2

Condiții

În rezolvarea problemei intervine vectorul soluție, x[]. Acesta reprezintă un aranjament candidat, care va deveni la un moment dat un aranjament de p elemente complet. Proprietățile vectorului soluție sunt cele specifice aranjamentelor:

• elementele sunt din mulțimea dată, adică numere intre 1 și n;
• elementele nu se repetă;
• vectorul se completează element cu element. Când va avea p elemente, reprezintă un aranjament complet, care urmează a fi afișat.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne: \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Sursă C++

Următorul program afișează pe ecran aranjamantele de n alemente luate câte p, în ordine lexicografică, folosind un algoritm recursiv:

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void Back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                Back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    Back(1);
    return 0;
}

Se poate observa că atât condițiile descrise mai sus, cât și algoritmul de generare sunt foarte asemănătoare cu cele de la generarea permutărilor.

Acest lucru se datorează faptului că, la ambele probleme, vectorii soluție identici în ceea ce privește conținutul: șiruri de elemente diferite cuprinse între 1 și n. Diferă numai lungimea lor – momentul când vectorul soluție x[] conține o soluție completă:

• la problema permutărilor un vector soluție final are n elemente (toate elementele mulțimii date, într-o anumită ordine);
• la problema aranjamentelor un vector soluție final are p elemente (p elemente dintre cele n ale mulțimii date, într-o anumită ordine).

La fel ca în cazul generării permutărilor, și pentru această problemă se pot scrie soluții iterative, precum și soluții în care verificarea condițiilor interne să se facă cu un vector caracteristic, evitându-se parcurgerile repetate ale vectorului soluție.

Probleme propuse

196 3159

Citește și

• Prezentare generală
• Generarea permutărilor

• Generarea combinărilor
• Generarea submulțimilor

Tipul char este folosit pentru lucrul cu caractere. O dată de acest tip va reprezenta un singur caracter. Pentru a stoca mai multe caractere vom folosi un tablou cu elemente char sau un string.

Variabile de tip char

O variabilă de tip char se declară astfel:

char C;

Valoarea unei variabile de tip char (sau signed char) este un număr natural cuprins între -128 și 127. Valorile cuprinse între 0 și 127 corespund caracterelor din codul ASCII.

Similar, datele de tip unsigned char au valori între 0 și 255. Observăm că ambele tipuri conțin valorile care corespund caracterelor din codul ASCII.

Literali

Un literal (valoare) de tip char este un caracter din codul ASCII, delimitat de caractere apostrof ‘.

Putem inițializa o variabilă de tip char atribuindu-i un literal de tip char sau o valoare numerică. Dacă valoarea numerică nu aparține intervalului de valori corespunzător, aceasta va fi trunchiată.

char C;
C = 'A';
C = 65;

Atenție! “ – ghilimele delimitează șiruri de caractere. Un șir de caractere format dintr-un singur caracter nu este același lucru cu un caracter.
“A” ≠ ‘A’!

Afișarea și citirea

Deși datele de tip char memorează numere întregi, la citirea și afișarea lor se va lucra cu caractere.

Afișarea

char C = 'A';
cout << C; // A
C = 65;
cout << C; // A

Afișarea unei date de tip char se face astfel:

• dacă valoarea este din codul ASCII, se va afișa caracterul corespunzător. Pentru caracterele neimprimabile efectul depinde de caracter și de mediul în care se lucrează (este posibil să nu se afișeze nimic sau să se afișeze diverse simboluri).
• dacă valoarea este din afara codului ASCII, efectul depinde de mediul în care se lucrează.

Citirea

char C;
cin >> C;
...

În urma citirii de la tastatură unei variabile de tip char, aceasta va reprezenta caracterul introdus. Dacă se introduc mai multe caractere, se va citi doar primul dintre ele.

Exemple

char x;
cin >> x; // introducem A
cout << x; // A

char x;
cin >> x; // introducem 145
cout << x; // 1

char x, y;
cin >> x >> y; // introducem A B
cout << x << endl; // A 
cout << y << endl; // B	

char x, y;
cin >> x >> y; // introducem AB
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem ABC
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem 65 66
cout << x << endl; // 6
cout << y << endl; // 5

Operații. Conversii de tip

Valorile de tip char pot fi convertite la alte tipuri.

char x;
x = 65; // conversie implicită de la int la char
cout << x; // A
cout << (int) x; // 65
int n = 65;
cout << (char) n; //A

Cu datele de tip char se pot face toate operațiile uzuale cu numere. Valoarea de tip char va fi convertită implicit la int, apoi se vor face operațiile.

char x = 'A';
cout << x + 1; // 66
cout << (char)(x + 1); // B

char x = 'A';
x ++;
cout << x; // B

Transformarea între litere mari și mici

O problemă frecventă este determinarea, pentru o literă mare, a literei mici corespunzătoare, sau invers. Rezolvarea se bazează pe faptul că, în codul ASCII, literele mari sunt poziționate înaintea celor mici, iar diferența dintre codul ASCII a unei litere mici și codul ASCII a literei mari corespunzătoare este aceeași pentru toate literele (32).

Transformarea se va face scăzând această valoare din litera mică, sau adunând-o la litere mare:

int dif = 'a' - 'A'; // 32
char x = 'k';
x = x - dif;
cout << x; // K

C++ ne permite să considerăm o valoare de un anumit tip da fiind de alt tip. Aceasta se numește conversie de tip.

În C++ sunt două feluri de conversii de tip:

• conversia implicită
• conversia explicită

Conversia implicită

Conversia implicită intervine de la sine când într-o operație avem operanzi de tipuri diferite. Compilatorul consideră automat ambele date de același tip pentru a putea efectua operația.

Conversia implicită se face doar dacă operanzii sunt de tipuri compatibile – vezi mai jos o listă de compatibilități pentru tipurile numerice. Dacă tipurile nu sunt compatibile obținem eroare de sintaxă!

Exemple

Conversie de la int la double

#include <iostream>
using namespace std;

int main()
{
    int n = 5;
    double x;

    /// conversie de la int la double
    x = n;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5

Conversie de la double la int

#include <iostream>
using namespace std;

int main()
{
    int n;
    double x = 5.75;

    /// conversie de la double la int

    n = x;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5.75

Deoarece o dată de tip int memorează numere întregi, în timpul conversiei zecimalele valorii lui x s-au pierdut.

Pierderea de date în timpul conversiei

Așa cum am văzut în exemplul anterior, conversia de tip poate duce la pierderea (trunchierea) unor date. Acest lucru nu este neapărat rău, dar trebuie să fim conștienți de această situație.

În fapt, conversia este de două feluri:

• promovare – conversie de la un tip de date inferior la unul superior; nu produce pierdere de date!
• retrogradare – conversie de la un tip de date superior la unul inferior; poate produce pierdere de date!

În primul exemplu de mai sus a avut loc o promovare de la int la double, iar în al doilea exemplu a avut loc o retrogradare de la double la int. Cea de-a doua a condus la pierderea unor date.

În situațiile în care este posibil, compilatorul realizează conversiile implicite prin promovare.

De exemplu, rezultatul expresiei 2 + 1.5 va fi 3.5, nu 3. Are loc promovarea valorii 2 la tipul double, nu retrogradarea lui 1.5 la int, ceea ce ar fi însemnat pierderi de date!

Conversia explicită

Conversia explicită a datelor înseamnă modificarea manuală, de către programator, a tipurilor de date folosite într-o expresie. Se mai numește și type casting.

Operatorul de conversie explicită

Are sintaxa:

(TIP) expresie

sau

TIP(expresie)

Observații

• este un operator unar;
• are prioritate mare;
• rezultatul său este rezultatul expresiei, considerat de tipul de date TIP;
• în varianta a doua TIP trebuie să fie un nume de tip format dintr-un singur cuvânt. Astfel, expresia unsigned int(expresie) este greșită.

Exemplu

char c='A';
cout << (int) c << endl; // 65
cout << char(97) << endl; // a

Notă: Limbajul C++ oferă și următorii operatori de conversie: static_cast, dynamic_cast, const_cast și reinterpret_cast.

Câteva reguli privind conversia

• dacă se convertește un întreg negativ la un tip fără semn rezultatul va fi complementul în baza 2 a valorii inițiale, datorită modului de reprezentare a valorilor întregi. Astfel, -1 devine cea mai mare valoare a tipului fără semn, -2 devine a doua cea mai mare valoare, etc.
• la conversia unei valori numerice la tiplul bool rezultatul va fi:
  • true, dacă valoarea inițială este nenulă;
  • false, dacă valoarea inițială este 0;
• la conversia unei valori de tip float, double la un tip întreg, valoare se va trunchia, pierzându-se partea zecimală. Dacă rezultatul nu se încadrează în limitele tipului întreg, comportamentul programului devine impredictibil.

Regulile de mai sus se aplică atât pentru conversia implicită, cât și pentru cea explicită.

Exemplu: media aritmetică

Să presupunem că dorim să determinăm media aritmetică trei numere întregi. Desigur, răspunsul este suma numerelor împărțită la 3, dar trebuie ținut cont de faptul că împărțirea a doi întregi este câtul împărțirii. Pentru a obține media corectă va trebui să facem anumite conversii.

Exemplu 1 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
/// cout << S / 3; // gresit - impartire intreaga
cout << S / 3.0;

A avut loc conversia implicită a lui S la double (promovare).

Exemplu 2 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << 1.0 * S / 3;

A avut loc conversia implicită a lui S, apoi a lui 3, la double (promovări).

Exemplu 3 – conversie explicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << (double)S / 3;

Mai întâi se convertește explicit valoarea lui S la double, apoi are loc conversia implicită la double a lui 3.

Evitarea depășirii de tip

În numeroase situații avem operații cu date de tip int, dar rezultatul depășește limita maximă (sau minimă) a acestui tip. Astfel se produce depășirea de tip – overflow. Soluția este utilizarea unor conversii prin care operațiile se realizează într-un tip de date mai larg, de exemplu long long.

Exemplu:

int n = 1000000;
cout << n * n << endl; /// posibil -727379968 - overflow
cout << 1LL * n * n << endl; /// corect 1000000000000
cout << (long long) n * n << endl; /// corect

La realizarea conversiilor trebuie ținut cont de precedența operatorilor. De exemplu, secvența de mai jos nu obține rezultatul corect.

int n = 1000000;
cout << 1LL * n + n * n << endl;
cout << (long long)n + n * n << endl;

Mai multe detalii despre conversii sunt diponibile aici: en.cppreference.com/w/cpp/language/implicit_conversion.

Definiție

Operatorul condițional este singurul operator ternar (cu trei operanzi) din C++. Sintaxa lui este:

ExpresieConditionala ? Expresie1 : Expresie2

și se evaluează astfel:

• se evaluează ExpresieConditionala. Rezultatul său va fi convertit implicit la bool.
• dacă rezultatul lui ExpresieConditionala este true, se evaluează Expresie1 și rezultatul său va fi rezultatul operației ?
• dacă rezultatul lui ExpresieConditionala este false, se evaluează Expresie2 și rezultatul său va fi rezultatul operației ?

Expresie2 și Expresie3 trebuie să aibă rezultate de același tip, sau de tipuri compatibile.

Exemplu

int x;
cin >> x;
cout << (x % 2 == 0? "par" : "impar");

Observații

• Operatorul ? poate fi înlocuit cu instrucțiunea if. Secvența de mai sus poate fi rescrisă astfel:
  

  int x;
  
  cin >> x;
  
  if (x % 2 == 0)
  	cout << “par”;
  
  else
  	cout << “impar”;

• Operațiile condiționale pot fi imbricate:
  

  cout << (x > 0? “pozitiv” : x == 0 ? “nul” : “negativ”);

• Rezultatele celor două expresii care reprezintă rezultatele posibile trebuie să fie de același tip sau de tipuri compatibile. Următoarea secvență nu este corectă;
  

  int x;
  
  cin >> x;
  
  cout << (x == 1? 1 : “diferit de 1”); // error: operands to ?: have different types ‘int’ and ‘const char*’

• Dacă expresiile Expresie1 și Expresie2 sunt de tip lvalue (de exemplu, variabile), rezultatul operației este chiar data corespunzătoare, nu valoarea ei, care poate fi apoi supusă unei atribuiri:
  

  int x = 1, y = 2, a = 10;
  
  ((a % 2 == 0) ? x : y) = 5;
  
  cout << x << “ “ << y << endl; // 5 2

Cea mai fecventă eroare este să uităm prioritatea operatorilor. Operatorul condițional are prioritate scăzută și este probabil să facem diverse erori!

În general, incrementarea unei date înseamnă mărirea valorii sale, de obicei cu 1, iar decrementarea unei date înseamnă micșorarea valorii sale.

Aceste operații sunt foarte frecvente. De aceea, numeroase limbaje de programare (inclusiv C/C++, Java, Javascript, C#, PHP) pun la dispoziția programatorilor operatori care fac tocmai acest lucru.

Operatorul de incrementare este ++, iar cel de decrementare este --. Sunt operatori unari și se pot aplica doar datelor (variabile sau operații care au rezultat de tip lvalue – element de tablou, câmp al unei structuri, etc.).

Operatorii de incrementare/decrementare nu se pot aplica pentru constante sau pentru operații care au ca rezultat valori (operații aritmetice, comparații, etc.).

De regulă, operatorii unari sunt prefixați (sunt plasați înaintea operandului, de exemplu - x). Operatorii de incrementare și decrementare pot fi atât prefixați ( se scriu înaintea operandului), cât și postfixați (se scriu după operand). Efectul lor este același (incrementarea/decrementarea operandului), dar rezultatul diferă.

Incrementarea

Operația de incrementare a variabilei X poate fi:

• postincrementare: X ++. Efectul expresiei este mărirea valorii lui X cu 1, iar rezultatul operației este valoarea inițială a lui X.
• preincrementare: ++ X. Efectul expresiei este mărirea valorii lui X cu 1, iar rezultatul operației este chiar variabila X (cu valoarea mărită, bineînțeles).

Exemplu postincrementare

int x = 5 , y = 10;
y = x ++; // y primeste valoare lui (x++), adica valoarea initiala a lui x
cout << x << " " << y; // 6 5

Exemplu preincrementare

int x = 5 , y = 10;
y = ++ x; // y primeste valoare lui (++x), adica valoarea marita a lui x
cout << x << " " << y; // 6 6

Observații

• preincrementarea are ca rezultat variabila (data) asupra căreia se aplică operația. În consecință, rezultatul poate fi folosit în orice context se poate folosi o lvalue – de exemplu i se poate aplica din nou operatorul de incrementare sau cel de decrementare.
• postincrementarea are ca rezultat o valoare – valoarea inițială a variabilei. Rezultatul postincrementării poate fi folosit doar în expresiile unde intervin valori.

Exemple:

int x = 5 , y = 10;
y = (++ x) ++; // x devine 7, y devine 6
cout << x << " " << y;

int x = 5 , y = 10;
y = ++ (x ++); // eroare, rezultatul lui x ++ nu este lvalue
cout << x << " " << y;

int x = 5 , y = 10;
y =  ++ ++ x; // x devine 7, y devine y
cout << x << " " << y;

Postincrementarea are prioritate mai mare decât preincrementarea (vezi aici prioritatea operatorilor). Din acest motiv următoarea secvență este greșită sintactic.

int x = 5 , y = 10;
y = ++ x ++; // eroare; prioritate are x ++, dar rezultatul sau nu este lvalue
cout << x << " " << y;

Decrementarea

Decrementarea respectă toate proprietățile incrementării, cu observația că valoarea datei asupra căreia se aplică se va micșora cu 1.

Operația de decrementare a variabilei X poate fi:

• postdecrementare: X --. Efectul expresiei este micșorarea valorii lui X cu 1, iar rezultatul operației este valoarea inițială a lui X.
• predecrementare: -- X. Efectul expresiei este micșorarea valorii lui X cu 1, iar rezultatul operației este chiar variabila X.

Înlănțuire

Înlănțuirea metodelor (method chaining) este un stil de programare ce poate fi utilizat în contextul programării orientate pe obiecte. Constă în faptul că metodele vor avea ca rezultat obiecte. În acest mod apelurile metodelor pot fi înlănțuite într-o singură instrucțiune, evitând declararea unor variabile care să stocheze rezultate intermediare.

Cascadarea

O situație particulară este cascadarea metodelor. Constă în faptul că metodele returnează tocmai obiectul curent (instanța curentă). Astfel apelurile lor sunt înlănțuite, făcând programul ușor de înțeles și evitând “efortul” necesar pentru alegerea unor nume pentru variabile.

Cascadarea metodelor este posibilă în C++ datorită pointerului this – pointer la obiectul curent. Pentru a realiza cascadarea trebuie îndeplinite următoarele:

• tiplul metodei este referință la clasa curentă;
• metoda returnează obiectul curent prin dereferențierea pointerului this, adică * this.

Exemple

Operatorul <<

Un exemplu C++ binecunoscut este operatorul de inserție în flux <<, care are ca rezultat obiectul din stânga. Acest fapt permite scrie unei instrucțiuni de forma:

cout << a << " " << b;

Ea este echivalentă cu următoarea secvență:

cout << a;
cout << " ";
cout << b;

sum00

Programul de mai jos este o rezolvare pentru problema #sum00 (suma a două numere):

#include <iostream>

using namespace std;

class T{
    private:
        int a , b;
    public:
        T & Citire(){
            cin >> a >> b;
            return * this;
        }
        T & Suma(){
            cout << a + b;
            return * this;
        }
};

int main()
{
    T().Citire().Suma();
    return 0;
}

Cascadare vs. înlănțuire

Considerăm următoarele două clase:

class A{
    private:
        int n;
    public:
        A & Citire(){
            cin >> n;
            return * this;
        }
        A & Afisare(){
            cout << n << endl;
            return * this;
        }

        A & Dublare(){
            n *= 2;
            return * this;
        }
};

class B{
    private:
        int n;
    public:
        B Citire(){
            cin >> n;
            return * this;
        }
        B Afisare(){
            cout << n << endl;
            return * this;
        }

        B Dublare(){
            n *= 2;
            return * this;
        }
};

Ele diferă doar prin faptul că metodele clasei A returnează însuși obiectul curent, în timp ce metodele clasei B returnează o copie a obiectului curent.

Următoarele două secvențe vor afișa același lucru, deși mecanismele sunt diferite:

A().Citire().Dublare().Afisare();

B().Citire().Dublare().Afisare();

Diferențele sunt vizibile în următoarele exemple:

A x;
x.Citire().Dublare();
x.Afisare();

B y;
y.Citire().Dublare();
y.Afisare();

Generalități

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.

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

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:

• clasa Caine este derivată din clasa Animal;
• obiectul C este de tip Caine, obiectul A este de tip Animal; ambele sunt obiecte statice;
• metoda vorbeste() este disponibilă în ambele clase, fiind suprascrisă în clasa derivată
• putem accesa corespunzător pentru fiecare obiect propria metoda vorbeste()
• pentru obiectul derivat putem accesa metoda clasei de bază folosind operatorul de rezoluție: 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).

Suprascrierea în cazul pointerilor

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ă:

• pointerul la clasa derivată (q) poate memora doar adresa unui obiect al acesteia;
• pointerul la clasa de bază (p) poate memora atât adresa unui obiect al clasei de bază, cât și adresa unui obiect al clasei derivate;
• chiar dacă pointerul memoreaza adresa unui obiect al clasei derivată, prin acel pointer se accesează metode ale clasei de bază!

Funcții virtuale

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ă;
• se apelează metoda corespunzătoare clasei din care face parte obiectul referit de pointer!