Algorytm Euklidesa

1. Wprowadzenie

Algorytm Euklidesa to jedno z najstarszych znanych algorytmicznych rozwiązań matematycznych, stosowane do wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb. Znajduje on szerokie zastosowanie w różnych dziedzinach matematyki, w tym w operacjach na ułamkach.

2. Kołdra patchworkowa a Algorytm Euklidesa

Kołdra patchworkowa składa się z kawałków materiału, które są zszywane w prostokątne lub kwadratowe wzory. Przy jej projektowaniu można wykorzystać algorytm Euklidesa do określenia największego możliwego rozmiaru powtarzających się elementów. Jeśli np. mamy kawałki materiału o wymiarach 24 cm x 18 cm, to największy możliwy kwadratowy element można obliczyć, znajdując NWD(24,18).

3. Największy wspólny dzielnik (NWD)

Największy wspólny dzielnik (NWD) to największa liczba naturalna, która dzieli dane liczby całkowite bez reszty. Przykładowo:

NWD(36, 24) = 12

NWD(48, 18) = 6

4. Algorytm naiwny wyznaczania NWD

Metoda naiwna polega na sprawdzaniu wszystkich dzielników obu liczb i wybieraniu największego wspólnego.

Przykład: Dla liczb 36 i 24:

• Dzielniki 36: {1, 2, 3, 4, 6, 9, 12, 18, 36}
• Dzielniki 24: {1, 2, 3, 4, 6, 8, 12, 24}
• Największy wspólny dzielnik: 12

Poniższy kod sprawdza wszystkie liczby od 1 do minimum z podanych liczb i wybiera największą, która dzieli obie liczby bez reszty. Jest to prosty, ale nieefektywny sposób obliczania NWD, który może być znacznie ulepszony np. poprzez algorytm Euklidesa.

def nwd_naiwny(a, b):
    """
    Naiwny algorytm wyznaczania największego wspólnego dzielnika (NWD)
    polegający na sprawdzaniu wszystkich możliwych dzielników od 1 do min(a, b).
    """
    nwd = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            nwd = i
    return nwd

# Przykładowe użycie
liczba1 = int(input("Podaj pierwszą liczbę: "))
liczba2 = int(input("Podaj drugą liczbę: "))
wynik = nwd_naiwny(liczba1, liczba2)
print(f"NWD({liczba1}, {liczba2}) = {wynik}")
            

5. Algorytm Euklidesa – optymalna metoda

Algorytm Euklidesa wykorzystuje operację dzielenia z resztą i działa w następujący sposób:

• Jeśli b = 0, to NWD(a, b) = a.
• W przeciwnym razie, obliczamy nową wartość: a := b, b := a mod b.
• Powtarzamy krok 2, aż b osiągnie wartość 0.

Przykład dla NWD(36, 24):

• 36 mod 24 = 12 → zastępujemy: (24, 12)
• 24 mod 12 = 0 → wynik to 12

Poniższy kod korzysta z algorytmu Euklidesa, który iteracyjnie (Słowo iteracyjnie pochodzi od terminu iteracja, który oznacza powtarzanie jakiegoś procesu lub czynności wielokrotnie, aż do osiągnięcia określonego rezultatu.) oblicza resztę z dzielenia i zamienia argumenty, aż druga liczba stanie się zerem. Wówczas pierwsza liczba to NWD. Możesz przetestować ten kod, wpisując dwie liczby w konsoli.

def nwd(a: int, b: int) -> int:
    """Funkcja oblicza największy wspólny dzielnik (NWD) dwóch liczb przy użyciu algorytmu Euklidesa z dzieleniem."""
    while b:
        a, b = b, a % b
    return a

# Przykładowe użycie
if __name__ == "__main__":
    x = int(input("Podaj pierwszą liczbę: "))
    y = int(input("Podaj drugą liczbę: "))
    print(f"NWD({x}, {y}) = {nwd(x, y)}")
            

6. Podsumowanie

Algorytm Euklidesa jest skutecznym sposobem wyznaczania największego wspólnego dzielnika, co ma kluczowe znaczenie w operacjach na ułamkach oraz w innych praktycznych zastosowaniach. Jest on znacznie szybszy niż metoda naiwna i pozwala na efektywne obliczenia nawet dla dużych liczb.