Recapitulare completă (orele 9-16)

Ora 9: Extragerea cifrelor unui număr

Cele două operații fundamentale

Definiție: Orice număr natural poate fi descompus cifră cu cifră folosind două operații:

n % 10 — extrage ultima cifră (cifra unităților)
n / 10 — elimină ultima cifră (împărțire întreagă)

Algoritmul de extragere a cifrelor

Extragerea tuturor cifrelor

while (n > 0) {
    int cifra = n % 10;   // extrage ultima cifră
    cout << cifra << " ";
    n = n / 10;            // elimină ultima cifră
}

Exemplu pas cu pas: n = 1234

Tracing pentru 1234

Pas	n	n % 10 (cifra)	n / 10 (noul n)
1	1234	4	123
2	123	3	12
3	12	2	1
4	1	1	0 → STOP

⚠️ Atenție: Cifrele sunt extrase în ordine inversă (de la dreapta la stânga): 4, 3, 2, 1.

Caz special: Dacă n = 0, bucla while (n > 0) nu se execută niciodată. Trebuie tratat separat dacă vrem să afișăm cifra 0.

Exerciții — Ora 9

Completează: Operatorul care extrage ultima cifră a unui număr este _______.
% 10 (modulo 10)
Completează: Operatorul care elimină ultima cifră a unui număr este _______.
/ 10 (împărțire întreagă la 10)
Adevărat sau Fals? Cifrele unui număr sunt extrase de la stânga la dreapta.
Fals — sunt extrase de la dreapta la stânga (inversă).
Ce afișează? 5207 % 10
7 — ultima cifră a lui 5207.
Ce rezultă? 5207 / 10
520 — se elimină ultima cifră.

Ora 10: Suma și produsul cifrelor

Suma cifrelor

Algoritm: Pornim cu suma = 0 (elementul neutru al adunării) și adăugăm fiecare cifră pe rând.

Suma cifrelor unui număr

int suma = 0;
while (n > 0) {
    suma += n % 10;
    n /= 10;
}
// Exemplu: 1234 → 1+2+3+4 = 10

Produsul cifrelor

Algoritm: Pornim cu produs = 1 (elementul neutru al înmulțirii) și înmulțim cu fiecare cifră.

Produsul cifrelor unui număr

int produs = 1;
while (n > 0) {
    produs *= n % 10;
    n /= 10;
}
// Exemplu: 1234 → 1×2×3×4 = 24

⚠️ Regula de aur: Suma începe cu 0, produsul începe cu 1. Dacă inițializezi produsul cu 0, rezultatul va fi mereu 0!

Suma cifrelor pare / impare

Suma selectivă a cifrelor

int sumaPare = 0, sumaImpare = 0;
while (n > 0) {
    int cifra = n % 10;
    if (cifra % 2 == 0) sumaPare += cifra;
    else sumaImpare += cifra;
    n /= 10;
}

Atenție la cifra 0: Dacă un număr conține cifra 0 (ex: 205), produsul cifrelor devine 0 (2×0×5 = 0), dar suma nu este afectată semnificativ (2+0+5 = 7).

Exerciții — Ora 10

Completează: Variabila suma se inițializează cu _______, iar produs cu _______.
0 (suma) și 1 (produs).
Calculează: Suma cifrelor lui 4073.
4 + 0 + 7 + 3 = 14
Calculează: Produsul cifrelor lui 305.
3 × 0 × 5 = 0 (cifra 0 distruge produsul!).
Adevărat sau Fals? Dacă inițializăm produsul cifrelor cu 0, rezultatul va fi mereu corect.
Fals — produsul inițializat cu 0 rămâne mereu 0.

Ora 11: Numere palindrom

Ce este un palindrom?

Definiție: Un număr palindrom se citește la fel de la stânga la dreapta și de la dreapta la stânga.

Exemple: 121, 12321, 7, 44, 1001, 505

Toate numerele de o singură cifră (0–9) sunt palindroame.

Algoritmul de inversare a cifrelor

Formula cheie: invers = invers * 10 + cifra

