Blog o programowaniu
Algorytmy

Algorytm Euklidesa

Poniższy materiał to część cyklu „Algorytmy dla uczniów”

Algorytm Euklidesa czyli algorytm wyznaczania  NWD – największego wspólnego dzielnika dwóch liczb całkowitych.

Zadanie:
Wyznacz największy wspólny dzielnik dwóch liczb naturalnych: a,b.

Przeanalizujmy zadanie. Dane mamy dwie liczby oznaczone jako a i b. Musimy odnaleźć liczbę przez którą dzielą się nasze obie liczby, zarówno a i b. Takich liczb może być wiele – my mamy odszukać największą.

Przykłady
Dane mamy dwie liczby: 4 i 6.
Dla tych liczb wspólnym dzielnikiem będą: 1, 2. Zatem największym wspólnym dzielnikiem obu tych liczb jest liczba 2.

Dane:  12, 9
Wynik: 3

Dane: 304, 304
Wynik: 304

Dane: 700, 21
Wynik:  7

Dane: 11, 76
Wynik: 1

Na tym etapie możemy zastanowić jak wyznaczyliśmy wspólny dzielnik i opracować algorytm. Możemy jednak skorzystać z gotowego rozwiązania, które opracował Euklides.

Algorytm Euklidesa

Wyznaczanie NWD, a więc największego wspólnego podzielnika dwóch liczb naturalnych
zrealizujemy za pomocą algorytmu Euklidesa. Opiera się on na
spostrzeżeniu, że jeśli odejmiemy od większej liczby mniejszą, to ta
mniejsza liczba i otrzymana różnica będą miały taki sam największy
wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego
odejmowania otrzymamy parę równych liczb, oznacza to, że znaleźliśmy NWD.

Algorytm Euklidesa: schemat blokowy

Przedstawimy teraz algorytm w postaci schematu blokowego. Na początku następuje wczytanie dwóch liczb. Następnie sprawdzamy czy są to takie same liczby. Jeśli bowiem liczby są równe to od razu wiemy iż ich wspólnym dzielnikiem jest ta sama liczba (przykład 3).
Jeśli liczby są różne sprawdzamy która z nich jest większa, by od większej liczby odjąć mniejszą.

Schemat blokowy algorytmu Euklidesa
Algorytm Euklidesa. Schemat blokowy

Podsumowanie

Ten artykuł jest częścią cyklu „Algorytmy dla uczniów”. Cały kurs zawierający materiały dotyczące algorytmów dla początkujących zawiera:

Lekcja 1: Co to jest algorytm? Podstawy algorytmów

Lekcja 2:  Sposoby zapisu algorytmów

Lekcja 3: Rodzaje algorytmów

Lekcja 4: Schematy blokowe algorytmów

Lekcja 5: Specyfikacja algorytmu. Specyfikacja problemu algorytmicznego

Lekcja 6: Algorytmy Przykłady i zadania 

Lekcja 6.1: Algorytmy. Przykłady i zadania.  Obliczanie pola trójkąta

Lekcja 6.2:  Algorytmy. Przykłady. Algorytm Euklidesa

Lekcja 6.3: Algorytm. Gra Kamień Papier Nożyce

Lekcja 7. Przykłady schematów blokowych. Ciągi liczb

Lekcja 8. Sortowanie – algorytmy sortowania

Lekcja 9: Algorytmy. Tablice jednowymiarowe

Lekcja 10. Algorytmy. Tablice dwuwymiarowe 


Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *