streamalism.org

1. Oversikt

I matematikk er GCD av to heltall, som ikke er null det største positive heltallet som deler hvert av heltallene jevnt.

I denne opplæringen vil vi se på tre tilnærminger for å finne den største felles divisoren (GCD) av to heltall. Videre vil vi se på implementeringen av dem i Java.

2. Brute Force

For vår første tilnærming gjentar vi fra 1 til det minste tallet som er gitt, og sjekker om de gitte heltallene er delbare med indeksen. Den største indeksen som deler de gitte tallene er GCD for de angitte tallene:

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 av implementeringen ovenfor O (min (n1, n2)) fordi vi trenger å gjenta over løkken for n ganger (tilsvarer det mindre tallet) for å finne GCD.

3. Euklids algoritme

For det andre kan vi bruke Euclids algoritme for å finne GCD. Euclids algoritme er ikke bare effektiv, men også lett å forstå og enkel å implementere ved hjelp av rekursjon i Java.

Euclids metode avhenger av to viktige teoremer:

• For det første, hvis vi trekker det mindre tallet fra det større tallet, endres ikke GCD - Derfor, hvis vi fortsetter å trekke tallet, ender vi endelig opp med GCD
• For det andre, når det mindre tallet nøyaktig deler det større tallet, er det mindre tallet GCD av de to gitte tallene.

Legg merke til i implementeringen at vi bruker modulo i stedet for subtraksjon, siden det i utgangspunktet er mange subtraksjoner om gangen:

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

Legg også merke til hvordan vi bruker n2 i n1’S posisjon og bruk resten i n2s posisjon i algoritmens rekursive trinn.

Lengre, kompleksiteten til Euclids algoritme er O (Logg min (n1, n2)) som er bedre sammenlignet med Brute Force-metoden vi så før.

4. Steins algoritme eller binær GCD-algoritme

Til slutt kan vi også bruke Steins algoritme kjent som den binære GCD-algoritmen, for å finne GCD av to ikke-negative heltall. Denne algoritmen bruker enkle aritmetiske operasjoner som aritmetiske skift, sammenligning og subtraksjon.

Steins algoritme bruker gjentatte ganger følgende grunnleggende identiteter relatert til GCDer for å finne GCD av to ikke-negative heltall:

1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
2. Når n1 og n2 er begge til og med heltall, da gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), siden 2 er felles divisor
3. Hvis n1 er til og med heltall og n2 er merkelig heltall, da gcd (n1, n2) = gcd (n1 / 2, n2), siden 2 ikke er felles divisor og omvendt
4. Hvis n1 og n2 er begge odde heltall, og n1> = n2, deretter gcd (n1, n2) = gcd ((n1-n2) / 2, n2) og vice versa

Vi gjentar trinn 2-4 til n1 er lik n2, eller n1 = 0. GCD er (2n) * n2. Her, n er antall ganger 2 er funnet vanlig i n1 og n2 mens du utfører trinn 2:

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

Vi kan se at vi bruker aritmetiske skiftoperasjoner for å dele eller multiplisere med 2. Videre bruker vi subtraksjon for å redusere de gitte tallene.

Kompleksiteten til Steins algoritme når n1> n2 er O ((logg₂n1) 2) mens. når n1 <n2, Det er O ((logg₂n2) 2).

5. Konklusjon

I denne opplæringen så vi på forskjellige metoder for å beregne GCD av to tall. Vi implementerte disse også i Java og så raskt på kompleksiteten.

Som alltid er den fullstendige kildekoden til eksemplene våre som alltid over på GitHub.