Operații cu cifrele unui număr (Ora 1)
Ultima cifră: n % 10 - restul împărțirii la 10. Pentru n = 1234, obținem 4.
Eliminarea ultimei cifre: n // 10 - câtul împărțirii la 10. Pentru n = 1234, obținem 123.
Legătura dintre ele: orice număr n se scrie ca n = (n // 10) * 10 + (n % 10): pentru 1234 avem 123 * 10 + 4. % și // sunt operații complementare, folosite mereu împreună.
Adăugarea unei cifre c la dreapta: n = n * 10 + c - înmulțim cu 10 ca să facem loc cifrei noi: n = 12, c = 7 → 12 * 10 + 7 = 127.
Adăugarea unei cifre c la stânga: n = c * 10**p + n, unde p este numărul de cifre ale lui n: pentru n = 23 (p = 2) și c = 5 → 5 * 100 + 23 = 523.
Oglinditul, palindromul și numărul de cifre (Ora 2)
Oglinditul: numărul obținut citind cifrele de la dreapta la stânga; se construiește cu og = og * 10 + n % 10 în bucla while n > 0. Pentru n = 123: pasul 1 → og = 3, pasul 2 → og = 32, pasul 3 → og = 321.
Palindrom: număr egal cu oglinditul său: 1221, 121, 5, 12321 sunt palindromuri. Un număr cu toate cifrele egale (111, 777) este automat palindrom.
Numărul de cifre: contor cnt = cnt + 1 în aceeași buclă; pentru n = 0, rezultatul corect este 1.
Regula de aur: salvează numărul inițial (x = n) înainte de orice buclă care îl modifică.
Divizori, numere prime și numere perfecte (Ora 3)
Divizor: d este divizor al lui n dacă n % d == 0; divizorii lui 12 sunt 1, 2, 3, 4, 6, 12. Divizorii se găsesc în perechi (d, n // d), de aceea căutarea merge doar până la sqrt(n).
Număr prim: număr cu exact 2 divizori (1 și el însuși): 2, 3, 5, 7, 11; numărul 1 nu este prim, pentru că are un singur divizor.
Număr perfect: egal cu suma divizorilor proprii (excludem numărul însuși, dar includem 1): 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, 496, 8128.
Optimizare: suma divizorilor proprii se calculează până la n // 2; numărul de divizori se calculează până la sqrt(n), numărând perechile.
Descompunerea în factori primi (Ora 4)
Definiție: orice număr natural n > 1 se scrie în mod unic ca produs de puteri de numere prime: 72 = 2^3 * 3^2, 12 = 2^2 * 3. Algoritmul pornește de la d = 2 și împarte repetat până când n ajunge la 1; fiecare divizor d folosit de mai multe ori marchează o putere.
Numărul de divizori: pentru n = p1^e1 * p2^e2, numărul de divizori este (e1+1) * (e2+1): 72 are (3+1)*(2+1) = 12 divizori, iar 12 = 2^2 * 3 are (2+1)*(1+1) = 6 divizori.
Cazuri speciale: n = 1 nu are factori primi; un număr prim are o singură linie de descompunere, la puterea 1.
CMMDC, CMMMC și algoritmul lui Euclid (Ora 5)
CMMDC: cel mai mare divizor comun; CMMDC(24, 36) = 12.
Algoritmul lui Euclid cu împărțiri: repetăm r = a % b; a = b; b = r cât timp b != 0; la final, a este CMMDC. Comparație pe CMMDC(24, 36): cu scăderi repetate facem 36 - 24 = 12, 24 - 12 = 12, 12 - 12 = 0 (mai mulți pași); cu împărțiri: 36 % 24 = 12, apoi 24 % 12 = 0 (doar 2 pași).
CMMMC: CMMMC(a, b) = a * b // CMMDC(a, b); CMMMC(4, 6) = 4 * 6 // 2 = 12.
Numere prime între ele: CMMDC = 1 (ex: 8 și 15).
Conversii între baze (Ora 6)
Din baza 10 în baza 2: împărțiri repetate la 2, resturile se citesc de la ultimul la primul. Pentru 10: 10 : 2 = 5 rest 0, 5 : 2 = 2 rest 1, 2 : 2 = 1 rest 0, 1 : 2 = 0 rest 1; resturile citite invers dau 1010(2).
Din baza 2 în baza 10: z = z * 2 + cifra, parcurgând șirul de la stânga la dreapta: pentru 1011: z = 1, apoi 1*2+0 = 2, apoi 2*2+1 = 5, apoi 5*2+1 = 11 → 1011(2) = 11.
Puteri utile: 2^0=1, 2^1=2, 2^2=4, 2^3=8, 2^4=16, 2^5=32, 2^6=64.
Aplicații integrate (Ora 9) și numere speciale (Ora 8)
Numere prietene: a și b sunt prietene dacă suma divizorilor proprii ai lui a este b, iar suma divizorilor proprii ai lui b este a: perechea (220, 284).
Problemă combinată: un singur pasaj prin cifre poate produce simultan suma, numărul de cifre, oglinditul și verificarea palindromului.
Aplicații reale: divizorii apar la tăierea materialelor în bucăți egale, la distribuirea obiectelor și la ambalarea produselor; CMMDC dă cea mai mare lungime comună.
Algoritmul 1: Oglinditul și verificarea palindromului
n = int(input())
x = n
og = 0
while n > 0:
og = og * 10 + n % 10
n = n // 10
if x == og:
print("palindrom")
else:
print("nu este palindrom")
Algoritmul 2: Afișarea divizorilor și numărul lor
n = int(input())
nr_div = 0
d = 1
while d * d <= n:
if n % d == 0:
if d * d == n:
nr_div = nr_div + 1
else:
nr_div = nr_div + 2
d = d + 1
print(nr_div)
Algoritmul 3: Descompunerea în factori primi
n = int(input())
d = 2
while n > 1:
p = 0
while n % d == 0:
n = n // d
p = p + 1
if p > 0:
print(d, "la puterea", p)
d = d + 1
Algoritmul 4: CMMDC (Euclid) și CMMMC
a, b = map(int, input().split())
x, y = a, b
while y != 0:
r = x % y
x = y
y = r
cmmdc = x
cmmmc = a * b // cmmdc
print(cmmdc)
print(cmmmc)
Algoritmul 5: Conversii între baze
n = int(input())
b = ""
while n > 0:
b = str(n % 2) + b
n = n // 2
print(b)
s = input()
z = 0
for ch in s:
z = z * 2 + int(ch)
print(z)
Algoritmul 6: Suma divizorilor proprii (perfecte și prietene)
def suma_divizori_proprii(n):
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
return s
n = int(input())
if suma_divizori_proprii(n) == n:
print("numar perfect")
else:
print("nu este numar perfect")
Algoritmul 7: Suma cifrelor unui număr
n = int(input())
s = 0
while n > 0:
s = s + n % 10
n = n // 10
print(s)
Observă: același tipar servește la orice prelucrare a cifrelor: suma (s = s + c), produsul (p = p * c), numărul de cifre (cnt = cnt + 1) sau oglinditul (og = og * 10 + c). Se pot combina toate într-un singur pasaj.
Algoritmul 8: Verificarea unui număr prim
n = int(input())
prim = True
if n < 2:
prim = False
d = 2
while d * d <= n:
if n % d == 0:
prim = False
d = d + 1
if prim:
print("numar prim")
else:
print("nu este prim")
Observă: căutarea divizorilor se oprește la sqrt(n); dacă n nu are divizori până acolo, nu are nici după, pentru că divizorii vin în perechi (d, n // d). Testează: 1 → nu este prim, 2 → prim, 97 → prim.
Tabel rezumativ: prelucrări numerice
| Prelucrare | Idee cheie | Operație principală |
|---|---|---|
| Ultima cifră | Restul împărțirii la 10 | n % 10 |
| Eliminarea ultimei cifre | Câtul împărțirii la 10 | n // 10 |
| Oglinditul | Adăugăm cifrele la dreapta | og = og * 10 + n % 10 |
| Divizorii | Restul împărțirii la d este 0 | n % d == 0 |
| Factorii primi | Împărțiri repetate de la 2 | n // d cât timp se poate |
| CMMDC | Algoritmul lui Euclid | a, b = b, a % b |
| CMMMC | a * b / CMMDC | a * b // cmmdc |
| Baza 2 | Resturile împărțirilor la 2 | n % 2 și n // 2 |
Numere speciale într-un tabel
| Tip de număr | Definiție | Exemple |
|---|---|---|
| Prim | Exact 2 divizori: 1 și el însuși | 2, 3, 5, 7, 11, 13, 17, 19 |
| Perfect | Egal cu suma divizorilor proprii | 6, 28, 496, 8128 |
| Palindrom | Egal cu oglinditul său | 121, 1221, 12321, 5 |
| Prieten | Formează o pereche cu sume reciproce ale divizorilor proprii | (220, 284), (1184, 1210) |
| Prime între ele | CMMDC = 1 | (8, 15), (7, 20) |
Greșeli frecvente din modul
- Confuzia % cu //:
n % 10dă ultima cifră,n // 10o elimină; cele două nu sunt interschimbabile. - Pierderea valorii lui n: orice buclă care face
n = n // 10saun = n // ddistruge valoarea; salveazăx = nînainte. - Euclid scris greșit:
a = b; b = a % bfolosește noul a; varianta corectă estea, b = b, a % b. - Resturile bazei 2 în ordine greșită: se adaugă la stânga șirului:
b = str(n % 2) + b. - Suma divizorilor proprii cu n inclus: bucla merge doar până la
n // 2. - Numărul 1 considerat prim: 1 are un singur divizor, deci nu este prim.
Reguli și trucuri de rezolvare
- Orice problemă are structura: citire - prelucrare - afișare.
- Alege algoritmul după tipul cerinței: cifre →
while n > 0; divizori →forcu%; CMMDC → Euclid; baze → resturi la 2. - Pentru restricții mari (n până la 10^9) folosește
sqrt(n)la divizori, nu parcurgerea completă. - Testează întotdeauna cu cazuri limită: n = 0, n = 1, număr prim, pătrat perfect, cifre identice.
- Verifică pe hârtie cu un exemplu mic înainte de rulare: 1234, 72, 24 și 36, 10.
- Combina mai multe prelucrări într-un singur pasaj prin cifre pentru eficiență maximă.
Comparații esențiale
% față de //: ambele lucrează cu împărțirea la 10, dar cu roluri opuse. Restul rămâne, câtul se aruncă; câtul rămâne, restul se aruncă.
| Operație | Rol | Exemplu |
|---|---|---|
n % 10 |
Restul împărțirii la 10: extrage ultima cifră | 1234 % 10 = 4 |
n // 10 |
Câtul împărțirii la 10: elimină ultima cifră | 1234 // 10 = 123 |
n % 2 |
Paritatea: 0 pentru par, 1 pentru impar | 7 % 2 = 1 |
n // 2 |
Un pas al conversiei în baza 2 | 10 // 2 = 5 |
Euclid cu scăderi față de Euclid cu împărțiri: același rezultat, dar cu număr foarte diferit de pași. Împărțirile „sar" peste multe scăderi deodată.
| Criteriu | Scăderi repetate | Împărțiri repetate |
|---|---|---|
| Bucla | cât timp a != b: a = a - b |
cât timp b != 0: r = a % b; a = b; b = r |
| Numărul de pași | Mare, proporțional cu valorile numerelor | Mic, restul scade rapid |
| CMMDC(24, 36) | 36-24=12, 24-12=12, 12-12=0 → 12 | 36 % 24 = 12, 24 % 12 = 0 → 12 |
| Recomandare | Utile pentru înțelegerea ideii | Folosite în programe și la test |
Conversiile între baze: cele două direcții folosesc operații inverse. La 10 → 2 numărul se micșorează cu // 2, iar resturile se citesc invers; la 2 → 10 numărul crește cu z = z * 2 + cifra.
| Direcție | Metoda | Exemplu |
|---|---|---|
| Baza 10 → baza 2 | Împărțiri repetate la 2; resturile se citesc invers | 10 = 1010(2) |
| Baza 2 → baza 10 | z = z * 2 + cifra, de la stânga la dreapta |
1011(2) = 11 |
Ce trebuie să știi pentru test
- Extragerea și eliminarea cifrelor: n % 10 dă ultima cifră, n // 10 o elimină; le combini în bucla
while n > 0. - Oglinditul și palindromul: construiești
og = og * 10 + n % 10și compari cux = nsalvat înaintea buclei. - Divizorii: afișarea cu o buclă for până la
sqrt(n), numărul de divizori numărând perechile (d, n // d). - Numere prime și perfecte: prim are exact 2 divizori; perfect este egal cu suma divizorilor proprii (fără n, cu 1).
- Descompunerea în factori primi: împărțiri repetate de la d = 2, iar numărul de divizori rezultă din exponenți: (e1+1) * (e2+1).
- Euclid și CMMMC:
a, b = b, a % bpână lab == 0, apoi CMMMC = a * b // CMMDC. - Conversiile între baze: resturile împărțirilor la 2 citite invers și reconstrucția cu
z = z * 2 + cifra. - Cazurile limită: n = 0 (are o cifră), n = 1 (nu este prim, nu are factori primi), pătrate perfecte la numărarea divizorilor.
Exerciții de recapitulare cu rezolvare
Exercițiul 1: suma cifrelor pare
Cerință: se citește n; afișează suma cifrelor pare ale lui n. Pentru n = 1234, rezultatul este 2 + 4 = 6.
n = int(input())
s = 0
while n > 0:
c = n % 10
if c % 2 == 0:
s = s + c
n = n // 10
print(s)
Verificare: pentru n = 1234, cifrele extrase sunt 4, 3, 2, 1; cele pare (4 și 2) dau suma 6. Testează și n = 0: bucla nu rulează, iar suma este 0.
Exercițiul 2: CMMDC și CMMMC pentru 48 și 72
Cerință: calculează CMMDC(48, 72) și CMMMC(48, 72).
a, b = 48, 72
x, y = a, b
while y != 0:
r = x % y
x = y
y = r
cmmdc = x
cmmmc = a * b // cmmdc
print(cmmdc, cmmmc) # 24 144
Verificare: 72 % 48 = 24, 48 % 24 = 0, deci CMMDC = 24; CMMMC = 48 * 72 // 24 = 144. Descompunerile confirmă: 48 = 2^4 * 3, 72 = 2^3 * 3^2.
Exercițiul 3: conversia lui 19 în baza 2
Cerință: transformă 19 din baza 10 în baza 2 și verifică rezultatul.
n = 19
b = ""
while n > 0:
b = str(n % 2) + b
n = n // 2
print(b) # 10011
Verificare: 19 : 2 = 9 rest 1, 9 : 2 = 4 rest 1, 4 : 2 = 2 rest 0, 2 : 2 = 1 rest 0, 1 : 2 = 0 rest 1; resturile citite invers: 10011. Reconstrucția: 1*16 + 0*8 + 0*4 + 1*2 + 1*1 = 19.
Greșeli frecvente la test
- / în loc de //:
1234 / 10 = 123.4(număr cu virgulă) strică buclele și comparațiile; folosește mereu//pentru câtul întreg. - Rolurile lui % și // inversate:
n // 10nu dă ultima cifră șin % 10nu elimină cifre; verifică cu un exemplu înainte de a scrie bucla. - Compararea oglinditului fără copie: dacă nu salvezi
x = nînainte de buclă, la final n este 0 și comparațian == ogeșuează. - Euclid cu atribuiri succesive:
a = b; b = a % bfolosește noul a; corect estea, b = b, a % b. - Resturile bazei 2 în ordine greșită: primul rest este cifra cea mai puțin semnificativă; adună la stânga:
b = str(n % 2) + b. - 1 tratat ca număr prim: 1 are un singur divizor, deci nu este prim; verifică explicit
n < 2. - Divizorii proprii cu n inclus: bucla pentru suma divizorilor proprii merge doar până la
n // 2, altfel n se adună singur. - Pătrate perfecte la numărarea divizorilor: la d cu d * d == n, numără o singură dată (d), nu de două ori (d și n // d sunt aceeași valoare).