Pagina Principală
Ora 14

Cel Mai Mare Divizor Comun (CMMDC)

Învață algoritmul lui Euclid pentru calcularea CMMDC și aplicații practice

40min teorie + 15min probleme PbInfo
Competența 3.3
Sigla liceului
TEORIE - 40 minute

Ce vei învăța astăzi?

După această lecție, vei stăpâni algoritmul lui Euclid și vei putea calcula CMMDC pentru orice numere.

Ce este CMMDC și unde se folosește
Algoritmul lui Euclid (scăderi și împărțiri)
CMMDC pentru mai multe numere
Aplicații practice ale CMMDC

Ce este CMMDC?

Definiție: Cel Mai Mare Divizor Comun (CMMDC) a două numere naturale este cel mai mare număr care divide ambele numere.

Exemplu: CMMDC(12, 18) = 6 deoarece 6 este cel mai mare număr care divide atât pe 12 cât și pe 18.

Regula de aur (foarte important!)

CMMDC(a, b) = CMMDC(b, a % b) deoarece orice divizor comun al lui a și b divide și restul (a % b).

Mini-schemă mentală:

a = b × cât + rest
Dacă un număr divide pe a și pe b, atunci divide și pe rest.

Deci „micșorăm problema” fără să schimbăm răspunsul.

12
→
6
←
18

Divizorii lui 12: 1, 2, 3, 4, 6, 12
Divizorii lui 18: 1, 2, 3, 6, 9, 18
Divizori comuni: 1, 2, 3, 6
Cel mai mare: 6 ✓

Analogie: Bățuri și măsurători

Gândește-te la CMMDC ca la cel mai lung băț care măsoară exact două lungimi diferite:

BĂȚ DE 12cm

Poate fi măsurat cu:

1,2,3,4,6,12 cm
BĂȚ DE 18cm

Poate fi măsurat cu:

1,2,3,6,9,18 cm
BĂȚ COMUN

6cm măsoară ambele

CMMDC = 6
APLICAȚIE

Simplificarea fracțiilor

12/18 = 2/3 (împărțit la 6)

Algoritmul lui Euclid pentru CMMDC

ALGORITM CMMDC_Scaderi VARIABILE a, b: întreg ÎNCEPUT CITESTE a, b // Cât timp numerele sunt diferite ┌ CÂT TIMP a ≠ b EXECUTĂ │ ┌ DACA a > b ATUNCI │ │ a ← a - b │ │ ALTEL │ │ b ← b - a │ └ SFÂRȘIT DACA └■ // Când devin egale, valoarea este CMMDC SCRIE "CMMDC = ", a SFÂRȘIT

Simplu dar ineficient: Pentru a=1000000, b=1, face 999999 de scăderi. Folosit doar pentru înțelegere.

48 - 18 = 30
a=48, b=18 → a=30
30 - 18 = 12
a=30, b=18 → a=12
18 - 12 = 6
a=12, b=18 → b=6
ALGORITM CMMDC_Impartiri VARIABILE a, b, r: întreg ÎNCEPUT CITESTE a, b // Cât timp b nu este 0 ┌ CÂT TIMP b ≠ 0 EXECUTĂ │ r ← a % b // Restul împărțirii │ a ← b // Devine vechiul b │ b ← r // Devine restul └■ // Când b devine 0, a este CMMDC SCRIE "CMMDC = ", a SFÂRȘIT

Eficient și elegant: Algoritmul lui Euclid clasic. Pentru a=1000000, b=1, face 2 iterații în loc de 999999.

48 ÷ 18 = 2 rest 12
48 % 18 = 12
18 ÷ 12 = 1 rest 6
18 % 12 = 6
12 ÷ 6 = 2 rest 0
12 % 6 = 0 → STOP
Metodă Principiu Pentru (48,18) Pentru (1000000,1) Recomandare
Scăderi a-b până sunt egale 7 iterații 999999 iterații ❌ Doar pentru înțelegere
Împărțiri a%b până rest 0 3 iterații 2 iterații ✅ Pentru orice numere

Proprietăți importante:

  1. CMMDC(a, b) = CMMDC(b, a % b)
  2. CMMDC(a, 0) = a (caz de bază)
  3. CMMDC(a, a) = a
  4. Dacă b divide pe a, CMMDC(a, b) = b

Unde folosim CMMDC în viața reală?

Simplificarea fracțiilor

24/36 = 2/3 (împărțind la CMMDC=12)

Matematică - fracții ireductibile

Organizarea petrecerilor

Dacă ai 12 prăjituri și 18 baloane, cea mai mare echipă care primește același număr din fiecare?

CMMDC(12,18)=6 echipe a câte 2 prăjituri și 3 baloane

Pavaj cu pătrate egale

Ai un dreptunghi de 24cm pe 36cm. Care e latura celui mai mare pătrat care îl poate „pava” perfect?

CMMDC(24, 36) = 12 → pătrate de 12cm × 12cm

Criptografie

Algoritmul RSA pentru securitatea online folosește CMMDC

Informatică - algoritmi de securitate

Exercițiu de completare - Algoritmul lui Euclid:

Completează codul C++ pentru calcularea CMMDC:
#include <iostream>
using namespace ______;
______ main() {
    int a, b;
    cin >> a >> ______;
    ______ (b != 0) { // Algoritmul lui Euclid
        int rest = a ______ b; // Calculăm restul împărțirii
        a = ______; // a devine vechiul b
        b = ______; // b devine restul
    }
    cout << ______; // Când b=0, a este CMMDC
    return ______;
}
Bancă de cuvinte:
std int b while % rest a 0

Test de înțelegere: Care este CMMDC?

Test rapid:

Care este CMMDC(56, 98) folosind algoritmul lui Euclid?

Pașii algoritmului:
Pas 1: 56 % 98 = 56 → a=98, b=56
Pas 2: 98 % 56 = 42 → a=56, b=42
Pas 3: 56 % 42 = 14 → a=42, b=14
Pas 4: 42 % 14 = 0 → a=14, b=0
STOP: b=0 → CMMDC = a = ?

Sfaturi practice pentru calculul CMMDC

Începe întotdeauna cu algoritmul lui Euclid

Metoda împărțirilor este cea mai rapidă și funcționează pentru orice numere.

Verifică dacă un număr divide pe celălalt

Dacă a % b == 0, atunci CMMDC = b (numărul mai mic).

Pentru numere prime între ele, CMMDC = 1

Dacă nu au divizori comuni în afară de 1, rezultatul este întotdeauna 1.

Salvează valorile originale dacă ai nevoie de ele

Algoritmul modifică valorile, așa că salvează-le în variabile auxiliare dacă le mai folosești.

Capcane comune și soluții pentru CMMDC

Greșeli frecvente la calculul CMMDC:

