Największy wspólny podzielnik i najmniejsza wspólna wielokrotność

Wyznaczanie największego wspólnego dzielnika dwóch liczb.

Wyznaczanie największego wspólnego podzielnika dwóch liczb należy do najstarszych problemów algorytmicznych. Pierwsze opis rozwiązania podał już Euklides około 300 lat p.n.e. i dlatego nosi on jego imię. Co więcej jest to efektywny sposób rozwiązania tego problemu.

Na początek jednak algorytm niezbyt efektywny, za to stosunkowo łatwy do zrozumienia. Polega on na dzieleniu modulo każdej z liczb przez kolejne liczby naturalne mniejsze lub równe mniejszej z dwóch liczb tak długo, aż obie reszty z dzielenia będą równe zero. Wynikiem jest dzielnik.

1. Dla dwóch niezerowych liczb naturalnych a i b wykonaj:

1. Jeżeli b jest większe od a, idź do kroku 3, w przeciwnym razie idź do kroku 2.

2. Zamień miejscami a i b; użyj do tego zmiennej pomocniczej

(pomocnicza ← b

b ← a

a ←pomocnicza)

3. Od i = a powtarzaj kroki od 4 i 5 dopóki reszta z dzielenia modulo jest różna od zera, w przeciwnym razie idź do kroku 6.

4. Dla a i b wykonaj dzielenie modulo i, idź do kroku 5

5. Jeśli wyniki dzielenia są różne od 0, zmniejsz i o 1.

6. 
   Wyprowadź NWD = i; zakończ algorytm.

Schemat blokowy obok przedstawia sposób obliczania NWD.

Spróbuj samodzielnie narysować schemat blokowy dla algorytmu, w którym sprawdzanie zaczyna się od i = 1, musi więc osiągnąć wartość a, przy założeniu, że a ≤ b.

2. Pierwsze rozwiązanie podane przez Euklidesa dotyczyło problemu geometrycznego. Szukał on wspólnej „miary” dwóch odcinków. Polegało ono na kolejnym odejmowaniu krótszego odcinka od dłuższego. Można je przedstawić następująco.

Dla dwóch niezerowych liczb naturalnych a i b wykonuj następujące kroki:

1. dopóki liczby a i b są różne, powtarzaj kroki 2 i 3 ; w przeciwnym razie przejdź do kroku 4.

2. jeżeli b > a, oblicz różnicę b ← b - a i idź do kroku 1, w przeciwnym razie idź do kroku 3

3. oblicz a ← a - b i idź do kroku 1

4. obliczyłeś NWD, wyprowadź wynik, zakończ algorytm

Schemat poniżej przedstawia algorytm wyznaczania NWD za pomocą obliczania różnicy liczb.

Pierwsze rozwiązanie podane przez Euklidesa dotyczyło problemu geometrycznego. Szukał on wspólnej „miary” dwóch odcinków. Polegało ono na kolejnym odejmowaniu krótszego odcinka od dłuższego. Można je przedstawić następująco.

3. Inny sposób zaproponowany przez Euklidesa to zastąpienie odejmowania dzieleniem modulo. Algorytm można przedstawić następująco:

Dla dwóch różnych niezerowych liczb naturalnych a i b wykonuj następujące kroki:

1. Dopóki reszta z dzielenia modulo liczb a i b jest różne od 0 wykonuj kroki 2 i 3, w przeciwnym razie idź do kroku 5.

2. Jeśli a > b, oblicz a jako resztę z dzielenia a przez b.

3. W przeciwnym wypadku zamień miejscami a i b i powtórz punkt 2.

4. Obliczyłeś NWD, wyprowadź wynik NWD = b.

Wyznaczanie najmniejszej wspólnej wielokrotności dwóch liczb.

Sposób wyznaczania najmniejszej wspólnej wielokrotności dwóch liczb znamy z lekcji matematyki w szkole podstawowej.

Algorytm postępowania był następujący:

• obie liczby należy rozłożyć na czynniki pierwsze,

• wśród czynników zaznaczamy wspólne pary, czyli znajdujemy największy wspólny podzielnik naszych liczb,

• najmniejsza wspólna wielokrotność jest równa iloczynowi jednej z naszych liczb przez te czynniki drugiej liczby, które nie weszły do NWD.

Ogólnie rzecz ujmując wzór pozwalający obliczyć NWW jest równy

.

Zadanie

1. Napisz programy obliczające NWD zgodnie z podanymi trzema algorytmami. Wykorzystaj schematy blokowe.

2. Narysuj schemat blokowy obliczania NWW. Napisz program realizujący ten algorytm.

START

STOP

Wyprowadź wynik: NWD

Wczytaj liczby: a, b

i = a

NWD = 1

b1 = b mod i

a1 = a mod i

Czy b1= a1 = 0?

i = i - 1

NWD = i

N

T

T

N

T

N

N

T

b ← b - a

a = b ?

a ← a - b

Wyprowadź:

NWD = a

Czytaj: a, b

STOP

a > b ?

START

a ← b

b ← r

N

T

a <> b ?

N

T

T

N

r ← a mod b

r = 0 ?

pom ← a

a ← b

b ← pom

Czytaj: a, b

STOP

a > b ?

START

Wyprowadź: NWD = b

---