Informatică Programare
Cel mai mare divizor comun C++
Cel mai mare divizor comun (CMMDC) în C++ este cel mai mare număr natural care împarte exact două sau mai multe numere întregi. Se calculează folosind algoritmul lui Euclid. De exemplu, CMMDC(12, 18) = 6.
Algoritmul lui Euclid
- 1 Pasul 1 Dacă b = 0, CMMDC(a, b) = a.
- 2 Pasul 2 Altfel, calculează restul r = a % b.
- 3 Pasul 3 Reia cu a = b și b = r până când b devine 0.
Exemplu de cod C++
- Funcția gcd int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
- Testare Pentru a = 56, b = 98, funcția returnează 14.
Algoritmul funcționează și pentru numere negative, dar convertește-le la pozitive în prealabil.