Aceasta „mută" cifrele la stânga și adaugă una nouă pe ultima poziție.

Inversarea unui număr

int original = n;
int invers = 0;
while (n != 0) {
    int cifra = n % 10;
    invers = invers * 10 + cifra;
    n = n / 10;
}

Exemplu pas cu pas: n = 123

Pas	n	cifra	invers
1	123	3	0×10 + 3 = 3
2	12	2	3×10 + 2 = 32
3	1	1	32×10 + 1 = 321

Verificarea palindromului

Este palindrom?

if (original == invers)
    cout << "Este palindrom";
else
    cout << "NU este palindrom";
// 121 → invers 121 → palindrom ✓
// 123 → invers 321 → NU palindrom ✗

Important: Salvează valoarea originală a lui n înainte de buclă, deoarece bucla distruge valoarea lui n (devine 0).

Exerciții — Ora 11

Adevărat sau Fals? Numărul 12321 este palindrom.
Adevărat — se citește la fel: 12321.
Completează: Formula care construiește inversul cifră cu cifră este: invers = invers * 10 + _______
cifra (ultima cifră extrasă cu n % 10).
Calculează: Care este inversul numărului 4560?
654 (zeroul de la început se pierde: 0654 → 654).
Adevărat sau Fals? La verificarea palindromului putem folosi direct n, fără a-l salva în altă variabilă.
Fals — bucla distruge n (devine 0), deci trebuie salvat în „original" înainte.

Ora 12: Divizorii unui număr

Ce este un divizor?

Definiție: Un număr d este divizor al lui n dacă n % d == 0 (restul împărțirii este 0).

Exemplu: Divizorii lui 12 sunt: 1, 2, 3, 4, 6, 12.

Metoda optimizată: parcurgere până la √n

Idee cheie: Divizorii vin în perechi: dacă d divide n, atunci și n/d divide n. Nu trebuie să căutăm decât până la √n.

Găsirea tuturor divizorilor (optimizat)

for (int d = 1; d * d <= n; d++) {
    if (n % d == 0) {
        cout << d << " ";          // divizorul mic
        if (d != n / d)
            cout << n / d << " ";  // perechea mare
    }
}

Exemplu: Divizorii lui 24

d	d*d ≤ 24?	24 % d == 0?	Pereche (d, 24/d)
1	1 ≤ 24 ✓	Da	(1, 24)
2	4 ≤ 24 ✓	Da	(2, 12)
3	9 ≤ 24 ✓	Da	(3, 8)
4	16 ≤ 24 ✓	Da	(4, 6)
5	25 > 24 ✗	STOP

Rezultat: 1, 2, 3, 4, 6, 8, 12, 24

⚠️ Pătrate perfecte: Pentru n = 16, perechea (4, 4) trebuie afișată o singură dată! De aceea verificăm d != n/d.

Reguli utile: Orice număr are cel puțin 2 divizori (1 și el însuși). Numerele prime au exact 2 divizori. Pătratele perfecte au un număr impar de divizori.

Exerciții — Ora 12

Completează: Un număr d este divizor al lui n dacă n % d == _______.
0 (restul este zero).
Adevărat sau Fals? Pentru a găsi toți divizorii lui n, trebuie să parcurgem de la 1 la n.
Fals — este suficient până la √n, apoi folosim perechile.
Enumeră: Care sunt toți divizorii lui 18?
1, 2, 3, 6, 9, 18.
Adevărat sau Fals? Pătratele perfecte au un număr par de divizori.
Fals — au un număr impar (ex: 16 are 5 divizori: 1,2,4,8,16).

Ora 13: Numere prime

Ce este un număr prim?

Definiție: Un număr natural p > 1 care are exact doi divizori: 1 și el însuși.

Exemple: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …

Atenție: 0 și 1 NU sunt numere prime. 2 este singurul număr prim par.

Algoritmul de verificare (optimizat)

Testare primalitate

