streamalism.org

1. Pregled

S obzirom na dvije cjelobrojne vrijednosti, a i b, kažemo da jesu relativno prost ako je jedini čimbenik koji dijeli oboje 1. Međusobno prosti ili supstratni sinonimi su za relativno proste brojeve.

U ovom brzom vodiču proći ćemo kroz rješenje ovog problema pomoću Jave.

2. Najveći algoritam zajedničkog faktora

Kako se ispostavilo, ako je najveći zajednički djelitelj (gcd) od 2 broja a i b je 1 (tj. gcd (a, b) = 1) onda a i b relativno su primarni. Kao rezultat toga, utvrđivanje jesu li dva broja relativno prosta sastoji se samo od pronalaska da li gcd je 1.

3. Provedba euklidskog algoritma

U ovom ćemo odjeljku koristiti euklidski algoritam za izračunavanje gcd od 2 broja.

Prije nego što pokažemo svoju implementaciju, sažeti ćemo algoritam i pogledati brzi primjer kako ga primijeniti radi razumijevanja.

Dakle, zamislite da imamo dvije cijele brojeve, a i b. U iterativnom pristupu prvo dijelimo a po b i dobiti ostatak. Dalje, dodjeljujemo a vrijednost b, i mi dodjeljujemo b ostatak vrijednosti. Ponavljamo ovaj postupak do b = 0. Napokon, kad dosegnemo ovu točku, vraćamo vrijednost a kao gcd rezultat i ako a = 1, to možemo reći a i b relativno su primarni.

Isprobajmo na dvije cijele brojke, a = 81 i b = 35.

U ovom slučaju, ostatak od 81 i 35 (81 % 35) je 11. Dakle, u prvom iteracijskom koraku završavamo sa a = 35 i b = 11. Slijedom toga, napravit ćemo još jednu ponavljanje.

Ostatak od 35 podjeljeno sa 11 je 2. Kao rezultat, sada imamo a = 11 (zamijenili smo vrijednosti) i b = 2. Idemo dalje.

Još jedan korak rezultirat će a = 2 i b = 1. Sad se približavamo kraju.

Napokon, nakon još jedne ponavljanja, stići ćemo a = 1 i b = 0. Algoritam se vraća 1 i to možemo zaključiti 81 i 35 doista su relativno primarni.

3.1. Imperativna provedba

Prvo, implementirajmo imperativnu Java verziju euklidskog algoritma kako je gore opisano:

int iterativeGCD (int a, int b) {int tmp; while (b! = 0) {if (a <b) {tmp = a; a = b; b = tmp; } tmp = b; b = a% b; a = tmp; } return a; } 

Kao što možemo primijetiti, u slučaju gdje a je manje od b, zamijenimo vrijednosti prije nastavka. Algoritam se zaustavlja kada b je 0.

3.2. Rekurzivna provedba

Dalje, pogledajmo rekurzivnu implementaciju. Ovo je vjerojatno čišće jer izbjegava eksplicitne zamjene vrijednosti varijabli:

int rekurzivnoGCD (int a, int b) {if (b == 0) {return a; } if (a <b) {return rekurzivnoGCD (b, a); } vratiti rekurzivniGCD (b, a% b); } 

4. Korištenje BigInteger‘S Implementacija

Ali pričekajte - nije gcd algoritam već implementiran u Javi? Da je! The BigInteger razred pruža a gcd metoda koja provodi euklidski algoritam za pronalaženje najvećeg zajedničkog djelitelja.

Korištenjem ove metode možemo lakše izraditi relativno osnovni algoritam kao:

boolean bigIntegerRelativelyPrime (int a, int b) {return BigInteger.valueOf (a) .gcd (BigInteger.valueOf (b)). jednako (BigInteger.ONE); } 

5. Zaključak

U ovom smo brzom vodiču predstavili rješenje problema pronalaženja jesu li dva broja relativno prosta koristeći tri implementacije gcd algoritam.

Kao i uvijek, uzorak koda dostupan je na GitHubu.