Ce vei învăța astăzi?
După această lecție vei ști să combini mai mulți algoritmi de prelucrare numerică într-o singură problemă și să alegi soluția cea mai eficientă pentru fiecare cerință.
Probleme combinate: descompunere + divizori + cifre
Definiție: O problemă combinată (o cerință care îmbină mai mulți algoritmi: cifre, divizori, factori primi) cere mai multe prelucrări asupra aceluiași număr: de exemplu, să descompunem n în factori primi, să calculăm numărul de divizori din descompunere și să verificăm o proprietate a cifrelor. Soluția corectă le rezolvă pe toate, de preferință într-un singur pasaj de prelucrare.
De exemplu, pentru n = 72: descompunerea este 2^3 * 3^2, numărul de divizori este (3+1) * (2+1) = 12, iar suma cifrelor este 7 + 2 = 9.
Analogie: examinarea unei clădiri
Un inspector care verifică o clădire nu o examinează separat pentru fiecare etaj: face un singur tur și în timpul turului notează numărul de ferestre, de uși și de alarme. La fel, un program eficient trece o singură dată prin cifrele (sau divizorii) unui număr și adună toate rezultatele cerute de problemă.
o singură buclă pentru mai multe rezultate
acumulator, contor, verificări în același pas
pași proporționali cu datele, nu cu cerințele
Exemplu: descompunere + număr de divizori + suma cifrelor pentru n = 72
n = int(input())
x = n
# Pasul 1: descompunerea in factori primi si numarul de divizori
d = 2
nr_div = 1
while n > 1:
p = 0
while n % d == 0:
n = n // d
p = p + 1
if p > 0:
print(d, "la puterea", p)
nr_div = nr_div * (p + 1)
d = d + 1
# Pasul 2: suma cifrelor (folosim valoarea salvata x)
s = 0
while x > 0:
s = s + x % 10
x = x // 10
# Pasul 3: afisarea rezultatelor
print("Numar de divizori:", nr_div)
print("Suma cifrelor:", s)
Observă: am salvat n în x înainte de descompunere, pentru că bucla de factori primi distruge valoarea. Numărul de divizori se construiește direct din exponenți (puterile la care apar factorii primi, de exemplu 3 și 2 în 2^3 * 3^2), fără a mai căuta divizorii unul câte unul: pentru 72 obținem (3+1)*(2+1) = 12.
Numerele perfecte: verificare și generare
Definiție: Un număr natural n este perfect dacă este egal cu suma divizorilor săi proprii (toți divizorii, cu excepția lui însuși).
Primele numere perfecte sunt 6 = 1 + 2 + 3 și 28 = 1 + 2 + 4 + 7 + 14. Toate numerele perfecte cunoscute sunt pare și se termină cu 6 sau cu 8.
Analogie: echipa completă
Un număr perfect este ca o echipă în care fiecare membru (divizor propriu) contribuie la un fond comun, iar la final fondul este exact egal cu numărul de membri: 6 primește de la 1, 2 și 3 exact 6. Este un „echilibru perfect" al contribuțiilor.
Exemplu: verificăm dacă n este perfect și generăm perfectele mai mici decât n
n = int(input())
# Pasul 1: calculam suma divizorilor proprii
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
# Pasul 2: comparam suma cu numarul
if s == n:
print(n, "este numar perfect")
else:
print(n, "nu este numar perfect")
Observă: suma merge doar până la n // 2, pentru că niciun divizor propriu nu depășește jumătatea numărului. Pentru a genera toate numerele perfecte mai mici decât o valoare maximă, punem această verificare într-o buclă for exterioară.
Exemplu: toate numerele perfecte mai mici decât o limită
lim = int(input())
for n in range(2, lim + 1):
# Pasul 1: suma divizorilor proprii ai lui n
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
# Pasul 2: daca suma este n, n este perfect
if s == n:
print(n, end=" ")
Observă: pentru lim = 1000 se afișează 6 28 496. Pentru limite mari, această variantă devine lentă, pentru că verifică fiecare număr; o variantă eficientă parcurge doar numerele de forma 2^(k-1) * (2^k - 1) cu 2^k - 1 prim.
Numerele prietene: perechi și șirul alicot
Definiție: Două numere naturale a și b sunt prietene dacă suma divizorilor proprii ai lui a este egală cu b, iar suma divizorilor proprii ai lui b este egală cu a.
Cea mai mică pereche este (220, 284): suma divizorilor proprii ai lui 220 este 284, iar suma divizorilor proprii ai lui 284 este 220. Următoarele perechi sunt (1184, 1210) și (2620, 2924).
Analogie: prietenii care se respectă reciproc
Două persoane sunt prietene adevărate dacă fiecare apreciază exact cât îi dă cealaltă: a îi oferă lui b suma divizorilor proprii ai lui a, iar b îi întoarce lui a exact aceeași sumă. Dacă unul singur dă mai mult decât primește, relația nu este echilibrată, deci numerele nu sunt prietene.
Exemplu: verificarea unei perechi de numere prietene
def suma_divizori_proprii(n):
# Pasul 1: initializam suma cu 0
s = 0
# Pasul 2: parcurgem divizorii posibili pana la jumatate
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
# Pasul 3: returnam suma obtinuta
return s
a, b = map(int, input().split())
# Pasul 4: verificam ambele egalitati
if suma_divizori_proprii(a) == b and suma_divizori_proprii(b) == a:
print("DA, numerele sunt prietene")
else:
print("NU")
Observă: funcția suma_divizori_proprii este apelată de două ori, o dată pentru fiecare număr. Pentru a căuta toate perechile prietene sub o limită, parcurgem perechile (a, b) și verificăm condiția; pentru o căutare eficientă calculăm o singură dată suma pentru fiecare număr și o păstrăm într-un dicționar.
| Pereche | Suma divizorilor proprii ai primului | Suma divizorilor proprii ai celui de-al doilea | Concluzie |
|---|---|---|---|
220 și 284 |
284 | 220 | Sunt prietene |
6 și 28 |
6 | 28 | Nu sunt prietene, dar fiecare este perfect |
1184 și 1210 |
1210 | 1184 | Sunt prietene |
Șirul alicot: pornind de la un număr n și calculând repetat suma divizorilor proprii, obținem un șir: de exemplu, din 220 obținem 284, apoi 220, apoi 284... Dacă șirul se întoarce la n, atunci n are un partener prieten. Dacă șirul se stabilizează la un număr perfect (6, 28, 496...), atunci am ajuns într-un „punct final" al lanțului.
Exercițiu de completare
Completează afirmațiile despre prelucrările integrate:
Dacă n = 2^3 * 3^2, atunci numărul de divizori este (3+1) * (2+1) = ______. Un număr perfect este egal cu suma divizorilor săi ______. Numerele 220 și 284 sunt ______. La descompunere, bucla interioară numără ______ factorului prim.
Bancă de cuvinte:
Exercițiu de completare
Completează codul pentru numărul de divizori din descompunere:
În descompunerea în factori primi pornim cu divizorul ______. Numărul de divizori se inițializează cu ______. La fiecare factor prim cu puterea p înmulțim numărul de divizori cu ______. Suma divizorilor proprii se calculează până la n ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - aplicații integrate:
1. Numărul de divizori ai lui 72 = 2^3 * 3^2 este:
2. Numerele 220 și 284 sunt:
3. Suma divizorilor proprii ai lui 28 este:
Aprofundare
Numărul de divizori fără descompunere: dacă o problemă cere doar numărul de divizori, varianta cu radical (radical = rădăcina pătrată a numărului) este mai simplă: parcurgem d de la 1 la int(n ** 0.5); dacă n % d == 0, adunăm 2 (perechea d și n // d), iar dacă d * d == n, adunăm doar 1 (divizorul din mijloc). Această variantă rulează în sqrt(n) pași, spre deosebire de parcurgerea completă în n pași.
Teorema lui Euclid-Euler: un număr par n este perfect dacă și numai dacă are forma n = 2^(k-1) * (2^k - 1), unde 2^k - 1 este un număr prim (numit prim Mersenne). Pentru k = 2 obținem 6, pentru k = 3 obținem 28, pentru k = 5 obținem 496. Astfel putem genera numere perfecte uriașe verificând doar un număr mic de candidați.
Verificarea prieteniei fără calcul dublu: dacă a = b, numărul este perfect, nu prieten cu sine. În plus, pentru că suma divizorilor proprii ai lui 1 este 0, perechea (1, 0) ar satisface formal egalitățile; problemele exclud valoarea 0, deci verificăm și a > 0 și b > 0 atunci când citim datele de la tastatură.
Eficiența prelucrărilor combinate: pentru un număr n cu până la 10 cifre, descompunerea face cel mult n//2 diviziuni în varianta simplă, dar doar aproximativ sqrt(n) în varianta optimizată. Regula practică: dacă n depășește un milion, folosește variantele optimizate (radical sau descompunere), altfel rularea poate dura prea mult în competiții.
Modularizarea soluțiilor: o problemă integrată se scrie cel mai clar cu funcții: descompunere(n), nr_divizori(n), suma_cifrelor(n), este_perfect(n). Fiecare funcție are o singură sarcină, poate fi testată separat și poate fi refolosită în alte probleme - exact principiul proiectării modulare.
PbInfo - Numărul de divizori (variantă eficientă)
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze numărul total de divizori ai lui n.
Date de intrare:
Programul citește de la tastatură numărul n.
Date de ieșire:
Programul va afișa pe ecran numărul de divizori ai lui n.
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^9. Se recomandă o soluție eficientă, care nu parcurge toate numerele până la n.
Exemplu:
Intrare:
12
Ieșire:
6
Cum gândim soluția:
- Parcurgem cu
fordivizorii d de la 1 laint(n ** 0.5) - Dacă
n % d == 0și d * d este diferit de n, adunăm 2 (perechea d, n // d) - Dacă d * d == n, adunăm doar 1 (pătrat perfect)
- Afișăm numărul total cu
print()
Scrie soluția în Python:
Soluție corectă:
n = int(input())
cnt = 0
for d in range(1, int(n ** 0.5) + 1):
if n % d == 0:
if d * d == n:
cnt = cnt + 1
else:
cnt = cnt + 2
print(cnt)
Ce învățăm: divizorii vin în perechi (d, n // d), deci parcurgem doar până la radicalul lui n. Pentru n = 12: d = 1, 2, 3, iar perechile 12, 6, 4 dau în total 6 divizori.
PbInfo - Numere perfecte sub o limită
Enunț:
Cerință: Se citește un număr natural lim. Să se afișeze, în ordine crescătoare, toate numerele perfecte mai mici sau egale cu lim.
Date de intrare:
Programul citește de la tastatură numărul lim.
Date de ieșire:
Programul va afișa pe ecran, separate prin spațiu, toate numerele perfecte găsite.
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^6.
Exemplu:
Intrare:
500
Ieșire:
6 28 496
Cum gândim soluția:
- Definim funcția
este_perfect(n)care calculează suma divizorilor proprii - Parcurgem cu
fortoate numerele de la 2 la lim - Pentru fiecare număr verificăm cu funcția și afișăm cele perfecte
- Pentru limite mari folosim teorema lui Euclid-Euler, verificând doar formele 2^(k-1) * (2^k - 1)
Scrie soluția în Python:
Soluție corectă:
def este_perfect(n):
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
return s == n
lim = int(input())
for n in range(2, lim + 1):
if este_perfect(n):
print(n, end=" ")
Ce învățăm: funcția este_perfect centralizează verificarea, iar programul principal doar parcurge numerele și afișează rezultatele. Pentru lim = 500 se afișează 6 28 496.
Exercițiul Practic: Aplicații integrate ale prelucrărilor numerice
Sarcini de lucru
Completează următoarele sarcini pentru a integra toți algoritmii numerici ai modulului
Sarcina 1: Descompunere + număr de divizori
Cerință: Scrie un program care citește un număr n, afișează descompunerea lui în factori primi (sub forma „p la puterea e") și numărul total de divizori, calculat din exponenți. Verifică pe hârtie pentru n = 60: descompunerea 2^2 * 3 * 5 dă (2+1) * (1+1) * (1+1) = 12 divizori.
Soluție pentru Sarcina 1:
n = int(input())
d = 2
nr_div = 1
while n > 1:
p = 0
while n % d == 0:
n = n // d
p = p + 1
if p > 0:
print(d, "la puterea", p)
nr_div = nr_div * (p + 1)
d = d + 1
print("Numar de divizori:", nr_div)
Verifică: pentru n = 60 se afișează 2 la puterea 2, 3 la puterea 1, 5 la puterea 1, iar numărul de divizori este 12. Pentru n = 72 rezultatul este 12, iar pentru n = 97 (număr prim) rezultatul este 2.
Sarcina 2: Căutarea perechilor de numere prietene
Cerință: Scrie un program care citește un număr lim și afișează toate perechile (a, b) de numere prietene, cu a mai mic decât b și a, b mai mici sau egale cu lim. Folosește o funcție suma_divizori_proprii și calculează o singură dată suma pentru fiecare număr, păstrând-o într-o listă (indexul = numărul, valoarea = suma divizorilor).
Soluție pentru Sarcina 2:
def suma_divizori_proprii(n):
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
return s
lim = int(input())
sume = [0] * (lim + 1)
for n in range(1, lim + 1):
sume[n] = suma_divizori_proprii(n)
for a in range(1, lim + 1):
b = sume[a]
if a < b and b <= lim and sume[b] == a:
print(a, b)
Verifică: pentru lim = 3000 se afișează 220 284 și 1184 1210. Condiția a < b evită dublarea perechilor, iar lista sume evită recalcularea sumei de două ori pentru fiecare pereche.