bool estePrim(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int d = 3; d * d <= n; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

Cele 3 optimizări

Optimizare	Explicație
Parcurgere până la √n	Dacă n are un factor > √n, are și unul < √n
Verifică doar d impar	Dacă n e par și ≠ 2, nu e prim (tratat separat)
Ieșire imediată	Dacă găsim un divizor, returnăm false instant

⚠️ Greșeli frecvente:

Uitarea că n ≤ 1 nu sunt prime
Uitarea că 2 este prim (singurul par!)
Parcurgerea tuturor valorilor de la 2 la n (lent, ineficient)

Exerciții — Ora 13

Adevărat sau Fals? Numărul 1 este un număr prim.
Fals — 1 nu este prim (are un singur divizor, nu doi).
Adevărat sau Fals? Numărul 2 este singurul număr prim par.
Adevărat — orice alt număr par se divide cu 2, deci are mai mult de 2 divizori.
Alegere multiplă: Până la ce valoare verificăm divisorii pentru a testa primalitatea?
a) n
b) n/2
c) √n
c) √n — este suficient și mult mai rapid.
Verifică: Este 37 un număr prim?
Da — √37 ≈ 6.08, verificăm 3 și 5 (ambele nu divid 37).

Ora 14: Cel mai mare divizor comun (CMMDC)

Definiția CMMDC

CMMDC(a, b) = cel mai mare număr care divide atât pe a cât și pe b.

Exemplu: CMMDC(12, 18) = 6, deoarece 6 este cel mai mare număr care divide și 12 și 18.

Algoritmul lui Euclid (cu împărțire)

Ideea cheie: CMMDC(a, b) = CMMDC(b, a % b). Se repetă până când b devine 0.

CMMDC — Algoritmul lui Euclid

while (b != 0) {
    int rest = a % b;
    a = b;
    b = rest;
}
// Când b == 0, CMMDC = a

Exemplu: CMMDC(48, 18)

Pas	a	b	rest = a % b
1	48	18	12
2	18	12	6
3	12	6	0 → STOP

Rezultat: CMMDC(48, 18) = 6

Algoritmul cu scăderi (mai lent)

CMMDC — Metoda scăderilor

while (a != b) {
    if (a > b) a = a - b;
    else b = b - a;
}
// Când a == b, CMMDC = a

⚠️ Comparație: Metoda scăderilor pentru CMMDC(1000000, 1) face 999.999 de pași! Cu algoritm Euclid: doar 2 pași.

Proprietăți: CMMDC(a, 0) = a; CMMDC(a, a) = a; dacă b divide a, CMMDC(a, b) = b.

Aplicație practică: simplificarea fracțiilor

Exemplu: Fracția 24/36 → CMMDC(24, 36) = 12 → fracția simplificată: 24/12 = 2, 36/12 = 3 → 2/3.

Exerciții — Ora 14

Calculează: CMMDC(36, 24).
12 (36%24=12 → 24%12=0 → CMMDC=12).
Completează: În algoritmul lui Euclid, ne oprim când b == _______.
0
Adevărat sau Fals? Metoda scăderilor și algoritmul lui Euclid dau mereu același rezultat.
Adevărat — ambele dau CMMDC corect, dar Euclid este mult mai rapid.
Aplicație: Simplificați fracția 42/56.
CMMDC(42,56) = 14 → 42/14 = 3, 56/14 = 4 → 3/4.

Ora 15: Cel mai mic multiplu comun (CMMMC)

Definiția CMMMC

CMMMC(a, b) = cel mai mic număr pozitiv care se divide atât cu a cât și cu b.

Exemplu: CMMMC(4, 6) = 12 (cel mai mic număr din multiplii comuni: 12, 24, 36…)

Formula de aur

CMMMC(a, b) × CMMDC(a, b) = a × b

Deci: CMMMC(a, b) = a × b / CMMDC(a, b)

Calculul CMMMC folosind CMMDC

int cmmdc = euclid(a, b);  // calculăm CMMDC mai întâi
long long cmmmc = (long long)a * b / cmmdc;
// Exemplu: CMMMC(12, 18)
// CMMDC(12, 18) = 6
// CMMMC = 12 × 18 / 6 = 216 / 6 = 36

Exemplu: CMMMC(8, 12)

