Algorytm Euklidesa

31.10.2009 - Damian Rusak
Trudność

Kolejny problem

Zastanówmy się nad rozwiązaniem poniższego zadania:

Aptekarz ma przed sobą ciężkie zadanie - musi odmierzyć $ k $ gramów leku, dysponuje dwoma odważnikami, o wagach $ a $ i $ b $ gramów. Może użyć dowolnej ilości każdego z tych odważników na wadze szalkowej. Znajdź sposób odważenia żądanej ilości leku.


Przykładowe odważenie jedengo grama niebieskiego leku za pomocą odważników o wagach $ 7 $ i $ 10 $ gramów.

 

 

 

 

 

 

Jak się do tego zabrać? Postarajmy się zapisać to zadanie w języku matematyki:

Szukamy takich liczb całkowitych $ x $ i $ y $, że:

$ ax - by = k $

Zauważ, że nie ma sensu kłaść odważników tej samej wagi na różnych szalach - równoważyłyby się. Wobec tego możemy założyć, że układamy odważniki wagi $ a $ na lewej szalce, a odważniki wagi $ b $ na prawej szalce. Wtedy różnica wag na obu szalkach musi być równa albo $ k $, albo $ -k $ - oznacza to, że jeśli umieścimy lek odpowiednio na prawej bądź lewej szalce, waga będzie w stanie równowagi i odważymy szukane $ k $ gramów.

Zauważmy, że musi zachodzić $ NWD\left(a,b\right) \mid k $. W istocie, skoro $ NWD\left(a,b\right) \mid a $ i $ NWD\left(a,b\right) \mid b  $, to również $ NWD\left(a,b\right) \mid ax - by = k $. Jeśli więc umielibyśmy znaleźć takie liczby $ X $ i $ Y $, że (przy oznaczeniu $ d = NWD\left(a,b\right)) $

$ aX - bY = d $

to biorąc $ x = \frac{k}{d} \cdot X $ i $ y = \frac{k}{d} \cdot Y $ dostalibyśmy

$  ax - by = a \cdot \left(\frac{k}{d} \cdot X\right) - b \cdot \left(\frac{k}{d} \cdot Y\right) = \frac{k}{d} \cdot \left(aX - bY\right) = \frac{k}{d} \cdot d = k $

Okazuje się, że Algorytm Euklidesa potrafi znaleźć takie liczby.

