Ce vei învăța astăzi?
După această lecție vei recapitula toți algoritmii modulului și vei rezolva probleme integrate asemănătoare celor de la evaluare.
Tabel rezumativ: întregul modul într-o privire
Definiție: Modulul 3 a acoperit prelucrările numerice: operații cu cifrele, parcurgerea cifrelor, divizori și multipli, descompunerea în factori primi, algoritmul lui Euclid și transformările între baze. Tabelul de mai jos rezumă fiecare algoritm, operația principală și un exemplu.
| Lecția | Algoritm / concept | Operație principală | Exemplu |
|---|---|---|---|
| Ora 1 | Ultima cifră, eliminare, adăugare | n % 10, n // 10, n * 10 + c |
1234 % 10 = 4 |
| Ora 2 | Oglindit, palindrom, numărul de cifre | og = og * 10 + n % 10 |
oglinditul lui 1234 = 4321 |
| Ora 3 | Divizori, numere prime, numere perfecte | n % d == 0 |
divizorii lui 12: 1 2 3 4 6 12 |
| Ora 4 | Descompunerea în factori primi | n // d cât timp n % d == 0 |
72 = 2^3 * 3^2 |
| Ora 5 | CMMDC (Euclid), CMMMC | a, b = b, a % b |
CMMDC(24, 36) = 12 |
| Ora 6 | Conversii între baze | n % 2, n // 2, z = z * 2 + cifra |
10 = 1010(2) |
| Ora 7 | Recapitulare: prelucrări combinate | combinarea algoritmilor | suma cifrelor + cifre pare |
| Ora 8 | Divizorii în contexte practice | divizori + CMMDC în probleme reale | 220 și 284 sunt prietene |
| Ora 9 | Aplicații integrate | descompunere + divizori + cifre | 72 are 12 divizori |
Recapitularea algoritmilor cheie
Orice problemă din acest modul se rezolvă combinând patru familii de algoritmi: prelucrarea cifrelor (while n > 0), căutarea divizorilor (for cu %), algoritmul lui Euclid (a, b = b, a % b) și conversiile între baze (resturi la 2).
Exemplu: analizor numeric complet (program care calculează mai multe caracteristici ale unui număr: numărul de cifre, suma cifrelor, oglinditul și verdictul de palindrom) pentru n
n = int(input())
x = n
# Pasul 1: parcurgem cifrele o singura data
cnt = 0
s = 0
og = 0
while x > 0:
c = x % 10
cnt = cnt + 1
s = s + c
og = og * 10 + c
x = x // 10
# Pasul 2: numarul de divizori, eficient, cu radical
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
# Pasul 3: afisam toate rezultatele
print("Numar de cifre:", cnt)
print("Suma cifrelor:", s)
print("Oglinditul:", og)
if og == n:
print("Palindrom")
else:
print("Nu este palindrom")
print("Numar de divizori:", nr_div)
Observă: un singur pasaj prin cifre produce patru rezultate (număr de cifre, sumă, oglindit, palindrom), iar numărul de divizori folosește varianta cu radical, deci programul rămâne rapid chiar și pentru n cu 10 cifre.
Strategia de rezolvare a problemelor de evaluare
Metoda în 5 pași: orice problemă de evaluare se rezolvă sistematic: (1) citim cu atenție cerința și datele de intrare, (2) identificăm algoritmii necesari, (3) scriem soluția în pseudocod pe caiet, (4) o implementăm în Python comentat pe pași, (5) o testăm cu exemple și cazuri limită.
Analogie: rețeta unui bucătar
Un bucătar nu începe să gătească fără să citească rețeta: întâi strânge ingredientele (datele), apoi urmează pașii (algoritmul), gustă la final (testează) și corectează dacă este nevoie. La fel, rezolvarea unei probleme de programare începe pe hârtie, nu la tastatură.
datele de intrare și restricțiile
pseudocodul, apoi codul Python
testarea cu exemple și cazuri limită
Exemple de cazuri limită de testat
- n = 0: bucla
while n > 0nu se execută; numărul de cifre trebuie tratat separat (0 are o cifră). - n = 1: nu este prim, are un singur divizor, descompunerea nu afișează nimic.
- Cifre identice: 111 este palindrom; oglinditul este el însuși.
- Număr prim: 97 are exact 2 divizori; descompunerea afișează 97 la puterea 1.
- Pătrat perfect: 144 are 15 divizori (număr impar de divizori).
Exercițiu de completare
Completează afirmațiile despre recapitularea modulului:
Oglinditul se construiește cu og = og * 10 + n ______ 10. Un număr prim are exact ______ divizori. CMMDC se calculează cu algoritmul lui ______. Conversia în baza 2 se face cu resturile împărțirilor la ______.
Bancă de cuvinte:
Exercițiu de completare
Completează codul algoritmului lui Euclid:
În Euclid cu împărțiri repetate, bucla rulează cât timp ______ != 0. La fiecare pas calculăm restul ______ = a % b, apoi a = b și b = r. La final, ______ este CMMDC. CMMMC se obține cu formula a * b // ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - recapitulare finală:
1. Oglinditul numărului 2024 este:
2. Numărul 496 este:
3. Numărul 13 în baza 2 este:
Aprofundare
Pregătirea pentru evaluare: exersează rezolvând pe hârtie, cu pseudocod, apoi în Python: oglinditul și palindromul (Ora 2), numărul de divizori și numerele perfecte (Ora 3), descompunerea în factori primi (Ora 4), CMMDC și CMMMC (Ora 5) și conversia în baza 2 (Ora 6). La test, punctajul se acordă și pentru corectitudinea pașilor, nu doar pentru rezultatul final.
Cazuri care „păcălesc" programele: n = 0 la numărarea cifrelor, numere cu zerouri în interior (ex: 1001), numere prime mari la descompunere și pătrate perfecte la numărarea divizorilor. Un program bine testat răspunde corect la toate.
Eficiența în contextul evaluării: restricțiile problemelor indică de obicei varianta cerută: dacă n poate ajunge la 10^9, parcurgerea de la 1 la n ar depăși timpul admis, deci folosim radicalul sau descompunerea. Dacă n este mic (sub 1000), și varianta simplă este acceptată.
Legătura cu modulele următoare: prelucrările numerice stau la baza algoritmilor pe șiruri de caractere (verificarea unui palindrom ca șir), a lucrului cu liste (filtrarea numerelor prime dintr-o listă) și a teoriei grafurilor (CMMDC apare în algoritmi de optimizare). Ceea ce ai învățat aici se reutilizează în tot restul clasei.
Autoevaluare: înainte de test, verifică-ți singur: știi să construiești oglinditul fără să te uiți în cod? Știi de ce bucla lui Euclid se oprește? Știi de ce resturile împărțirilor la 2 se citesc invers? Dacă poți explica aceste întrebări cu voce tare, ești pregătit pentru evaluare.
PbInfo - Oglinditul unui număr
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze oglinditul lui n.
Date de intrare:
Programul citește de la tastatură numărul n.
Date de ieșire:
Programul va afișa pe ecran oglinditul lui n.
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.
Exemplu:
Intrare:
1234
Ieșire:
4321
Cum gândim soluția:
- Inițializăm
og = 0 - Repetăm cât timp
n > 0:og = og * 10 + n % 10, apoin = n // 10 - Afișăm og cu
print()
Scrie soluția în Python:
Soluție corectă:
n = int(input())
og = 0
while n > 0:
og = og * 10 + n % 10
n = n // 10
print(og)
Ce învățăm: oglinditul se construiește adăugând fiecare cifră la dreapta numărului nou. Atenție: după buclă, n este 0, deci dacă mai avem nevoie de valoarea inițială o salvăm înainte.
PbInfo - CMMDC a două numere (Euclid)
Enunț:
Cerință: Se citesc două numere naturale a și b. Să se afișeze cel mai mare divizor comun al lor.
Date de intrare:
Programul citește de la tastatură numerele a și b, separate printr-un spațiu.
Date de ieșire:
Programul va afișa pe ecran CMMDC-ul celor două numere.
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.
Exemplu:
Intrare:
24 36
Ieșire:
12
Cum gândim soluția:
- Citim a și b cu
input().split()șimap(int, ...) - Aplicăm algoritmul lui Euclid cu împărțiri repetate:
while b != 0 - La fiecare pas:
r = a % b; a = b; b = r - Afișăm a, care este CMMDC
Scrie soluția în Python:
Soluție corectă:
a, b = map(int, input().split())
while b != 0:
r = a % b
a = b
b = r
print(a)
Ce învățăm: algoritmul lui Euclid reduce problema la perechi din ce în ce mai mici, până când b devine 0, iar a rămâne CMMDC. Pentru 24 și 36: resturile sunt 12, apoi 0, deci rezultatul este 12.
Exercițiul Practic: Recapitulare și pregătire pentru evaluare
Sarcini de lucru
Rezolvă cele două probleme complete, asemănătoare cu cele de la evaluarea finală
Sarcina 1: Palindrom și număr de cifre
Cerință: Scrie un program care citește un număr n și afișează: numărul de cifre, oglinditul și mesajul „DA" dacă n este palindrom, altfel „NU". Salvează n înainte de buclă. Verifică pe hârtie pentru n = 12321: 5 cifre, oglinditul 12321, DA.
Soluție pentru Sarcina 1:
n = int(input())
x = n
cnt = 0
og = 0
while x > 0:
cnt = cnt + 1
og = og * 10 + x % 10
x = x // 10
print("Numar de cifre:", cnt)
print("Oglinditul:", og)
if og == n:
print("DA")
else:
print("NU")
Verifică: pentru n = 12321 se afișează „Numar de cifre: 5", „Oglinditul: 12321" și „DA". Pentru n = 1234 se afișează „NU", pentru că oglinditul 4321 este diferit.
Sarcina 2: Număr perfect sau descompunere
Cerință: Scrie un program care citește un număr n și afișează descompunerea în factori primi („p la puterea e" pentru fiecare factor). Dacă n este perfect, afișează și mesajul „Numar perfect". Verifică pentru n = 28: descompunerea 2^2 * 7 și mesajul „Numar perfect".
Soluție pentru Sarcina 2:
n = int(input())
x = n
# Pasul 1: suma divizorilor proprii (pentru verificarea perfectului)
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
# Pasul 2: descompunerea in factori primi
d = 2
while x > 1:
p = 0
while x % d == 0:
x = x // d
p = p + 1
if p > 0:
print(d, "la puterea", p)
d = d + 1
# Pasul 3: verificarea proprietatii de numar perfect
if s == n:
print("Numar perfect")
Verifică: pentru n = 28 se afișează „2 la puterea 2", „7 la puterea 1" și „Numar perfect". Pentru n = 30 se afișează descompunerea fără mesajul de perfect.