Modul 03 — Prelucrarea numerelor

Cutia de unelte pentru cifre

Patru formule care apar în 90% din problemele cu numere. Învață-le ca pe tabla înmulțirii.

Ultima cifră

uc = n % 10

restul împărțirii la 10 · 573 % 10 = 3

Tai ultima cifră

n = n / 10 (C++) · n // 10 (Py)

573 / 10 = 57 — împărțire întreagă!

Adaug cifră la dreapta

n = n * 10 + c

57 → 57·10+9 = 579

Adaug cifră la stânga

n = c * p + n

p = 10^{nr. cifre} → 9 · 100 + 57 = 957

Șablonul universal: „cât timp n > 0: prelucrez n % 10, apoi n = n / 10". Cu el numeri cifrele, le aduni, cauți maximul, construiești inversul — schimbi doar prelucrarea. Îl vezi la lucru de trei ori mai jos, în trei probleme diferite.

Simulator: suma cifrelor

Prima aplicare a șablonului: golim numărul cifră cu cifră și le adunăm într-un „coș" numit s.

n =

Variabile

n	—
c	—
s	—

Ecran

n	c = n%10	s

Apasă „Pas cu pas" și urmărește cum s adună cifră după cifră. 👣

Variații pe același schelet (încearcă-le pe caiet): numărul de cifre (nr ← nr + 1), cifra maximă (dacă c > max atunci max ← c), câte cifre pare are numărul (dacă c % 2 = 0 …). Schimbi doar linia de prelucrare — scheletul rămâne identic.

Simulator: inversul unui număr

Același schelet, altă prelucrare: cifrele „se mută" din n în inv — și pentru că ies de la coadă, numărul se răstoarnă.

n =

Variabile

n	—
c	—
inv	—

Ecran

n	c = n%10	inv

Apasă „Pas cu pas" și urmărește cum inv crește în timp ce n se golește. 👣

Compară cu suma cifrelor: singura linie diferită e prelucrarea — inv ← inv·10 + c în loc de s ← s + c. Schimbi o linie → rezolvi altă problemă. Ăsta e șablonul!

Capcana de BAC: dacă n se termină în zero (de ex. 570 → 75), inversul „pierde" zeroul — e normal, 075 nu există ca număr. Iar dacă distrugi n în buclă și îl mai folosești după… l-ai pierdut! Salvează-l într-o copie înainte.

Simulator: reconstrucția cu puteri ale lui 10

Problema-capcană: construiește numărul doar din cifrele pare ale lui n, păstrând ordinea lor. Metoda de la invers nu merge — cifrele ar ieși răsturnate!

n =

Variabile

n	—
c	—
p	—
nou	—

Ecran

c	pară?	p	nou

Pentru 28371, rezultatul corect e 28 — cifrele pare 2 și 8, în ordinea lor. Verifică pas cu pas! 👣

Diferența-cheie față de invers: acolo cifra nouă împinge totul la stânga (nou·10 + c); aici cifra se lipește în față, la poziția dictată de p (c·p + nou), iar p crește doar când chiar am folosit cifra. Alege metoda după ordinea în care vrei cifrele!

Divizorii unui număr — și prima lecție de eficiență

Un divizor e un număr care îl împarte exact pe n. Întrebarea de aur: până unde are rost să cauți?

🔍 Explorator de divizori

n =

verificări: 0

divizori găsiți: —

De ce merge trucul cu √n: divizorii vin în perechi — dacă d îl împarte pe n, atunci și n/d îl împarte. Pentru 36: (1,36), (2,18), (3,12), (4,9), (6,6). Unul din fiecare pereche e mereu ≤ √n. Deci verifici doar până la 6 în loc de 36 — la n = 1.000.000 înseamnă de 1000 de ori mai puțini pași. Asta înseamnă eficiență: același răspuns, alt drum.

Numere prime + descompunerea în factori primi

Un număr e prim dacă are exact 2 divizori: 1 și el însuși. Testul eficient: dacă n nu are niciun divizor d cu 2 ≤ d ≤ √n, e prim. Atenție: 1 NU e prim, iar 2 e singurul prim par.

1bool prim = (n >= 2);

2for (int d = 2; d * d <= n; d++)

3 if (n % d == 0) prim = false;

Descompunerea: împarte repetat cu cel mai mic factor posibil. 360 = 2·2·2·3·3·5 = 2³·3²·5.

1for (int d = 2; d <= n; d++)

2 while (n % d == 0) {

3 cout << d << " ";

4 n = n / d; }

Algoritmul lui Euclid: cursa celor două variante

Cel mai mare divizor comun (cmmdc) — calculat cu scăderi repetate și cu împărțiri repetate, umăr la umăr. Cine termină primul?

a = b =

Varianta 1 — scăderi repetate

Varianta 2 — împărțiri cu rest

1while (a != b)

2 if (a > b) a = a - b;

3 else b = b - a;

4cout << a;

1while (b != 0) {

2 int r = a % b;

3 a = b; b = r; }

4cout << a;

🎁 Bonusul cursei: după ce rulezi cursa, aici se calculează și cel mai mic multiplu comun — direct din rezultatul cmmdc-ului. Apasă „Start cursa" 👆

Concluzia cursei: pentru a = 252, b = 18, scăderile fac 14 pași, împărțirile doar 2 — iar cu cât numerele cresc, cu atât diferența devine mai zdrobitoare. Ține minte ideea: DOI algoritmi corecți pot avea viteze complet diferite.

Fișa de sinteză

Uneltele de azi — le vei folosi în fiecare modul de acum înainte.

n % 10 = ultima cifră · n / 10 = numărul fără ultima cifră (împărțire întreagă).

Șablon: cât timp n > 0 → prelucrez n%10 → n = n/10. Rezolvă: sumă, număr, maxim, invers.

Invers: inv = inv·10 + n%10, în buclă. Salvează o copie a lui n dacă îl mai folosești!

Divizorii vin în perechi (d, n/d) → e suficient să cauți până la √n.

Prim = exact 2 divizori; testezi d·d ≤ n. 1 nu e prim; 2 e singurul prim par.

Euclid cu împărțiri e drastic mai rapid decât cu scăderi — iar cmmmc(a,b) = a·b / cmmdc(a,b).

Reconstrucție în ordine: nou = c·p + nou cu p·10 la fiecare cifră păstrată — când NU vrei inversarea.

Suma cifrelor: s = s + n%10 în buclă — schimbi o singură linie față de invers.

Exersează pe pbinfo.ro: „Cifrele unui număr" (suma cifrelor, inversul, palindrom) și „Divizibilitate" (numărul de divizori, prim, cmmdc). Țintă: 10 probleme.