Algorytm Euklidesa jest używany już od setek lat i jest jednym z najstarszych znanych sposobów obliczania największego wspólnego dzielnika (NWD). Z jego pomocą można w prosty sposób znaleźć NWD dla dwóch konkretnych wartości, niezależnie od tego, czy są one małe czy bardzo duże. Jest to jeden z tematów, które przeprowadzamy na naszym kursie przygotowującym do matury z informatyki.
Algorytm Euklidesa, opracowany przez Euklidesa w Aleksandrii w III wieku p.n.e., polega na odejmowaniu od siebie dwóch liczb (mniejszej od większej), a następnie podmienianiu większej wartości przez uzyskany wynik. Proces ten powtarza się, dopóki nie uzyska się wartości 0 zamiast jednej z liczb, dzięki czemu uzyskuje się NWD (największy wspólny dzielnik).
NWD (Największy Wspólny Dzielnik) to największa liczba naturalna, która dzieli dwie liczby (lub więcej) na wyniki bez reszty.
Algorytm Euklidesa dostępny jest w dwóch formach, czyli z odejmowaniem lub z resztą z dzielenia. Co istotne, można z niego korzystać także w przypadku liczb całkowitych lub zmiennoprzecinkowych.
Złożoność czasowa algorytmu Euklidesa wynosi O(log2(a+b)), przy czym a i b to wejściowe liczby całkowite.
W przypadku odejmowania odejmuje się od siebie dwie liczby (a i b), a uzyskany wynik zamienia z większą z wartości. W momencie, gdy uzyska się wartość 0 (czyli liczby przed odejmowaniem są takie same) zamiast jednej z liczb (a lub b), działanie algorytmu się kończy i uzyskuje się największy wspólny dzielnik (NWD), czyli tę liczbę, która jest większa od 0.
Algorytm Euklidesa wykorzystujący odejmowanie jest stosowany głównie dla małych liczb, bo można oczekiwać, że proces dla małych wartości przebiegnie szybko.
Dla przykładu zastosujemy algorytm Euklidesa wykorzystujący odejmowanie na liczbach 1050 oraz 420.
W tym przypadku 1050 to większa liczba, więc to od niej odejmujemy drugą, czyli 420:
1050 – 420 = 630
Uzyskany wynik zamieniamy z większą z liczb w parze.
Czyli teraz to: 630, 420
Wartość 630 jest większa od 420, dlatego:
630 – 420 = 210
420, 210
420 – 210 = 210
210, 210
210 – 210 = 0
0, 210
Największym wspólnym dzielnikiem (NWD) liczb 1050 oraz 420 jest 210.
Poniżej zapisano algorytm Euklidesa z odejmowaniem w formie schematu blokowego oraz pseudokodu. Skorzystaj z nich, by lepiej zrozumieć działanie metody wykorzystującej odejmowanie.
funkcja AlgorytmEuklidesa_Odejmowanie (zm_a, zm_b)
dopóki zm_a ≠ zm_b wykonuj
jeżeli zm_a > zm_b
zm_a ← zm_a - zm_b
w przeciwnym razie
zm_b ← zm_b - zm_a
zwróć zm_a i zakończOpis pseudokodu - algorytm Euklidesa z odejmowaniem
Każdy z poniższych punktów oznacza kolejną linię w pseudokodzie.
Poniżej znajdziesz implementację algorytmu Euklidesa wykorzystującą odejmowanie w językach Python, C++ oraz Java. Do każdego z języków podano dwie formy implementacji: jedną utworzoną przy pomocy iteracji (pętli), a drugą przy pomocy rekurencji.
# Algorytm Euklidesa z odejmowaniem w formie iteracyjnej
def Iteracyjnie_AlgorytmEuklidesa_Odejmowanie(zm_a, zm_b):
while zm_a != zm_b:
if zm_a > zm_b:
zm_a -= zm_b
else:
zm_b -= zm_a
return zm_a # Zwracanie NWD
print(Iteracyjnie_AlgorytmEuklidesa_Odejmowanie(1050, 420))# Algorytm Euklidesa z odejmowaniem w formie rekurencyjnej
def Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(zm_a, zm_b):
if zm_a == zm_b:
return zm_a
if zm_a > zm_b:
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(zm_a - zm_b, zm_b)
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(zm_b - zm_a, zm_a)
# Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na wynik różnicy zm_b oraz zm_a, natomiast zm_b na zm_a
print(Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(1050, 420))// Algorytm Euklidesa z odejmowaniem w formie iteracyjnej
#include <iostream>
using namespace std;
int Iteracyjnie_AlgorytmEuklidesa_Odejmowanie (int zm_a, int zm_b) {
while (zm_a != zm_) {
if (zm_a > zm_b)
zm_a -= zm_b;
else
zm_b -= zm_a;
}
return zm_a; // Zwracanie NWD
}
int main() {
cout << Iteracyjnie_AlgorytmEuklidesa_Odejmowanie (1050, 420) << endl;
return 0;
}// Algorytm Euklidesa z odejmowaniem w formie rekurencyjnej
#include <iostream>
using namespace std;
int Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie (int zm_a, int zm_b) {
if (zm_a == zm_b)
return zm_a;
if (zm_a > zm_b)
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie (zm_a-zm_b, zm_b);
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie (zm_b-zm_a, zm_a);
// Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na wynik różnicy zm_b oraz zm_a, natomiast zm_b na zm_a
}
int main() {
cout << Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie (1050, 420) << endl;
return 0;
}// Algorytm Euklidesa z odejmowaniem w formie iteracyjnej
public class Main {
static int Iteracyjnie_AlgorytmEuklidesa_Odejmowanie(int zm_a, int zm_b) {
while (zm_a != zm_b) {
if (zm_a > zm_b)
zm_a -= zm_b;
else
zm_b -= zm_a;
}
return zm_a; // Zwracanie NWD
}
public static void main(String[] args) {
System.out.println(Iteracyjnie_AlgorytmEuklidesa_Odejmowanie(1050, 420));
}
}// Algorytm Euklidesa z odejmowaniem w formie rekurencyjnej
public class Main {
static int Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(int zm_a, int zm_b) {
if (zm_a == zm_b)
return zm_a;
if (zm_a > zm_b)
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(zm_a - zm_b, zm_b);
return Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(zm_b - zm_a, zm_a);
// Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na wynik różnicy zm_b oraz zm_a, natomiast zm_b na zm_a
}
public static void main(String[] args) {
System.out.println(Rekurencyjnie_AlgorytmEuklidesa_Odejmowanie(1050, 420));
}
}W przypadku obliczania NWD z resztą z dzielenia należy dzielić przez siebie dwie liczby (a i b), a uzyskaną resztę z dzielenia zamienia się z większą z wartości. W momencie, gdy reszta z dzielenia wynosi 0, a więc jedna z liczb (a lub b) jest równa 0, algorytm zostaje zakończony i uzyskuje się największy wspólny dzielnik (NWD), czyli tę liczbę, która jest większa od 0.
Algorytm Euklidesa wykorzystujący resztę z dzielenia jest wykorzystywany przy dużych liczbach, bo nawet w przypadku bardzo dużych wartości może wykonać cały proces w zaledwie kilku krokach.
Zastosujemy algorytm Euklidesa wykorzystujący metodę reszty z dzielenia na liczbach 1050 oraz 420.
W tym przypadku 1050 to większa liczba, więc dzielimy ją przez 420 i obliczamy resztę:
1050 % 420 = 210
Uzyskany wynik zamieniamy z większą z liczb w parze.
Czyli teraz to: 420, 210
Wartość 420 jest większa od 210, dlatego ponownie obliczamy resztę:
420 % 210 = 0
Teraz mamy: 210, 0
Największym wspólnym dzielnikiem (NWD) liczb 1050 oraz 420 jest 210.
Warto zauważyć, że w tym przypadku zastosowano znak % jako mod lub modulo, czyli dzielenie, które zwraca jako wynik resztę z dzielenia.
Poniżej znajdziesz algorytm Euklidesa z resztą z dzielenia zapisany poprzez schemat blokowy i pseudokod. Z ich pomocą łatwiej zrozumiesz działanie algorytmu.
funkcja AlgorytmEuklidesa_Dzielenie (zm_a, zm_b)
dopóki zm_b ≠ 0 wykonuj
pom ← zm_b
zm_b ← zm_a mod zm_b
zm_a ← pom
zwróć zm_a i zakończOpis pseudokodu - algorytm Euklidesa z dzieleniem
Każdy z poniższych punktów oznacza kolejną linię w pseudokodzie.
Poniżej znajdziesz implementację algorytmu Euklidesa wykorzystującą resztę z dzielenia w językach Python, C++ oraz Java. Do każdego z języków podano dwie formy implementacji: jedną utworzoną przy pomocy iteracji (pętli), a drugą przy pomocy rekurencji.
# Algorytm Euklidesa z resztą z dzielenia w formie iteracyjnej
def Iteracyjnie_AlgorytmEuklidesa_Dzielenie(zm_a, zm_b):
while zm_b != 0:
pom = zm_b
zm_b = zm_a % zm_b
zm_a = pom
return zm_a # Zwracanie NWD
print(Iteracyjnie_AlgorytmEuklidesa_Dzielenie(1050, 420))# Algorytm Euklidesa z resztą z dzielenia w formie rekurencyjnej
def Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(zm_a, zm_b):
if zm_a == 0:
return zm_b
return Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(zm_b % zm_a, zm_a)
# Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na resztę z dzielenia zm_b % zm_a, natomiast zm_b na zm_a
print(Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(1050, 420))// Algorytm Euklidesa z resztą z dzielenia w formie iteracyjnej
#include <iostream>
using namespace std;
int Iteracyjnie_AlgorytmEuklidesa_Dzielenie (int zm_a, int zm_b) {
while (zm_b != 0) {
int pom = zm_b;
zm_b = zm_a % zm_b;
zm_a = pom;
}
return zm_a; // Zwracanie NWD
}
int main() {
cout << Iteracyjnie_AlgorytmEuklidesa_Dzielenie (1050, 420) << endl;
return 0;
}// Algorytm Euklidesa z resztą z dzielenia w formie rekurencyjnej
#include <iostream>
using namespace std;
int Rekurencyjnie_AlgorytmEuklidesa_Dzielenie (int zm_a, int zm_b) {
if (zm_a == 0)
return zm_b;
return Rekurencyjnie_AlgorytmEuklidesa_Dzielenie (zm_b % zm_a, zm_a);
// Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na resztę z dzielenia zm_b % zm_a, natomiast zm_b na zm_a
}
int main() {
cout << Rekurencyjnie_AlgorytmEuklidesa_Dzielenie (1050, 420) << endl;
return 0;
}// Algorytm Euklidesa z resztą z dzielenia w formie iteracyjnej
public class Main {
static int Iteracyjnie_AlgorytmEuklidesa_Dzielenie(int zm_a, int zm_b) {
while (zm_b != 0) {
int pom = zm_b;
zm_b = zm_a % zm_b;
zm_a = pom;
}
return zm_a; // Zwracanie NWD
}
public static void main(String[] args) {
System.out.println(Iteracyjnie_AlgorytmEuklidesa_Dzielenie(1050, 420));
}
}// Algorytm Euklidesa z resztą z dzielenia w formie rekurencyjnej
public class Main {
static int Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(int zm_a, int zm_b) {
if (zm_a == 0)
return zm_b;
return Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(zm_b % zm_a, zm_a);
// Po rekurencyjnym wywołaniu funkcji, następuje zamiana między zm_a na resztę z dzielenia zm_b % zm_a, natomiast zm_b na zm_a
}
public static void main(String[] args) {
System.out.println(Rekurencyjnie_AlgorytmEuklidesa_Dzielenie(1050, 420));
}
}W przypadku systemu dwójkowego istnieje binarna implementacja algorytmu Euklidesa. Wykorzystuje się tam przesunięcia bitowe oraz AND, dzięki czemu to rozwiązanie okazuje się znacznie wydajniejsze od standardowych operacji arytmetycznych.
Natomiast jeśli w ramach programu wykorzystuje się kilka razy algorytm Euklidesa na tych samych liczbach, można śmiało zadbać o zapamiętanie wyników. Dzięki temu wypisuje się je potem ze zmiennej, zamiast ponownie wykonywać działania. Okazuje się to dużym usprawnieniem, szczególnie w przypadku wielkich programów.
Poza tym można zadbać o czytelność kodu, jeśli doda się na początku ustalanie wartości wejściowych jako wartości bezwzględnych, czyli bez znaku minusa. Dzięki temu nie trzeba w późniejszych fragmentach dodawać żadnych warunków (bo algorytm Euklidesa działa dla liczb dodatnich).
Zacznij przygotowania do matury z informatyki już dziś i zdobądź pewność siebie oraz wysokie wyniki!
