Programare Competitivă

CMMDC-ul a două numere

În multe probleme avem nevoie să aflăm cel mai mare număr care divide două valori.

Acest număr se numește CMMDC (Cel Mai Mare Divizor Comun).

Exemplu:

  • pentru 12 și 18, divizorii comuni sunt 1, 2, 3, 6;
  • cel mai mare dintre ei este 6;
  • deci CMMDC(12, 18) = 6.

Ce înseamnă „divizor comun”?

Un număr d este divizor comun pentru a și b dacă:

  • a % d == 0
  • b % d == 0

Iar CMMDC este cel mai mare astfel de d.

Soluția 1 (ineficientă): căutare de la 1 la min(a, b)

Ideea:

  • verificăm toate valorile d de la 1 la min(a, b);
  • dacă d divide ambele numere, îl memorăm;
  • la final, ultima valoare validă este CMMDC.
int a, b;
cin >> a >> b;

int cmmdc = 1;
int limita;
if (a < b) {
    limita = a;
} else {
    limita = b;
}

for (int d = 1; d <= limita; d++) {
    if (a % d == 0 && b % d == 0) {
        cmmdc = d;
    }
}

cout << cmmdc;
Input:
12 18
Output:
6

De ce este ineficientă?

Pentru numere mari, bucla face foarte multe verificări.

Dacă a și b sunt aproape de 10^9, metoda devine lentă.

De ce devine lentă?

Metoda testează fiecare valoare de la 1 la min(a, b).

Pentru numere mari, numărul de verificări este foarte mare, iar timpul de execuție crește mult.

Soluția 2: Algoritmul lui Euclid prin scăderi

Ideea matematică:

CMMDC-ul a două numere nu se schimbă dacă îl înlocuim pe cel mai mare cu diferența dintre ele.

Adică:

  • dacă a > b, înlocuim a cu a - b;
  • dacă b > a, înlocuim b cu b - a;
  • repetăm până când a == b.

Atunci valoarea comună este CMMDC.

int a, b;
cin >> a >> b;

while (a != b) {
    if (a > b) {
        a = a - b;
    } else {
        b = b - a;
    }
}

cout << a;
Input:
12 18
Output:
6

Explicație pas cu pas pentru 12 și 18

  • (12, 18) -> 18 este mai mare -> devine 18 - 12 = 6 -> (12, 6)
  • (12, 6) -> 12 este mai mare -> devine 12 - 6 = 6 -> (6, 6)
  • numerele sunt egale -> CMMDC este 6.

Observație

Metoda prin scăderi este mai bună decât cea ineficientă, dar poate avea multe iterații când numerele sunt foarte diferite.

Soluția 3 (cea eficientă): Algoritmul lui Euclid prin rest

Ideea matematică:

CMMDC(a, b) = CMMDC(b, a % b) pentru b != 0.

Pași:

  1. cât timp b este diferit de 0;
  2. calculăm restul r = a % b;
  3. mutăm valorile: a = b, b = r;
  4. când b devine 0, răspunsul este a.
int a, b;
cin >> a >> b;

while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
}

cout << a;
Input:
12 18
Output:
6

Explicație pas cu pas pentru 12 și 18

  • (a, b) = (12, 18) -> r = 12 % 18 = 12 -> (a, b) = (18, 12)
  • (18, 12) -> r = 18 % 12 = 6 -> (12, 6)
  • (12, 6) -> r = 12 % 6 = 0 -> (6, 0)
  • b este 0 -> ne oprim -> CMMDC este 6.

De ce este cea mai bună metodă?

  • are puține iterații;
  • funcționează foarte bine pentru numere mari;
  • este metoda standard folosită în concursuri și în practică.
Proprietatea-cheie a algoritmului lui Euclid

CMMDC(a, b) rămâne același dacă înlocuim perechea (a, b) cu (b, a % b).

Această transformare micșorează rapid valorile și de aceea metoda este foarte eficientă.

Comparație rapidă între metode

  • Căutare 1 ... min(a, b) -> simplă, dar lentă.
  • Euclid prin scăderi -> mai bună, dar încă poate fi lentă.
  • Euclid prin rest -> cea mai eficientă dintre cele trei.

Greșeli frecvente

1. Împărțire la zero în varianta cu rest

Trebuie să verificăm condiția while (b != 0).

2. Uitarea actualizării ambelor valori

În varianta cu rest, după r = a % b, trebuie:

  • a = b
  • b = r

Dacă uităm una dintre atribuiri, algoritmul nu mai funcționează corect.

3. Presupunerea că metoda ineficientă este „destul de bună” pentru orice

La numere mici merge, dar la numere mari poate depăși timpul limită.

Ce să reții

  • CMMDC este cel mai mare divizor comun al a două numere.
  • Există mai multe metode de calcul.
  • Metoda prin căutare este corectă, dar lentă.
  • Metoda lui Euclid prin scăderi este corectă și mai bună.
  • Metoda lui Euclid prin rest este cea mai eficientă și recomandată.

Probleme

pbinfoCmmdc→

pbinfoCmmdc2→

pbinfoCmmdcn→

Cuprins Inapoi Inainte