Algorytm Euklidesa

Praktycznym i szybkim sposobem obliczania największego wspólnego dzielnika dwóch liczb całkowitych jest algorytm Euklidesa. Jest to jeden z najstarszych algorytmów - został opisany przez Euklidesa ok. roku 300 p.n.e. Opiera się on na spostrzeżeniu, że jeśli od większej liczby odejmiesz mniejszą, to mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego odejmowania otrzymasz parę równych liczb, oznacza to, że znalazłeś NWD.

Algorytm Euklidesa jest algorytmem rekurencyjnym, chociaż w bardzo prosty sposób można go przekształcić do formy iteracyjnej. Mając do policzenia NWD(a, b) sprawdzamy, czy b = 0. Jeśli tak jest to NWD(a, b) = a. W przeciwnym wypadku wywołujemy rekurencyjnie algorytm dla liczb b i reszty z dzielenia a przez b.

Dane są dwie liczby naturalne a i b.
1. Jeśli b ≠ 0 oblicz c jako resztę z dzielenia a przez b i zastąp a przez b, zaś b przez c.
2. Jeżeli b = 0, NWD wynosi a, w przeciwnym wypadku wróć do punktu pierwszego i kontynuuj.

Nasuwa się pytanie, czy takie postępowanie zawsze się skończy. Istotnie dla liczb naturalnych zawsze tak jest. Korzyść z algorytmu Euklidesa jest taka, że ostatnia niezerowa reszta jest, co łatwo sprawdzić jest największym wspólnym dzielnikiem liczb a i b.

Przykład
243 : 111 = 2, reszty 21
111 : 21 = 5, reszty 6
21 : 6 = 3, reszty 3
6 : 3 = 2, reszty 0
Ostatnia niezerowa reszta wynosi 3.
NWD(243, 111) = 3


ZnajdĽ NWD za pomocą algorytmu Euklidesa

,   
matematyka » arytmetyka » podzielność liczb » nwd » algorytm Euklidesa




gość logowanie

© 2014 Mariusz Śliwiński      mapa | o serwisie | kontakt | rss online: 256 drukuj