Ai nevoie de meditații? Alege eQualifai și învață fără stres.

Ce este algoritmul lui Euclid?

Există două moduri diferite de a rezolva aceeași problemă de matematică, și anume aflarea celui celui mai mare divizor comun.

Un mod este scăderea repetată, iar celălalt este împărțirea repetată.
Scăderea repetată este mai ușor de scris.

Pentru algoritmul prin scăderi repetate, se scade cel mai mic număr din cel mai mare, până când acestea sunt egale. Valoarea unde amândouă sunt egale, este cel mai mare divizor comun.

Exemplu:

Pentru algoritmul prin împărțiri repetate, se împarte cel mai mare număr la cel mai mic, cel mare ia valoarea celui mic, iar cel mic ia valoarea restului, până împărțirea are restul 0. Vom folosi operația % care are ca rezultat restul împărțirii a două numere.

Exemplu:

După cum se poate observa, algoritmul prin împărțire a ajuns la același rezultat cu mai puține operații. Acest lucru poartă denumirea de eficiență în programare, și este parte din barem la ultima problemă de informatică de la bac.

Cum se scrie Algoritmul lui Euclid în C++?

Aici găsești teste de antrenament la informatică.

Următorul cod C++ reprezintă algoritmul lui Euclid prin scădere, așa cum este predat la liceu:

// Inițializăm și citim cele două numere întregi
int a, b;
cin >> a;
cin >> b;

// Stabilim condiția ca a să fie diferit de b
while(a != b) 
{
    /* Numărul mai mare, devine
    diferența dintre el și 
    numărul mai mic */
    if(a > b)
        a = a - b;
    else
        b = b - a; 
}
// Afișăm numărul.
cout << a;

Următorul cod C++ reprezintă algoritmul lui Euclid prin împărțire, așa cum este predat la liceu:

// Inițializăm și citim cele două numere întregi,
// Plus variabila r (rest)
int a, b, r;
cin >> a;
cin >> b;

// Stabilim condiția ca a să fie diferit de b
while(b != 0) 
{
    /* dacă b este mai mare decât a, r va fi
    a-ul inițial, astfel că la a doua iterație,
    a va fi întotdeauna numărul mai mare. După
    care, când b = r = 0, se iese din while */
    r = a % b;
    a = b;
    b = r; 
}
// Afișăm numărul
cout << a;

Pentru orice neclarități, ne poți găsi pe Instagram.

Echipa bac simplu este recunoscătoare oricui lasă un comentariu !