Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – najwi kszy wspólny dzielnik
5 kwietnia 2009
1
N
AJWI KSZY WSPÓLNY DZIELNIK
D
EFINICJA
. Liczba całkowita jest
dzielnikiem (
divisor
) liczby całkowitej
, wtedy i
tylko wtedy, gdy jest całkowit wielokrotno ci .
Inaczej mówi c, dla pewnej liczby
spełnione jest równanie
.
Poniewa
, wi c ka da liczba całkowita jest dzielnikiem zera. St d wy-
nika, e zero ma niesko czon liczb dzielników.
Nietrudno widzie , e je eli jest dzielnikiem liczby
, to jest te dzielnikiem liczby
. Z tego wnioskujemy, e dzielniki liczb
i
s takie same. Poza tym,
jest
dzielnikiem
, wtedy i tylko wtedy, gdy
jest dzielnikiem
. W zwi zku z tym,
dalsze rozwa ania mo na ograniczy do nieujemnych liczb całkowitych.
Niech
i
dla pewnych
. Poniewa
, wi c
,
.
(*)
Pokazali my, e wszystkie dzielniki liczby
nale do przedziału
.
D
EFINICJA
.
Wspólnym dzielnikiem
(
common divisor
) liczb
i nazywamy liczb
całkowit , która jest jednocze nie dzielnikiem i .
Zauwa my, e liczby
i s wspólnymi dzielnikami ka dej liczby całkowitej.
Je eli
nie s równocze nie równe zeru, czyli prawdziwe jest zdanie
or
,
to zgodnie z (*) mog mie tylko sko czon liczb wspólnych dzielników.
D
EFINICJA
.
Najwi kszym wspólnym dzielnikiem (
greatest common divisor
) liczb
,
z których co najmniej jedna jest ró na od zera, nazywamy najwi kszy z ich wspólnych
dzielników. Oznaczamy go
, albo
.
Mo emy teraz zaj si problemem obliczania
, czyli opracowaniem algo-
rytmu wyznaczaj cego
.
Pierwszy algorytm znamy z matematyki elementarnej
1. Rozło y liczby
i
na czynniki pierwsze,
2. Znale najwy sze pot gi czynników pierwszych, które s wspólnymi dzielnikami
i
,
3. Znale iloczyn tych pot g, co daje
.
Przykład.
Obliczmy
wg tego algorytmu.
Rozkład na czynniki pierwsze jest nast puj cy:
,
.
Dzielnikami tych liczb s
,
,
a wspólnymi dzielnikami
i st d
.
Zauwa my, e ten algorytm wyznaczania
wymaga rozkładu argumentów na czyn-
niki pierwsze, co w przypadku du ych liczb znacznie wydłu a działanie algorytmu.
Zajmijmy si wi c inn metod , która nie wymaga kosztownego wyznaczania rozkładu na
czynniki pierwsze.
Na pocz tku zauwa my, e je eli prawdziwe jest zdanie
xor
,
czyli dokładnie jedna z liczb jest równa zeru, to
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – najwi kszy wspólny dzielnik
5 kwietnia 2009
2
,
natomiast, gdy obydwie te liczby s ró ne od zera, czyli spełniaj warunek
and
,
to musi zachodzi nierówno
.
St d wynika, e w tym ostatnim przypadku mo emy wykona obliczenia w p tli
while
, za-
czynaj c od
i sprawdzenia czy liczba ta dzieli bez reszty
i
. Je eli tak jest, to
i
algorytm si ko czy. W przeciwnym przypadku zmniejszamy o i przeprowadzamy test
dzielenia bez reszty liczb
. Ten krok powtarzamy tak długo, a obydwie reszty z
dzielenia b d równe zeru. W najgorszym przypadku otrzymamy
, poniewa
jest dzielnikiem ka dej liczby całkowitej.
Opisany
algorytm wyznaczania NWD nazywany bezpo rednim, a Sedgewick (
1983
) na-
zywa go siłowym (
brute force
).
Zadanie.
Ile razy wykonywana jest p tla
while
, w przypadku, gdy liczby
s
wzgl dnie pierwsze i adna z nich nie jest równa zeru.
Zadanie obliczeniowe 1.
Napisa , uruchomi i przetestowa program w j zyku Ada
wyznaczaj cy NWD wg podanego algorytmu bezpo redniego. W przypadku, gdy dane wej-
ciowe
s zerowe, nale y ten przypadek wyró ni komunikatem "NWD
nieokreslony" i nie wykonywa głównej cie ki algorytmu. Oprócz NWD wyznaczy liczb
wykona p tli.
Algorytm bezpo redni nie opiera si na kosztownym rozkładzie argumentów na czynniki
pierwsze, ale liczba powtórze p tli
while
w przypadku du ych warto ci danych wej cio-
wych jest wielka (patrz
Zadanie
). Znacznie efektywniejszy jest
algorytm Euklidesa
(
Courant, Robbins, 1967: Ross, Wright, 2000
), który oparty jest na nast puj cym wyniku:
T
WIERDZENIE
(
Ross, Wright, 2000, 259
). Je eli liczby
i
, to wspólne
dzielniki tych liczb s takie same jak wspólne dzielniki liczb i
mod
, co zapisujemy w
postaci
mod
.
(**)
Dowód: (
Ross, Wright, 2000, 258
).
Przykład.
Zastosowa to twierdzenie do wyznaczenia NWD nast puj cych liczb
i
.
mod
mod
mod
mod
mod
mod
mod
Przy implementacji komputerowej algorytmu Euklidesa warto zauwa y , e reszta z
dzielenia spełnia nierówno
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – najwi kszy wspólny dzielnik
5 kwietnia 2009
3
mod
oraz
,
.
W zwi zku z tym, dogodnie jest zdefiniowa zmienne pomocnicze
,
,
które spełniaj warunki
i
.
Obliczenia wykonujemy przy pomocy p tli
while
, której test wej ciowy jest relacj
.
Wewn trz p tli stosujemy podane twierdzenie, czyli
mod
i odpo-
wiednio wymieniamy zmienne. Powtarzamy ten proces tak długo, a reszta z dzielenia stanie
si równa zeru.
Nietrudno widzie , e tak robili my w ostatnim przykładzie, przy czym deklaracja zmiennych
wg podanych wzorów pozwala na pomini cie pierwszych dwóch operacji wykonanych
przy wyznaczaniu
.
To, e algorytm Euklidesa wyznacza
potwierdza
T
WIERDZENIE
. Algorytm Euklidesa daje w wyniku NWD liczb całkowitych
takich,
e
or
.
Dowód: (
Ross, Wright, 2000, 260
).
Liczb przebiegów p tli
while
w tym algorytmie mo na oszacowa stosuj c
T
WIERDZENIE
. Dla danych liczb całkowitych
algorytm Euklidesa wyznacza-
nia
wykonuje co najwy ej
(#)
przebiegów p tli.
Dowód: (
Ross, Wright, 2000, 260
).
Zadanie obliczeniowe 2.
Napisa , uruchomi i przetestowa program w j zyku Ada
wyznaczaj cy NWD wg podanego algorytmu Euklidesa. W przypadku, gdy dane wej ciowe
s zerowe, nale y ten przypadek wyró ni komunikatem "NWD nieokreslony" i nie
wykonywa głównej cie ki algorytmu. Oprócz NWD wyznaczy liczb wykona p tli i po-
równa z oszacowaniem (#).
L
ITERATURA
Courant, R. i H. Robbins. (1967). Co to jest matematyka. PWN, Warszawa (tłum. z ang.).
Ross, K.A i C.R.B. Wright. (2000). Matematyka dyskretna. PWN, Warszawa (tłum. z ang.).
Sedgewick, R. (1983). Algorithms. Addison-Wesley, Reading, Massachussets.