Strona główna » Algorytmy » Artykuły » NWD wielu liczb
 

NWD wielu liczb

https://mattomatti.com/a0022

Wstęp

Zazwyczaj największy wspólny dzielnik wylicza się tylko dla dwóch liczb, ale mogą się zdarzyć przypadki, gdy trzeba znaleźć NWD dla większej ilości liczb. Wtedy można skorzystać z własności, że NWD(a, b, c) = NWD(NWD(a, b), c) = NWD(NWD(a, c), b) = NWD(NWD(b, c), a). Własność tą można uogólnić na dowolną liczbę argumentów.

Informacje o NWD można znaleźć w tym artykule.

Implementacja

Własność

W celu wyliczenia NWD dowolnej ilości argumentów wystarczy zadeklarować pewną zmienną nwdv i przypisać jej wartość pierwszej liczby, a następnie dla każdej pozostałej liczby obliczyć NWD(nwdv, i-ta liczba) i wynik przypisać do nwdv. Poniżej znajduje się kompletny kod:

  1. int nwd(int* tab, int n) {
  2.   int nwdv = tab[0];
  3.   for (int i = 1; i < n; i++)
  4.     nwdv = nwd(nwdv, tab[i]);
  5.   return nwdv;
  6. }

Algorytm korzysta z przeciążenia funkcji nwd dla dwóch konkretnych wartości, dlatego należy dodatkowo dopisać nwd dla dwóch argumentów int. Przykładowo może być to algorytm Euklidesa.

  1. int nwd(int a, int b) {
  2.   int c;
  3.   while (b != 0) {
  4.     c = a % b;
  5.     a = b;
  6.     b = c;
  7.   }
  8.   return a;
  9. }

Rozkład

Jak wiadomo każdą liczbę można przedstawić jako iloczyn liczb pierwszych. Wtedy NWD to iloczyn tych liczb, które występuje tyle samo razy w każdej liczbie. Pomysł na drugie rozwiązanie tego problemu polega na znalezieniu kolejnych liczb pierwszych, które dzielą wszystkie liczby i na bieżąco aktualizować iloczyn znalezionych wartości.

Warto zauważyć, że podczas szukania liczb pierwszych należy szukać w zakresie [2, k], gdzie k to połowa najmniejszej wartości na przekazanej liście. Kod funkcji NWD wygląda wtedy następująco:

  1. int nwd(int* tab, int n) {
  2.   int k = tab[0];
  3.   for (int i = 1; i < n; i++)
  4.     if (tab[i] < k)
  5.       k = tab[i];
  6.   int nwdv = 1;
  7.   for (int i = 2; i <= k/2; i++) {
  8.     while (sprawdzPodzielnosc(tab, n, i)) {
  9.       nwdv *= i;
  10.       for (int j = 0; j < n; j++)
  11.         tab[j] /= i;
  12.     }
  13.   }
  14.   while (sprawdzPodzielnosc(tab, n, k)) {
  15.     nwdv *= k;
  16.     for (int j = 0; j < n; j++)
  17.       tab[j] /= k;
  18.   }
  19.   return nwdv;
  20. }

Pierwszy etap polega na (2. - 5.) znalezieniu minimum wśród szukanych wartości. Następnie dla (6. - 12.) każdej wartości z określonego przedziału należy szukać dzielników. (7.) W każdej iteracji dzielnikiem jest wartość i. Jeśli każda z liczb jest podzielna przez tę wartość to (8.) mnożymy nwdv przez i, a następnie (9. - 10.) każdą wartość dzielimy przez i, aby usunąć wystąpienie liczby pierwszej z każdej liczby. (Jest to bardzo ważne, bo inaczej jeśli w rozkładzie występują dwie wartości 2 to bez usuwania program by stwierdził, że 4 też dzieli wszystkie, ale 4 nie jest pierwsze.) Przed zwróceniem wartości należy wykonać (13. - 17.) dodatkowe sprawdzenie dla wartości k, ponieważ k może być pierwsze.

W funkcji została wykorzystana funkcja sprawdzPodzielnosc(), która dla danej listy tab o rozmiarze n sprawdza czy wszystkie liczby na liście są podzielne przez d.

  1. bool sprawdzPodzielnosc(int* tab, int n, int d) {
  2.   for (int i = 0; i < n; i++)
  3.     if (tab[i] % d != 0)
  4.       return false;
  5.   return true;
  6. }

Testowanie funkcji

W celu przetestowania działania napisanych funkcji można skorzystać z poniższej funkcji main():

  1. int main() {
  2.   int n;
  3.   cout << "Podaj ile liczb jest w tablicy: ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj " << n << " liczb: ";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   cout << "NWD(tab) = " << nwd(tab, n) << endl;
  10.   system("pause");
  11.   return 0;
  12. }