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.