CMMDC și CMMMC: algoritmul lui Euclid explicat

CMMDC (cel mai mare divizor comun) al două numere naturale este cel mai mare număr care le divide pe amândouă: cmmdc(12, 18) = 6. CMMMC (cel mai mic multiplu comun) este cel mai mic număr nenul divizibil cu amândouă: cmmmc(12, 18) = 36. La BAC informatică apar sub formă de algoritmi în pseudocod pe care trebuie să-i urmărești, ca subprograme cerute la Subiectul III și ca pas intermediar în probleme (simplificarea fracțiilor, numere prime între ele).

Ideea algoritmului lui Euclid

Soluția naivă ar fi să încerci toți divizorii posibili, de la cel mai mic dintre numere în jos. Euclid a observat ceva mult mai eficient: orice divizor comun al lui a și b divide și diferența lor, deci și restul împărțirii lui a la b. Prin urmare cmmdc(a, b) = cmmdc(b, a % b), iar numerele scad foarte repede până când unul devine 0.

Varianta cu resturi

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

Urmărirea pentru a = 48, b = 18:

Rezultatul este 6. Observă că nu contează care număr e mai mare: pentru a = 18, b = 48, primul pas dă r = 18 % 48 = 18, deci numerele doar se inversează și algoritmul continuă normal.

Varianta cu resturi tratează corect și cazul în care unul dintre numere este 0: cmmdc(a, 0) = a, iar pentru a = 0, b = 5 primul pas face a = 5, b = 0 și întoarce 5. Numărul de pași este foarte mic, proporțional cu numărul de cifre (complexitate logaritmică).

În pseudocod, aceeași variantă arată așa:

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

Varianta cu scăderi

Este forma originală a algoritmului și apare des în pseudocodul de la Subiectul II, pentru că se poate „ascunde” ușor:

int cmmdcScaderi(int a, int b)
{
    while (a != b)
        if (a > b)
            a = a - b;
        else
            b = b - a;
    return a;
}

Pentru 48 și 18: (48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6). Se oprește când numerele devin egale, iar rezultatul este 6.

Această variantă are două dezavantaje. Este mai lentă când numerele sunt foarte diferite: pentru (1 000 000, 1) face 999 999 de scăderi, pe când varianta cu resturi face un singur pas. Și, mai grav, intră în buclă infinită dacă unul dintre numere este 0 și celălalt nu: pentru (0, 5), b = b - a lasă b egal cu 5 la nesfârșit. Funcționează corect doar pentru numere nenule.

Varianta recursivă

Relația cmmdc(a, b) = cmmdc(b, a % b) se traduce direct într-o funcție recursivă:

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

Apelurile pentru (48, 18) sunt: cmmdcRec(48, 18) → cmmdcRec(18, 12) → cmmdcRec(12, 6) → cmmdcRec(6, 0), care întoarce 6.

CMMMC: cel mai mic multiplu comun

Între cmmdc și cmmmc există relația a · b = cmmdc(a, b) · cmmmc(a, b). Deci cmmmc(a, b) = a · b / cmmdc(a, b). Pentru 12 și 18: 12 · 18 / 6 = 216 / 6 = 36.

Produsul a * b poate depăși int chiar dacă rezultatul final încape. Scrie împărțirea înaintea înmulțirii, pentru că a se divide exact cu cmmdc-ul:

long long cmmmc(int a, int b)
{
    return 1LL * a / cmmdc(a, b) * b;
}

Atenție: dacă folosești funcția cmmdc cu bucla while, ea lucrează pe copii ale lui a și b (transmitere prin valoare), deci valorile originale rămân disponibile pentru calculul cmmmc. Dacă scrii totul în main, salvează produsul sau copiile înainte de buclă, pentru că după ea b este 0.

Aplicații tipice

• Numere prime între ele: a și b sunt prime între ele dacă cmmdc(a, b) = 1. De exemplu, 8 și 15.
• Simplificarea unei fracții: împarți numărătorul și numitorul la cmmdc. 84/36 are cmmdc 12, deci devine 7/3.
• Cmmdc-ul a n numere: cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c). Pornești cu primul număr și aplici funcția cu fiecare număr citit.

Iată un program complet care citește n numere naturale nenule și afișează cmmdc-ul lor:

#include <iostream>
using namespace std;

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

int main()
{
    int n, x, d;
    cin >> n >> d;           // n, apoi primul număr
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        d = cmmdc(d, x);
    }
    cout << d;
    return 0;
}

Pentru intrarea 4 24 36 60 18 se afișează 6: cmmdc(24, 36) = 12, cmmdc(12, 60) = 12, cmmdc(12, 18) = 6.