
Cel mai mare divizor comun (CMMDC) a două numere în C++
Se dau două numere naturale a
și b
și se cere să aflăm CMMDC-ul celor două
numere (c el m ai m are d ivizor c omun).
Exemplu: pentru a = 14
, b = 6
, cmmdc(a, b) = 2
.
În acest articol vorbim despre varianta normală (pentru clasa a IX-a). Pentru varianta recursivă (clasa a X-a), puteți intra pe această lecție.
Ce este CMMDC-ul a două numere?
CMMDC-ul, sau Cel Mai Mare Divizor Comun a două numere naturale a
și b
este un alt număr natural d
cu proprietățile:
-
d | a
șid | b
(d
dividea
șid
divideb
); -
d
este cel mai mare număr posibil.
Cmmdc-ul a două numere poate avea diverse notații: cmmdc(a, b)
, gcd(a, b)
— greatest common divisor, sau chiar mai scurt, (a, b)
.
Determinarea celui mai mare divizor comun în C++
Există câteva metode de a determina cel mai mare divizor comun a două numere
naturale nenule a
și b
. Vom prezenta două variante, ambele bazate pe
același algoritm, algoritmul lui Euclid.
Metoda 1. Algoritmul lui Euclid cu scăderi
Algoritmul lui Euclid cu scăderi este o metodă mai puțin eficientă, însă mai ușor de înțeles. Acest algoritm se bazează pe principiul următor: dacă d | a
și d | b
, atunci d | a - b
(unde a ≥ b
) — dacă d
divide ambele numere, atunci divide și diferența lor.
Iată algoritmul propriu zis:
- cât timp numerele sunt diferite, se scade numărul mai mic din cel mai mare;
- când numerele devin egale, atunci CMMDC-ul lor este chiar numărul lor.
Iată implementarea algoritmului în C++:
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim cele două numere
int a, b;
cin >> a >> b;
while(a != b) {
if(a > b) a = a - b;
else b = b - a;
}
cout << "cmmdc-ul este " << a;
return 0;
}
Metoda 2. Algoritmul lui Euclid clasic (cu împărțiri)
Algoritmul lui Euclid cu împărțiri este mai dificil de înțeles, însă este mai eficient (acesta este algoritmul recomandat pentru rezolvarea problemelor).
Pe scurt, observăm că în codul anterior facem scăderi repetate. Aceste scăderi se pot înlocui cu împărțiri, astfel că algoritmul este următorul:
-
cât timp
b
este diferit de0
,a
primeșteb
, iarb
primește restul împărțirii luia
lab
; -
răspunsul în final se află în
a
.#include
using namespace std;
int main() { //Declarăm și citim cele două numere int a, b; cin >> a >> b; while(b != 0) { int r = a % b; //Restul împărțirii lui a la b a = b; b = r; } cout << "cmmdc-ul este " << a; return 0; }
Alte resurse sau bibliografie
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