Invatare Atomica

Algoritmul lui Euclid — CMMDC & CMMMC

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege si implementa algoritmul lui Euclid in doua variante (scaderi repetate si impartiri repetate), vei calcula CMMMC folosind CMMDC si vei analiza complexitatea fiecarei variante.

Dupa aceasta lectie vei putea:

  • Sa definesti CMMDC si CMMMC si sa explici relatia dintre ele
  • Sa implementezi algoritmul lui Euclid prin scaderi repetate
  • Sa implementezi algoritmul lui Euclid prin impartiri repetate (varianta clasica)
  • Sa calculezi CMMMC folosind formula CMMMC(a,b) = (a*b) / CMMDC(a,b)
  • Sa compari complexitatea O(max(a,b)) vs O(log(min(a,b))) pentru cele doua variante
  • Sa rezolvi exercitii de tip BAC privind algoritmul lui Euclid

Incearca singur!

Provocare:

Ai doua numere: a = 48 si b = 18. Fara calculator, aplica algoritmul scaderilor repetate pas cu pas pana obtii CMMDC. Scrie fiecare pas.

💡 Ai nevoie de un indiciu?

La fiecare pas, scazi numarul mai mic din cel mai mare. Continui pana cand cele doua numere devin egale.

Traseul complet: 48,18 → 30,18 → 12,18 → 12,6 → 6,6. Gata! CMMDC = 6.

1

1. Ce este CMMDC?

CMMDC(a, b) — Cel Mai Mare Divizor Comun al numerelor a si b — este cel mai mare numar natural pozitiv care imparte exact atat pe a cat si pe b.
Exemplu vizual pentru CMMDC(12, 8):

Divizorii lui 12: 1, 2, 3, 4, 6, 12

Divizorii lui  8: 1, 2,     4, 8

Divizori comuni: 1, 2, 4 → CMMDC = 4

CMMMC(a, b) — Cel Mai Mic Multiplu Comun — este cel mai mic numar natural nenul care este multiplu atat al lui a cat si al lui b. Formula fundamentala:
Formula de legatura CMMDC ↔ CMMMC:

CMMMC(a, b) = (a × b) / CMMDC(a, b)

Exemplu: CMMMC(4, 6) = (4 × 6) / CMMDC(4, 6) = 24 / 2 = 12

2

2. Euclid prin scaderi repetate

Idee: La fiecare pas, scadem numarul mai mic din cel mai mare. Repetam pana cand cele doua numere devin egale. Acel numar comun este CMMDC.

Proprietate matematica: CMMDC(a, b) = CMMDC(a − b, b) daca a > b.
Urmarire pas cu pas — CMMDC(48, 18):

Pas 0: a=48, b=18   (48 ≠ 18, continuam)

Pas 1: 48 > 18 → a = 48 − 18 = 30    a=30, b=18

Pas 2: 30 > 18 → a = 30 − 18 = 12    a=12, b=18

Pas 3: 12 < 18 → b = 18 − 12 =  6    a=12, b=6

Pas 4: 12 >  6 → a = 12 −  6 =  6    a=6, b=6

Pas 5: a == b → CMMDC = 6

Codul Python corespunzator:

