Stosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z resztą z dzielenia

Algorytm wyznaczania największego wspólnego dzielnika opisany został przez greckiego matematyka Euklidesa. Algorytm ten ma dwie wersje. Pierwsza wykorzystuje odejmowanie i została przedstawiona w e‑materiale Stosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z odejmowaniemP1BvUOkroStosowanie funkcji w języku Python do realizacji algorytmu Euklidesa z odejmowaniem. Druga wersja –  wykorzystująca operacje obliczania reszty z dzielenia – zostanie opisana w tym e‑materiale.

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 liczb całkowitych 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 nieskracalnej, tzn. takiej, w której licznik i mianownik są liczbami względnie pierwszymi, czyli NWD(a, b) = 1.

Algorytm Euklidesa z zastosowaniem działania reszty z dzielenia

Specyfikacja algorytmu:

Dane wejściowe:

• a, b – dodatnie liczby naturalne

Wynik:

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

Do rozwiązania postawionego problemu użyjemy algorytmu Euklidesa w wersji z zastosowaniem działania reszty z dzielenia.

Przeanalizujemy schemat blokowy algorytmu.

R1crwcNRkMMEP

Na diagramie widoczny jest algorytm wyznaczania największego wspólnego dzielnika dwóch liczb przy użyciu metody Euklidesa. Diagram jest przedstawiony w formie schematu blokowego. Algorytm rozpoczyna się od zielonego owalu z napisem START. Od niego schodzi strzałka w dół prowadząca do pierwszego różowego równoległoboku. W nim wpisany jest tekst Wczytaj liczbę a, Wczytaj liczbę b. Od równoległoboku schodzi strzałka w dół do fioletowego rombu. W nim wpisane jest b znak większe od zero. Od rombu odchodzą dwie strzałki. Jedna z napisem tak, druga z napisem nie. Strzałka z napisem tak prowadzi do zielone prostokąta. W nim wpisany jest tekst r znak równości a mod b, a znak równości b, b znak równości r. Od prostokąta prowadzi strzałka, która zakręca do strzałki odchodzącej od różowego równoległoboku. Strzałka z napisem nie prowadzi do drugiego różowego równoległoboku. W nim wpisany jest tekst Wypisz a. Od tego równoległoboku prowadzi strzałka do czerwonego owalu z napisem STOP.

Przykład pokazuje, że dopóki b > 0, powtarzamy wykonywanie następującego zestawu instrukcji: wyliczamy resztę z dzielenia a mod b, do a przypisujemy b, natomiast do b przypisujemy wyliczoną resztę. Kiedy b, czyli ostatnia obliczona reszta, wyniesie 0, algorytm kończy działanie, a wynikiem jest wartość a, czyli wartość przedostatniej wyliczonej reszty.

Najważniejszą częścią algorytmu jest pętla, która wykonuje się, dopóki warunek b > 0 jest prawdziwy. Wewnątrz pętli obliczamy resztę z dzielenia liczb r = a mod b i wykonujemy przypisania: a = b, b = r. Po zakończeniu pętli wypisujemy wynik, tj. wartość a.

Zapis algorytmu w postaci programu

Napiszemy program, który będzie obliczał NWD, wykorzystując omówiony algorytm.

# pobierz liczbę całkowitą a


# pobierz liczbę całkowitą 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 liczby naturalne większe od zera.

Kod z uzupełnionymi instrukcjami pobierania od użytkownika danych:

# pobierz liczbę całkowitą a
a = int(input("Podaj liczbę a: "))

# pobierz liczbę całkowitą b
b = int(input("Podaj liczbę b: "))

# pętla obliczająca NWD


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

Pętla

Naszym zadaniem jest teraz zapisanie w programie pętli obliczającej NWD. Ponieważ nie wiemy, ile razy trzeba wykonać instrukcje wewnętrzne pętli, aby uzyskać wynik, użyjemy instrukcji while. Pętla będzie działać, dopóki warunek b > 0 będzie prawdziwy. Wewnątrz pętli umieścimy trzy instrukcje przypisania. Pierwsza instrukcja przypisze zmiennej r obliczoną resztę z dzielenia: r = a % b, pozostałe instrukcje przypisania zmienią wartości zmiennych: a = b oraz b = r.

while b > 0:
    r = a % b
    a = b
    b = r

Gotowy kod:

# pobierz liczbę całkowitą a
a = int(input("Podaj liczbę a: "))

# pobierz liczbę całkowitą b
b = int(input("Podaj liczbę b: "))

# pętla obliczająca NWD
while b > 0:
    r = a % b
    a = b
    b = r

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

a = b
b = a % b

b = a % b
a = b

Wynik działania programów zaprezentowanych w testerce:

Przypadek pierwszy:
a: 51, b: 13
a: 13, b: 0
Zwrócona wartość: 13 

Przypadek drugi:
a: 51, b: 13
a: 12, b: 12
a: 0, b: 0
Zwrócona wartość: 0 

