Намиране на най-големия общ делител в Java

1. Общ преглед

В математиката GCD на две цели числа, които са ненулеви, е най-голямото положително цяло число, което разделя равномерно всяко от целите числа.

В този урок ще разгледаме три подхода за намиране на най-големия общ делител (GCD) на две цели числа. Освен това ще разгледаме тяхното изпълнение в Java.

2. Груба сила

За нашия първи подход итерираме от 1 до най-малкото дадено число и проверяваме дали дадените цели числа се делят на индекса. Най-големият индекс, който разделя дадените числа, е GCD на дадените числа:

int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }

Както можем да видим, сложността на горното изпълнение е O (min (n1, n2)), защото трябва да повторим цикъла за n пъти (еквивалентно на по-малкия брой), за да намерим GCD.

3. Алгоритъмът на Евклид

Второ, можем да използваме алгоритъма на Евклид, за да намерим GCD. Алгоритъмът на Euclid е не само ефективен, но и лесен за разбиране и лесен за изпълнение с помощта на рекурсия в Java.

Методът на Евклид зависи от две важни теореми:

  • Първо, ако извадим по-малкото число от по-голямото, GCD не се променя - следователно, ако продължим да изваждаме числото, накрая ще получим техния GCD
  • Второ, когато по-малкото число точно разделя по-голямото число, по-малкото число е GCD на двете дадени числа.

Забележете в нашата реализация, че ще използваме modulo вместо изваждане, тъй като това са основно много изваждания наведнъж:

int gcdByEuclidsAlgorithm(int n1, int n2) { if (n2 == 0) { return n1; } return gcdByEuclidsAlgorithm(n2, n1 % n2); }

Също така обърнете внимание как използваме n2 в позиция n1 и използваме остатъка в позиция n2 в рекурсивната стъпка на алгоритъма .

Освен това сложността на алгоритъма на Евклид е O (Log min (n1, n2)), което е по-добре в сравнение с метода на грубата сила, който видяхме преди.

4. Алгоритъм на Щайн или двоичен алгоритъм на GCD

И накрая, можем да използваме алгоритъма на Stein, известен също като двоичен GCD алгоритъм , за да намерим GCD на две неотрицателни цели числа. Този алгоритъм използва прости аритметични операции като аритметични отмествания, сравнение и изваждане.

Алгоритъмът на Stein многократно прилага следните основни идентичности, свързани с GCD, за да намери GCD на две неотрицателни цели числа:

  1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
  2. Когато n1 и n2 са четни цели числа, тогава gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2) , тъй като 2 е общият делител
  3. Ако n1 е четно число и n2 е нечетно цяло число, тогава gcd (n1, n2) = gcd (n1 / 2, n2) , тъй като 2 не е общият делител и обратно
  4. Ако n1 и n2 са нечетни цели числа и n1> = n2 , тогава gcd (n1, n2) = gcd ((n1-n2) / 2, n2) и обратно

Повтаряме стъпки 2-4, докато n1 не е равно на n2 или n1 = 0 . GCD е (2n) * n2 . Тук n е броят пъти, когато 2 се среща често в n1 и n2, докато се изпълнява стъпка 2:

int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }

Виждаме, че използваме операции на аритметично преместване, за да разделим или умножим по 2. Освен това използваме изваждане, за да намалим дадените числа.

Сложността на алгоритъма на Щайн, когато n1> n2 е O ((log 2 n1) 2), докато. когато n1 <n2, това е O ((log 2 n2) 2).

5. Заключение

В този урок разгледахме различни методи за изчисляване на GCD на две числа. Също така ги внедрихме в Java и разгледахме набързо тяхната сложност.

Както винаги, пълният изходен код на нашите примери тук е, както винаги, на GitHub.