Școala Româno-Britanică
Modulul 3 Clasa a IX-a | Python

Ora 5: Algoritmul lui Euclid - CMMDC și CMMMC

Ce vei învăța astăzi: CMMDC prin scăderi repetate și împărțiri repetate, CMMMC

Rezultat practic: Aplici algoritmul lui Euclid pentru CMMDC și calculezi CMMMC cu relația a*b/cmmdc (Competența 1.2).

Competența 1.2 Săptămâna 15

Înainte de a începe

De ce contează? CMMDC (cel mai mare divizor comun: cel mai mare număr care împarte exact ambele numere, de exemplu 12 pentru 24 și 36) rezolvă probleme reale de împărțire egală (tăiere, distribuire, ambalare) și stă la baza simplificării fracțiilor, iar CMMMC (cel mai mic multiplu comun: cel mai mic număr care este multiplu al ambelor numere, de exemplu 12 pentru 4 și 6) apare la sincronizarea evenimentelor periodice.

Ce știi deja?

Știi deja ce este un divizor și cum se testează cu n % d == 0. Găsește divizorii comuni ai lui 24 și 36; cel mai mare dintre ei este chiar CMMDC(24, 36).

Ideea-cheie: Algoritmul lui Euclid (metoda clasică de calcul al CMMDC, prin scăderi sau împărțiri repetate) reduce problema CMMDC(a, b) la CMMDC(b, a % b), repetată până când al doilea număr devine 0; ultimul a este răspunsul.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei ști să calculezi CMMDC cu algoritmul lui Euclid (prin scăderi și prin împărțiri) și CMMMC folosind CMMDC.

Ce sunt CMMDC și CMMMC
Euclid cu scăderi repetate
Euclid cu împărțiri repetate
CMMMC = a * b / CMMDC
Simplificarea fracțiilor

Ce este CMMDC?

Definiție: CMMDC (cel mai mare divizor comun) al două numere a și b este cel mai mare număr care le divide pe amândouă.

De exemplu, divizorii lui 24 sunt 1, 2, 3, 4, 6, 8, 12, 24, iar ai lui 36 sunt 1, 2, 3, 4, 6, 9, 12, 18, 36. Divizorii comuni sunt 1, 2, 3, 4, 6, 12, deci CMMDC(24, 36) = 12.

Analogie

Dacă ai 24 mere roșii și 36 mere verzi și vrei să le împarți în coșuri identice, folosind cât mai multe mere per coș, atunci fiecare coș va avea 12 mere - exact CMMDC.

Euclid cu scăderi repetate

Algoritmul: Cât timp a != b: dacă a > b, scădem a = a - b, altfel b = b - a. La final, a (sau b) este CMMDC.

Exemplu: CMMDC(24, 36) prin scăderi repetate

Python - Euclid cu scăderi
a = 24
b = 36
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
print(a)

Observă: numerele devin tot mai mici până devin egale. Valoarea comună finală (12) este CMMDC.

Euclid cu împărțiri repetate

Algoritmul: Cât timp b != 0: calculăm restul r = a % b, apoi a = b și b = r. La final, CMMDC este a.

Exemplu: CMMDC(24, 36) prin împărțiri repetate

ALGORITMUL Euclid cu împărțiri repetate (CMMDC) citește a, b cât timp b != 0 execută r <- a % b a <- b b <- r sfârșit cât timp scrie a // a este CMMDC
Python - Euclid cu împărțiri
a = 24
b = 36
while b != 0:
    r = a % b
    a = b
    b = r
print(a)

Observă: această variantă este mult mai rapidă decât scăderile repetate, mai ales pentru numere mari.

CMMMC și simplificarea fracțiilor

Definiție: CMMMC (cel mai mic multiplu comun) se calculează cu formula: CMMMC(a, b) = a * b // CMMDC(a, b).

De exemplu: CMMMC(4, 6) = 4 * 6 // 2 = 12.

