Strona główna » Algorytmy » 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.

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

  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:

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

Ćwiczenia

  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.
  2. Zapisz algorytm Euklidesa przy użyciu jak najmniejszej liczby znaków.