Stosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z odejmowaniem

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.

1. Interaktywna treść merytoryczna1Interaktywna treść merytoryczna

2. Multimedium2Multimedium

3. Zestaw ćwiczeń interaktywnych3Zestaw ćwiczeń interaktywnych

4. Słownik4Słownik

5. Bibliografia5Bibliografia

NWD

Największy wspólny dzielnik (NWD) dwóch dodatnich liczb naturalnych a i b 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 wejściowe:

• 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 zmiennej b przypisz b - a.

4. Przejdź do kroku 2.

5. Wypisz a i zakończ algorytm.

Przeanalizujmy również schemat blokowy algorytmu:

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

Zapis algorytmu w postaci programu

Napiszemy prosty program, który będzie obliczał NWD według omówionego algorytmu.

# pobierz liczbę naturalną a


# pobierz liczbę naturalną b


# pętla obliczająca NWD


# wypisanie wyniku
print("NWD(", a, ",", b,") = ", a)

Dane

Jak wynika z komentarzy w kodzie programu, na początku musimy pobrać dane, czyli dwie dodatnie liczby naturalne.

# pobierz liczbę naturalną a
a = int(input("Podaj liczbę a: "))

# pobierz liczbę naturalną b
b = int(input("Podaj liczbę b: "))

Pętla

W najważniejszej części algorytmu porównujemy podane liczby, dopóki nie są równe. Warunek ten możemy zapisać jako a != b. Ponieważ nie wiemy, ile trzeba powtórzeń, aby uzyskać wynik, w programie musimy użyć pętli while. Wewnątrz pętli do sprawdzania, która z liczb jest większa, będziemy potrzebowali instrukcji warunkowej if badającej warunek a > b. Do zakodowania operacji zmniejszania większej liczby o mniejszą użyjemy instrukcji przypisania, np. a = a - b.

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

# pobierz liczbę naturalną a
a = int(input("Podaj liczbę a: "))

# pobierz liczbę naturalną b
b = int(input("Podaj liczbę b: "))


# pętla obliczająca NWD
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

# wypisanie wyniku
print("NWD(", a, ",", b,") = ", a)

Przetestujmy działanie napisanego programu.

# Pierwszy zestaw danych
a = 4
b = 10

# Drugi zestaw danych
a = 1020
b = 20

NWD(a, b) = 2
NWD(a, b) = 20

Użycie funkcji

Obliczanie NWD to operacja, którą można w programie wykonywać wielokrotnie, np. gdy umożliwimy użytkownikowi wielokrotne podawanie liczb wejściowych. Kod realizujący tę operację umieścimy więc w funkcjifunkcjafunkcji, która do działania będzie wymagała dwóch parametrówparametry i argumenty funkcjiparametrów, tzn. pobranych liczb.

def oblicz_nwd(a, b):
    # kod pętli

W ciele funkcji należy umieścić zasadniczą część algorytmu, czyli pętlę obliczającą NWD.

def oblicz_nwd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a

Zwracanie wartości z funkcji

Po umieszczeniu pętli wyznaczającej NWD w funkcji musimy zdecydować, co zrobimy z wynikiem jej działania, tzn. ze zmienną a, która zawiera NWD. Moglibyśmy od razu wypisać wynik, ale w funkcjach, które coś obliczają, zazwyczaj się tego nie robi, chyba że testujemy ich działanie. Wynik działania funkcji najczęściej zwracamy do miejsca wywołania po to, żeby go wykorzystać, np. wypisać w terminalu albo użyć w dalszych obliczeniach.

Do zwracania wartości z funkcji używamy instrukcji return wyrażenie. Wyrażeniem może być zmienna, kilka zmiennych czy nawet wynik wywołania innej funkcji. W naszym przypadku wystarczy, że po pętli umieścimy instrukcję return a.

def oblicz_nwd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Wywołanie funkcji

Wykonywanie naszego programu rozpoczyna się od pobrania dwóch liczb od użytkownika. Po pobraniu tych danych musimy umieścić wywołaniewywołanie funkcjiwywołanie naszej funkcji w postaci oblicz_nwd(a, b). Liczby a i b przekazujemy jako argumenty.

Funkcja oblicz_nwd() zwraca wynik do miejsca wywołania. Możemy go przypisać do zmiennej d, a na koniec wypisać.

d = oblicz_nwd()

print("NWD(", a, ",", b,") = ", d)

def oblicz_nwd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

# pobierz liczbę naturalną a
a = int(input("Podaj liczbę a: "))

# pobierz liczbę naturalną b
b = int(input("Podaj liczbę b: "))

# wywołanie funkcji i przypisanie zwróconego wyniku
d = oblicz_nwd(a, b)

# wypisanie komunikatu:  NWD( a , b ) = d
print("NWD(", a, ",", b,") = ", d)

Notatnik

Film

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

Słownik

Bibliografia

• Największy wspólny dzielnik https://encyklopedia.pwn.pl/szukaj/najwi%C4%99kszy%20wsp%C3%B3lny%20dzielnik.html [dostęp 2022‑07‑07].

• Sysło M.M., Algorytmy, Helion, Gliwice 2016.