Korepetycje Olsztyn
Algorytm Euklidesa

Jak znaleźć największy wspólny dzielnik dwóch liczb, gdy nie da się łatwo rozłożyć ich na czynniki? Algorytm Euklidesa robi to w kilku krokach, a przy tym jest jednym z najstarszych znanych algorytmów. Poniżej wyjaśniamy, jak działa, jak go zapisać i zaimplementować oraz gdzie się go stosuje. Może się sprawdzić na korepetycje Olsztyn.
Co to jest algorytm Euklidesa
To metoda obliczania największego wspólnego dzielnika dwóch liczb całkowitych.
Czym jest NWD i jak oblicza go algorytm Euklidesa?
NWD (po angielsku GCD) to największa liczba całkowita, która dzieli obie liczby bez reszty. Algorytm Euklidesa NWD oblicza przez kolejne dzielenia z resztą, aż reszta będzie równa zero. Ostatni niezerowy dzielnik to szukany wynik.
Kto i kiedy wynalazł algorytm Euklidesa?
Opisał go starożytny grecki matematyk Euklides w dziele „Elementy”, około 300 roku p.n.e. To matematyka starożytna, która nadal jest podstawą w teorii liczb i programowaniu.
Jak działa algorytm Euklidesa
Opiera się na własności: NWD(a, b) = NWD(b, a mod b), gdzie a mod b to reszta z dzielenia a przez b:
NWD(a, b) = NWD(b, a mod b)
Dla liczb a > b > 0 kroki są takie: dzielisz a przez b, zapisujesz resztę r, następnie zastępujesz parę (a, b) parą (b, r) i powtarzasz, aż reszta wyniesie 0.
Algorytm Euklidesa krok po kroku: przykład
Algorytm Euklidesa przykład dla liczb 48 i 18:
- 48 = 2 · 18 + 12
- 18 = 1 · 12 + 6
- 12 = 2 · 6 + 0
Ostatnia niezerowa reszta to 6, więc największy wspólny dzielnik algorytm daje wynik:
NWD(48, 18) = 6
Sprawdzenie: 48 = 6 · 8 i 18 = 6 · 3, a liczby 8 i 3 nie mają wspólnego dzielnika większego od 1.
Zapis w pseudokodzie i schemat blokowy
funkcja NWD(a, b):
dopóki b ≠ 0:
r = a mod b
a = b
b = r
zwróć a
Algorytm Euklidesa schemat blokowy przykład ma trzy elementy: start z wczytaniem a i b, pętlę z warunkiem „b ≠ 0?” (tak: oblicz resztę i podstaw, nie: wypisz a) oraz koniec. To klasyczny przykład iteracji w arytmetyce, który pojawia się w zadaniach z informatyki.
Algorytm Euklidesa w Pythonie i rekurencja
Algorytm Euklidesa przykład w Pythonie, wersja iteracyjna:
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
Na czym polega rekurencyjna wersja algorytmu Euklidesa?
Rekurencyjny algorytm Euklidesa implementacja jest jeszcze krótsza: funkcja wywołuje samą siebie z nową parą liczb:
def nwd(a, b):
if b == 0:
return a
return nwd(b, a % b)
Iteracja i rekurencja dają ten sam wynik. Wersja iteracyjna jest zwykle szybsza i nie zużywa stosu wywołań.
Liczby ujemne, NWW i rozszerzony algorytm
NWD definiuje się dla wartości bezwzględnych, więc przed obliczeniem zamień liczby na ich moduły (np. NWD(−12, 18) = NWD(12, 18) = 6).
Jak zastosować algorytm Euklidesa do obliczania NWW?
Najmniejszą wspólną wielokrotność wyznaczysz ze wzoru:
NWW(a, b) = a · b / NWD(a, b)
Dla 48 i 18: NWW = 48 · 18 / 6 = 144.
Czym różni się algorytm Euklidesa od rozszerzonego algorytmu Euklidesa?
Rozszerzony wyznacza dodatkowo liczby całkowite x i y, dla których a · x + b · y = NWD(a, b). Przydaje się w kryptografii, np. do liczenia odwrotności modulo.
Złożoność obliczeniowa i zastosowania
Algorytm Euklidesa złożoność obliczeniowa wyjaśnienie: liczba kroków rośnie logarytmicznie względem mniejszej z liczb, czyli O(log(min(a, b))), ponieważ co dwa kroki reszta maleje co najmniej o połowę. Dlatego algorytm działa szybko nawet dla bardzo dużych liczb.
Do czego służy algorytm Euklidesa?
Algorytm Euklidesa zastosowanie w programowaniu to m.in.:
- skracanie ułamków do postaci nieskracalnej,
- obliczanie NWW,
- sprawdzanie, czy liczby są względnie pierwsze (NWD równe 1),
- kryptografia, na przykład w algorytmach klucza publicznego,
- zadania z liczbami pierwszymi i arytmetyką modularną.
FAQ
Czy algorytm Euklidesa działa dla dowolnych liczb całkowitych?
Tak, po zamianie na wartości bezwzględne. Gdy jedna z liczb jest zerem, NWD jest równy drugiej liczbie.
Ile kroków potrzebuje algorytm Euklidesa?
Zwykle kilka do kilkunastu, nawet dla liczb o wielu cyfrach, bo liczba kroków rośnie logarytmicznie.
Czy algorytm Euklidesa to to samo co rozkład na czynniki pierwsze?
Nie. Rozkład na liczby pierwsze też pozwala znaleźć NWD, ale jest wolniejszy dla dużych liczb. Algorytm Euklidesa nie wymaga rozkładu.
Jeśli chcesz przećwiczyć arytmetykę i algorytmy z nauczycielem, sprawdź korepetycje z matematyki.