Simplificarea fracțiilor: o fracție a/b se simplifică împărțind numărătorul și numitorul la CMMDC(a, b).

Exemplu CMMDC CMMMC
CMMDC(24, 36) 12 24 * 36 // 12 = 72
CMMDC(4, 6) 2 4 * 6 // 2 = 12
CMMDC(12, 18) 6 12 * 18 // 6 = 36

Exercițiu de completare

Completează codul pentru Euclid cu împărțiri repetate:

În algoritmul lui Euclid cu împărțiri repetate folosim bucla ______ ______ != 0. Calculăm restul ______ = a % b, apoi facem a = b și b = r. La final, CMMDC este a, iar condiția de oprire este când b devine ______.

Bancă de cuvinte:
while b r 0

Test de înțelegere

Test rapid - CMMDC și CMMMC:

1. CMMDC(12, 18) este:

2. În algoritmul lui Euclid cu împărțiri, bucla continuă cât timp b:

3. CMMMC(4, 6) este:

Test de înțelegere - suplimentar

Test rapid suplimentar - CMMDC și CMMMC:

1. CMMDC(8, 12) este:

2. CMMMC(6, 8) este:

3. În pasul algoritmului lui Euclid, a și b devin:

Ai grijă la: în Euclid cu împărțiri, atribuirile trebuie făcute simultan: a, b = b, a % b. Dacă scrii a = b, apoi b = a % b, al doilea pas folosește noul a și rezultatul este greșit.

Aprofundare

De ce este corect algoritmul lui Euclid: orice divizor comun al lui a și b divide și restul a % b, deci CMMDC(a, b) = CMMDC(b, a % b). Repetând, ajungem la perechea (CMMDC, 0), iar CMMDC(d, 0) = d. Această proprietate garantează că algoritmul nu ratează niciodată răspunsul.

Eficiența celor două variante: scăderile repetate pot necesita foarte mulți pași (de exemplu, pentru 100000 și 1 ar fi 99999 scăderi), în timp ce împărțirile repetate termină în cel mult de 5 ori mai mulți pași decât numărul de cifre al celui mai mic număr. De aceea, varianta cu împărțiri este preferată în problemele cu valori mari.

CMMDC a trei numere: CMMDC(a, b, c) se calculează în doi pași: mai întâi CMMDC(a, b), apoi CMMDC cu rezultatul și c. Proprietatea de asociativitate ne permite să extindem algoritmul la oricâte numere, într-o buclă.

Aplicații în viața reală: CMMDC este folosit la tăierea a două benzi de lungimi diferite în bucăți egale cât mai mari (de exemplu, 24 cm și 36 cm se taie în bucăți de 12 cm), la simplificarea fracțiilor și la sincronizarea roților dințate în mecanică.

Numere prime între ele: două numere sunt prime între ele dacă CMMDC-ul lor este 1 (de exemplu, 8 și 15). O pereche de numere prime între ele poate fi formată și din două numere compuse, deci verificarea se face doar cu algoritmul lui Euclid.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - CMMDC

Enunț:

Cerință: Se citesc două numere naturale a și b. Să se afișeze cel mai mare divizor comun al lor, folosind algoritmul lui Euclid cu împărțiri repetate.

Date de intrare:

Programul citește de la tastatură numerele a și b, pe aceeași linie.

Date de ieșire:

Programul va afișa pe ecran CMMDC(a, b).

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:
  1. Citim a și b de pe aceeași linie cu split()
  2. Cât timp b != 0, calculăm r = a % b, apoi a = b și b = r
  3. Afișăm a, care este CMMDC
Scrie soluția în Python:
Soluție corectă:
a, b = map(int, input().split())

while b:
    a, b = b, a % b

print(a)

Ce învățăm: atribuirea multiplă a, b = b, a % b face algoritmul lui Euclid foarte scurt și elegant.

PbInfo - CMMMC

Enunț:

