Algorytm Euklidesa służy do wyznaczenia największego wspólnego dzielnika (NWD) dwóch liczb całkowitych.
Przydatne wiadomości:
- Największy wspólny dzielnik,
- Liczby całkowite,
- Liczby naturalne,
- Algorytm Euklidesa,
- Modulo,
- Pseudokod,
- Schemat blokowy,
- Schemat blokowy NWD z odejmowaniem – program w Scratch'u,
- Schemat blokowy NWD z dzieleniem – program w Scratch'u.
Największy wspólny dzielnik (NWD) dwóch liczb całkowitych jest największą liczbą naturalną, która dzieli każdą z nich bez reszty.
Uwaga! Najprostsze algorytmy Euklidesa spotykane w podręcznikach dla szkoły podstawowej prawidłowo obliczają NWD tylko dla liczb naturalnych (całkowitych dodatnich) większych od zera.
Algorytm Euklidesa - wersja z odejmowaniem
a, b - liczby naturalne większe od zera
Przykładowy zapis w postaci listy kroków:
- Wprowadź liczby: a, b
- Jeżeli a = b to: przejdź do kroku 5
- Jeżeli a > b to: a = a - b w przeciwnym razie: b = b - a
- Przejdź do kroku 2
- Wyprowadź wynik NWD = a
Ten sam algorytm przedstawiony w postaci schematu blokowego:
Algorytm Euklidesa - wersja z dzieleniem (obliczaniem reszty z dzielenia)
a, b - liczby naturalne większe od zera
Przykładowy zapis w postaci listy kroków:
- Wprowadź liczby: a, b
- Jeżeli b = 0 to: przejdź do kroku 7
- reszta = a mod b
- a = b
- b = reszta
- Przejdź do kroku 2
- Wyprowadź wynik NWD = a
Poniżej algorytm w postaci schematu blokowego:
Działanie tego algorytmu można wypróbować i prześledzić na stronie: Schemat blokowy NWD z dzieleniem.
Inne warianty algorytmu Euklidesa z obliczaniem reszty z dzielenia
Instrukcje wewnątrz pętli mają zmienioną kolejność, a zmienna pomocnicza n wykorzystana jest do zapamiętania początkowej wartości zmiennej b.
Wariant ze sprawdzaniem warunku na końcu pętli.
