Algorytm Euklidesa, wyznaczanie NWD

Algorytm Euklidesa, służy do wyznaczania największego wspólnego dzielnika dowolnie wybranych dwóch liczb naturalnych. Został on stworzony w IV wieku p.n.e. przez Eudoksosa z Knidos.

Pozwala on na wyznaczenie NWD nie rozkładając liczb na czynniki pierwsze. Cały algorytm opiera się na poniższym założeniu:

algorytm-euklidesa

Zasada działania:

  1. Użytkownik musi wprowadzić dwie liczby naturalne, do zmiennych a oraz b;
  2. do zmiennej c przypisujemy resztę z dzielenia a przez b;
  3. zmienną a zastępujemy wartością zmiennej b, a do b przypisujemy wartość c;
  4. jeżeli b = 0 to NWD = a, jeżeli nie przejdź do punktu 2.

Przykładowy program wykorzystujący algorytm Euklidesa (napisany w języku Pascal):

,

Przeczytaj poprzedni wpis:
Sortowanie bąbelkowe, algorytm klasy O(N2)

Algorytm sortowania "bąbelkowego" jest jednym z najprostszych algorytmów służących do sortowania liczb, o złożoności czasowej O(N2) i pamięciowej O(1). Jego nazwa wzięła się...

Zamknij