Cerință: Se citesc două numere naturale a și b. Să se afișeze cel mai mic multiplu comun al lor.

Date de intrare:

Programul citește de la tastatură numerele a și b, pe aceeași linie.

Date de ieșire:

Programul va afișa pe ecran CMMMC(a, b).

Restricții și precizări:

Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.

Exemplu:

Intrare:

4 6

Ieșire:

12
Cum gândim soluția:
  1. Salvăm valorile inițiale ale lui a și b
  2. Calculăm CMMDC cu algoritmul lui Euclid
  3. Calculăm CMMMC = a_initial * b_initial // CMMDC
  4. Afișăm CMMMC
Scrie soluția în Python:
Soluție corectă:
a, b = map(int, input().split())
ca, cb = a, b

while b:
    a, b = b, a % b

cmmdc = a
cmmmc = ca * cb // cmmdc

print(cmmmc)

Ce învățăm: CMMMC se obține dintr-o singură formulă, folosind CMMDC calculat cu Euclid.

EXERCIȚII PRACTICE

Exercițiul Practic: CMMDC și CMMMC

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre CMMDC și CMMMC

Sarcina 1: Simplifică o fracție

Cerință: Scrie un program care citește un numărător a și un numitor b și afișează fracția simplificată, adică a și b împărțite la CMMDC(a, b).

Soluție pentru Sarcina 1:
a, b = map(int, input().split())
x, y = a, b

while y:
    x, y = y, x % y

c = x
print(a // c, "/", b // c)

Verifică: pentru 12 18 se afișează 2 / 3 (fracția 12/18 s-a simplificat la 2/3).

Sarcina 2: Numere prime între ele

Cerință: Scrie un program care citește două numere a și b și afișează "DA" dacă sunt prime între ele (CMMDC = 1), altfel "NU".

Soluție pentru Sarcina 2:
a, b = map(int, input().split())
x, y = a, b

while y:
    x, y = y, x % y

if x == 1:
    print("DA")
else:
    print("NU")

Verifică: pentru 8 15 se afișează DA; pentru 8 12 se afișează NU.

Scrie pe caiet - De reținut

Titlul lecției

Algoritmul lui Euclid - CMMDC și CMMMC.

Definiția lecției

Lecția ne învață algoritmul lui Euclid, cea mai veche și mai eficientă metodă de calcul al celui mai mare divizor comun a două numere: cât timp b != 0, înlocuim perechea (a, b) cu (b, a % b), până când al doilea număr devine 0, iar ultimul a este CMMDC. Din CMMDC obținem imediat CMMMC-ul cu formula a * b // CMMDC. În viața reală, CMMDC este folosit la tăierea a două benzi de lungimi diferite în bucăți egale cât mai mari, la simplificarea fracțiilor și la distribuirea obiectelor în mod egal, iar CMMMC apare la sincronizarea evenimentelor periodice, de exemplu când două autobuze pleacă din aceeași stație la intervale diferite. De exemplu, CMMDC(24, 36) = 12, iar CMMMC(4, 6) = 12.

Definiții esențiale

Algoritmul cheie - pseudocod

ALGORITMUL Euclid cu împărțiri repetate citește a, b x <- a // salvăm valorile inițiale y <- b cât timp y != 0 execută r <- x % y x <- y y <- r sfârșit cât timp scrie "CMMDC:", x scrie "CMMMC:", a * b // x

Algoritmul cheie - cod Python

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:", cmmdc)
print("CMMMC:", cmmmc)

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

Simplificăm fracția 24 pe 36 la forma ireductibilă, împărțind numărătorul și numitorul la CMMDC-ul lor:

a, b = 24, 36
x, y = a, b
while y != 0:
    x, y = y, x % y
cmmdc = x
print(a // cmmdc, b // cmmdc)

CMMDC(24, 36) = 12, deci programul afișează 2 3: fracția se simplifică la 2 pe 3, exact cum procedăm la matematică.