Algorytm Euklidesa
2017-04-25 / Krzysztof Kozłowski

Algorytm Euklidesa to sposób wyznaczania największego wspólnego dzielnika dwóch liczb (w skrócie zwanego NWD).

Przykład

Założmy, że chcemy znaleźć NWD liczb 12 i 18. Obie te liczby dzielą się przez: 1, 2, 3 i 6. Liczba 6 jest największą liczbą spośród tych będących dzielnikami i 12 i 18, a więc to liczba 6 jest nawiększym wspólnym dzielnikiem 12 i 18. W skrócie zapisujemy to jako NWD(12, 18) = 6

Algorytm

Algorytm Euklidesa jest bardzo prosty: sprawdzamy, która z obu liczb jest większa i od większej odejmujemy tę mniejszą. Drugą liczbę przepisujemy. Odejmowanie i przepisywanie powtarzamy tak długo, aż obie liczby będą równe.

Oto przykład wyznaczania NWD liczba 12 i 18:

Przyjmiemy, że liczbę 12 oznaczać będziemy jako np. liczbę a, 18 to będzie liczba b. 18 jest liczbą większą, więc odejmujemy od niej liczbę 12 i od tej pory to będzie nasza liczba a, czyli a = 18 – 12 = 6. Liczbę b (wynoszącą 12) przepisujemy.

Po dokonaniu pierwszego odejmowania a = 6, b = 12. Teraz to b jest większe, więc teraz to od tej liczby odejmujemy mniejszą i mamy: a = 6, b = 12 – 6 = 6.

Po drugim odejmowaniu okazuje się, że a i b są sobie równe (a = 6, b = 6), kończymy więc obliczenia. 6 jest największym wspólnym dzielnikiem liczb 12 i 18.

Schemat blokowy

Powyższy obrazek to tzw. schemat blokowy. Pokazuje on, jak powinien działać program zgodnie z wybranym algorytmem. Ważną rzeczą jest to, że schemat określa tylko ogólne działanie, bez względu na to jakiego języka programowania użyjemy do napisania programu.

Program

Program do wyznaczania NWD zrealizujemy jako aplikację konsolową, z tym że w klasie oprócz metody Main utworzymy sobie specjalną metodę o nazwie nwd(), która przyjmie jako argumenty dwie liczby całkowite, a w wyniku poda liczbę całkowitą, będącą nawiększym wspólnym dzielnikiem obu podanych liczb.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {

 public static void main(String[] args) {
   Integer nwd = nwd(12, 18);
   System.out.println(nwd);
 }
 
 public static Integer nwd(Integer a, Integer b) {
   while (a != b) {
     if (a > b) {
       a = a - b;
     } else {
       b = b - a;
     }
   } 
   return a;
 }
}

Działanie powyższego programu można sprawdzić w serwisie Repl.it.

Słowo wyjaśnienia należy się linijce:

1
Integer nwd = nwd(12, 18);

ponieważ nazwy nwd użyto i dla zmiennej i dla funkcji (metody). Jak widać nie jest to problemem z uwagi na to, że po nazwie metody występują nawiasy. Dzięki nawiasom Java wie, kiedy ma do czynienia ze zmiennymi lub polami klasy, a kiedy z funkcjami lub metodami klasy.

PermaLink: https://java.kozlowski.photos/2017/04/algorytm-euklidesa/