algorytm euklidesa
Algorytm Euklidesa
Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych.
Algorytm
Aby obliczyć NWD(a,, wykonujemy kolejno następujące kroki:
Dzielimy z resztą liczbę a przez liczbę b jeżeli reszta =0, to NWD(a,b)=b jeżeli reszta ?0, to przypisujemy liczbie a wartość liczby b, liczbie b wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.Przykład 1.
Wyznacz największy wspólny dzielnik liczb 282 i 78.
Rozwiązanie:
Zaczynamy od podzielenia liczby 282 przez liczbę 78 z resztą:
282:78=3, reszty 48
Otrzymaliśmy resztę różną od zera, zatem teraz podzielimy liczbę 78 przez resztę 48. Ten schemat będziemy powtarzać do momentu otrzymania reszty równej 0.
78:48=1, reszty 3048:30=1, reszty 1830:18=1, reszty 1218:12=1,<span style="transition: none
Dodaj komentarz