algorytm Euklidesa
 
Encyklopedia PWN
algorytm Euklidesa,
mat. metoda wyznaczania największego wspólnego dzielnika (NWD) 2 liczb całkowitych lub 2 wielomianów (znana już w starożytności).
Schemat czynnościowy algorytmu Euklidesa dla liczb orzeka: weź liczby ab, oznacz przez M większą z nich [max (a, b)], a przez m mniejszą [min (a, b)], oblicz resztę z dzielenia M : m [r = reszta (M : m)]. Gdy ta reszta jest zerem, wówczas m jest szukanym NWD liczb ab; jeżeli reszta r ≠ 0, wówczas w miejsce M weź m [mM], w miejsce m weź r [rm], po czym kontynuuj (pętla powrotna) obliczanie reszty z dzielenia nowych wartości Mm itd., aż któraś z kolei reszta będzie równa zeru. Algorytm Euklidesa jest także nazywany metodą kolejnych dzieleń lub algorytmem ułamka ciągłego.
Ilustracje
Euklidesa algorytm, schemat wykonawczyrys. Archiwum Ilustracji WN PWN SA © Wydawnictwo Naukowe PWN
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia