:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/algorytm-euklidesa-wyznaczanie-nwd.md

Algorytm Euklidesa, wyznaczanie NWD

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dowolnie wybranych dwóch liczb naturalnych. Został on opisany około 300 roku p.n.e. przez Euklidesa w dziele „Elementy” i jest jednym z najstarszych algorytmów wciąż pozostających w użyciu.

Pozwala on na wyznaczenie NWD, nie rozkładając liczb na czynniki pierwsze. Cały algorytm opiera się na poniższym założeniu:

algorytm-euklidesa

Zasada działania:

  1. Użytkownik musi wprowadzić dwie liczby naturalne, do zmiennych a oraz b;
  2. do zmiennej c przypisujemy resztę z dzielenia a przez b;
  3. zmienną a zastępujemy wartością zmiennej b, a do b przypisujemy wartość c;
  4. jeżeli b = 0 to NWD = a, jeżeli nie przejdź do punktu 2.

Przykładowy program wykorzystujący algorytm Euklidesa (napisany w języku Pascal):

pascal
program NWD;
USES crt;
VAR
    a,b,c:integer;
BEGIN
    clrscr;
    writeln('Podaj dwie liczby naturalne:');
    readln(a);
    repeat
         writeln('Druga liczba musi być różna od 0:');
         readln(b);
    until b <> 0;

    {obliczamy NWD}

    repeat
         c := a mod b;
         a := b;
         b := c;
    until b = 0;

    {wyświetlamy wynik}
    writeln('NWD = ', a);
    repeat until keypressed;
end.

Przykład rozpisany: NWD(252, 105)

Zobaczmy algorytm w akcji na konkretnych liczbach. W każdym kroku większą liczbę zastępujemy resztą z dzielenia:

Krokaba mod b
125210542
21054221
342210

Reszta wyszła zero, więc NWD(252, 105) = 21. Trzy dzielenia zamiast rozkładania obu liczb na czynniki pierwsze, i to jest cała elegancja tego algorytmu: liczby maleją bardzo szybko, więc nawet dla ogromnych wartości kroków jest niewiele (złożoność logarytmiczna).

Implementacje: iteracyjna i rekurencyjna

cpp
// C++ - wersja iteracyjna (petla while)
int nwd(int a, int b) {
    while (b != 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

// C++ - wersja rekurencyjna, ten sam pomysl w dwoch liniach
int nwdRek(int a, int b) {
    if (b == 0) return a;
    return nwdRek(b, a % b);
}
python
# Python - identyczna logika
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


print(nwd(252, 105))   # 21

Bonus: NWW z NWD i praktyczne zastosowanie

Znając NWD, najmniejszą wspólną wielokrotność liczymy jednym wzorem: NWW(a, b) = a · b / NWD(a, b). Dla naszych liczb: 252 · 105 / 21 = 1260. A po co to wszystko w praktyce? Klasyczne zastosowanie to skracanie ułamków (licznik i mianownik dzielimy przez ich NWD), sprowadzanie ułamków do wspólnego mianownika (przez NWW) oraz kryptografia, gdzie rozszerzona wersja algorytmu Euklidesa pracuje w sercu RSA.

Wersje w Javie i C#

Java:

java
public class Main {

    public static int nwd(int a, int b) {
        while (b != 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(nwd(252, 105));   // 21
    }
}

C#:

csharp
using System;

class Program
{
    static int Nwd(int a, int b)
    {
        while (b != 0)
        {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }

    static void Main()
    {
        Console.WriteLine(Nwd(252, 105));   // 21
    }
}
udostępnij: ·
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).