Algorytm Euklidesa

Witam!

Dzisiaj chciałbym przybliżyc wam na czym polega algorytm Euklidesa.

Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika dwóch liczb.Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy” .Najprostsza wersja algorytmu rozpoczyna się od wybrania dwóch liczb naturalnych, dla których należy wyznaczyć największy wspólny dzielnik. Następnie z tych dwóch liczb tworzymy nową parę: pierwszą z liczb jest liczba mniejsza, natomiast drugą jest różnica liczby większej i mniejszej. Proces ten jest powtarzany aż obie liczby będą sobie równe – wartość tych liczb to największy wspólny dzielnik wszystkich par liczb wcześniej wyznaczonych. Wadą tej wersji algorytmu jest duża liczba operacji odejmowania, które należy wykonać w przypadku, gdy różnica pomiędzy liczbami z pary jest znacząca. Np. Załóżmy, że chcemy znaleźć największy wspólny dzielnik liczb 1989 oraz 867. Jeżeli od większej liczby odejmiemy liczbę mniejszą, wartość największego wspólnego dzielnika nie ulegnie zmianie. Ponieważ 1989 – 867 = 1122, nowa para liczb wygląda następująco:

1122, 867

Ponownie odejmujemy mniejszą liczbę od większej 1122 – 867 = 255, tworząc w ten sposób kolejną parę:

255, 867

867 nie jest już mniejszą liczbą. Stosując ten sam sposób, ponownie zmniejszamy wartość większej liczby o wartość mniejszej: 867 – 255 = 612, nowa para liczb to:

255, 612

Pierwsza liczba, 255, jest wciąż mniejsza, ponownie więc odejmujemy 255 od liczby większej: 612 – 255 = 357, więc kolejna para liczb to:

255, 357

357 – 255 = 102, kolejna para to:

255, 102

Teraz widać, że 255 jest większą liczbą, odejmujemy więc od niej 102, co daje nam parę:

153, 102

Odjęcie 102 od 153 tworzy nam kolejną parę:

51, 102.

Teraz odejmujemy 51 od 102, co daje nam: 51 i 51. 51 jest największym wspólnym dzielnikiem liczb 1989 i 867.

Dziekuje za uwagę.