Algorytm Euklidesa opisuje metodę znajdowania największego wspólnego dzielnika dwóch liczb naturalnych. Nazwa pochodzi od greckiego matematyka Euklidesa, który jako pierwszy opisał algorytm w IV w p.n.e., chociaż nie był jego autorem. Problem wyznaczania NWD rozwiązywany jest na wiele sposobów, w tym materiale wykorzystamy wersję opartą na odejmowaniu.

NWD

Największy wspólny dzielnik (NWD) dwóch liczb naturalnych a i b większych od 0 to największa liczba naturalna d, która jest dzielnikiem każdej z nich, czyli dzieli je bez reszty. Przyjmijmy, że będziemy ją oznaczać jako d = NWD(a, b).

NWD ma wiele zastosowań, m.in. pozwala skracać ułamki zwykłe do postaci, w której licznik i mianownik są liczbami względnie pierwszymi, czyli NWD(a, b) = 1.

Algorytm Euklidesa z zastosowaniem odejmowania

Skonstruujemy algorytm, który obliczy największy wspólny dzielnik dwóch dodatnich liczb naturalnych.

Specyfikacja algorytmu:

Dane:

• a, b – dodatnie liczby naturalne

Wynik:

• d - dodatnia liczba naturalna, NWD(a, b)

Do rozwiązania postawionego zadania użyjemy algorytmu Euklidesa w wersji z odejmowaniem.

Z powyższego przykładu wynika, że dopóki liczby a i b są różne, w każdym powtórzeniu sprawdzamy, która liczba jest większa. Jeżeli a > b, obliczamy a = a - b, w przeciwnym razie wyliczamy b = b - a. Kiedy a i b są równe, wynikiem jest dowolna z tych liczb.

Zapiszmy algorytm w postaci listy kroków:

1. Wczytaj a, b.

2. Jeżeli a jest równe b, przejdź do kroku 5.

3. Jeżeli a > b, zmiennej a przypisz a - b, w przeciwnym razie b przypisz b - a.

4. Przejdź do kroku 2.

5. Wypisz a i zakończ algorytm.

Przeanalizujmy również schemat blokowy algorytmu:

R7eTw2k5l821C

Na grafice widoczny jest schemat blokowy ilustruje implementację klasycznego algorytmu Euklidesa służącego do obliczania największego wspólnego dzielnika (NWD). Schemat składa się z: zielonego owalu z napisem start. Kolejnym elementem jest blok purpurowy równoległobok zawierający instrukcje "Wczytaj liczbę a" oraz "Wczytaj liczbę b". Główna Pętla Algorytmiczna i Warunki Decyzyjne. Centralnym elementem schematu jest struktura decyzyjna przedstawiona w formie niebieskiego rombu z warunkiem "Jeżeli a = b". W przypadku gdy wartości zmiennych a i b są równe, algorytm przechodzi do fazy zakończenia poprzez wyprowadzenie wyniku. Alternatywnie, gdy warunек równości nie jest spełniony, następuje przejście do kolejnej fazy przetwarzania danych. Kolejnym elementem jest niebieski romb, zawiera warunek "Jeżeli a > b" i służy do określenia, która z dwóch zmiennych powinna zostać zmodyfikowana w bieżącej iteracji. Operacje Arytmetyczne i Modyfikacja Zmiennych Schemat zawiera dwa prostokątne elementy w kolorze jasnoniebieskim reprezentujące operacje arytmetyczne "a = a - b" oraz "b = b - a". Gdy warunek a = b zostanie spełniony, algorytm przechodzi do fazy wyprowadzenia wyniku poprzez element "Wypisz a" przedstawiony w formie purpurowego równoległoboku. W tym momencie zmienna a (równa również zmiennej b) zawiera wartość największego wspólnego dzielnika liczb wprowadzonych na początku algorytmu. Wybór wyprowadzenia zmiennej a jest arbitralny, gdyż w stanie końcowym obie zmienne mają identyczną wartość będącą poszukiwanym NWD. Element końcowy STOP, reprezentowany przez czerwony owal, oznacza formalne zakończenie wykonywania algorytmu.

Z obydwu sposobów zapisu algorytmu wynika, że na początku pobieramy dane wejściowe, czyli dwie dodatnie liczby całkowite. Następnie porównujemy je i większą pomniejszamy o mniejszą. Operacje te powtarzają się dopóki liczby a i b są różne. Kiedy zrównają się, wyprowadzamy wynik, tj. dowolną z tych liczb, i kończymy.

Notatnik

Animacja

R1E3bvJEBiR8S

Animacja pod tytułem Największy wspólny dzielnik

Animacja pod tytułem Największy wspólny dzielnik

Film dostępny pod adresem /preview/resource/R1E3bvJEBiR8S

Animacja pod tytułem Największy wspólny dzielnik

Program nwd_odejmowanie_licznik.py zaprezentowany w animacji:

# Pierwszy zestaw danych
a = 8
b = 32

# Drugi zestaw danych
a = 8
b = 2848

# Trzeci zestaw danych
a = 2
b = 10

# Czwarty zestaw danych
a = 2
b = 22222

NWD( 8, 32 ) = 8
Liczba operacji = 3

NWD( 8, 2848 ) = 8
Liczba operacji = 355

NWD( 2, 10 ) = 2
Liczba operacji = 4

NWD( 2, 22222 ) = 2
Liczba operacji = 11110

# Pierwszy zestaw danych
a = 34
b = 16

# Drugi zestaw danych
a = 16
b = 34

NWD( 34, 16 ) = 2
Liczba operacji = 9
NWD( 16, 34 ) = 2
Liczba operacji = 9

# Pierwszy zestaw
a = 28
b = 4

# Wyniki
Liczba operacji = 6
NWD( 28 , 4 ) =  4

# Drugi zestaw
a = 4
b = 28

# Wyniki
NWD( 4, 28 ) = 4
Liczba operacji = 6

# Trzeci zestaw
a = 4
b = 280

# Wyniki
NWD( 4, 280 ) = 4
Liczba operacji = 69

Zestaw ćwiczeń interaktywnych