Pas	Calcul
1. CMMDC	CMMDC(8, 12) = 4
2. Formula	CMMMC = 8 × 12 / 4 = 96 / 4 = 24
3. Verificare	Multipli de 8: 8, 16, 24… Multipli de 12: 12, 24… ✓

⚠️ Greșeli frecvente:

a / cmmdc * b — poate pierde precizia (ordinea contează!)
Uitarea de long long — a * b poate depăși limita lui int!

Corect: (long long)a * b / cmmdc

Aplicații practice

Sincronizare: Evenimentele la fiecare 4 și 6 zile se întâlnesc la fiecare CMMMC(4,6) = 12 zile.
Numitori comuni: 1/4 + 1/6 → numitor comun = CMMMC(4,6) = 12.
Autobuze: Autobuzele la 12 și 18 minute se sincronizează la CMMMC(12,18) = 36 minute.

Exerciții — Ora 15

Calculează: CMMMC(6, 8).
CMMDC(6,8) = 2 → CMMMC = 6×8/2 = 24.
Completează: CMMMC(a, b) = a × b / _______.
CMMDC(a, b)
Adevărat sau Fals? CMMMC(a, b) poate fi calculat fără a cunoaște CMMDC(a, b).
Fals — formula folosește CMMDC, deci trebuie calculat mai întâi.
Problemă: Două lumini clipesc la fiecare 5 și 7 secunde. După câte secunde clipesc împreună?
CMMMC(5, 7) = 35 secunde (CMMDC=1, deci 5×7/1=35).

Ora 16: Sume și produse complexe

Ce înseamnă „calcule complexe"?

Definiție: Calcule complexe = efectuarea mai multor operații simultan într-o singură parcurgere (buclă), folosind condiții pentru a distribui fiecare valoare la variabila potrivită.

Modelul general

Mai multe operații într-o singură buclă

int sumaPare = 0;        // suma începe cu 0
long long produsImpare = 1;  // produsul începe cu 1
int contor = 0;

for (int i = 1; i <= n; i++) {
    if (i % 2 == 0) {
        sumaPare += i;       // adună doar numerele pare
        contor++;
    } else {
        produsImpare *= i;   // înmulțește doar numerele impare
    }
}
// Rezultat n=10: sumaPare = 2+4+6+8+10 = 30
//                produsImpare = 1×3×5×7×9 = 945

Regula de aur — mereu valabilă

⚠️ Suma începe cu 0, produsul începe cu 1!

suma = 0; — elementul neutru al adunării
produs = 1; — elementul neutru al înmulțirii

Dacă inițializezi produsul cu 0, rezultatul va fi mereu 0, indiferent de valorile din buclă.

Exemplu: calcule simultane pentru cifrele lui 2538

Cifra	Pară?	sumaPare	produsImpare
8	Da	0 + 8 = 8	1 (nemodificat)
3	Nu	8 (nemodificat)	1 × 3 = 3
5	Nu	8 (nemodificat)	3 × 5 = 15
2	Da	8 + 2 = 10	15 (nemodificat)

Rezultat: Suma cifrelor pare = 10, Produsul cifrelor impare = 15.

Avantajul: O singură buclă face totul — nu parcurgem datele de mai multe ori. Eficiență O(n) în loc de O(2n) sau O(3n).

Exerciții — Ora 16

Adevărat sau Fals? Într-un calcul complex, trebuie să facem câte o buclă separată pentru fiecare operație.
Fals — totul se face într-o singură buclă, cu condiții if/else.
Calculează: Pentru numerele 1–6, care este suma celor pare și produsul celor impare?
Suma pare: 2+4+6 = 12. Produs impare: 1×3×5 = 15.
Completează: Elementul neutru al adunării (cu care inițializăm suma) este _______, iar al înmulțirii (produsul) este _______.
0 (pentru sumă) și 1 (pentru produs).
Adevărat sau Fals? Dacă inițializăm produs = 0, obținem răspunsul corect.
Fals — 0 × orice = 0, deci produsul rămâne mereu 0.

Recapitulare completă: orele 9 - 16