Strona Główna » Artykuły » Algorytm Euklidesa

Algorytm Euklidesa

Algorytm

Algorytm Euklidesa pozwala na obliczenie największego wspólnego dzielnika (NWD) dwóch liczb a i b, gdzie obie liczby należą do zbioru liczb naturalnych. Metoda ta jest znacznie szybsze od wyszukiwania NWD na podstawie rozkładu wartości a i b na czynniki pierwsze.

W celu wyliczenia dwóch NWD dwóch liczb a i b należy je tak przyjąć, aby a ≥ b. Dopóki a ≠ b należy od a odjąć b. Po każdym odjęciu należy pamiętać, aby zamienić wartości a i b jeśli a < b. Po zakończeniu pętli NWD = a = b.

Przykład

Proces wyliczania NWD(138, 27) można rozpisać następująco:

NWD(138, 27) = NWD(138 - 27, 27) = NWD(111, 27) = NWD(84, 27) = NWD(57, 27) = NWD(30, 27) = NWD(3, 27) = NWD(27, 3) = NWD(3, 3) = 3

Ostatecznym wynikiem jest NWD(138, 27) = 3.

Implementacja

Odejmowanie

Algorytm Euklidesa można zapisać na wiele różnych sposobów. Jeden z nich polega na wykorzystaniu operacji odejmowania w celu uzyskania NWD:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int nwd(int a, int b) {
    while (a != b) {
        if (a < b) {
            b -= a;
        } else {
            a -= b;
        }
    }
    return a;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        static int nwd(int a, int b) {
            while (a != b) {
                if (a < b) {
                    b -= a;
                } else {
                    a -= b;
                }
            }
            return a;
        }

(1.) Funkcja nwd() przyjmuje dwa argumenty a i b. (2.) Dopóki oba argumenty są różne to (3. - 7.) należy odjąć mniejszą liczbę od większej. Na koniec (9.) wystarczy zwrócić a lub b. Jest to szukana wartość NWD(a,b). Warto zauważyć, że funkcja napotyka problem kiedy jedna z wartości wynosi 0. Wtedy program będzie działał w nieskończoność, ponieważ 0 nie będzie zmieniać wartości drugiej zmiennej, która będzie dodatnia, ponieważ wiadomo, że a i b należą do liczb naturalnych.

Modulo

Algorytm Euklidesa można też zapisać przy pomocy funkcji modulo. W tym przypadku będzie jednak potrzebna dodatkowe zmienna, która będzie przechowywać resztę z dzielenia a przez b. Tego typu rozwiązanie jest znacznie lepsze, ponieważ program oblicza szybciej ze względu na fakt, że przy kolejnych iteracjach jest sprawdzany tylko jeden warunek, a nie dwa. Jednak należy pamiętać, że w tym momencie program deklaruje dodatkową zmienną c, która zwiększa zapotrzebowanie programu na pamięć.

1
2
3
4
5
6
7
8
9
int nwd(int a, int b) {
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

1
2
3
4
5
6
7
8
9
        static int nwd(int a, int b) {
            int c;
            while (b != 0) {
                c = a % b;
                a = b;
                b = c;
            }
            return a;
        }

(2.) Zmienna c pozwoli zapamiętać wynik a % b. (3.) Dopóki b jest różne od 0 to: (4.) zapisujemy w c wynik resztę z dzielenia a przez b. Jak wiadomo wynik tej operacji da liczbę, która będzie zarówno mniejsza od a jak i od b, dlatego wystarczy (5.) wartość b przypisać do a, a następnie (6.)b wartość c. W ten sposobób b < a, a co za tym idzie jeśli a = b to reszta z dzielenia a przez b to 0, a wtedy pętla zostaje przerwana, a a zawiera NWD(a,b).

Rekurencja

Algorytm Euklidesa można rozwiązać używając do wyliczeń rekurencji. Nie jest to metoda, która jest przejrzysta, ale spełnia swoje zadanie w tym przypadku. Kod wtedy można zapisać w zaledwie kilku linijkach:

1
2
3
4
5
int nwd(int a, int b) {
    if (a == 0)
        return b;
    return nwd(b % a, a);
}

1
2
3
4
5
        static int nwd(int a, int b) {
            if (a == 0)
                return b;
            return nwd(b % a, a);
        }

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

1
2
3
4
5
6
7
8
9
int main() {
    int a, b;
    cout << "Podaj wartości a i b\na = ";
    cin >> a;
    cout << "b = ";
    cin >> b;
    cout << nwd(a, b) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
        static void Main(string[] args) {
            int a, b;
            Console.Write("Podaj wartości a i b\na = ");
            a = Convert.ToInt32(Console.ReadLine());
            Console.Write("b = ");
            b = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine(nwd(a, b));
        }

Ćwiczenia

Zadanie 1

Napisz program, który wczyta od użytkownia dwie liczby a i b, a następnie wykorzystując dowolny sposób obliczy NWD podanych liczb. W przypadku, gdy wprowadzone są błędne to należy wypisać na ekranie odpowiedni komunikat.

Zadanie 2

Zapisz algorytm Euklidesa przy użyciu jak najmniejszej liczby znaków.