Embedded Files
Algorytm Euklidesa (NWD)
Algorytm Euklidesa (NWD)
Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych.
Najwięszy wspólny dzielnik to największa liczba, która dzieli bez reszty każdą z dwóch podanych liczb.
Metoda 1. Realizacja z odejmowaniem (algorytm niezoptymalizowany)
Wybieramy większą z dwóch liczb i oddejmujemy od niej mniejszą (liczbę większą zastępujemy różnicą), aż do momentu jak liczby staną się równe, stanowiąc NWD.
(54, 30) → (54 – 30, 24)
(24, 30) → (30 – 24, 6)
(24, 6) → (24 – 6, 18)
(18, 6) → (18 – 6, 12)
(12, 6) → (12 – 6, 6)
(6, 6)
NWD (54, 30) = 6
Metoda 2. Realizacja z dzieleniem
Zauważmy, że w metodzie z odejmowaniem, wynik odejmowania był resztą resztą z dzielenia liczby większej przez mniejszą, stąd zamiast odejmowania możemy zastosować dzielenie z resztą.
Dzielimy kolejno 2 liczby (zastępując dzielną dzielnikiem, a dzielnik resztą z dzielenia dzielnej przez dzielnik), dopóki dzielnik nie osiągnie wartości 0. NWD jest równy ostatniej niezerowej reszcie.
54 : 30 = 1 reszty 24
30 : 24 = 1 reszty 6
24 : 6 = 4 reszty 0
Z1. NWD (odejmowanie, iteracja)
Napisz program wyznaczający NWD w wersji z odejmowaniem, metodą iteracyjną.
Z2. NWD (dzielenie, iteracja)
Przedstaw w postaci listy kroków, schematu blokowego oraz programu algorytm wyznaczania NWD dwóch liczb naturalnych różnych od zera (w wersji z dzieleniem, metodą iteracyjną).
Z3. NWD (dzielenie, iteracja, funkcja)
Napisz program wyznaczający NWD w wersji z dzieleniem, metodą iteracyjną. Zdefiniuj funkcję z dwoma parametrami, którą wywołasz w funkcji głownej main.
Report abuse