Pronalaženje najvećeg zajedničkog djelitelja u Javi
1. Pregled
U matematici je GCD dviju cijelih brojeva koji nisu nula najveći pozitivni cijeli broj koji svaku od cijelih brojeva dijeli ravnomjerno.
U ovom ćemo uputstvu razmotriti tri pristupa za pronalaženje Najvećeg zajedničkog djelitelja (GCD) dviju cijelih brojeva. Dalje, osvrnut ćemo se na njihovu implementaciju u Javi.
2. Brute Force
Za naš prvi pristup ponavljamo od 1 do najmanjeg zadanog broja i provjeravamo jesu li zadane cijele vrijednosti djeljive indeksom. Najveći indeks koji dijeli zadane brojeve je GCD danih brojeva:
int gcdByBruteForce (int n1, int n2) {int gcd = 1; za (int i = 1; i <= n1 && i <= n2; i ++) {if (n1% i == 0 && n2% i == 0) {gcd = i; }} vrati gcd; }
Kao što vidimo, složenost gornje provedbe je O (min (n1, n2)) jer moramo ponoviti petlju za n puta (ekvivalentno manjem broju) za pronalaženje GCD-a.
3. Euklidov algoritam
Drugo, možemo koristiti Euclidov algoritam za pronalaženje GCD-a. Euclidov algoritam nije samo učinkovit, već je i lako razumljiv te ga je lako implementirati pomoću rekurzije u Javi.
Euklidova metoda ovisi o dva važna teorema:
- Prvo, ako od većeg broja oduzmemo manji broj, GCD se neće promijeniti - stoga, ako nastavimo oduzimati broj, konačno ćemo završiti s njihovim GCD-om
- Drugo, kada manji broj točno dijeli veći broj, manji je broj GCD od dva dana.
Primijetite u našoj implementaciji da ćemo umjesto oduzimanja koristiti modulo, jer je u osnovi mnogo oduzimanja odjednom:
int gcdByEuclidsAlgorithm (int n1, int n2) {if (n2 == 0) {return n1; } vratiti gcdByEuclidsAlgoritam (n2, n1% n2); }
Također, imajte na umu kako koristimo n2 u n1'S položaj i koristi ostatak u položaju n2 u rekurzivnom koraku algoritma.
Unaprijediti, složenost Euklidovog algoritma je O (zapis min (n1, n2)) što je bolje u usporedbi s Brute Force metodom koju smo prije vidjeli.
4. Steinov algoritam ili binarni GCD algoritam
Napokon, možemo se poslužiti i Steinovim algoritmom poznat kao Binarni GCD algoritam, kako bi se pronašao GCD dviju negativnih cijelih brojeva. Ovaj algoritam koristi jednostavne aritmetičke operacije poput aritmetičkih pomaka, usporedbe i oduzimanja.
Steinov algoritam više puta primjenjuje sljedeće osnovne identitete povezane s GCD-ima kako bi pronašao GCD dvaju negativnih cijelih brojeva:
- gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
- Kada n1 i n2 onda su obje čak i cijele brojeve gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), budući da je 2 zajednički djelitelj
- Ako n1 je čak cijeli broj i n2 je onda neparan cijeli broj gcd (n1, n2) = gcd (n1 / 2, n2), budući da 2 nije zajednički djelitelj i obrnuto
- Ako n1 i n2 su obje neparne cijele vrijednosti i n1> = n2, onda gcd (n1, n2) = gcd ((n1-n2) / 2, n2) i obrnuto
Ponavljamo korake 2-4 do n1 jednako n2, ili n1 = 0. GCD je (2n) * n2. Ovdje, n je broj puta kada se 2 nađe uobičajeno u n1 i n2 tijekom izvođenja koraka 2:
int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } if (n2 == 0) {return n1; } int n; za (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); } dok (n2! = 0); povratak n1 << n; }
Vidimo da koristimo operacije aritmetičkog pomaka kako bismo podijelili ili pomnožili s 2. Nadalje, koristimo oduzimanje kako bismo smanjili zadane brojeve.
Složenost Steinova algoritma kada n1> n2 je O ((log2n1) 2) dok. kada n1 <n2, to je O ((log2n2) 2).
5. Zaključak
U ovom smo tutorijalu pogledali razne metode za izračunavanje GCD-a dva broja. Također smo ih implementirali u Javu i na brzinu pogledali njihovu složenost.
Kao i uvijek, puni izvorni kod naših primjera ovdje je, kao i uvijek, gotov na GitHubu.