Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
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ą.
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 a ≠ b wykonuj K03
K03: Jeśli a > b, to
a ←
a - b, inaczej b ← b - 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.
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: b ← a mod b
K04: a ← x
K05: Jeśli b ≠ 0, to idź do K02
K06: Pisz a
K07: Koniec
Schemat blokowy:
Program w języku C++:
Ćwiczenie na lekcji
Wykorzystując algorytm Euklidesa napisz programy w języku C++:
Sprawdzania względnej pierwszości dwóch liczb naturalnych a i b.
Obliczania najmniejszej wspólnej wielokrotności dwóch liczb a i b
Obliczania sumy ułamków l1, m1 i l2, m2, gdzie wynik jest ułamkiem nieskracalnym l, m
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe