Algoritmul lui Euclid in C++

Algoritmul lui Euclid

Buna ziua prieteni, astazi va prezint un alt algoritm folosit: algoritmul lui Euclid. Acest algoritm este o metoda eficienta pentru a calcula cel mai mare divizor comun (cmmdc) a doua numere, cred ca se invata in clasa 5 sau a 6-a, dar pentru cei care au uitat intre-timp, CMMDC a doua numere este cel mai mare numar care divide (sau imparte exact) ambele numere. De exemplu, cmmdc dintre 210 si 189 este 21.

In programare, acest algoritm se foloseste de doua metode diferite: prima metoda este efectuarea unor scaderi repetate, iar cea de a doua metoda se foloseste de impartiri repetate, de-asemenea, eu prefer metoda anterior mentionata datorita simplitatii cu care poate fi scrisa (o sa va arat la final, o metoda recursiva, usor de retinut). Daca tot am adus vorba de programare, trebuie mentionat faptul ca acest algoritm nu este foarte eficient atunci cand calculam cmmdc-ul a doua numere ce apartim sirului lui Fibonacci (o sa explic sirul lui Fibonacci, intr-un alt video).

Inainte de a va prezenta o animatie care explica pe rand cele doua metode ale algoritmului, trebuie sa va mai spun ca acest algoritm, are si o varianta extinsa, insa nu o voi prezenta acum, pentru ca ma adresez in acest video doar celor care se afla acum in clasa 9.

Vom lua cele doua numere mentionate cu putin timp in urma: 210 si 189 si vom scadea din cel mai mare, pe cel mai mic, pana cand cele doua numere, devin egale.

Animatia din videoul de mai sus, la minutul 02:15

Iar acum, vom explica ceea ce se intampla in timpul algoritmului. Prima data, cred ca este destul de clar ca acest algoritm se repeta pana in momentul cand cele doua numere sunt egale, deci putem spune ca avem while(a != b). Apoi, algoritmul continua cu verificarea celui mai mare numar, si scaderea din acesta, a celui de-al doilea numar, asa ca vom scrie.. Iar la final, rezultatul este stocat in a (sau b, deoarece sunt egale), si il vom afisa.

int a, b;
cin >> a;
cin >> b;

while(a != b)
{
    if(a > b)
        a = a - b; 
    if(b > a)
        b = b - a; 
}

cout << a;

Din cate ati vazut, algoritmul se repeta in destul de multi pasi, asa ca vom intervenii cu cea de a doua metoda: metoda prin impartiri repetate

Animatia din videoul de mai sus, la minutul 05:39

Explicatia este asemanatoare cu cea a primei metode: algoritmul se repeta pana in momentul in care cel de-al doilea numar devine 0 (deci avem, while (b != 0) ), iar primul numar va prelua valoarea celui de-al doilea numar, iar cel de-al doilea numar va lua valoarea restului impartirii dintre a si b.

int a, b, r;
cin >> a;
cin >> b; 
while(b != 0) 
{
  r = a % b;
  a = b;
  b = r; 
}
cout << a;

Iar metoda recursiva (ce deriva din cea de a doua metoda), care ne scuteste de multe randuri in plus, este sa scriem o functie de tip int si sa ne folosim de recursivitatea ce o invatam in clasa a 10-a.

int GCD(int A, int B) 
{
    if(!B)
        return A;
    return GCD(B, A%B); 
}

GCD – Greater Common Divisor (adica CMMDC – in limba engleza), imi place sa scriu denumirile functiilor in limba engleza  :sleepy:

Daca aveti intrebari sau nelamuriri, va rog sa le lasati mai jos.