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

NWD wielu liczb

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. }