streamalism.org

1. Overzicht

In de wiskunde is de GCD van twee gehele getallen, die niet nul zijn het grootste positieve gehele getal dat elk van de gehele getallen gelijkmatig verdeelt.

In deze zelfstudie bekijken we drie benaderingen om de grootste gemene deler (GCD) van twee gehele getallen te vinden. Verder zullen we hun implementatie in Java bekijken.

2. Brute kracht

Voor onze eerste benadering itereren we van 1 tot het kleinste gegeven getal en controleren of de gegeven gehele getallen deelbaar zijn door de index. De grootste index die de gegeven getallen deelt is de GCD van de gegeven nummers:

int gcdByBruteForce (int n1, int n2) {int gcd = 1; voor (int i = 1; i <= n1 && i <= n2; i ++) {if (n1% i == 0 && n2% i == 0) {gcd = i; }} geef gcd terug; }

Zoals we kunnen zien, is de complexiteit van de bovenstaande implementatie O (min (n1, n2)) omdat we de lus moeten herhalen voor n keer (gelijk aan het kleinere getal) om de GCD te vinden.

3. Euclides algoritme

Ten tweede kunnen we het algoritme van Euclides gebruiken om de GCD te vinden. Het algoritme van Euclid is niet alleen efficiënt, maar ook gemakkelijk te begrijpen en gemakkelijk te implementeren met recursie in Java.

Euclides methode hangt af van twee belangrijke stellingen:

• Ten eerste, als we het kleinere getal aftrekken van het grotere getal, verandert de GCD niet - daarom, als we het aantal blijven aftrekken, eindigen we uiteindelijk met hun GCD
• Ten tweede, wanneer het kleinere getal het grotere getal precies deelt, is het kleinere getal de GCD van de twee gegeven getallen.

Merk op dat we in onze implementatie modulo zullen gebruiken in plaats van aftrekken, aangezien het in feite veel aftrekkingen tegelijk zijn:

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

Merk ook op hoe we n2 in n1‘S positie en gebruik de rest in de positie van n2 in de recursieve stap van het algoritme.

Verder, de complexiteit van het algoritme van Euclides is O (Log min (n1, n2)) wat beter is in vergelijking met de Brute Force-methode die we eerder zagen.

4. Stein's algoritme of binair GCD-algoritme

Ten slotte kunnen we ook het algoritme van Stein gebruiken bekend als het binaire GCD-algoritme, om de GCD van twee niet-negatieve gehele getallen te vinden. Dit algoritme maakt gebruik van eenvoudige rekenkundige bewerkingen zoals rekenkundige verschuivingen, vergelijking en aftrekken.

Het algoritme van Stein past herhaaldelijk de volgende basisidentiteiten toe met betrekking tot GCD's om GCD van twee niet-negatieve gehele getallen te vinden:

1. ggd (0, 0) = 0, ggd (n1, 0) = n1, ggd (0, n2) = n2
2. Wanneer n1 en n2 zijn dan allebei even gehele getallen ggd (n1, n2) = 2 * ggd (n1 / 2, n2 / 2), aangezien 2 de gemene deler is
3. Als n1 is zelfs geheel getal en n2 is dan een oneven geheel getal ggd (n1, n2) = ggd (n1 / 2, n2), aangezien 2 niet de gemene deler is en vice versa
4. Als n1 en n2 zijn beide oneven gehele getallen, en n1> = n2, dan ggd (n1, n2) = ggd ((n1-n2) / 2, n2) en vice versa

We herhalen stap 2-4 tot n1 is gelijk aan n2, of n1 = 0. De GCD is (2n) * n2. Hier, n is het aantal keren dat 2 vaak voorkomt in n1 en n2 tijdens het uitvoeren van stap 2:

int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } if (n2 == 0) {retourneer n1; } int n; voor (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); } while (n2! = 0); terug n1 << n; }

We kunnen zien dat we rekenkundige verschuivingsbewerkingen gebruiken om te delen of vermenigvuldigen met 2. Verder gebruiken we aftrekken om de gegeven getallen te verminderen.

De complexiteit van het algoritme van Stein wanneer n1> n2 is O ((log₂n1) 2) terwijl. wanneer n1 <n2, het is O ((log₂n2) 2).

5. Conclusie

In deze tutorial hebben we verschillende methoden bekeken om de GCD van twee getallen te berekenen. We hebben deze ook in Java geïmplementeerd en hebben snel gekeken naar hun complexiteit.

Zoals altijd is de volledige broncode van onze voorbeelden hier, zoals altijd, op GitHub.