Przypadek ze zmienną pomocniczą:
a: 51, b: 13
r: 12 a: 13, b: 12
r: 1 a: 12, b: 1
r: 0 a: 1, b: 0, 
Zwrócona wartość: 1

Pierwsze dwie funkcje działają błędnie – prawidłowa wartość NWD podanych liczb wynosi 1.

W funkcji nwd_pierwsza(a, b), po aktualizacji a na b, wartość b jest ustawiana na a % b, tymczasem b powinno przyjąć poprzednią wartość r (reszta z dzielenia a przez b).

W funkcji nwd_druga(a, b) najpierw aktualizujemy b, a następnie a, co prowadzi do utraty oryginalnej wartości a przed kolejną iteracją.

Funkcja

Obliczanie NWD można w programie wykonywać wielokrotnie dla różnych danych. Fragment kodu programu służący do obliczania NWD zapiszemy w funkcjifunkcjafunkcji o nazwie oblicz_nwd(). Funkcja będzie wymagała dwóch parametrów – liczb naturalnych a i b. Zadaniem funkcji będzie obliczenie NWD liczb a i b oraz zwrócenie odpowiedniego wyniku.

def oblicz_nwd(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

Użycie funkcji

W programie umieścimy wywołaniewywołanie funkcjiwywołanie funkcji oblicz_nwd(). Pobrane liczby (zmienne l1 i l2) przekażemy jako argumenty, tj. konkretne wartości parametrów w wywołaniu funkcji. Zwrócony wynik przypiszemy do zmiennej d, aby wypisać go na końcu programu.

d = oblicz_nwd(l1, l2)

print("NWD(", l1, ",", l2,") = ", d)

def oblicz_nwd(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

l1 = int(input("Podaj pierwszą liczbę: "))
l2 = int(input("Podaj drugą liczbę: "))

d = oblicz_nwd(l1, l2)

print("NWD(", l1, ",", l2,") = ", d)

# Pierwszy zestaw danych
l1 = 8
l2 = 38

# Drugi zestaw danych
l1 = 68
l2 = 16

# Trzeci zestaw danych
l1 = 7
l2 = 17

NWD(8, 38) = 2
NWD(68, 16) = 4
NWD(7, 17) = 1

Skracanie ułamków

Jednym z zastosowań algorytmu Euklidesa jest skracanie ułamków zwykłych. Wykorzystamy napisany wcześniej program do tego zadania.

Przyjmiemy, że danymi będą licznik i mianownik ułamka, który chcemy skrócić. Powinny to być liczby całkowite większe od 0, więc do programu dodamy instrukcję warunkową, która będzie sprawdzała, czy tak jest. Jeżeli któraś z podanych liczb będzie mniejsza od jeden, wypiszemy komunikat i zakończymy program, wywołując funkcję exit():

if l1 < 1 or l2 < 1:
    print("Błędne dane!")
    exit()

Skracanie ułamka zwykłego polega na podzieleniu licznika i mianownika przez tę samą liczbę - największy wspólny dzielnik licznika i mianownika. W tym wypadku liczbą będzie największy wspólny dzielnik zapisany w zmiennej d. Jeżeli będzie on większy niż 1, wypiszemy skrócony ułamek.

Pełen kod programu:

def oblicz_nwd(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

l1 = int(input("Podaj licznik: "))
l2 = int(input("Podaj mianownik: "))

if l1 < 1 or l2 < 1:
    print("Błędne dane!")
    exit()

d = oblicz_nwd(l1, l2)
print("NWD(", l1, ",", l2,") = ", d)

if d > 1:
    print("Ułamek:", l1, "/", l2)
    print("Po skróceniu:", l1 // d, "/", l2 // d)
else:
    print("Ułamka nie da się skrócić.")

W kodzie warto zwrócić uwagę na operator //, który oznacza dzielenie całkowite.

# Pierwszy zestaw danych
l1 = 9
l2 = 45

# Drugi zestaw danych
l1 = 7
l2 = 9

NWD( 9 , 45 ) =  9
Ułamek: 9 / 45
Po skróceniu: 1 / 5

NWD( 7 , 9 ) =  1
Ułamka nie da się skrócić.

Notatnik

Symulacja interaktywna

R1HnYmDmqDrqF

Symulacja dotyczy algorytmów do znajdowania największego wspólnego dzielnika (NWD) przy użyciu dwóch metod: odejmowania i dzielenia modulo. Na grafice znajduje się instrukcja dotycząca analizy tych algorytmów. Instrukcja jest umieszczona w ramce z niebieskim obramowaniem, z ilustracją osoby w lewym górnym rogu oraz pytajnikiem w różowym kółku nad ilustracją. Po lewej stronie widnieje tekst: „Korzystając z przygotowanej symulacji, przeanalizuj, jak przebiega znajdowanie NWD w obydwu algorytmach dla wartości podanych w polach zamieszczonych pod symulacją. Zwróć uwagę na wartości, które przyjmują zmienne w kolejnych powtórzeniach oraz liczbę powtórzeń koniecznych do uzyskania wyniku. By wykonać jedno powtórzenie działania pętli, użyj przycisku „Wykonaj jedno powtórzenie”. By obliczyć od razu wynik końcowy, użyj przycisku „Oblicz wynik końcowy'”. W centralnej części grafiki znajdują się dwa prostokąty z pseudokodem algorytmów: pętla wykorzystująca odejmowanie oraz pętla wykorzystująca dzielenie modulo. Poniżej znajdują się pola do wprowadzenia wartości liczb a i b oraz dwa przyciski: „Wykonaj jedno powtórzenie” oraz „Oblicz wynik końcowy”. Pola te umożliwiają użytkownikowi interaktywne wprowadzenie danych i przeprowadzenie symulacji działania algorytmów.

Symulacja dotyczy algorytmów do znajdowania największego wspólnego dzielnika (NWD) przy użyciu dwóch metod: odejmowania i dzielenia modulo. Na grafice znajduje się instrukcja dotycząca analizy tych algorytmów. Instrukcja jest umieszczona w ramce z niebieskim obramowaniem, z ilustracją osoby w lewym górnym rogu oraz pytajnikiem w różowym kółku nad ilustracją. Po lewej stronie widnieje tekst: „Korzystając z przygotowanej symulacji, przeanalizuj, jak przebiega znajdowanie NWD w obydwu algorytmach dla wartości podanych w polach zamieszczonych pod symulacją. Zwróć uwagę na wartości, które przyjmują zmienne w kolejnych powtórzeniach oraz liczbę powtórzeń koniecznych do uzyskania wyniku. By wykonać jedno powtórzenie działania pętli, użyj przycisku „Wykonaj jedno powtórzenie”. By obliczyć od razu wynik końcowy, użyj przycisku „Oblicz wynik końcowy'”. W centralnej części grafiki znajdują się dwa prostokąty z pseudokodem algorytmów: pętla wykorzystująca odejmowanie oraz pętla wykorzystująca dzielenie modulo. Poniżej znajdują się pola do wprowadzenia wartości liczb a i b oraz dwa przyciski: „Wykonaj jedno powtórzenie” oraz „Oblicz wynik końcowy”. Pola te umożliwiają użytkownikowi interaktywne wprowadzenie danych i przeprowadzenie symulacji działania algorytmów.

Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DN1sz1Nco

Symulacja dotyczy algorytmów do znajdowania największego wspólnego dzielnika (NWD) przy użyciu dwóch metod: odejmowania i dzielenia modulo. Na grafice znajduje się instrukcja dotycząca analizy tych algorytmów. Instrukcja jest umieszczona w ramce z niebieskim obramowaniem, z ilustracją osoby w lewym górnym rogu oraz pytajnikiem w różowym kółku nad ilustracją. Po lewej stronie widnieje tekst: „Korzystając z przygotowanej symulacji, przeanalizuj, jak przebiega znajdowanie NWD w obydwu algorytmach dla wartości podanych w polach zamieszczonych pod symulacją. Zwróć uwagę na wartości, które przyjmują zmienne w kolejnych powtórzeniach oraz liczbę powtórzeń koniecznych do uzyskania wyniku. By wykonać jedno powtórzenie działania pętli, użyj przycisku „Wykonaj jedno powtórzenie”. By obliczyć od razu wynik końcowy, użyj przycisku „Oblicz wynik końcowy'”. W centralnej części grafiki znajdują się dwa prostokąty z pseudokodem algorytmów: pętla wykorzystująca odejmowanie oraz pętla wykorzystująca dzielenie modulo. Poniżej znajdują się pola do wprowadzenia wartości liczb a i b oraz dwa przyciski: „Wykonaj jedno powtórzenie” oraz „Oblicz wynik końcowy”. Pola te umożliwiają użytkownikowi interaktywne wprowadzenie danych i przeprowadzenie symulacji działania algorytmów.

# Pierwszy zestaw
a = 56
b = 3

# Drugi zestaw
a = 3
b = 56

# Pierwszy zestaw danych
a = 3
b = 566

# Drugi zestaw danych
a = 3
b = 5666

Zestaw ćwiczeń interaktywnych

Słownik

def nazwa_funkcji():
	# ciało funkcji

Bibliografia

• Bhargava A.Y., Algorytmy. Ilustrowany przewodnik, wyd. Helion, Gliwice 2017.

• Lutz M., Python. Wprowadzenie (wyd. V), wyd. Helion, Gliwice 2022.

• Algorytm Euklidesa, pl.wikipedia.org, dostęp 08.03.2024.

• Największy wspólny dzielnik, encyklopedia.pwn.pl, dostęp 08.03.2024.