Strona główna » Algorytmy » Artykuły » Algorytm Euklidesa
 

Algorytm Euklidesa

https://mattomatti.com/a01

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:

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

(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ęć.

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

(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.) bwartość 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:

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

Testowanie funkcji

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

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

Ć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.