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 poprzednim e‑materiale, druga wersja, wykorzystująca operacje obliczania reszty z dzielenia, zostanie opisana w tym e‑materiale.

NWD

Największy wspólny dzielnik (NWD) dwóch 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 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, do b przypisujemy wyliczoną resztę. Kiedy b, czyli ostatnia obliczona reszta, wyniesie 0, algorytm kończy działanie, 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.

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.

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.

# 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/DkQUBpqX1

# 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

A teraz... czas na ćwiczenia!