Jeśli udałoby się znaleźć szukane liczby $ X $ i $ Y $, to $ d $ byłoby kombinacją liniową liczb $ a $ i $ b $ - to właśnie oznacza równanie $ aX - bY = d $ - liczbę d można zapisać jako sumę pewnej wielokrotności całkowitej liczby $ a $ i pewnej wielokrotności całkowitej liczby $ b $ (nie przejmujmy się tym, że mamy minus - można by bez żadnej szkody napisać $ aX + \left(-b\right)Y = d $.

Zauważmy, że jeśli jakieś liczba $ K $ i $ L $ są kombinacjami liniowymi $ a $ i $ b $, to ich różnica, $ K-L $, również jest kombinacją liniową $ a $ i $ b $. Spójrzmy:

Jeśli $ K = x_{1}a + y_{1}b \:\: L = x_{2}a + y_{2}b $ dla pewnych całkowitych $ x_{1}, y_{1}, x_{2}, y_{2} $, to $ K - L = (x_{1}-x_{2})a + (y_{1}-y_{2})b $.

Jak działa Algorytm Euklidesa? Zaczynamy od $ NWD\left(a,b\right) $. Zarówno $ a $ jak i $ b $ są oczywiście kombinacjami liniowymi $ a $ i $ b $. W każdym kolejnym kroku algorytmu zamieniamy jedną z tych liczb na ich różnicę. Wobec tego cały czas algorytm pracuje na dwóch liczbach, będących kombinacjami liniowymi $ a $ i $ b $. W końcu docieramy do $ NWD\left(d,0\right) $ - wobec tego $ d $ też jest kombinacją liniową $ a $ i $ b $ . Spójrzmy na przykład:

Niech $ a = 126, b = 54 $

$ 126 = 1\cdot 126 + 0\cdot 54\:\:\:54 = 0\cdot 126 + 1\cdot 54 $

$ NWD\left(126,54\right) = NWD\left(126-54,54\right) $

$ 72 = 126 - 54 = \left(1\cdot 126 + 0 \cdot 54 \right) - \left(0\cdot 126 + 1\cdot 54 \right) = 1\cdot 126 - 1\cdot 54 $

$ NWD\left(72,54\right) = NWD\left(54, 72-54\right) $

$ 18 = 72 - 54 = \left(1\cdot 126 - 1\cdot 54 \right) - \left(0\cdot 126 + 1\cdot 54\right) = 1 \cdot 126 - 2\cdot 54 $

$ NWD\left(54,18\right) = NWD\left(54-18,18\right) $

$ 36 = 54 - 18 = \left(0\cdot 126 + 1\cdot 54\right) - \left(1\cdot 126 - 2\cdot 54\right) = -1 \cdot 126 + 3\cdot 54 $

$ NWD\left(36,18\right) = NWD\left(36-18,18\right) $

$ 18 = 36 - 18 = \left(-1\cdot 126 + 3\cdot 54\right) - \left(1\cdot 126 - 2\cdot 54\right) = -2\cdot 126 + 5\cdot 54 $

$ NWD\left(18,18\right) = NWD\left(18,0\right) = 18 $

Udało się! Nie dość, że znaleźliśmy $ NWD\left(126,54\right) $, równe $ 18 $, to wiemy, że $ 18 = -2 \cdot 126 + 5\cdot 54  $. Zauważ, że policzyliśmy też krok wcześniej w algorytmie, że $ 18 = 1 \cdot 126 - 2\cdot 54  $. Widzimy więc, że takie przedstawienie w postaci kombinacji liniowej nie jest unikalne. Zajmiemy się tą sprawą w dalszej części algorytmu, teraz postarajmy się wyprowadzić sposób na obliczanie współczynników $ X $ i $ Y $ do równania $ Xa + Yb = d $. Przy okazji warto byłoby też przekształcić powyższy przykład do ulepszonego algorytmu Euklidesa - tego, w którym zamiast odejmować liczby od siebie wielokrotnie, od razu "wycinaliśmy" wszystkie wystąpienia mniejszej liczby z większej liczby.

Nie będzie to dużo trudniejsze - spójrzmy na ten sam przykład:

Niech $ a = 126, b = 54 $

$ 126 = 1\cdot 126 + 0\cdot 54 $   $ 54 = 0\cdot 126 + 1\cdot 54 $   $ NWD\left(126,54\right) = NWD\left(54, 126-\left\lfloor\frac{126}{54}\right\rfloor\cdot 54\right) $

$ 18 = 126 - \left\lfloor\frac{126}{54}\right\rfloor \cdot 54 = 126 - 2\cdot 54 =\left(1\cdot 126 + 0\cdot 54 \right) - 2\cdot \left(0\cdot 126 + 1\cdot 54\right) = 1\cdot 126 - 2\cdot 54 $

$ NWD\left(54,18\right) = NWD\left(18,54-\left\lfloor\frac{54}{18}\right\rfloor\cdot 18\right) = NWD\left(18, 0\right) = 18 $

$ 18 = 1\cdot 126 - 2\cdot 54 $

Poniżej przykład dla $ a = 32 $ i $ b = 17 $:

Algorytm

O ileż szybciej! Wprowadźmy pewne oznaczenia, aby móc łatwo zapisać tę zależność algorytmem:

1. Oznaczmy kolejne liczby pojawiające się w Algorytmie Euklidesa, jako $ a_{0}, a_{1}, a_{2}, ...  $. Mamy na myśli to, że $ a_{0} = a $, $ a_{1} = b $, $ a_{2} = a - \left\lfloor\frac{a}{b}\right\rfloor \cdot b  $ i tak dalej...

2. Niech ciągi $ \left(s_{n}\right) $ $ \left(t_{n}\right) $ spełniają zależności:

$ s_{0} = 1, t_{0} = 0, s_{1} = 0, t_{1} = 1 $

$ a_{n+1} = s_{n}\cdot a + t_{n} \cdot b  $

Co to oznacza? Liczby $ s_{n} $ i $ t_{n} $ to współczynniki, które pozwalają przedstawić kolejne liczby pojawiające się w algorytmie Euklidesa jako kombinacje liniowe $ a $ i $ b $. Mamy więc dla naszego powyższego przykładu:

$ a_{0} = 126\:\:\:s_{0} = 1\:\:\:t_{0} = 0\:\:\:126 = a_{0} = s_{0}\cdot 126 + t_{0}\cdot 54 $

$ a_{1} = 54\:\:\:s_{1} = 0\:\:\:t_{1} = 1\:\:\:54 = a_{1} = s_{1}\cdot 126 + t_{1}\cdot 54 $

$ a_{2} = 18\:\:\:s_{2} = 1\:\:\:t_{1} = -2\:\:\:18 = a_{2} = s_{2}\cdot 126 + t_{2}\cdot 54 $

$ a_{3} = 0 $ - Koniec algorytmu

Widzimy wobec tego, że gdy algorytm się zakończy ( dla pewnego $ n $ $ a_{n} = 0 $ ) to współczynniki, których szukamy, to $ s_{n-1} $ i $ t_{n-1} $ - one spełniają $ s_{n-1}\cdot a + t_{n-1} \cdot b = a_{n-1} = NWD\left(a,b\right)  $ gdyż wiemy, że gdy osiągamy zero dla $ a_{n} $, to poprzednio uzyskana liczba $ a_{n-1} $ jest największym współnym dzielnikiem $ a $ i $ b $.

Jak obliczać te współczynniki? Spójrzmy poniżej:

$ a_{n+1} = a_{n-1} - \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot a_{n} $

$ a_{n+1} = \left(s_{n-1}\cdot a + t_{n-1} \cdot b\right) - \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot \left(s_{n}\cdot a + t_{n} \cdot b\right) $

$ a_{n+1} = \left(s_{n-1} - \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot s_{n}\right) \cdot a + \left(t_{n-1} - \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot t_{n}\right)\cdot b $

Więc jeśli przyjmiemy:

$ s_{n+1} = s_{n-1} -  \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot s_{n} $

$ t_{n+1} = t_{n-1} -  \left\lfloor\frac{a_{n-1}}{a_{n}}\right\rfloor \cdot t_{n} $

to otrzymamy:

$ a_{n+1} = s_{n+1} \cdot a + t_{n+1} \cdot b $   Hurra!

Przyjżyjmy się poniższemu algorytmowi:

int a[1000], s[1000], t[1000];
int A, B, n, q, temp;

cin >> A >> B;

a[0] = A;
a[1] = B;
s[0] = 1; s[1] = 0;
t[0] = 0; t[1] = 1;
n = 1;

while(a[n] != 0){

q = a[n-1]/a[n];

a[n+1] = a[n-1] - q*a[n];
s[n+1] = s[n-1] - q*s[n];
t[n+1] = t[n-1] - q*t[n];

n++;
}

cout << "NWD(" << A << "," << B << ") = " << a[n-1] << endl;
cout << s[n-1] << "*" << A << " + ";
cout << t[n-1] << "*" << B << " = " << a[n-1] << endl;

Wypróbuj go! Zastanów się, dlaczego tablice o rozmiarze $ 1000 $ na pewno wystarczą. Zastanów się też, czy nie dałoby się zapisać tego algorytmu z mniejszym zużyciem pamięci - nie deklarując tablic (zwróć uwagę na to, że np. gdy już obliczysz $ a\left[10\right], s\left[10\right] $ i $ t\left[10\right] $, to nigdy nie będziesz korzystać z $ a\left[0\right], a\left[1\right], \ldots , a\left[8\right] $$ s\left[0\right], s\left[1\right], \ldots , s\left[8\right] $, $ t\left[0\right], t\left[1\right], \ldots , t\left[8\right] $.

 

Kilka ciekawych problemów

W jednym z naszych przykładów okazało się, że $ NWD\left(a,b\right) $ można zapisać jako kombinację liniową $ a $ i $ b $ na wiele sposobów. Jak wyzaczyć wszystkie takie sposoby?

Załóżmy, że:

$ d = NWD\left(a,b\right)\:\:\:ax + by = d $

Weźmy $ x_{t} = x + \frac{b}{d} \cdot t $, $ y_{t} = y - \frac{a}{d} \cdot t $ dla liczby całkowitej $ t $.

Wtedy $ x_{t}\cdot a + y_{t} \cdot b = \left(x - \frac{b}{d} \cdot t\right)\cdot a + \left(y - \frac{a}{d} \cdot t\right)\cdot b = ax + by + \frac{abt}{d} - \frac{abt}{d} = ax + by = d $

Wobec tego dla każdego $ t $ całkowitego $ x_{t} $ i $ y_{t} $ też są dobrymi współczynnikami, pozwalającymi uzyskać $ d $ jako kombinację liniową $ a $ i $ b $. Znaleźliśmy nieskończenie wiele takich liczb. Ale czy to wszystkie takie liczby?

Załóżmy przeciwnie - że można znaleźć takie dwie liczby całkowite $ X $, $ Y $, że nie różnią się od naszych $ x $ i $ y $ o odpowiednio wielokrotność $ \frac{b}{d} $ i $  \frac{a}{d} $. Mielibyśmy wtedy:

$ xa + yb = d = Xa + Yb $

$ x \frac{a}{d} + y \frac{b}{d} = 1 = X \frac{a}{d} + Y \frac{b}{d} $

$  \frac{a}{d}\left(x - X\right) =  \frac{b}{d}\left(Y - y\right)  $

Ale $  \frac{b}{d} $ i $  \frac{a}{d} $ są względnie pierwsze (inaczej $ d $ nie byłoby największym dzielnikiem). Wobec tego musi zachodzić:

$   \frac{a}{d} \mid Y - y\:\:\:\:\:\: \frac{b}{d} \mid x - X $

A to oznacza, że muszą się różnić o wielokrotność odpowiednio $  \frac{a}{d} $ i $  \frac{b}{d} $, co dowodzi, że nasz sposób znajduje wszystkie rozwiązania.

 

4.208335
Twoja ocena: Brak Ocena: 4.2 (24 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com