Ce vei învăța astăzi?
După această lecție vei ști să aplici divizorii și CMMDC în probleme din viața reală: tăierea materialelor, distribuirea obiectelor, ambalarea produselor și verificarea numerelor prietene.
De ce sunt utili divizorii?
Definiție: Un număr d este divizor al lui L dacă L % d == 0, adică banda poate fi împărțită în bucăți de lungime d fără rest. Toate lungimile posibile ale bucăților egale sunt exact divizorii lui L.
Analogie: tăierea unei benzi
Avem o bandă de material de L centimetri. Vrem să o tăiem în bucăți egale, fără pierderi. O tăietură este posibilă doar dacă lungimea aleasă a bucăților divide exact pe L, adică dacă acea lungime este un divizor al lui L.
Aceeași idee apare la distribuirea a N caiete unui număr de elevi în mod egal: fiecare elev primește același număr de caiete și nu rămâne nimic, deci numărul de elevi trebuie să fie un divizor al lui N.
divizor al lui L, fără rest
L / lungime, număr natural
numărul de elevi divide pe N
Determinarea tuturor posibilităților de tăiere
Idee: pentru o bandă de lungime L, parcurgem toate lungimile posibile d de la 1 la L și păstrăm numai valorile pentru care L % d == 0. Fiecare astfel de valoare este o lungime validă a bucăților.
Exemplu: toate lungimile posibile ale bucăților
L = int(input())
print("Lungimi posibile ale bucatilor:")
for d in range(1, L + 1):
if L % d == 0:
print(d, end=" ")
Observă: pentru L = 12 se afișează 1 2 3 4 6 12. Deci banda de 12 cm poate fi tăiată în bucăți de 1, 2, 3, 4, 6 sau 12 centimetri, fiecare variantă fără pierderi. Numărul de bucăți este L / d.
Numerele prietene
Definiție: Două numere naturale a și b sunt prietene dacă suma divizorilor proprii ai lui a este egală cu b și suma divizorilor proprii ai lui b este egală cu a. Divizorii proprii sunt divizorii mai mici decât numărul.
Cel mai cunoscut exemplu este perechea 220 și 284: suma divizorilor proprii ai lui 220 este 284, iar suma divizorilor proprii ai lui 284 este 220.
Exemplu: verificăm dacă 220 și 284 sunt 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
a = 220
b = 284
if suma_divizori_proprii(a) == b and suma_divizori_proprii(b) == a:
print("220 si 284 sunt numere prietene")
else:
print("Nu sunt numere prietene")
Observă: verificăm împărțitii doar până la n // 2, pentru că niciun divizor propriu nu poate fi mai mare decât jumătatea numărului. Funcția suma_divizori_proprii este apelată pentru ambele numere.
| 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 |
Exercițiu de completare
Completează afirmațiile despre divizorii în contexte practice:
Toate lungimile posibile ale bucăților egale dintr-o bandă de L centimetri sunt ______ lui L. Verificăm cu operația L ______ d == 0. Numărul de bucăți se obține cu L / d, iar distribuirea a N caiete este posibilă când numărul de elevi divide pe ______.
Bancă de cuvinte:
Exercițiu de completare
Completează afirmațiile despre numerele prietene:
Numerele 220 și ______ sunt prietene. Suma divizorilor proprii ai lui 220 este ______. Numerele 6 și 28 nu sunt prietene, dar fiecare este un număr ______. Suma divizorilor proprii ai lui 6 este ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - divizorii în contexte practice:
1. O bandă de 12 centimetri poate fi tăiată în bucăți egale fără pierderi de lungime:
2. Suma divizorilor proprii ai lui 220 este:
3. Numerele 6 și 28:
Aprofundare
Cazul L = 0 și L = 1: pentru L = 1, singura lungime posibilă este 1, iar bucla afișează corect un singur divizor. Pentru L = 0, împărțirea L % d este 0 pentru orice d, ceea ce ar afișa toate numerele; de aceea restricțiile problemelor exclud valoarea 0, iar în practică o bandă de lungime 0 nu are sens.
Optimizarea căutării divizorilor: pentru L mare, parcurgerea de la 1 la L este lentă. Este suficient să căutăm până la int(L ** 0.5) (radicalul lui L): la fiecare divizor d găsit, afișăm și partenerul L // d. Divizorii obținuți nu mai sunt în ordine crescătoare, deci îi sortăm sau îi afișăm în două faze: întâi perechile mici, apoi cele mari în ordine inversă.
Numărul de bucăți: dacă lungimea bucăților este d, atunci numărul de bucăți este L / d. Pentru a obține numărul minim de bucăți, alegem lungimea maximă, adică pe L însuși: o singură bucată de lungime L. Pentru un număr minim de tăieturi cu bucăți cât mai mari și egale, se folosește CMMDC în probleme cu două benzi de lungimi diferite.
Numerele prietene și șirul alicot: pornind de la un număr și calculând repetat suma divizorilor proprii, obținem șirul alicot (șirul de numere obținut aplicând în mod repetat suma divizorilor proprii). Dacă șirul revine la numărul inițial, perechea este prietenă; dacă se stabilizează într-un număr perfect, am găsit un număr perfect. Perechea (220, 284) este cea mai mică pereche de numere prietene.
Aplicații reale: divizorii apar la împărțirea uniformă a fondurilor între echipe, la planificarea turelor de lucru, la aranjarea produselor în cutii de aceeași capacitate și la alegerea dimensiunilor unui gresie pentru a acoperi perfect o suprafață dreptunghiulară (plăci cu latura egală cu CMMDC al laturilor).
PbInfo - Tăierea benzii
Enunț:
Cerință: Se citește un număr natural L, lungimea unei benzi de material în centimetri. Să se afișeze toate lungimile posibile ale bucăților egale în care poate fi tăiată banda, fără pierderi.
Date de intrare:
Programul citește de la tastatură numărul L.
Date de ieșire:
Programul va afișa pe ecran, în ordine crescătoare, separate prin spațiu, toate lungimile posibile ale bucăților.
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.
Exemplu:
Intrare:
12
Ieșire:
1 2 3 4 6 12
Cum gândim soluția:
- Citim lungimea L cu
input()și o transformăm cuint() - Parcurgem cu
fortoate lungimile posibile d de la 1 la L - Dacă
L % d == 0, atunci d este o lungime validă a bucăților - Afișăm fiecare divizor cu
print(d, end=" ")
Scrie soluția în Python:
Soluție corectă:
L = int(input())
for d in range(1, L + 1):
if L % d == 0:
print(d, end=" ")
Ce învățăm: toate posibilitățile de tăiere a benzii sunt exact divizorii lui L, verificați cu operația L % d == 0.
PbInfo - Numere prietene
Enunț:
Cerință: Se citesc două numere naturale a și b. Să se afișeze "DA" dacă suma divizorilor proprii ai lui a este egală cu b și suma divizorilor proprii ai lui b este egală cu a, altfel "NU".
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 mesajul "DA" sau "NU".
Restricții și precizări:
Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.
Exemplu:
Intrare:
220 284
Ieșire:
DA
Cum gândim soluția:
- Definim funcția
suma_divizori_proprii(n)care adună divizorii mai mici decât n - Parcurgem cu
forde la 1 la n // 2 și verificămn % d == 0 - Citim a și b cu
input().split() - Verificăm cele două egalități și afișăm "DA" sau "NU"
Scrie soluția în Python:
Soluție corectă:
def suma_divizori_proprii(n):
s = 0
for d in range(1, n // 2 + 1):
if n % d == 0:
s = s + d
return s
a, b = map(int, input().split())
if suma_divizori_proprii(a) == b and suma_divizori_proprii(b) == a:
print("DA")
else:
print("NU")
Ce învățăm: folosim o funcție pentru a calcula suma divizorilor proprii pentru ambele numere, apoi comparăm cele două egalități care definesc prietenia.
Exercițiul Practic: Divizorii în contexte practice
Sarcini de lucru
Completează următoarele sarcini pentru a aplica divizorii și CMMDC în probleme reale
Sarcina 1: Ambalarea produselor
Cerință: Scrie un program care citește numărul N de produse și afișează toate posibilitățile de ambalare în pachete egale, fără să rămână produse neambalate: afișează numărul de produse dintr-un pachet pentru fiecare variantă (adică divizorii lui N).
Soluție pentru Sarcina 1:
n = int(input())
print("Numarul de produse dintr-un pachet poate fi:")
for d in range(1, n + 1):
if n % d == 0:
print(d, end=" ")
print()
for d in range(2, n + 1):
if n % d == 0:
print("Numar minim de pachete:", n // d)
break
Verifică: pentru n = 12 se afișează variantele 1 2 3 4 6 12 produse pe pachet. Numărul minim de pachete se obține pentru cel mai mare pachet posibil (divizorul cel mai mare), iar pentru 12 produse minimul este 1 pachet de 12 sau 2 pachete de câte 6.
Sarcina 2: Numere prime între ele
Cerință: Scrie un program care citește două numere și verifică dacă sunt prime între ele, adică dacă CMMDC-ul lor este 1, folosind algoritmul lui Euclid.
Soluție pentru Sarcina 2:
a, b = map(int, input().split())
x, y = a, b
while y != 0:
x, y = y, x % y
cmmdc = x
if cmmdc == 1:
print("DA, numerele sunt prime intre ele")
else:
print("NU, CMMDC este", cmmdc)
Verifică: pentru 8 15 se afișează "DA, numerele sunt prime intre ele", iar pentru 12 18 se afișează "NU, CMMDC este 6".