streamalism.org

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:

1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
2. 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
3. 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
4. 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 ((log₂n1) 2) dok. kada n1 <n2, to je O ((log₂n2) 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.