NWD

Największy wspólny dzielnik (w skrócie NWD)

Czym jest największy wspólny dzielnik?

Każdy zbiór liczb naturalnych ma zbiór wspólnych dzielników. "W najgorszym" przypadku taki zbiór wspólnych dzielników (liczb, przez które one obie dzielą się bez reszty) składa się z jednego elementu:

\(\{1\}\)

ponieważ każda liczba naturalna jest podzielna przez \(1\). Przyjrzyjmy się parze liczb, którą otrzymałem przez losowanie w pseudolosowym kalkulatorze:

\(\{2238744, 5477478\}\)

Oczywiście, że możemy wyznaczyć wszystkie dzielniki dla tej pary, ale chyba nie będzie to najłatwiejszy przykład. Zastąpmy to czymś prostszym, np. :

\(\{8, 20\}\)

Wymieńmy wszystkie dzielniki obu liczb:

  • dla liczby \(8\) mamy zbiór dzielników (liczb przez które
    \(8\)  dzieli się bez reszty): \(\{1, 2, 4, 8\}\)
  • dla liczby \(20\) mamy zbiór dzielników (liczb przez które 
    \(20\)  dzieli się bez reszty): \(\{1, 2, 4, 5, 10, 20\}\)

Poszukajmy wśród nich wspólnych dzielników (zaznaczone na czerwono):

  • dla liczby \(8\): \(\{\color{red}{1}, \color{red}{2}, \color{red}{4}, 8\}\)
  • dla liczby \(20\): \(\{\color{red}{1}, \color{red}{2}, \color{red}{4}, 5, 10, 20\}\)

Jak widać wspólne dzielniki to:

\(1, 2, 4\)

A największy z nich to \(4\). Ta liczba jest największym wspólnym dzielnikiem (NWD).

Ten przykład nie był najtrudniejszy. Udało się wyznaczyć NWD prawie w pamięci (jak poćwiczysz, to dla takich zestawów liczb będziesz to potrafił). Jednak przy większych liczbach już trzeba się trochę wysilić. Ale jak to kiedyś pewna kobieta w autobusie powiedziała - nic co ludzkie nie jest mi obce. Ta kobieta jednak nie potrafiła podać algorytmów obliczania NWD. Wydaję mi się, że ja jednak potrafię. Co więcej - przygotowałem kilka skryptów do obliczania tego dzielnika:

Algorytm Euklidesa ...

... to jedna z metod wyznaczania NWD dwóch liczb. W podstawowym swoim zakresie wyznacza NWD dla dwóch liczb naturalnych. Poniżej przedstawione zostały narzędzia wyliczające NWD na podstawie algorytmu z dzieleniem modulo, drugi natomiast to klasyczny Euklides.

  • NWD online (modulo):
  • NWD online (klasyczny euklides):

Arkusz kalkulacyjny został odblokowany do edycji. Maksymalna ilość iteracji jest ograniczona do 294 kroków. NWD obliczone na podstawie algorytmu Euklidesa. Celowo zrezygnowałem z VBA i pętli, aby nie utrudniać w jego interpretacji. Ze względu na niezoptymalizowaną strukturę algorytmu wersja online została wykonana tak, aby użytkownik miał pełną kontrolę nad każdym krokiem obliczeniowym,


Czytaj też:
  NWD - wikipedia PL   Algorytm Euklidesa - wikipedia PL

NWD
5 (100%) 1 głos[ów]

One Comment

  1. Pingback: Skracanie ułamków zwykłych - Oblicz.com.pl

Comments are closed.