Rozszerzony algorytm Euklidesa

Z RNO-Wiki


Rozszerzony algorytm Euklidesa jest rozszerzoną wersją Algorytmu Euklidesa.

Rozszerzony algorytm Euklidesa służy do znajdowania współczynników x i y: d = gcd( a, b) = ax + by, przy czym x i y mogą być niedodatnie.

Algorytm będzie pobierał wyłącznie liczby a i b, zwróci zaś trójkę liczb (d, x, y). Resztę informacji zawrzemy w komentarzach.


Implementacja w C++

#include<cstdio>
struct triple //struktura "trójka"
{
        int d, x, y;
        triple() { } // pusty konstruktor
        triple( int aa, int bb, int cc )
        {
                d = aa; x = bb; y = cc;
        }
};
triple ext_euclid( int a, int b )
{
        if( b == 0 )
                return triple( a, 1, 0 );
        //jeśli b = 0 to gcd( a, b) = a = 1 * a + 0 * b
        triple tmp = ext_euclid( b, a % b );
        //wywołujemy to tak jak w zwykłym algorytmie euklidesa i budujemy trójkę ( d, x', y')
        triple do_zwrotu(tmp.d, tmp.y, tmp.x - (a / b) * tmp.y);
        //zwracamy trójkę ( d = gcd( a. b ), x, y ) = ( d, y', x' - ( a / b ) * y')
        //x = y' i y = x' - ( a / b) * y' gdyż wcześniej braliśmy modulo i teraz musimy wrócić piętro wyżej w rekursji
        return do_zwrotu;
}
int main()
{
        triple wynik;
        int a, b, x, y, d;
        scanf("%d %d", &a, &b);
        wynik = ext_euclid( a, b);
        d = wynik.a;
        x = wynik.b;
        y = wynik.c;
        printf("%d = %d * %d + %d * %d\n", d, a, x, b, y);
}


Tabelka obrazująca działanie algorytmu

Weźmy wejściowe a = 700 i b = 300

a b Głębokosć rekursji
700 300 1
300 100 2
100 0 3

Skoro b = 0 to d = a = 100 i pniemy się w górę rekursji:

a b d x y Głębokosć rekursji
100 0 100 1 0 3
300 100 100 0 1 2
700 300 100 1 -2 1
Osobiste