Login lub e-mail Hasło   

Największy wspólny dzielnik - algorytm Euklidesa

Wprowadzenie Z pewnością każdy z nas miał do czynienia w szkole na lekcjach matematyki z pojęciem największego wspólnego dzielnika dwóch lub więcej liczb. W skr&oa...
Wyświetlenia: 18.314 Zamieszczono 29/10/2006

Wprowadzenie

Z pewnością każdy z nas miał do czynienia w szkole na lekcjach matematyki z pojęciem największego wspólnego dzielnika dwóch lub więcej liczb. W skrócie wyrażaliśmy to NWD. Okazuje się, iż istnieje efektywny algorytm liczenia NWD. Jest to jeden z najstarszych algorytmów - został opisany przez Euklidesa ok. roku 300 p.n.e.

 

Idea

Algorytm Euklidesa jest algorytmem rekurencyjnym, chociaż w bardzo prosty sposób można go przekształcić do formy iteracyjnej. Jego idea jest następująca: 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 (a mod b), czyli liczymy NWD(b, (a mod b)). Dla tych którzy nie wiedzą - a mod b to reszta z dzielenia a przez b. Np. 7 mod 2=1, 15 mod 10=5, 8 mod 4=0.

 

Przykład

Rozważmy obliczenie NWD dla liczb 54 i 69. Ponieważ  liczba b, czyli 69 nie jest równe 0 więc wykonujemy algorytm dla b i (a mod b). W tym przypadku będą to liczby 69 i (54 mod 69), czyli 54. Proszę zauważyć, że liczby w tym przypadku zamieniły się miejscami. Tak więc liczby w algorytmie Euklidesa nie muszą być podane w odpowiedniej kolejności - zostaną one automatycznie odwrócone. Dobra, wróćmy do naszego przykładu. Teraz mamy liczby 69 i 54. Ponieważ 54 nie jest równe 0, to wykonujemy rekurencyjnie algorytm dla liczb 54 i (69 mod 54), czyli 15. Znowu druga liczba nie wynosi 0. Wykonujemy dalej rekurencyjnie algorytm i otrzymujemy liczby 15 i (54 mod 15)=9. Liczba 9 nie jest zerem, więc wykonując dalej algorytm otrzymujemy liczby 9 i (15 mod 9), czyli 6. Jak poprzednio 6 nie jest równe 0, tak więc po kolejnym rekurencyjnym wywołaniu otrzymujemy 6 i (9 mod 6)=3. Jak wiadomo 3 to nie zero, więc wykonujemy algorytm dalej i otrzymujemy liczby 3 i (6 mod 3)=0. Ponieważ druga liczba jest równa 0 tak więc szukane NWD jest równe pierwszej liczbie, czyli 3.

Analizując po kolei wszystkie kroki naszego przykładu możemy napisać:

NWD(54,69)=NWD(69,54)=NWD(54,15)=NWD(15,9)=NWD(9,6)=NWD(6,3)=NWD(3,0)=3

Można udowodnić, że algorytm Euklidesa działa najgorzej dla liczb Fibonacciego.

 

NWD dla więcej niż dwóch liczb

Czasami spotykamy sytuację, gdy mamy policzyć największy wspólny dzielnik dla kilku liczb. Co wtedy robić? Po prostu liczymy NWD dla dwóch pierwszych liczb. Potem liczymy NWD dla otrzymanego wyniku i liczby trzeciej. Następnie NWD dla otrzymanego wyniku i czwartej liczby... itd.

Na przykład - jak policzyć NWD dla 84, 96, 32 i 24. Oto wynik:

NWD(84, 96, 32, 24) = NWD(84, NWD(96, NWD(32, 24))) = NWD(84, NWD(96, 8)) = NWD(84, 8) = 4

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9205
10
komentarze: 0 | wyświetlenia: 2930
49
komentarze: 18 | wyświetlenia: 65793
12
komentarze: 3 | wyświetlenia: 30397
37
komentarze: 9 | wyświetlenia: 29286
11
komentarze: 2 | wyświetlenia: 33539
7
komentarze: 1 | wyświetlenia: 34809
17
komentarze: 4 | wyświetlenia: 14964
15
komentarze: 5 | wyświetlenia: 33396
13
komentarze: 2 | wyświetlenia: 23252
12
komentarze: 2 | wyświetlenia: 18692
11
komentarze: 1 | wyświetlenia: 10832
11
komentarze: 1 | wyświetlenia: 87040
10
komentarze: 1 | wyświetlenia: 35174
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska