Jak wyznaczyć największy wspólny dzielnik dwóch liczb?
Największy wspólny dzielnik dwóch liczb (NWD) to największa taka liczba naturalna, która dzieli bez reszty obie te liczby. Do wyznaczenia tej liczby użyjemy algorytmu Euklidesa. Załóżmy, że dane są dwie liczby naturalne a i b.
Kroki
1
Jeżeli liczba b jest różna od zera to:
niech c będzie resztą z dzielenia a przez b;
niech a będzie miało teraz wartość b;
niech b będzie miało teraz wartość c;
przejdź do kroku 2.
przejdź do kroku 2.
2
Jeżeli liczba b jest równa zero:
to liczba a jest szukanym NWD. Przejdź do kroku 3.
w przeciwnym przypadku przejdź do kroku 2.
w przeciwnym przypadku przejdź do kroku 2.
3
Problem zawsze najlepiej zobrazować przykładem, dlatego na zdjęciu pokazałem kolejne kroki algorytmu przy założeniu, że szukamy NWD dla liczb 19305 i 2392. W ostatniej linijce widać, że liczba a ma wartość 13, czyli największym wspólnym dzielnikiem powyższych liczb jest liczba 13.
Oceń tę poradę
1.8
(4 głosów)
Twoja ocena:
Zapisywanie głosu...