Nájdenie najväčšieho spoločného deliteľa v Jave

1. Prehľad

V matematike je GCD dvoch celých čísel, ktoré sú nenulové, rovné najväčšie kladné celé číslo, ktoré rovnomerne rozdeľuje každé z celých čísel.

V tomto tutoriále sa pozrieme na tri prístupy k nájdeniu najväčšieho spoločného deliteľa (GCD) dvoch celých čísel. Ďalej sa pozrieme na ich implementáciu v Jave.

2. Hrubá sila

Pri našom prvom prístupe iterujeme od 1 po najmenšie dané číslo a kontrolujeme, či sú dané celé čísla deliteľné indexom. Najväčší index, ktorý rozdeľuje dané čísla je GCD z daných čísel:

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

Ako vidíme, zložitosť vyššie uvedenej implementácie je O (min (n1, n2)) pretože musíme iterovať cez slučku pre n krát (zodpovedá menšiemu počtu), aby ste našli GCD.

3. Euklidov algoritmus

Po druhé, na nájdenie GCD môžeme použiť Euklidov algoritmus. Euklidov algoritmus je nielen efektívny, ale aj ľahko pochopiteľný a ľahko implementovateľný pomocou rekurzie v Jave.

Euklidova metóda závisí od dvoch dôležitých viet:

  • Po prvé, ak odčítame menšie číslo od väčšieho, GCD sa nezmení - Preto, ak budeme stále odpočítavať číslo, nakoniec skončíme s ich GCD
  • Po druhé, keď menšie číslo presne rozdeľuje väčšie číslo, menšie číslo je GCD z dvoch uvedených čísel.

V našej implementácii si všimnite, že namiesto odčítania použijeme modulo, pretože je to v podstate veľa odčítaní naraz:

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

Všimnite si tiež, ako používame n2 v n1A zvyšok použijeme v polohe n2 v rekurzívnom kroku algoritmu.

Ďalej zložitosť Euklidovho algoritmu je O (Log min (n1, n2)) čo je lepšie v porovnaní s metódou Brute Force, ktorú sme videli predtým.

4. Steinov algoritmus alebo binárny GCD algoritmus

Nakoniec môžeme použiť aj Steinov algoritmus známy ako binárny GCD algoritmus, aby ste našli GCD dvoch nezáporných celých čísel. Tento algoritmus využíva jednoduché aritmetické operácie, ako sú aritmetické posuny, porovnanie a odčítanie.

Steinov algoritmus opakovane používa nasledujúce základné identity súvisiace s GCD na nájdenie GCD dvoch nezáporných celých čísel:

  1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
  2. Kedy n1 a n2 sú teda párne celé čísla gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), keďže 2 je spoločný deliteľ
  3. Ak n1 je párne celé číslo a n2 je nepárne celé číslo gcd (n1, n2) = gcd (n1 / 2, n2), keďže 2 nie je spoločným deliteľom a naopak
  4. Ak n1 a n2 sú nepárne celé čísla a n1> = n2potom gcd (n1, n2) = gcd ((n1-n2) / 2, n2) a naopak

Opakujeme kroky 2-4, kým n1 rovná sa n2alebo n1 = 0. GCD je (2n) * n2. Tu, n je počet prípadov, v ktorých sa 2 vyskytujú bežne v n1 a n2 pri vykonávaní kroku 2:

int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } if (n2 == 0) {návrat n1; } int n; pre (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 = teplota; } n2 = (n2 - n1); } while (n2! = 0); návrat n1 << n; }

Vidíme, že na rozdelenie alebo vynásobenie číslom 2 používame operácie aritmetického posunu. Ďalej používame odčítanie, aby sme dané čísla zmenšili.

Zložitosť Steinovho algoritmu, keď n1> n2 je O ((log2n1) 2) keďže. kedy n1 <n2, to je O ((log2n2) 2).

5. Záver

V tomto tutoriáli sme sa pozreli na rôzne metódy výpočtu GCD dvoch čísel. Tieto sme implementovali aj v prostredí Java a rýchlo sme sa pozreli na ich zložitosť.

Celý zdrojový kód našich príkladov je ako vždy na GitHube ako vždy.


$config[zx-auto] not found$config[zx-overlay] not found