# CMMDC prin scaderi repetate
def cmmdc_scaderi(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

print("cmmdc_scaderi(48, 18) =", cmmdc_scaderi(48, 18))
print("cmmdc_scaderi(12, 8) =", cmmdc_scaderi(12, 8))
Output real (rulat cu python):
cmmdc_scaderi(48, 18) = 6
cmmdc_scaderi(12, 8) = 4
Complexitate: O(max(a, b) / CMMDC(a, b)) — in cel mai rau caz proportionala cu max(a, b). Pentru numere mari poate fi extrem de lenta.
3

3. Euclid prin impartiri repetate (varianta clasica)

Idee: La fiecare pas inlocuim perechea (a, b) cu (b, a mod b). Cand b devine 0, CMMDC este valoarea curenta a lui a.

Proprietate matematica: CMMDC(a, b) = CMMDC(b, a mod b).
Urmarire pas cu pas — CMMDC(48, 18):

Pas 1: 48 = 18 × 2 + 12 → (a, b) = (18, 12)

Pas 2: 18 = 12 × 1 +  6 → (a, b) = (12, 6)

Pas 3: 12 =  6 × 2 +  0 → (a, b) = (6, 0)

b = 0 → CMMDC = 6 (valoarea lui a)

Codul Python corespunzator:

# CMMDC prin impartiri repetate
def cmmdc_impartiri(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print("cmmdc_impartiri(48, 18) =", cmmdc_impartiri(48, 18))
print("cmmdc_impartiri(12, 8) =", cmmdc_impartiri(12, 8))
Output real (rulat cu python):
cmmdc_impartiri(48, 18) = 6
cmmdc_impartiri(12, 8) = 4
Complexitate: O(log(min(a, b))) — mult mai eficienta decat varianta prin scaderi, chiar si pentru numere de ordinul miliardelor.
4

4. Calculul CMMMC folosind CMMDC

Formula CMMMC(a, b) = (a × b) / CMMDC(a, b) este valabila pentru orice numere naturale nenule.

Atentie practica: In cod, impartim intai pe a la CMMDC, apoi inmultim cu b. Se evita astfel depasirea (overflow) pentru numere mari: (a // cmmdc) * b. 
# CMMMC folosind CMMDC
def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

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

print("cmmmc(4, 6) =", cmmmc(4, 6))
print("cmmmc(12, 8) =", cmmmc(12, 8))
Output real (rulat cu python):
cmmmc(4, 6) = 12
cmmmc(12, 8) = 24
Verificare manuala:

CMMMC(4, 6): CMMDC(4,6)=2; (4×6)/2 = 24/2 = 12 ✓

CMMMC(12, 8): CMMDC(12,8)=4; (12×8)/4 = 96/4 = 24 ✓

5

5. Comparatie: scaderi vs. impartiri — complexitate

Scaderi repetate: O(max(a, b) / CMMDC(a, b))
Impartiri repetate: O(log(min(a, b)))

Exemplu concret: a = 1 000 000 000, b = 1
• Scaderi: un miliard de pasi!
• Impartiri: un singur pas (1 000 000 000 mod 1 = 0, CMMDC = 1)
Exemplu numaratoare pasi — CMMDC(100, 75):
# Numaratoare pasi scaderi
a, b = 100, 75
pasi = 0
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
    pasi += 1
print("CMMDC =", a, ", pasi scaderi:", pasi)
Output real (rulat cu python):
CMMDC = 25 , pasi scaderi: 3

In acest caz avem doar 3 pasi, deoarece CMMDC(100,75)=25 este relativ mare. Cel mai rau caz apare la numere consecutive de Fibonacci: CMMDC(Fib(n+1), Fib(n)) necesita n pasi prin impartiri.

6

6. Varianta recursiva — Python & C++ EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

La profilul intensiv, algoritmul lui Euclid se implementeaza si recursiv. Subprogramele recursive sunt in programa clasei a X-a exclusiv pentru matematica-informatica si intensiv (Domeniu 3). Aceasta sectiune arata cum stiva de apeluri executa algoritmul.

Cazul de baza: CMMDC(a, 0) = a
Pasul recursiv: CMMDC(a, b) = CMMDC(b, a mod b)

Implementare Python:

# CMMDC recursiv (Python)
def cmmdc_recursiv(a, b):
    if b == 0:
        return a            # caz de baza
    return cmmdc_recursiv(b, a % b)  # pas recursiv

print("cmmdc_recursiv(48, 18) =", cmmdc_recursiv(48, 18))
print("cmmdc_recursiv(12, 8) =", cmmdc_recursiv(12, 8))
Output real (rulat cu python):
cmmdc_recursiv(48, 18) = 6
cmmdc_recursiv(12, 8) = 4

Acelasi algoritm in C++:

#include <iostream>
using namespace std;

int cmmdc_recursiv(int a, int b) {
    if (b == 0) return a;
    return cmmdc_recursiv(b, a % b);
}

int main() {
    cout << "cmmdc_recursiv(48, 18) = " << cmmdc_recursiv(48, 18) << endl;
    cout << "cmmdc_recursiv(12, 8) = " << cmmdc_recursiv(12, 8) << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, apoi rulat):
cmmdc_recursiv(48, 18) = 6
cmmdc_recursiv(12, 8) = 4
Stiva de apeluri pentru CMMDC(48, 18):

cmmdc_recursiv(48, 18) → apeleaza

  cmmdc_recursiv(18, 12) → apeleaza

    cmmdc_recursiv(12, 6) → apeleaza

      cmmdc_recursiv(6, 0) → returneaza 6

    ← 6  ← 6  ← 6   (raspuns propagat inapoi)

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire manuala

Aplica algoritmul prin impartiri repetate pentru a calcula CMMDC(56, 98). Scrie fiecare pas in forma a = b × cat + rest. Care este rezultatul?

Raspuns asteptat: 98 = 56×1+42; 56 = 42×1+14; 42 = 14×3+0; CMMDC = 14.

Exercitiul 2 (Nivel standard) — Implementare + CMMMC

Scrie un program Python care citeste doua numere naturale a si b de la tastatura si afiseaza atat CMMDC cat si CMMMC, folosind varianta prin impartiri repetate. Testeaza cu a=36, b=48.

Rezultat asteptat: CMMDC(36,48) = 12; CMMMC(36,48) = 144.

Exercitiul 3 (Nivel performanta) — Problema BAC

Se considera urmatorul algoritm in pseudocod:

CITESTE a, b
cat ← 0
CAT TIMP a ≠ b EXECUTA
    DACA a > b
        ATUNCI a ← a − b
    ALTFEL b ← b − a
    cat ← cat + 1
SCRIE a, cat

a) Ce afiseaza pentru a=30, b=12?   b) Ce calculeaza variabila cat?   c) De ce nu se afiseaza si b la final?

Raspuns: a) 6 3; b) numarul de scaderi efectuate; c) la final a == b, ambele au valoarea CMMDC deci e suficient sa afisam una.

Ce ai invatat astazi

  • CMMDC(a,b) = cel mai mare numar care divide exact atat a cat si b
  • Algoritm Euclid prin scaderi repetate: O(max(a,b)/CMMDC); simplu dar lent
  • Algoritm Euclid prin impartiri repetate: O(log(min(a,b))); rapid si recomandat
  • CMMMC(a,b) = (a × b) / CMMDC(a,b); se calculeaza dupa CMMDC
  • [Intensiv] Varianta recursiva: CMMDC(a,0)=a; CMMDC(a,b)=CMMDC(b, a%b)

Urmatoarea lectie

Continua cu Lectia 3 — Numere prime: verificare primalitate si Ciurul lui Eratostene.

Continua →