Find den største fælles skiller i Java

1. Oversigt

I matematik er GCD af to heltal, som ikke er nul det største positive heltal, der deler hvert enkelt tal jævnt.

I denne vejledning ser vi på tre tilgange til at finde den største fælles divisor (GCD) af to heltal. Yderligere vil vi se på deres implementering i Java.

2. Brute Force

For vores første tilgang gentager vi fra 1 til det mindste antal, der gives, og kontrollerer, om de givne heltal er delelige med indekset. Det største indeks, der deler de givne tal er GCD for de givne tal:

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; }} returner gcd; }

Som vi kan se, er kompleksiteten af ovenstående implementering O (min (n1, n2)) fordi vi har brug for at gentage over løkken for n gange (svarende til det mindre antal) for at finde GCD.

3. Euklids algoritme

For det andet kan vi bruge Euclids algoritme til at finde GCD. Euclids algoritme er ikke kun effektiv, men også let at forstå og nem at implementere ved hjælp af rekursion i Java.

Euclids metode afhænger af to vigtige sætninger:

For det første, hvis vi trækker det mindre tal fra det større tal, ændres GCD ikke - derfor, hvis vi fortsætter med at trække tallet, ender vi endelig med deres GCD
For det andet, når det mindste tal nøjagtigt deler det større tal, er det mindre antal GCD for de to givne tal.

Bemærk i vores implementering, at vi bruger modulo i stedet for subtraktion, da det stort set er mange subtraktioner ad gangen:

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

Bemærk også, hvordan vi bruger n2 i n1'S position og brug resten i n2's position i algoritmens rekursive trin.

Yderligere, kompleksiteten af Euclids algoritme er O (Log min (n1, n2)) hvilket er bedre sammenlignet med Brute Force-metoden, vi så før.

4. Steins algoritme eller binær GCD algoritme

Endelig kan vi også bruge Steins algoritme kendt som den binære GCD-algoritme, for at finde GCD for to ikke-negative heltal. Denne algoritme bruger enkle aritmetiske operationer som aritmetiske forskydninger, sammenligning og subtraktion.

Steins algoritme anvender gentagne gange følgende grundlæggende identiteter relateret til GCD'er for at finde GCD af to ikke-negative heltal:

gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
Hvornår n1 og n2 begge er endda heltal gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), da 2 er fælles skillevæg
Hvis n1 er endda heltal og n2 er ulige heltal, så gcd (n1, n2) = gcd (n1 / 2, n2), da 2 ikke er fælles skiller og omvendt
Hvis n1 og n2 er begge ulige heltal, og n1> = n2, derefter gcd (n1, n2) = gcd ((n1-n2) / 2, n2) og omvendt

Vi gentager trin 2-4 indtil n1 lige med n2, eller n1 = 0. GCD er (2n) * n2. Her, n er antallet af gange 2 findes almindeligt i n1 og n2 under udførelse af trin 2:

int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } hvis (n2 == 0) {return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n ++) {n1 >> = 1; n2 >> = 1; } mens ((n1 & 1) == 0) {n1 >> = 1; } gør {mens ((n2 & 1) == 0) {n2 >> = 1; } hvis (n1> n2) {int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } mens (n2! = 0); returnere n1 << n; }

Vi kan se, at vi bruger aritmetiske skiftoperationer for at dele eller gange med 2. Yderligere bruger vi subtraktion for at reducere de givne tal.

Kompleksiteten af Steins algoritme når n1> n2 er O ((log₂n1) 2) der henviser til. hvornår n1 <n2, det er O ((log₂n2) 2).

5. Konklusion

I denne vejledning så vi på forskellige metoder til beregning af GCD af to tal. Vi implementerede disse også i Java og kiggede hurtigt på deres kompleksitet.

Som altid er den fulde kildekode for vores eksempler her som altid forbi på GitHub.

streamalism.org