❌ Folosirea metodei scăderilor pentru numere mari
while (a != b) { // GREȘIT pentru numere mari! if (a > b) a -= b; else b -= a; }

Soluție: Folosește întotdeauna metoda împărțirilor (algoritmul lui Euclid).

❌ Uitarea că algoritmul schimbă valorile

După algoritm, a și b sunt modificate. Dacă ai nevoie de valorile originale, salvează-le.

int originalA = a, originalB = b; while (b != 0) { // ... algoritmul lui Euclid } // originalA și originalB păstrează valorile inițiale
❌ Neglijarea cazului b=0

CMMDC(a, 0) = a. Algoritmul lui Euclid funcționează corect pentru b=0 (nu intră în buclă).

Best Practices pentru CMMDC:

✅ Folosește întotdeauna algoritmul lui Euclid (metoda împărțirilor)
✅ Verifică dacă ai nevoie de valorile originale - salvează-le
✅ Testează cu numere prime între ele - CMMDC = 1
✅ Testează cazul un număr divide pe celălalt - CMMDC = numărul mai mic
✅ Pentru numere negative, folosește valoarea absolută: CMMDC(|a|, |b|)

Încălzire (2 minute)

Calcul rapid: Scrie doar rezultatul (fără explicații):

  • CMMDC(8, 12) = ___
  • CMMDC(9, 28) = ___
  • CMMDC(25, 10) = ___

Hint: dacă unul divide pe celălalt, CMMDC este numărul mai mic.

PROBLEME PBINFO - 15 minute

PbInfo #11 - CMMDC a două numere

Enunț:

Cerință: Se citesc două numere naturale a și b. Să se calculeze CMMDC al celor două numere.

Date de intrare:

Programul citește de la tastatură numerele a și b.

Date de ieșire:

Programul va afișa pe ecran CMMDC al numerelor a și b.

Exemplu:

Intrare:

48 18

Ieșire:

6

Explicație: Cel mai mare divizor comun al lui 48 și 18 este 6

Cum gândim soluția:
  1. Citim numerele a și b
  2. Aplicăm algoritmul lui Euclid:
    • while (b != 0)
    • rest = a % b
    • a = b
    • b = rest
  3. Când b devine 0, a este CMMDC
  4. Afișăm a
Execuție pentru a=48, b=18:
Iterația 1: b=18≠0 → rest=48%18=12 → a=18, b=12
Iterația 2: b=12≠0 → rest=18%12=6 → a=12, b=6
Iterația 3: b=6≠0 → rest=12%6=0 → a=6, b=0
STOP: b=0 → CMMDC = a = 6 ✓
Ce trebuie să verifici mereu?
  • Cazul a=0 sau b=0: CMMDC(0, x) = x
  • Numere prime între ele: CMMDC = 1
  • Un număr divide pe celălalt: CMMDC = numărul mai mic
  • Numere egale: CMMDC = numărul
  • Ordinea numerelor: CMMDC(a, b) = CMMDC(b, a)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    // Salvăm valorile originale dacă este necesar
    int originalA = a, originalB = b;
    
    // Algoritmul lui Euclid
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    
    // Când b devine 0, a este CMMDC
    cout << a;
    
    return 0;
}
Varianta cu funcție recursivă:
#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << cmmdc(a, b);
    
    return 0;
}

Ce învățăm din această problemă:

  • Algoritmul lui Euclid: Cel mai eficient algoritm pentru CMMDC
  • Recursivitate: Implementare elegantă cu funcție recursivă
  • Cazuri speciale: Funcționează corect pentru orice numere, inclusiv 0
  • Eficiență: Complexitate O(log min(a,b)) vs O(n) pentru metode naive
  • Proprietate fundamentală: CMMDC(a, b) = CMMDC(b, a % b)

PbInfo #12 - CMMDC a n numere

Problemă care calculează CMMDC pentru mai multe numere

Enunț:

Cerință: Se citește un număr n, apoi n numere naturale. Să se calculeze CMMDC al celor n numere.

Date de intrare:

Programul citește de la tastatură numărul n, apoi n numere naturale.

Date de ieșire:

Programul va afișa pe ecran CMMDC al celor n numere.

Exemplu:

Intrare:

4
12 18 24 30

Ieșire:

6

Explicație: Cel mai mare divizor comun al numerelor 12, 18, 24, 30 este 6

Cum gândim soluția:
  1. Citim n
  2. Citim primul număr → acesta devine rezultatul curent
  3. Pentru fiecare din următoarele n-1 numere:
    • Calculăm CMMDC între rezultatul curent și numărul curent
    • Actualizăm rezultatul cu CMMDC-ul găsit
  4. Afișăm rezultatul final
Cum funcționează pentru 12, 18, 24, 30:
Pas 1: rezultat = 12
Pas 2: CMMDC(12, 18) = 6 → rezultat = 6
Pas 3: CMMDC(6, 24) = 6 → rezultat = 6
Pas 4: CMMDC(6, 30) = 6 → rezultat = 6
REZULTAT: 6 ✓
De ce această metodă funcționează?

Folosim proprietatea asociativității CMMDC:

  1. CMMDC(a, b, c) = CMMDC(CMMDC(a, b), c)
  2. CMMDC(a, b, c, d) = CMMDC(CMMDC(a, b, c), d)
  3. Ordinea nu contează: CMMDC este comutativ și asociativ

Formula cheie: rezultat = cmmdc(rezultat, numar) pentru fiecare număr

Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

// Funcție pentru calcularea CMMDC
int cmmdc(int a, int b) {
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    return a;
}

