Algoritmul lui Euclid ne poate ajuta să determinăm, având 2 numere, cel mai mare divizor comun, printr-o metodă simplă şi eficientă din punctul de vedere al consumului de resurse.
„Un număr întreg d se numește cel mai mare divizor comun a numerelor întregi a și b dacă și numai dacă pentru orice divizor comun c al lui a și b, d este un divizor al lui c.
În cazul în care impunem condiția d>0 este relativ simplu de verificat dacă d este unic. Acest număr se notează cu c.m.m.d.c(a,b), sau mai simplu: (a,b).
Folosind principiul bunei ordonări a numerelor naturale, putem deduce că c.m.m.d.c(a,b) este cel mai mic număr pozitiv care poate fi scris ca o combinație liniară a lui a și b, adică cel mai mic număr natural de forma a*x+b*y, unde x,y sunt numere întregi.”
Sursă: Wikipedia
|
Pseudocod Di: n, m De: n citeşte n, m ┌cât timp n!=m execută │ ┌dacă n>m │ │ atunci n←n-m │ │ altfel m←m-n │ └■ └■ Scrie n |
Limbaj C++ #include <iostream.h>
unsigned int n, m;
main()
{
cin>>n>>m;
while (n=m)
if (n>m)
n=n-m;
else m=m-n;
Cout<<n;
}
|
