Algorytm Euklidesa - oparty na dzieleniu, oparty na odejmowaniu i rekurencyjny

Algorytm Euklidesa to jeden z najstarszych i najprostszych algorytmów do obliczania największego wspólnego dzielnika (NWD) dwóch liczb. Istnieją różne warianty tego algorytmu, w tym wersja oparta na dzieleniu i wersja oparta na odejmowaniu. Poniżej znajdują się szczegółowe opisy obu metod oraz ich implementacje w języku Python.

Algorytm Euklidesa oparty na dzieleniu

Ten wariant algorytmu Euklidesa wykorzystuje operację dzielenia i oblicza resztę z dzielenia dwóch liczb. Główna idea polega na tym, że NWD dwóch liczb a i b jest równy NWD b i reszty z dzielenia a przez b.

Kroki algorytmu

1. Jeśli b jest równe 0, to NWD wynosi a.
2. W przeciwnym razie, oblicz resztę z dzielenia a przez b.
3. Powtórz proces z b i resztą z poprzedniego kroku.

Implementacja algorytmu Euklidesa opartego na dzieleniu w języku Python

def euclidean_gcd_division(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# Przykład użycia
a = 48
b = 18
print(f"NWD({a}, {b}) = {euclidean_gcd_division(a, b)}")

Algorytm Euklidesa oparty na odejmowaniu

W tej wersji algorytmu Euklidesa zamiast dzielenia, używamy odejmowania. Główna idea polega na tym, że NWD dwóch liczb a i b jest taki sam jak NWD a−b i b, jeśli a>b.

Kroki algorytmu

1. Jeśli a jest równe b, to NWD wynosi a (lub b).
2. Jeśli a jest większe od b, od a odejmujemy b.
3. Jeśli b jest większe od a, od b odejmujemy a.
4. Powtarzamy proces, aż a będzie równe b.

Implementacja algorytmu Euklidesa opartego na odejmowaniu w języku Python

def euclidean_gcd_subtraction(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a
# Przykład użycia
a = 48
b = 18
print(f"NWD({a}, {b}) = {euclidean_gcd_subtraction(a, b)}")

Algorytm Euklidesa rekurencyjny

Rekurencyjna wersja algorytmu Euklidesa opiera się na tych samych zasadach co metoda dzielenia, ale implementuje proces w sposób rekurencyjny.

Kroki algorytmu

1. Jeśli b jest równe 0, to NWD wynosi a.
2. W przeciwnym razie, wywołaj funkcję rekurencyjnie z parametrami b i a%b (reszta z dzielenia a przez b).

Implementacja rekurencyjnego algorytmu Euklidesa w języku Python

def euclidean_gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return euclidean_gcd_recursive(b, a % b)
# Przykład użycia
a = 48
b = 18
print(f"NWD({a}, {b}) = {euclidean_gcd_recursive(a, b)}")

Porównanie metod

• Metoda dzielenia jest najbardziej efektywna pod względem liczby operacji i jest szeroko stosowana w praktyce.
• Metoda odejmowania może być mniej efektywna w przypadku dużych liczb, ale jest łatwa do zrozumienia i implementacji.
• Metoda rekurencyjna jest elegancka i łatwa do zrozumienia, ale może prowadzić do głębokiej rekursji dla bardzo dużych liczb, co może być nieefektywne w niektórych środowiskach programistycznych.

Każda z tych metod algorytmu Euklidesa jest przydatna w różnych kontekstach, a wybór odpowiedniej zależy od specyficznych wymagań i ograniczeń danego problemu.