Algorytm Euklidesa

RNO-Wiki

Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych a, b. Bazuje na obserwacji

Opis algorytmu (w pseudokodzie)

     Euklides(a,b)
        1. Jeśli b = 0, to
               o wynik algorytmu to a
               o KONIEC 
        2. w przeciwnym wypadku wykonaj:
               o c := a mod b
               o a := b
               o b := c 
        3. idź do kroku nr 1

Schemat blokowy algorytmu

Implementacja w języku C/C++

Funkcja iteracyjna

int gcd(int a, int b)
{
     int mem;
     while (b!=0)
     {
        mem = b;
        b = a%b
        a = mem;
     }
     return a;
}

Funkcja rekurencyjna

int gcd(int a, int b) // funkcja rekurencyjna
{
     // if (a<b) return gcd(b,a); <--- to nie jest potrzebne, dlaczego?
     if (b==0) return a;
     return gcd(b,a%b);
}

Zobacz także

1. rozszerzony algorytm Euklidesa