Lecția de față adună algoritmii elementari pe care se construiesc majoritatea problemelor de informatică din liceu și din concursuri: lucrul cu cifrele unui număr, divizibilitate, numere prime, CMMDC și șirul Fibonacci. Pentru fiecare algoritm găsești ideea din spatele lui, codul în C++ și observațiile care te scapă de greșelile clasice.
1. Spargerea unui număr în cifre
Aproape orice problemă cu cifrele unui număr se rezolvă cu același tipar: extragem ultima cifră cu n % 10, o prelucrăm, apoi „tăiem” ultima cifră cu n / 10. Repetăm cât timp numărul mai are cifre.
if (n == 0) prelucrare_caz_special();
while (n > 0)
{
cif = n % 10;
// ... prelucrăm cifra determinată, conform problemei
n = n / 10;
}while (n > 0) nu se execută deloc pentru 0, deși 0 are o cifră. Tratează cazul separat, înaintea buclei.a) Numărul de cifre
nrcifre = 0;
if (n == 0) nrcifre = 1;
while (n > 0)
{
nrcifre++;
n = n / 10;
}b) Prima cifră a numărului
Împărțim repetat la 10 până când rămâne o singură cifră — exact prima.
if (n == 0) primacif = 0;
while (n > 9)
n = n / 10;
primacif = n;c) Oglinditul unui număr
Oglinditul lui 12345 este 54321. Construim noul număr cifră cu cifră: la fiecare pas, mutăm cifrele deja adunate cu o poziție la stânga (înmulțire cu 10) și adăugăm cifra curentă.
ogl = 0;
while (n > 0)
{
cif = n % 10;
ogl = ogl * 10 + cif;
n = n / 10;
}d) Generarea cifrelor în ordinea din număr
Dacă vrem cifrele de la stânga la dreapta, calculăm mai întâi puterea lui 10 corespunzătoare primei cifre, apoi extragem pe rând cifra cea mai semnificativă.
p = 1;
while (p * 10 <= n)
p = p * 10;
while (n > 0)
{
cif = n / p;
// prelucrăm cifra cif
n = n % p;
p = p / 10;
}if (n == 0) prelucrează cifra 0;e) Numărarea aparițiilor cifrei k
nrap = 0;
if (n == 0 && k == 0) nrap = 1;
while (n > 0)
{
cif = n % 10;
if (cif == k) nrap++;
n = n / 10;
}f) Eliminarea cifrelor pare
Reconstruim numărul doar din cifrele impare. Pentru că parcurgem cifrele de la dreapta la stânga, le lipim la noul număr tot „de la dreapta”, folosind o putere a lui 10 care crește doar când păstrăm o cifră — astfel ordinea inițială se păstrează.
p = 1; nr = 0;
while (n > 0)
{
cif = n % 10;
if (cif % 2 != 0)
{
nr = nr + cif * p;
p = p * 10;
}
n = n / 10;
}Două proprietăți utile despre divizori
- n are un număr impar de divizori ⇔ n este pătrat perfect:
sqrt(n) == (int)sqrt(n) - n are exact 3 divizori ⇔ n este pătratul unui număr prim:
sqrt(n)trebuie să fie întreg și număr prim.
2. Verificarea dacă un număr este prim
Un număr n ≥ 2 este prim dacă nu are niciun divizor între 2 și √n. E suficient să mergem până la √n, deoarece divizorii apar în perechi (d, n/d): dacă n ar avea un divizor mai mare decât √n, ar avea automat și unul mai mic.
if (n < 2) prim = 0;
else
{
prim = 1; // presupunem că n este prim
for (d = 2; d * d <= n; d++)
if (n % d == 0) { prim = 0; break; }
if (prim == 1)
{
// ... operațiile de efectuat când n este prim
}
}d <= sqrt(n) cu numere reale — preferă d * d <= n, care lucrează doar cu întregi.3. Cel mai mare divizor comun (CMMDC) — algoritmul lui Euclid
Înlocuim repetat perechea (a, b) cu (b, a % b) până când restul devine 0. Ultimul împărțitor nenul este CMMDC-ul.
rest = a % b;
while (rest != 0)
{
a = b;
b = rest;
rest = a % b;
}
cmmdc = b;cmmmc = (ca * cb) / cmmdc, unde ca și cb sunt copii ale valorilor inițiale, salvate înainte de a aplica algoritmul lui Euclid (care modifică a și b).a % b încă dinaintea buclei, deci pentru b = 0 se produce o împărțire la zero. O variantă mai robustă mută testul pe b și funcționează pentru orice pereche cu cel puțin o valoare nenulă (prin convenție, cmmdc(a, 0) = a):while (b != 0)
{
rest = a % b;
a = b;
b = rest;
}
cmmdc = a;4. Divizorii proprii ai lui n
Divizorii proprii sunt divizorii diferiți de 1 și de n. Cel mai mare divizor propriu posibil este n/2, deci parcurgem doar până acolo.
for (d = 2; d <= n / 2; d++)
if (n % d == 0)
{
// operații cu divizorul propriu d
// s = s + d; — suma divizorilor proprii
// nrd++; — numărul divizorilor proprii
}5. Câte numere din [a, b] sunt divizibile cu k?
Nu este nevoie de nicio buclă — doar de puțină aritmetică:
- Numerele ≤ n divizibile cu k:
n / k(împărțire întreagă) - Numerele din [a, b] divizibile cu k:
b / k − (a − 1) / k - Multiplii comuni ai lui a și b din [1, n]:
n / cmmmc(a, b) - Multiplii lui a care nu sunt multipli de b, din [1, n]:
n / a − n / cmmmc(a, b)
6. Descompunerea în factori primi
Încercăm pe rând divizorii d = 2, 3, 4, … și, pentru fiecare, împărțim numărul cât timp se mai poate, numărând puterea m. Deși d parcurge și numere compuse, ele nu mai divid n la momentul respectiv (factorii lor primi au fost deja eliminați), deci doar divizorii primi sunt prelucrați efectiv.
d = 2;
while (d * d <= n)
{
m = 0;
while (n % d == 0)
{
m++;
n = n / d;
}
if (m > 0)
{
// operații cu divizorul prim d, aflat la puterea m
}
d++;
}
if (n > 1)
{
// n rămas este ultimul divizor prim, la puterea 1
}7. Numărul divizorilor lui n — formula lui Euler
Dacă N = p₁m₁ · p₂m₂ · … · pkmk, atunci numărul total de divizori este:
Nrdiv = (m₁ + 1)(m₂ + 1)…(mk + 1)
Intuiția: un divizor se formează alegând pentru fiecare factor prim pi o putere între 0 și mi — adică mi + 1 variante.
d = 2; nrdiv = 1;
while (d * d <= n)
{
m = 0;
while (n % d == 0)
{
m++;
n = n / d;
}
nrdiv = nrdiv * (m + 1);
d++;
}
if (n > 1) nrdiv = nrdiv * 2; // ultimul factor prim, la puterea 1: (1+1) = 28. Cel mai mare număr Fibonacci ≤ n
Generăm termenii șirului 1, 1, 2, 3, 5, 8, … păstrând mereu ultimii doi (f0 și f1) și ne oprim înainte ca suma lor să depășească n.
fin >> n;
f0 = f1 = 1;
while (f0 + f1 <= n)
{
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
// f1 este cel mai mare termen Fibonacci <= n9. Cifra de control a lui n
Cifra de control se obține adunând repetat cifrele numărului până rămâne o singură cifră. Nu este nevoie de bucle: rezultatul coincide cu restul împărțirii la 9 (cu două cazuri speciale).
if (n == 0) cifc = 0;
else if (n % 9 == 0) cifc = 9;
else cifc = n % 9;10. Ultima cifră a lui xy
Ultimele cifre ale puterilor se repetă periodic, dar perioada depinde de ultima cifră a lui x: cifrele 0, 1, 5 și 6 au perioada 1 (de exemplu, 6, 36, 216, … se termină mereu în 6), cifrele 4 și 9 au perioada 2 (4, 16, 64, … alternează 4, 6, 4, 6), iar cifrele 2, 3, 7 și 8 au perioada 4 (puterile lui 2 se termină în 2, 4, 8, 6, 2, 4, 8, 6, …).
c = x % 10;
if (y % 4 == 1) ucif = c;
else if (y % 4 == 2) ucif = (c * c) % 10;
else if (y % 4 == 3) ucif = (c * c * c) % 10;
else if (y % 4 == 0) ucif = (c * c * c * c) % 10; // y multiplu de 411. Citirea pe rând a n numere
Când avem multe numere de prelucrat, nu le memorăm pe toate: citim câte unul și îl prelucrăm pe loc, refolosind aceeași variabilă.
fin >> n;
for (i = 1; i <= n; i++)
{
fin >> a;
// prelucrăm a cu oricare dintre algoritmii de mai sus
}12. Prelucrarea perechilor de numere consecutive
Pentru perechi de tipul (primul, al doilea), (al doilea, al treilea) etc., păstrăm mereu valoarea anterioară în a și pe cea curentă în b, iar la final mutăm b în a.
fin >> n;
fin >> a;
for (i = 2; i <= n; i++)
{
fin >> b;
// prelucrăm perechea (a, b)
a = b;
}13. Minimul / maximul a n numere citite pe rând
Presupunem că primul element este minimul, apoi comparăm fiecare număr nou cu minimul curent și îl actualizăm dacă găsim ceva mai mic.
fin >> n;
fin >> a;
min = a; // presupunem că minimul este primul element
for (i = 2; i <= n; i++)
{
fin >> a;
if (a < min) min = a; // pentru maxim: if (a > max) max = a;
}Recapitulare și exerciții propuse
- Verificați dacă un număr citit de la tastatură este palindrom (egal cu oglinditul său).
- Afișați suma cifrelor pare și produsul cifrelor impare ale unui număr.
- Citiți n numere și afișați câte dintre ele sunt prime.
- Determinați CMMDC-ul și CMMMC-ul a două numere citite.
- Afișați descompunerea în factori primi a unui număr sub forma
n = p1^m1 * p2^m2 * ... - Câte numere din intervalul [a, b] sunt divizibile cu 3, dar nu și cu 5?
- Citiți n numere și afișați cea mai mare diferență dintre două numere citite consecutiv.