NWD i NWW

NWD

Do czego służy?

NWD - Największy Wspólny Dzielnik. Zapewne słyszałeś/słyszałaś o czymś takim w szkole na matematyce. Tam żeby obliczyć NWD najpierw rozkładało się liczby na czynniki pierwsze. Lecz w algorytmice, takie podejście jest zbyt wolne... Z pomocą przychodzi algorytm wymyślony już w starożytności!

Algorytm

Algorytm Euklidesa, służący do znajdowania NWD (dla liczb n, k) działa w taki sposób (zakładamy że n <= k): x(dodatkowa zmienna przechowująca poprzednią wartość n) ustawiamy na n
n ustawiamy na k - n
k ustawiamy na x (czyli poprzednie n)
Powtarzamy te trzy kroki aż n będzie równe zero. Wynikiem będzie k.
Niestety taki algorytm pesymistycznie będzie działał w O(k). Ale można go przyspieszyć! Zamiast różnicy k - n będziemy brać resztę z dzielenia k przez n. Tutaj nawet bez założenia, że n <= k algorytm będzie działał - w pierwszym kroku n i k się zamienią. Dokładniej algorytm będzie wyglądał tak:
x ustawiamy na n
n ustawiamy na k mod n (reszta z dzielenia k przez n)
k ustawiamy na x (czyli poprzednie n)
Powtarzamy to aż n będzie równe 0. Wynikiem będzie k. Złożoność tego algorytmu jest mniejsza - wynosi log₂(max(n, k)).

Przykład

Policzmy NWD liczb 12 i 32.
n = 12, k = 32
n = 32 mod 12 = 8, k = 12
n = 12 mod 8 = 4, k = 8
n = 8 mod 4 = 0, k = 4
Tutaj zauważamy, że n jest równy 0, więc zwracamy k.
NWD(12, 32) = 4

Implementacja i złożoność

implementacja w c++:

int nwd(int k, int n){
int x;
while (n != 0){
x = n;
n = k % n;
k = x;
}
return k;
}

implementacja w python:

def nwd(n, k):
x = 0
while k != 0:
x = n % k
n, k = k , x
return n

złożoność:

O(log₂(max(n, k)))

Zadania

Zadanie C. Modified GCD(GCD to NWD tyle że po angielsku)
Zadanie Wesoła Małpka

NWW

Do czego służy?

NWW - Najmniejsza Wspólna Wielokrotność. Pewnie słyszałeś/słyszałaś już o nim na lekcjach matematyki w szkole. Tam żeby policzyć NWW, najpierw trzeba było rozłożyć liczbę na czynniki pierwsze. Jednak istnieje dużo prostszy sposób, który jest też lepszy dla komputera. Jest jednak do niego potrzebne NWD. Jeśli jeszcze nie znasz algorytmu NWD to patrz powyżej.

Algorytm

NWW dla dwóch liczb (n i k) opisuje się wzorem:
n * k / NWD(n, k)
Zauważmy, że ta liczba będzie zawsze całkowita - n*k musi być podzielne przez NWD(n, k). Jeśli umiemy policzyć NWD, to jesteśmy w stanie policzyć NWW. Kod niewiele będzie się różnił, tylko w NWW dodamy drugą funkcję, która nam policzy w złożoności O(1) NWW. Złożoność załego algorytmu będzie taka sama jak złożoność algorytmu NWD (jedynkę pomijamy - jest nieistotna), czyli log₂(max(n, k))

Przykład

Policzmy NWW liczb 12 i 32.
NWW(12, 32) = 12 * 32 / NWD(12, 32)
NWD(12, 32) = 4
12 * 32 = 384
NWW(12, 32) = 384 / 4
NWW(12, 32) = 96

Implementacja i złożoność

implementacja w c++:

int nwd(int k, int n){
int x;
while (n != 0){
x = n;
n = k % n;
k = x;
}
return k;
}

int nww(int k, int n){
int x;
x = (k * n) / nwd(k, n);
return x;
}

implementacja w python:

def nwd(n, k):
x = 0
while k != 0:
x = n % k
n, k = k , x
return n

def nww(n, k):
return n*k // nwd(n, k)

złożoność:

O(log₂(max(n, k)))