Czym jest Algorytm Euklidesa i jak taki algorytm można zapisać? Do czego służy? Jeżeli chcesz poznać odpowiedź na te pytania, zapraszamy do lektury! Ten algorytm to rzecz niezbędna dla każdego, kto chce wykorzystać w swoich programach siłę liczb.
Nim przejdziemy do sedna sprawy, spróbujmy rozwiązać takie zadanie:
Dysponujemy monetami o dwóch nominałach - i złotych (to musi być w jakiś dawnych czasach...). Chcemy za ich pomocą wypłacić tę samą kwotę - raz tylko monetami -cio złotowymi, raz tylko -cio złotowymi. Jaka jest najmniejsza niezerowa kwota, która spełnia te wymagania?
No tak, to nie jest trudne - wystarczy chwilę pomyśleć, aby znaleźć tę kwotę - to .
Faktycznie:
Ale dlaczego jest najmniejszą taką liczbą? Ten przykład był prosty, występowały w nim niewielkie liczby. Ale jak znaleźć odpowiedź, gdy ktoś zapyta nas o monety o nominałach i ? Albo i ? To wcale nietrudne!
Na początek przypomnijmy kilka wiadomości z matematyki:
1. Mówimy, że liczba dzieli liczbę , jeśli istnieje taka liczba całkowita , że .
Np. dzieli , gdyż , a dzieli , gdyż .
Fakt, że dzieli zapisujemy w ten sposób: . Mamy więc oraz . Mówimy, że jeśli dzieli , to jest dzielnikiem , a jest wielokrotnością .
Jeżeli liczba nie dzieli , będziemy pisać, że .
2. Jeżeli liczba dzieli zarówno liczbę , jak i liczbę , to dzieli też ich różnicę, , oraz sumę .
Linia powyżej mówi nam, że jeśli dzieli i dzieli , to znaczy, że obie te liczby można zapisać jako iloczyn i odpowiednio oraz . W takim razie ich różnica, , równa jest , a to oznacza, że ta różnica jest podzielna przez . Podobnie jest podzielne przez , gdyż ta suma to .
3. Jeżeli dzieli , i dzieli , to dzieli .
4. Jeżeli liczby i nie mają żadnego wspólnego dzielnika, większego niż jeden (czyli nie istnieje liczba większa od jeden, która dzieliłaby zarówno jaki i ), to mówimy, że te liczby są względnie pierwsze. Zapisujemy to w ten sposób : .
Na przykład i są względnie pierwsze, za to i nie są względnie pierwsze, gdyż oraz .
Jaki mamy z tego pożytek? Powróćmy do przykładu z monetami o nominałach i . Szukaliśmy takiej kwoty, która byłaby podzielna zarówno przez jak i przez . To oznacza, że taka kwota musi się dzielić przez te same liczby, przez które dzielą się i . Chcemy też, aby ta liczba była jak najmniejsza.
Taką najmniejszą dodatnią liczbę, podzielną przez i przez , nazywamy najmniejszą wspólną wielokrotnością i oznaczamy przez .
Jak ją wyznaczyć? Zauważmy, że wystarczy, aby dzieliła się przez wszystkie dzielniki i . Chcemy otrzymać liczbę jak najmniejszą, więc nie ma sensu duplikować dzielników - jeżeli jakaś liczba dzieli zarówno jak i , ale nie dzieli obu tych liczb, to nie ma sensu, aby dzieliła się przez , wystarczy aby dzieliła się przez . Stąd często .
Gdybyśmy potrafili wyznaczyć największą taką liczbę, przez którą dzielą się obie liczby i , to w łatwy sposób wyznaczylibyśmy ... dlaczego?
Spójrzmy na nasz przykład - , . Widzimy, że to największy wspólny dzielnik tych dwóch liczb. W takim razie ich najmniejsza wspólna wielokrotność musi być równa . Dlaczego? Ponieważ musi dzielić się przez (bo jest podzielne przez ), musi się też dzielić przez ( jest podzielne przez ), oraz przez - największy wspólny dzielnik i .
I to wszystko - każda liczba która dzieli oraz dzieli , dzieli też ich (największy wspólny dzielnik), czyli . Gdyby było inaczej, powiedzmy, że istniałaby liczba pierwsza , taka, że , nie byłoby - wszak jest większe niż i też dzieli obie nasze liczby.
Wiemy też, że . Dlaczego?
Wobec tego liczby oraz są względnie pierwsze - w znajdują się wszystkie wspólne dzielniki i - gdy podzielimy i przez ich , dostaniemy liczby, które nie mogą mieć wspólnego dzielnika, większego od .
Wobec tego, wymnażając , oraz otrzymamy najmniejszą liczbę podzielną przez i przez .
Faktycznie, .
Wiemy już, że pozostało nam znaleźć sposób na obliczanie największego wspólnego dzielnika.
Wiemy już pewną bardzo ważną rzecz - jeśli jakaś liczba dzieli i dzieli , to dzieli również ich różnicę, . W szczególności dotyczy to . Mamy więc:
Jeśli to
Dlaczego? Wiemy już, że jeśli jakaś liczba dzieli i , to dzieli ich różnicę. Więc napewno . Z kolei wiemy też, że każdy wspólny dzielnik dwóch liczb dzieli ich sumę, stąd . Wobec tego zachodzi powyższa równość, bo każdy wspólby dzielnik i dzieli , i każdy wspólny dzielnik i dzieli .
Stąd już tylko parę kroków do zachwycającego prostotą algorytmu Euklidesa.
Prześledźmy wykorzystanie faktu dla konkretnych liczb, na przykład i :
Uff... trochę to przydługawe, ale w końcu dobrnęliśmy do rozwiązania - musi być równe , gdyż dzieli się przez każdą niezerową liczbę, więc też przez , które z kolei jest największym dzielnikiem , czyż nie?
To, co wykonaliśmy powyżej, to właśnie Algorytm Euklidesa. Dopóki jedna z liczb i nie jest równa , odejmujemy mniejszą liczbę od większej. Każde kolejne jest równe poprzedniemu, a kiedyś musimy dobrnąć do zera (dlaczego?) i odnaleźć rozwiązanie, gdyż jeśli , to .
Oczywiście da się ten algorytm ulepszyć. Zauważ, że trochę bez sensu było liczenie kolejno , . Cały czas odejmowaliśmy , aż osiągnęliśmy liczbę mniejszą niż . Tak przecież działa Algorytm Euklidesa - dopóki pierwsza liczba jest większa od drugiej, odejmujemy drugą od pierwszej.
W takim razie nietrudno jest ulepszyć nasz algorytm do takiej postaci:
Wyjaśnijmy sobie to! to wynik dzielenia przez bez reszty - mówiąc nieformalnie, jest to ilość pełnych wystąpień w . Innymi słowy, tyle właśnie razy możemy odejmować od , aż dostaniemy liczbę mniejszą od . W takim razie "kompresujemy" sobie kolejne kroki algorytmu, polegające na żmudnym odejmowaniu wielokrotnie, do jedengo kroku. Zauważ, że to właśnie wynik odjęcia od wszystkich "mieszczących" się w wystąpień .
Zauważ, jak przyspiesza to działanie algorytmu - gdybyśmy chcieli poprzednią metodą liczyć ... Tymczasem w naszej nowej metodzie mamy .
Zapiszmy nasz algorytm w języku C++:
int NWD(int a, int b){
int q, temp;
while(b){
q = a/b;
temp = b;
b = a - q*b;
a = temp;
}
return a;
}
Jest to dokładnie zapis naszego algorytmu - dopóki mniejszy z elementów pary nie jest zerem, wykonujemy "zamianę" na . Gdy , nasz największy wspólny dzielnik to .
Jak szybko działa ten algorytm? Jeżeli znane są Ci pojęcia złożoności obliczeniowej to zapewne ucieszy Cię wiadomość, że Algorytm Euklidesa działa w czasie logarytmicznym względem wielkości liczb i . Jeśli zaś nie, to zachęcamy do dowiedzenia się czegoś na ten temat - nie mniej jednak oznacza to, że algorytm działa błyskawicznie.
Zachęcamy do zapisania tego algorytmu i wykorzystania go do rozwiązania zadania Monety. Jego dokładna treść i specyfikacja znajdują się na ostatniej stronie artykułu.
Zastanówmy się nad rozwiązaniem poniższego zadania:
Aptekarz ma przed sobą ciężkie zadanie - musi odmierzyć gramów leku, dysponuje dwoma odważnikami, o wagach i 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 i gramów.
Jak się do tego zabrać? Postarajmy się zapisać to zadanie w języku matematyki:
Szukamy takich liczb całkowitych i , że:
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 na lewej szalce, a odważniki wagi na prawej szalce. Wtedy różnica wag na obu szalkach musi być równa albo , albo - 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 gramów.
Zauważmy, że musi zachodzić . W istocie, skoro i , to również . Jeśli więc umielibyśmy znaleźć takie liczby i , że (przy oznaczeniu
to biorąc i dostalibyśmy
Okazuje się, że Algorytm Euklidesa potrafi znaleźć takie liczby.
Jeśli udałoby się znaleźć szukane liczby i , to byłoby kombinacją liniową liczb i - to właśnie oznacza równanie - liczbę d można zapisać jako sumę pewnej wielokrotności całkowitej liczby i pewnej wielokrotności całkowitej liczby (nie przejmujmy się tym, że mamy minus - można by bez żadnej szkody napisać .
Zauważmy, że jeśli jakieś liczba i są kombinacjami liniowymi i , to ich różnica, , również jest kombinacją liniową i . Spójrzmy:
Jeśli dla pewnych całkowitych , to .
Jak działa Algorytm Euklidesa? Zaczynamy od . Zarówno jak i są oczywiście kombinacjami liniowymi i . 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 i . W końcu docieramy do - wobec tego też jest kombinacją liniową i . Spójrzmy na przykład:
Niech
Udało się! Nie dość, że znaleźliśmy , równe , to wiemy, że . Zauważ, że policzyliśmy też krok wcześniej w algorytmie, że . 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 i do równania . 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
Poniżej przykład dla i :
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 . Mamy na myśli to, że , , i tak dalej...
2. Niech ciągi spełniają zależności:
Co to oznacza? Liczby i to współczynniki, które pozwalają przedstawić kolejne liczby pojawiające się w algorytmie Euklidesa jako kombinacje liniowe i . Mamy więc dla naszego powyższego przykładu:
- Koniec algorytmu
Widzimy wobec tego, że gdy algorytm się zakończy ( dla pewnego ) to współczynniki, których szukamy, to i - one spełniają gdyż wiemy, że gdy osiągamy zero dla , to poprzednio uzyskana liczba jest największym współnym dzielnikiem i .
Jak obliczać te współczynniki? Spójrzmy poniżej:
Więc jeśli przyjmiemy:
to otrzymamy:
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 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 i , to nigdy nie będziesz korzystać z , , .
W jednym z naszych przykładów okazało się, że można zapisać jako kombinację liniową i na wiele sposobów. Jak wyzaczyć wszystkie takie sposoby?
Załóżmy, że:
Weźmy , dla liczby całkowitej .
Wtedy
Wobec tego dla każdego całkowitego i też są dobrymi współczynnikami, pozwalającymi uzyskać jako kombinację liniową i . 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 , , że nie różnią się od naszych i o odpowiednio wielokrotność i . Mielibyśmy wtedy:
Ale i są względnie pierwsze (inaczej nie byłoby największym dzielnikiem). Wobec tego musi zachodzić:
A to oznacza, że muszą się różnić o wielokrotność odpowiednio i , co dowodzi, że nasz sposób znajduje wszystkie rozwiązania.
Zastanów się nad dwoma poniższymi problemami (możesz wysłać do nich rozwiązanie na sprawdzaczkę).
1. Mamy liczbę pierwszą , oraz liczbę całkowitą dodatnią , . Jak znaleźć taką liczbę całkowitą dodatnią , , taką, że ?. (Taką liczbę nazywamy odwrotnością w modulo p).
2. Rozważmy wspominany problem aptekarza, z jednym dodatkiem - aptekarz chciałby użyć jak najmniej odważników. Jak znaleźć takie rozwiązanie?
Poniżej znajdują się dokładne specyfikacje tych zadań i okienka do wysłania rozwiązań. Zachęcamy do spróbowania swoich sił!
Limit czasowy: 1s; Limit pamięciowy: 16 MB
Aptekarz Joe bardzo lubi liczyć bilon z kasy w swojej aptece. Dzisiaj wpadł na pomysł, aby wziąć sobie dwie monety o pewnych nominałach i znaleźć taką kwotę, którą można wypłacić zarówno za pomocą dowolnej ilości monet pierwszego rodzaju jak i za pomocą dowolnej ilości monet drugiego rodzaju. Joe nie jest zbyt inteligentny, poprosił więc Cię o pomoc. Napisz program, który znajdzie dla niego taką kwotę!
Wejście:
Pierwsza linia wejścia składa się z jednej liczby całkowitej , oznaczającej ilość testów do rozważenia. W kolejnych liniach znajdują się pary liczb całkowitych , .
Wyjście:
Dla każdej pary należy na wyjściu wypisać jedną linię z jedną liczbą - najmniejszą taką kwotą, którą można wypłacić zarówno za pomocą nominału jak i .
Przykład:
Dla wejścia:
3
10 6
36 60
1 1
Poprawne wyjście to:
30
180
1
Limit czasowy: 1s; Limit pamięciowy: 16MB
Liczby pierwsze mają bardzo dużo ciekawych właściwości. Jedną z nich jest to, że każda liczba całkowita, mniejsza od danej liczby pierwszej, ma swoją unikalną odwrotność - czyli taką liczbę, że te dwie wymnożone dają resztę 1 z dzielenia przez tę liczbę pierwszą. Napisz program, który odnajduje takie odwrotności.
Wejście:
Pierwsza linia wejścia zawiera dwie liczby całkowite i , . W kolejnych n liniach znajduje się po jednej liczbie , .
Wyjście:
Dla każdej liczby należy wypisać jej odwrotność - liczbę całkowitą dodatnią , mniejszą od , taką ,że .
Przykład:
Dla wejścia:
3 7
5
6
2
Poprawne wyjście to:
3
6
4
Limit czasowy: 1s; Limit pamięciowy: 16MB
Aptekarz Joe chce odmierzyć gramów substancji. Ma do dyspozycji dwa rodzaje odważników - o wadze i wadze , oraz wagę szalkową. Chciałby odważyć gramów i przy okazji użyć do tego celu jak najmniej odważników. Joe wie, że jest największym wspólnym dzielnikiem i . Pomóż mu!
Wejście:
W pierwszej linii wejścia znajduje się jedna liczba całkowita , , oznaczające ilość zestawów testowych. W kolejnych liniach znajdują się pary liczb całkowitych , , . Są to wagi dwóch odważników. Wiadomo, że Joe chce za ich pomocą odważyć - największy wspólny dzielnik i .
Wyjście:
Dla każdego zestawu testowego należy wypisać jedną linię, zawierającą najmniejszą liczbę odważników, potrzebnych do odważenia gramów substancji.
Przykład:
Dla danych wejściowych:
2
10 8
1 11
Poprawne wyjście to:
2
1
Objaśnienie: , , więc potrzeba co najmniej dwóch odważników. W drugim przykładzie wystarczy jeden odważnik o wadze 1.
Odnośniki:
[1] http://informatyka.wroc.pl/user
[2] http://informatyka.wroc.pl/user/register