Największym wspólnym dzielnikiem liczb i jest taka liczba , która dzieli i przez możliwie jak największą wartość. Największy wspólny dzielnik jest bardzo często używany do skracania ułamków, bądź wyznaczania najmniejszej wspólnej wielokrotności.
Zacznijmy od najprostszego wariantu wyznaczania NWD. Jeżeli od większej liczby zaczniemy odejmować mniejszą i w pewnym momencie będą sobie równe, oznacza to że ich wartości będą szukanym największym wspólnym dzielnikiem. Sprawdźmy to dla pary liczb 105 i 45:
Przypadki brzegowe, które należy uwzględnić:
Uwaga! jest sprawą sporną. Na internecie można znaleźć wiele twierdzeń, że jest to wartość niezdefiniowana, nieskończona, czy też równa 0. W algorytmie przyjmuję ją jako równą zero ze względu na uproszczenie całości. WolframAlpha też podaje że jest równa 0.
Nasz algorytm działa i wydaje się w miarę szybki. Co się jednak stanie, gdy weźmiemy dla przykładu parę liczb 333 i 3?
Widzicie ile operacji musimy wykonać? Z pomocą przychodzi zoptymalizowany algorytm Euklidesa…
W tym przypadku zamiast odejmowania będziemy wykorzystywać operator modulo czyli resztę z dzielenia. Przyda się nam tutaj pomocnicza zmienna - wartość wyrażenia . powinno być większe od .
Lista kroków:
Prześledźmy to dla naszych poprzednich par liczb:
Oj chyba troszkę szybciej ;)
Co z naszymi przypadkami brzegowymi z poprzedniego algorytmu? Jeżeli , algorytm poprawnie wskaże . Nietrudno zauważyć, że jeżeli , algorytm dalej poda prawidłową odpowiedź czyli .
Koniec skomplikowanych rzeczy. Jako że potrafimy już wyliczać NWD, skorzystamy z prostej zależności:
Po przekształceniu otrzymujemy:
Przetestujmy powyższą zależność dla naszej pary liczb 105 i 45:
Zauważmy tylko, że nie może być równe 0. Jest to kolejny warunek, o który musimy zadbać. W C++ dzielenie liczby całkowitej przez 0 skutkuje undefined behavior co może prowadzić do crasha programu! Jeżeli , zwracam . Na maturze jednak raczej niepowinny się pojawić takie dane aby NWD i NWW wynosiło 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <algorithm>
using namespace std;
// Wyznaczanie NWD metodą odejmowania
int odejmowanieNWD(int a, int b) {
// Obsługujemy przypadki brzegowe
// Nie musimy obsługiwać osobno NWD(0, 0) = 0
// ponieważ oba ify zwróciłyby prawdę i wartość 0
if(b == 0) return a;
if(a == 0) return b;
// Dopóki liczby są różne, wykonuj pętlę
while(a != b) {
// Jeżeli b jest większe od a, zamień ich wartości
if(b > a) swap(a, b);
// Od a odejmujemy b
a -= b;
}
// a = b, więc zwracamy którąkolwiek z wartości
return a;
}
// Wyznaczanie NWD metodą modulo
int moduloNWD(int a, int b) {
int c;
// Dopóki b jest różne od zera, wykonuj pętlę
while(b != 0) {
c = a % b;
a = b;
b = c;
// Inny sposób zapisania powyższej zawartości pętli:
// swap(a %= b, b);
// Dzięki temu zmienna a będzie zawierać wartość zmiennej b,
// a zmienna b wartość a % b
}
// b = 0, więc zwracamy a
return a;
}
int NWW(int a, int b) {
// Obliczamy wartość NWD(a, b)
int nwd = moduloNWD(a, b);
// Jeżeli NWD(a, b) = 0, zwracamy 0
if(nwd == 0) return 0;
// W przeciwnym wypadku liczymy NWW(a, b)
return a * b / nwd;
}
int main() {
cout << "odejmowanieNWD(105, 45) = " << odejmowanieNWD(105, 45) << endl;
cout << "moduloNWD(105, 45) = " << moduloNWD(105, 45) << endl;
cout << "NWW(105, 45) = " << NWW(105, 45) << endl << endl;
cout << "odejmowanieNWD(333, 3) = " << odejmowanieNWD(333, 3) << endl;
cout << "moduloNWD(333, 3) = " << moduloNWD(333, 3) << endl;
cout << "NWW(333, 3) = " << NWW(333, 3) << endl << endl;
cout << "odejmowanieNWD(1024, 768) = " << odejmowanieNWD(1024, 768) << endl;
cout << "moduloNWD(1024, 768) = " << moduloNWD(1024, 768) << endl;
cout << "NWW(1024, 768) = " << NWW(1024, 768) << endl << endl;
cout << "Przypadki brzegowe:" << endl << endl;
cout << "odejmowanieNWD(5, 0) = " << odejmowanieNWD(5, 0) << endl;
cout << "moduloNWD(5, 0) = " << moduloNWD(5, 0) << endl;
cout << "NWW(5, 0) = " << NWW(5, 0) << endl << endl;
cout << "odejmowanieNWD(0, 5) = " << odejmowanieNWD(0, 5) << endl;
cout << "moduloNWD(0, 5) = " << moduloNWD(0, 5) << endl;
cout << "NWW(0, 5) = " << NWW(0, 5) << endl << endl;
cout << "odejmowanieNWD(0, 0) = " << odejmowanieNWD(0, 0) << endl;
cout << "moduloNWD(0, 0) = " << moduloNWD(0, 0) << endl;
cout << "NWW(0, 0) = " << NWW(0, 0) << endl << endl;
}
odejmowanieNWD(105, 45) = 15
moduloNWD(105, 45) = 15
NWW(105, 45) = 315
odejmowanieNWD(333, 3) = 3
moduloNWD(333, 3) = 3
NWW(333, 3) = 333
odejmowanieNWD(1024, 768) = 256
moduloNWD(1024, 768) = 256
NWW(1024, 768) = 3072
Przypadki brzegowe:
odejmowanieNWD(5, 0) = 5
moduloNWD(5, 0) = 5
NWW(5, 0) = 0
odejmowanieNWD(0, 5) = 5
moduloNWD(0, 5) = 5
NWW(0, 5) = 0
odejmowanieNWD(0, 0) = 0
moduloNWD(0, 0) = 0
NWW(0, 0) = 0