CMMDC recursiv a două numere naturale în C++

Dându-se două numere naturale a și b, vrem să aflăm CMMDC-ul (c el m ai m are d ivizor c omun) al celor două numere.

Exemplu: pentru a = 4, b = 6, cmmdc(a, b) = 2.

În acest articol vom aborda o soluție folosind o funcție recursivă.

Soluția 1

În primul rând, căutăm cazurile de bază:

  • Pentru a = 0 sau b = 0, cmmdc(a, 0) = cmmdc(0, b) = 0;
  • Pentru a = b, cmmdc(a, b) = cmmdc(a, a) = a;

De asemenea, observăm că cmmdc(a, b) = cmmdc(a - b, b) (considerând a > b).

Cu aceste observații, putem să construim ușor funcția de CMMDC recursiv:

#include <iostream>

using namespace std;

int cmmdcRec(int a, int b) {
    if(a == 0 || b == 0) {
        //Primul caz de bază: cmmdc(a, 0) = 0
        return 0;
    }
    if(a == b) {
        //Al doilea caz de bază: cmmdc(a, a) = a
        return a;
    }
    //Conform observației de mai sus,
    //cmmdc(a, b) = cmmdc(a - b, b), pt a > b
    //cmmdc(a, b) = cmmdc(a, b - a), pt a < b
    if(a > b) {
        return cmmdcRec(a - b, b);
    } else {
        return cmmdcRec(a, b - a);
    }
}

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

Soluția 2 (algoritmul lui Euclid)

Prima soluție merge, însă are complexitate liniară (O(n)). Folosind algoritmul lui Euclid, putem să optimizăm soluția de mai devreme, astfel:

#include <iostream>

using namespace std;

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

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

A doua soluție poate fi un pic mai greu de înțeles, însă este mai scurtă.

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te