int main() {
    int n;
    cin >> n;
    
    int rezultat;
    cin >> rezultat;  // Citim primul număr
    
    // Pentru fiecare din următoarele n-1 numere
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        rezultat = cmmdc(rezultat, x);
    }
    
    cout << rezultat;
    
    return 0;
}
Varianta cu funcție inline:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int rezultat;
    cin >> rezultat;
    
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        
        // Calculăm CMMDC direct
        int a = rezultat, b = x;
        while (b != 0) {
            int rest = a % b;
            a = b;
            b = rest;
        }
        rezultat = a;
    }
    
    cout << rezultat;
    
    return 0;
}

Ce învățăm din această problemă:

  • Asociativitatea CMMDC: CMMDC(a, b, c) = CMMDC(CMMDC(a, b), c)
  • Algoritm incremental: Pornim cu primul număr și reducem progresiv
  • Cazuri speciale:
  • n=1 → CMMDC = singurul număr
  • Dacă apare 0: CMMDC(0, x) = x (pentru că orice număr divide 0)
  • Numere prime între ele → CMMDC = 1
  • Eficiență: O(n × log(min)) - foarte rapid
EXERCIȚII PRACTICE - 10 minute

Exercițiul Practic: CMMDC și aplicații

Sarcini de lucru

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

Sarcina 1: Analiză algoritm Euclid

Analizează algoritmul lui Euclid pentru calcularea CMMDC:

Pentru a=1071, b=462, câte iterații face algoritmul și care sunt pașii?

Soluție pentru Sarcina 1:

Analiza pentru a=1071, b=462:

  • Algoritmul lui Euclid (metoda împărțirilor):
  • Iterația 1: 1071 % 462 = 147 → a=462, b=147
  • Iterația 2: 462 % 147 = 21 → a=147, b=21
  • Iterația 3: 147 % 21 = 0 → a=21, b=0
  • Rezultat: CMMDC = 21 (după 3 iterații)
  • Verificare:
  • 1071 = 21 × 51
  • 462 = 21 × 22
  • 21 este cel mai mare divizor comun ✓
  • Comparație cu metoda scăderilor:
  • Metoda scăderilor ar face: 1071-462=609, 609-462=147, 462-147=315, 315-147=168, 168-147=21, 147-21=126, 126-21=105, 105-21=84, 84-21=63, 63-21=42, 42-21=21, 21-21=0
  • 12 iterații vs 3 iterații! Algoritmul lui Euclid este mult mai eficient.

Concluzie importantă: Algoritmul lui Euclid (metoda împărțirilor) este exponențial mai rapid decât metoda scăderilor, mai ales pentru numere mari.

Sarcina 2: Implementare în C++ pentru simplificarea fracțiilor

Cerință: Implementează în C++ un program care citește două numere a și b (numărător și numitor) și simplifică fracția folosind CMMDC.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    // Salvăm valorile originale pentru afișare
    int originalA = a, originalB = b;
    
    // Calculăm CMMDC folosind algoritmul lui Euclid
    int x = a, y = b;
    while (y != 0) {
        int rest = x % y;
        x = y;
        y = rest;
    }
    int cmmdc = x;
    
    // Simplificăm fracția
    a = a / cmmdc;
    b = b / cmmdc;
    
    // Afișăm rezultatul
    cout << originalA << "/" << originalB << " = ";
    cout << a << "/" << b << endl;
    
    // Dacă numitorul este 1, afișăm ca număr întreg
    if (b == 1) {
        cout << "sau " << a << " (număr întreg)";
    }
    
    return 0;
}

Explicații importante:

  • Algoritmul lui Euclid: Folosit pentru calcularea CMMDC
  • Salvare valori originale: Pentru a putea afișa fracția inițială
  • Simplificare: Împărțim atât numărătorul cât și numitorul la CMMDC
  • Afișare inteligentă: Dacă numitorul devine 1, afișăm ca număr întreg
  • Teste recomandate:
  • 24/36 → 2/3
  • 15/5 → 3/1 sau 3
  • 7/11 → 7/11 (fracție ireductibilă)
  • 0/8 → 0/1 sau 0

Descarcă toate exercițiile și soluțiile