Rozszerzony algorytm Euklidesa
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 |
