- 2 stycznia 2024
- Posted by: Daria
- Category: Baza wiedzy
Algorytm Euklidesa jest to jeden z najpowszechniejszych i najstarszych algorytmów używanych do tej pory. Służy on do obliczania Największego Wspólnego Dzielnika (NWD), dla dwóch liczb.
Algorytm Euklidesa – metody tradycyjne
Podstawowe pytanie, zadawane przez wielu uczniów brzmi: co to jest algorytm Euklidesa? W dużym skrócie to oryginalna metoda opracowana przez Euklidesa z Aleksandrii w III w. p.n.e. opierająca się na odejmowaniu mniejszej liczby z pary od większej, i podmienianiu wyniku działania za większą wartość. Czynność tę powtarza się do momentu, w którym jedna z liczb nie wynosi 0. W ten sposób można obliczyć NWD, czyli największą możliwą wartość, pozwalającą na podzielenie całkowicie dwóch konkretnych liczb.
Algorytm obejmuje dwa główne sposoby:
- przez odejmowanie,
- przez liczenie reszty z dzielenia.
Algorytm Euklidesa NWD może być stosowany nie tylko dla liczb naturalnych, ale także do liczb całkowitych, wymiernych czy zmiennoprzecinkowych. Złożoność czasowa wynosi O(log2(a+b)), gdzie a i b to wejściowe liczby całkowite.
Co ciekawe, “Elementy” Euklidesa były wykorzystywane jako podręcznik matematyki przez ponad 2000 lat i były podstawą nauki w szkołach na całym świecie.
Algorytm Euklidesa NWD – Kalkulator
NWD: Metoda poprzez odejmowanie
Wytłumaczmy tę metodę na przykładzie dwóch liczb (504, 315):
315 jest mniejszą liczbą z pary, więc odejmujemy ją od 504:
504 – 315 = 189
Wynik różnicy podmieniamy z większą liczbą w parze.
Wygląda to teraz tak: (189, 315)
Różnica jest mniejsza niż 315:
315 – 189 = 126
(189, 126)
189 – 126 = 63
(63, 126)
126 – 63 = 63
(63, 63)
63 – 63 =0
(0, 63) Tutaj kończymy działanie algorytmu, ponieważ otrzymaliśmy liczbę 0.
Największym dzielnikiem liczb 504 i 315 jest 63.
Powyższą metodą byliśmy w stanie uzyskać wynik, to prosty sposób na to jak obliczyć NWD, ale jak możemy sobie wyobrazić, używanie tego algorytmu dla dużych liczb pokroju miliona byłoby bardzo powolne. Istnieje również druga metoda, która zamiast odejmować wykorzystuje resztę z dzielenia, aby znaleźć NWD.
NWD: Metoda poprzez liczenie reszty z dzielenia
Przetestujmy nową metodę na trochę większych liczbach (1230, 528):
1230 % 528 = 174
(174, 528)
528 % 174 = 6
(6, 174)
174 % 6 = 0
(0,6)
Widzimy, że nawet dla tak dużych liczb, algorytm znalazł Największy Wspólny Dzielnik w zaledwie kilku krokach.
Algorytm Euklidesa – schemat blokowy i pseudokod
Pod spodem znajdziesz algorytm Euklidesa zapisany w formie schematu blokowego. Taka forma zapisu umożliwi Ci łatwe zrozumienie tego rozwiązania, niezależnie od tego czy chodzi o metodę wykorzystującą modulo (resztę z dzielenia), czy też odejmowanie.
NWD: Metoda odejmowania – schemat blokowy i pseudokod
1 2 3 4 5 6 7 | funkcja EuklidesOdejmowanie (a, b) dopóki a ≠ b wykonuj jeżeli a > b a ← a - b w przeciwnym razie b ← b - a zwróć a i zakończ |
NWD: Metoda reszty z dzielenia – schemat blokowy i pseudokod
1 2 3 4 5 6 | funkcja EuklidesModulo (a, b) dopóki b ≠ 0 wykonuj zmienna ← b b ← a mod b a ← zmienna zwróć a i zakończ |
Optymalizacja algorytmu Euklidesa
Tak jak w przypadku praktycznie każdego algorytmu, także i tutaj można pokusić się o optymalizację. Można to rozwiązać na różne sposoby:
- Algorytm binarny Euklidesa – informatyka często wykorzystuje działania binarne ze względu na ich szybkość. Dlatego też powstało specjalnie dopasowane rozwiązanie będące zoptymalizowaną wersją algorytmu Euklidesa, która wykorzystuje operacje takie jak przesunięcia bitowe i AND, zamiast standardowych działań arytmetycznych. Działa on szybciej dla wartości z systemu dwójkowego w porównaniu ze standardową implementacją.
- Wykorzystanie pamięci podręcznej – algorytm Euklidesa często jest używany w różnych częściach programu. Można wykorzystać pamięć podręczną (cache) w celu przechowywania wyników obliczeń NWD, aby uniknąć wielokrotnego obliczania dzielnika dla tych samych par liczb. Te wyniki są zawsze takie same, o ile korzysta się z identycznych wartości. Jest to istotne w przypadku programów, gdzie algorytm jest wywołany więcej niż jeden raz.
Poza tym dla poprawy czytelności kodu, rozsądnym rozwiązaniem okazuje się uwzględnianie wartości bezwzględnej – algorytm Euklidesa działa dla dodatnich liczb całkowitych. Jednak jeśli liczby wejściowe mogą być ujemne, warto uwzględnić wartość bezwzględną w celu obliczenia NWD. Na przykład, można użyć funkcji Math.abs() w języku Java, aby uzyskać liczbę bez znaku minusa. Dzięki temu ogranicza się konieczność stosowania większej ilości dodatkowych warunków w przypadku liczb ujemnych.
Zastanówmy się teraz nad implementacją algorytmu znajdowania największego wspólnego dzielnika w C++, Python i Java.
Algorytm Euklidesa – C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include <iostream> using namespace std; // Implementacja algorytmu Euklidesa w formie iteracyjnej int euklidIter (int a, int b) { while (a != b) { if (a > b) a -= b; else b -= a; } return a; // Zwracamy największy wspólny dzielnik } // Implementacja algorytmu Euklidesa w formie rekurencyjnej int euklidRekur (int a, int b) { if (a == b) return a; if (a > b) return euklidRekur (a-b, b); return euklidRekur (b-a, a); // Rekurencyjnie wywołujemy funkcję, zamieniając a na różnicę między b i a, a zmienną b na wartość zmiennej a } // Ulepszona implementacja algorytmu Euklidesa w formie iteracyjnej int betterEuklidIter (int a, int b) { while (b != 0) { int zmienna = b; b = a % b; a = zmienna; } return a; // Zwracamy największy wspólny dzielnik } // Ulepszona implementacja algorytmu Euklidesa w formie rekurencyjnej int betterEuklidRekur (int a, int b) { if (a == 0) return b; return betterEuklidRekur (b % a, a); // Rekurencyjnie wywołujemy funkcję, zamieniając a na resztę z dzielenia b przez a, a b na a } int main() { cout << euklidIter (315, 504) << endl; cout << euklidRekur (315, 504) << endl; cout << betterEuklidIter (1230, 528) << endl; cout << betterEuklidRekur (1230, 528) << endl; return 0; } |
Algorytm Euklidesa – Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | def euclidIter(a, b): while a != b: if a > b: a -= b else: b -= a return a # Zwracamy największy wspólny dzielnik def euclidRecur(a, b): if a == b: return a if a > b: return euclidRecur(a - b, b) return euclidRecur(b - a, a) # Rekurencyjnie wywołujemy funkcję, zamieniając a na różnicę między b i a, a zmienną b na wartość zmiennej a def betterEuclidIter(a, b): while b != 0: zmienna = b b = a % b a = zmienna return a # Zwracamy największy wspólny dzielnik def betterEuclidRecur(a, b): if a == 0: return b return betterEuclidRecur(b % a, a) # Rekurencyjnie wywołujemy funkcję, zamieniając a na resztę z dzielenia b przez a, a b na a print(euclidIter(315, 504)) print(euclidRecur(315, 504)) print(betterEuclidIter(1230, 528)) print(betterEuclidRecur(1230, 528)) |
Algorytm Euklidesa – Java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | public class Main { // Implementacja algorytmu Euklidesa w formie iteracyjnej static int euklidIter(int a, int b) { while (a != b) { if (a > b) a -= b; else b -= a; } return a; // Zwracamy największy wspólny dzielnik } // Implementacja algorytmu Euklidesa w formie rekurencyjnej static int euklidRekur(int a, int b) { if (a == b) return a; if (a > b) return euklidRekur(a - b, b); return euklidRekur(b - a, a); // Rekurencyjnie wywołujemy funkcję, zamieniając a na różnicę między b i a, a zmienną b na wartość zmiennej a } // Ulepszona implementacja algorytmu Euklidesa w formie iteracyjnej static int betterEuklidIter(int a, int b) { while (b != 0) { int zmienna = b; b = a % b; a = zmienna; } return a; // Zwracamy największy wspólny dzielnik } // Ulepszona implementacja algorytmu Euklidesa w formie rekurencyjnej static int betterEuklidRekur(int a, int b) { if (a == 0) return b; return betterEuklidRekur(b % a, a); // Rekurencyjnie wywołujemy funkcję, zamieniając a na resztę z dzielenia b przez a, a b na a } public static void main(String[] args) { System.out.println(euklidIter(315, 504)); System.out.println(euklidRekur(315, 504)); System.out.println(betterEuklidIter(1230, 528)); System.out.println(betterEuklidRekur(1230, 528)); } } |
Powyższe algorytmy NWD są zaimplementowane zarówno w formie iteracyjnej, jak i rekurencyjnej. Jak widzimy, ich składnia nie jest złożona i są podobne do siebie.
Podsumowanie – Algorytm Euklidesa
Algorytm Euklidesa, okazuje się istotny w różnych przypadkach. Skorzystasz z niego zarówno w czasie nauki informatyki w szkole średniej jak i na studiach. Warto więc zapoznać się z tym rozwiązaniem, w wersji iteracyjnej oraz rekurencyjnej. Należy zauważyć, że w momencie gdy NWD wynosi 1, to znaczy, że wartości są liczbami względnie pierwszymi. Jest to ciekawe wykorzystanie tej metody, co przydaje w wykonywaniu rozmaitych zadań matematycznych.
Najczęściej zadawane pytania o algorytm Euklidesa
Gdzie wykorzystuje się algorytm Euklidesa?
- NWD jest przydatny w wielu zagadnieniach matematycznych i inżynieryjnych, takich jak uproszczenie ułamków, czy testowanie wzajemnej pierwszości liczb.
- Algorytm Euklidesa jest wykorzystywany w protokołach kryptograficznych, takich jak RSA, do generowania kluczy publicznych i prywatnych oraz do obliczania odwrotności modularnych.
Jakie są inne metody obliczania NWD oprócz algorytmu Euklidesa?
Wykorzystuje się również klasyczny sposób “na piechotę”. Ten sposób opiera się o sprawdzanie kolejnych dzielników obu liczb, rozpoczynając od największej możliwej wartości. Gdy znaleziony zostanie pierwszy dzielnik, który jest wspólny dla obu liczb, staje się on NWD.
Czy algorytm Euklidesa jest deterministyczny?
Algorytm Euklidesa jest deterministyczny, czyli dla tych samych danych wejściowych zawsze zwraca ten sam wynik. Działanie tego rozwiązania opiera się na prostych regułach matematycznych, które są niezależne od jakiejkolwiek losowości czy zewnętrznych czynników.
Wpisy, które mogą Cię zainteresować:
