Algorytm Euklidesa

Znany matematyk starożytnej Grecji, Euklides,  opisał prosty sposób znajdowania wspólnej miary dwóch odcinków - czyli znajdowania takiego odcinka, który można odłożyć całkowitą liczbę razy zarówno w jednym, jak i w drugim odcinku.

 

 

Euklides zauważył, iż wspólna miara odkłada się również całkowitą liczbę razy w różnicy odcinków a - b. Zatem od dłuższego odcinka odejmujemy krótszy dotąd, aż otrzymamy odcinki o równej długości - ich dalsza różnica równa jest 0. Długość dowolnego z wynikowych odcinków jest wspólną miarą odcinków wejściowych.

W języku liczb naturalnych wspólna miara liczb a i b jest ich Największym Wspólnym Dzielnikiem, czyli NWD (ang. GCD - Greatest Common Divisor). Przez NWD liczb a i b rozumiemy największą liczbę naturalną, która dzieli bez reszty liczbę a i liczbę b. NWD dwóch liczb a i b zawsze istnieje - w ostateczności jest równy 1.

Pierwszy algorytm znajduje NWD odejmując w pętli od większej liczby mniejszą dotąd, aż liczby te się zrównają.

 

Algorytm obliczania NWD - wersja nr 1

Dane wejściowe:

a,b - liczby naturalne, których NWD poszukujemy

 

Dane wyjściowe:

NWD(a,b)

 

Lista kroków:

K01: Czytaj a,b
K02: Dopóki ab wykonuj K03
K03:     Jeśli a > b, to aa - b, inaczej bb - a
K04: Pisz a
K05: Zakończ

 

Schemat blokowy:

 

Program w języku C++:

Ćwiczenie na lekcji

 


 

Pierwszy algorytm jest poprawny, lecz mało efektywny. Wyobraźmy sobie, iż a = 4000000000, a b = 2. Rozwiązanie zostanie znalezione dopiero po wykonaniu dwóch miliardów odejmowań. Tymczasem od liczby większej mniejszą można odjąć tyle razy, ile większa dzieli się przez mniejszą. To co pozostanie jest resztą z dzielenia. Zatem algorytm Euklidesa możemy zmodyfikować następująco:

W pętli dzielną zastępujemy dzielnikiem, a dzielnik resztą z dzielenia dzielnej przez dzielnik dotąd, aż po tej zamianie dzielnik osiągnie wartość 0. Wtedy dzielna jest równa NWD.

 

Algorytm obliczania NWD - wersja nr 2

Dane wejściowe:

a,b - liczby naturalne, których NWD poszukujemy

 

Dane wyjściowe:

NWD(a,b)

 

Zmienne pomocnicze:

x - przechowuje dzielnik

 

Lista kroków:

K01: Czytaj a,b
K02: x b
K03: ba mod b
K04: ax
K05: Jeśli b ≠ 0, to idź do K02
K06: Pisz a
K07: Koniec

 

Schemat blokowy:

 

Program w języku C++:

Ćwiczenie na lekcji

 

Zadania

Wykorzystując algorytm Euklidesa napisz programy w języku C++:

  1. Sprawdzania względnej pierwszości dwóch liczb naturalnych a i b.

  2. Obliczania najmniejszej wspólnej wielokrotności dwóch liczb a i b

  3. Obliczania sumy ułamków l1, m1 i l2, m2, gdzie wynik jest ułamkiem nieskracalnym l, m

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.