Algorytm Euklidesa | Korepetycje do matury z informatyki - Maurycy Gast

Algorytm Euklidesa

Algorytm Euklidesa jest to jeden z najpowszechniejszych i najstarszych wciąż używanych algorytmów. Służy on do obliczania Największego Wspólnego Dzielnika (NWD) dla dwóch liczb naturalnych.

Algorytm obejmuje dwa główne sposoby:

  • metodę poprzez odejmowanie,
  • metoda poprzez liczenie reszty z dzielenia.

Oryginalna metoda opracowana przez Euklidesa z Aleksandrii w III w. p.n.e. opierała się na odejmowaniu mniejszej liczby z pary od większej i podmienianie wyniku tego działania za większą liczbę z pary. Czynność tą powtarzało się do momentu, w którym jedna z liczb nie wynosiła 0.

największy wspólny dzielnik c++
Algorytm Euklidesa służy do znajdowania Największego Wspólnego Dzielnika.

Metoda poprzez odejmowanie

Wytłumaczmy tą metodę na przykładzie dwóch liczb 504 i 315:

315 jest mniejszą liczbą z pary więc odejmujemy ją od 504:

504 – 315 = 189

Wynik różnicy podmieniamy za większą liczbę w parze.

Nasza para wygląda teraz tak: (189, 315)

Wynik różnicy jest mniejszy 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 liczenie algorytmu, ponieważ otrzymaliśmy liczbę 0 w parze.

Największym dzielnikiem liczb 504 i 315 jest 63.

Powyższą metodą byliśmy w stanie uzyskać wynik, 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.

Metoda poprzez liczenie reszty z dzielenia

Przetestujmy nową metodę na trochę większych liczbach: 1230 i 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 ten znalazł Największy Wspólny Dzielnik w zaledwie kilka kroków.

Zastanówmy się teraz nad implementacją algorytmu znajdywania największej wspólnej wielokrotności w C++ i w Pythonie.

 

Algorytm Euklidesa C++:

#include <iostream>

using namespace std;

int euklidIter(int a, int b)
{
    while(a != b)
    {
        if(a>b)
        {
            a-= b;
        }
        else
        {
            b -= a;
        }
    }
    return a;
}

int euklidRekur(int a, int b)
{
    if (a == 0)
        return b;
    return euklidRekur(b-a, a);
}

int betterEuklidIter(int a, int b)
{
    while(a != b && a>0)
    {
        if(a>b)
        {
            a %= b;
        }
        else
        {
            b %= a;
        }
    }
    return b;
}

int betterEuklidRekur(int a , int b)
{
    if(a == 0)
        return b;
    return betterEuklidRekur(b%a, a);
}

int main()
{
    cout<< euklidIter(315, 504);
    cout<< euklidRekur(315, 504);
    cout<< betterEuklidIter(1230, 528);
    cout<< betterEuklidRekur(1230, 528);
    return 0;
}

 

Algorytm Euklidesa Python:

def euclidIter(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a


def euclidRecur(a, b):
    if a == 0:
        return b
    return euclidRecur(b - a, a)


def betterEuclidIter(a, b):
    while a != b and a > 0:
        if a > b:
            a %= b
        else:
            b %= a
    return b


def betterEuclidRecur(a, b):
    if a == 0:
        return b
    return betterEuclidRecur(b % a, a)


print(euclidIter(315, 504))
print(euclidRecur(315, 504))
print(betterEuclidIter(1230, 528))
print(betterEuclidRecur(1230, 528))

Powyższe algorytmy NWD są zaimplementowane zarówno w funkcjach iteracyjnych, jak i rekurencyjnych. Jak widzimy, ich składnia nie jest zbytnio złożona i są bardzo podobne do siebie.

Wpisy, które mogą Cię zainteresować:



Dodaj komentarz

kurs maturalny informatyka