LECȚIE · CAPITOLUL 2

2.3. CMMDC și CMMMC

Algoritmul lui Euclid prin scăderi și resturi și calculul CMMMC.

DIVIZORI COMUNI

→

EUCLID

→

CMMDC

→

CMMMC

→

APLICAȚII

OBIECTIVE

La finalul lecției vei putea...

CMMDC

Explici cel mai mare divizor comun.

Euclid

Aplici varianta cu scăderi și varianta cu resturi.

CMMMC

Calculezi cel mai mic multiplu comun folosind CMMDC.

Eficiență

Compari cele două variante ale algoritmului.

✓

Checkpoint

În algoritmul lui Euclid cu resturi, când ne oprim?

EXPLICAȚIE

CMMDC, Euclid și CMMMC

2.1. Ce este CMMDC?

Pentru două numere naturale nenule a și b, un divizor comun divide atât pe a, cât și pe b. CMMDC(a,b) este cel mai mare dintre divizorii comuni.

Pentru 24 și 36, divizorii comuni sunt 1, 2, 3, 4, 6, 12, deci CMMDC(24,36)=12.

2.2. Euclid prin scăderi

Dacă x>y, înlocuim x cu x−y; dacă y>x, înlocuim y cu y−x. Repetăm până când x=y.

2.3. Euclid prin resturi

Dacă a=b·q+r, atunci CMMDC(a,b)=CMMDC(b,r). Pentru 84 și 30 obținem 24, apoi 6, apoi 0.

2.4. CMMMC

CMMMC(a,b) este cel mai mic multiplu pozitiv comun. Pentru a,b pozitive: CMMMC(a,b)=a·b/CMMDC(a,b).

EXEMPLU INTUITIV

Două bucăți de bandă și două semafoare

Ai benzi de 24 cm și 36 cm și vrei bucăți egale cât mai mari, fără rest. Lungimea maximă este 12 cm, adică CMMDC(24,36).

Două semafoare repetă ciclurile la 6 și 8 secunde. Prima sincronizare după pornire apare după CMMMC(6,8)=24 secunde.

Activitate: următorul pas

În algoritmul lui Euclid pentru (84,30), după 84 % 30 = 24, ce pereche urmează?

PYTHON

Algoritmul lui Euclid

Varianta cu scăderi

def cmmdc_scadere(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Varianta cu resturi

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

CMMMC

def cmmmc(a, b):
    return a * b // cmmdc(a, b)

Formula folosește CMMDC și este mult mai directă decât enumerarea multiplilor.

ALGORITM / PSEUDOCOD

Algoritmul lui Euclid și CMMMC

citește a, b
cât timp b ≠ 0 execută
    r ← a mod b
    a ← b
    b ← r
sfârșit cât timp
scrie a

CMMMC

citește a, b
d ← CMMDC(a,b)
m ← a · b div d
scrie m

ATENȚIE!

Greșeli frecvente

Oprirea

Nu confundați condiția a=b din varianta cu scăderi cu b=0 din varianta cu resturi.

Ordinea actualizării

Calculați restul înainte de a modifica valorile.

% și //

% este restul, // este câtul întreg.

Testare ≠ verificare

Testarea observă comportamentul pe date; verificarea justifică de ce algoritmul produce rezultatul corect.

EXEMPLU REZOLVAT

CMMDC și CMMMC pentru 84 și 30

Problemă

Se citesc a și b. Determinați CMMDC și CMMMC.

Analiză → Algoritm → Python

Pentru 84 și 30: 84%30=24, 30%24=6, 24%6=0. Ultima valoare nenulă este 6.

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

a = int(input())
b = int(input())
d = cmmdc(a, b)
m = a * b // d
print(d)
print(m)

Urmărirea variabilelor

a	b	r
84	30	24
30	24	6
24	6	0

Testare

Teste: (84,30), numere egale, numere prime între ele și cazul în care unul îl divide pe celălalt.

Verificare

6 divide atât 84, cât și 30 și niciun divizor comun mai mare decât 6 nu le divide pe ambele. CMMMC=84·30/6=420.

EXERCIȚII DE BAZĂ

Aplică direct

Determină CMMDC(18,24) folosind scăderi repetate.
Determină CMMDC(84,30) folosind resturi.
Scrie în pseudocod algoritmul lui Euclid cu resturi.
Scrie un program Python care citește două numere și afișează CMMDC.
Completează pentru 48 și 18 pașii algoritmului lui Euclid.
Calculează CMMMC(12,20) folosind formula bazată pe CMMDC.
Verifică prin enumerarea multiplilor că CMMMC(6,8)=24.
Construiește trei teste pentru funcția cmmdc(a,b).

EXERCIȚII DE APROFUNDARE

Eficiență și aplicații

Compară scăderile și resturile pentru a=1, b=1 000 000.
Tratează explicit cmmdc(25,0) și cmmdc(0,25).
Determină toate perechile 1≤a,b≤20 pentru care CMMDC(a,b)=5.
Două autobuze pleacă la fiecare 12 și 18 minute. După câte minute pleacă simultan?
Un dreptunghi are 84 cm × 126 cm. Determină latura maximă a unei dale pătrate și numărul de dale.
Verifică experimental a·b=CMMDC(a,b)·CMMMC(a,b).
Afișează numărul de repetări ale buclei algoritmului lui Euclid.

VERIFICARE

Verifică ce ai înțeles

MINI-PROIECT

Planificatorul comun

MISIUNE

Dale și semafoare

Construiește o aplicație cu funcția cmmdc și calculează atât latura maximă a unei dale pătrate pentru un dreptunghi, cât și prima sincronizare a două semafoare.

Separă cele două aplicații în funcții.
Afișează pașii lui Euclid pentru un exemplu.
Testează numere egale, prime între ele și valori mai mari.

Criterii

Corectitudine40%

Algoritm25%

Implementare20%

Testare15%

Ai terminat lecția?

Recitește explicațiile și verifică rezultatele înainte de a marca lecția.