streamalism.org

1. Overzicht

Het kleinste gemene veelvoud (LCM) van twee niet-nul gehele getallen (a, b) is het kleinste positieve gehele getal dat perfect deelbaar is door beide een en b.

In deze zelfstudie leren we over verschillende benaderingen om de LCM van twee of meer getallen te vinden. Dat moeten we opmerken negatieve gehele getallen en nul zijn geen kandidaten voor LCM.

2. LCM van twee getallen berekenen met behulp van een eenvoudig algoritme

We kunnen de LCM van twee getallen vinden door het simpele feit te gebruiken dat vermenigvuldiging is herhaald optellen.

2.1. Algoritme

Het eenvoudige algoritme om de LCM te vinden is een iteratieve benadering die gebruik maakt van enkele fundamentele eigenschappen van LCM van twee getallen.

Ten eerste weten we dat de LCM van elk getal met nul is nul zelf. We kunnen de procedure dus vroegtijdig verlaten wanneer een van de gegeven gehele getallen 0 is.

Ten tweede kunnen we ook gebruik maken van het feit dat de ondergrens van de LCM van twee niet-nul gehele getallen is de grootste van de absolute waarden van de twee getallen.

Bovendien, zoals eerder uitgelegd, kan de LCM nooit een negatief geheel getal zijn. Zo goed Gebruik alleen absolute waarden van de gehele getallen voor het vinden van de mogelijke veelvouden totdat we een gemene veelvoud vinden.

Laten we eens kijken naar de exacte procedure die we moeten volgen om lcm (a, b) te bepalen:

1. Als a = 0 of b = 0, keer dan terug met lcm (a, b) = 0, ga anders naar stap 2.
2. Bereken de absolute waarden van de twee getallen.
3. Initialiseer lcm als de hoogste van de twee waarden die in stap 2 zijn berekend.
4. Als lcm deelbaar is door de lagere absolute waarde, retourneer dan.
5. Verhoog lcm met de hoogste absolute waarde tussen de twee en ga naar stap 4.

Voordat we beginnen met de implementatie van deze eenvoudige benadering, laten we een test uitvoeren om lcm te vinden (12, 18).

Aangezien zowel 12 als 18 positief zijn, gaan we naar stap 3, initialiseren lcm = max (12, 18) = 18, en gaan we verder.

In onze eerste iteratie, lcm = 18, wat niet perfect deelbaar is door 12. Dus we verhogen het met 18 en gaan verder.

In de tweede iteratie kunnen we zien dat lcm = 36 en nu perfect deelbaar is door 12. We kunnen dus terugkeren van het algoritme en concluderen dat lcm (12, 18) 36 is.

2.2. Implementatie

Laten we het algoritme in Java implementeren. Onze lcm () methode moet twee integer-argumenten accepteren en hun LCM als retourwaarde geven.

We kunnen opmerken dat het bovenstaande algoritme het uitvoeren van een paar wiskundige bewerkingen op de getallen omvat, zoals het vinden van absolute, minimale en maximale waarden. Voor dit doel kunnen we de overeenkomstige statische methoden van de Wiskunde klasse zoals buikspieren(), min (), en max (), respectievelijk.

Laten we onze lcm () methode:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } int absNumber1 = Math.abs (nummer1); int absNumber2 = Math.abs (nummer2); int absHigherNumber = Math.max (absNumber1, absNumber2); int absLowerNumber = Math.min (absNumber1, absNumber2); int lcm = absHigherNumber; while (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } retourneer lcm; }

Laten we vervolgens ook deze methode valideren:

@Test openbare leegte testLCM () {Assert.assertEquals (36, lcm (12, 18)); }

De bovenstaande testcase verifieert de juistheid van het lcm () methode door te beweren dat lcm (12, 18) 36 is.

3. De aanpak van priemfactorisatie gebruiken

De fundamentele stelling van de rekenkunde stelt dat het mogelijk is om elk geheel getal groter dan één uniek uit te drukken als een product van machten van priemgetallen.

Dus voor elk geheel getal N> 1 hebben we N = (2k1) * (3k2) * (5k3) * ...

Met behulp van het resultaat van deze stelling zullen we nu de priemfactorisatiebenadering begrijpen om de LCM van twee getallen te vinden.

3.1. Algoritme

De priemfactorisatiebenadering berekent de LCM op basis van de primaire ontbinding van de twee getallen. We kunnen de priemfactoren en exponenten van de priemfactorisatie gebruiken om de LCM van de twee getallen te berekenen:

Wanneer, | a | = (2p1) * (3p2) * (5p3) *…

en | b | = (2q1) * (3q2) * (5q3) *…

dan, lcm (a, b) = (2max (p₁, q₁)) * (3max (p₂, q₂)) * (5max (p₃, q₃)) …

Laten we eens kijken hoe we de LCM van 12 en 18 kunnen berekenen met behulp van deze benadering:

Ten eerste moeten we de absolute waarden van de twee getallen weergeven als producten van priemfactoren:

12 = 2 * 2 * 3 = 2² * 3¹

18 = 2 * 3 * 3 = 2¹ * 3²

We kunnen hier opmerken dat de belangrijkste factoren in de bovenstaande weergaven 2 en 3 zijn.

Laten we vervolgens de exponent van elke priemfactor voor de LCM bepalen. We doen dit door zijn hogere macht uit de twee representaties te halen.

Met deze strategie is de macht van 2 in de LCM max (2, 1) = 2, en de macht van 3 in de LCM is max (1, 2) = 2.

Ten slotte kunnen we de LCM berekenen door de priemfactoren te vermenigvuldigen met een overeenkomstig vermogen verkregen in de vorige stap. Bijgevolg hebben we lcm (12, 18) = 2² * 3² = 36.

3.2. Implementatie

Onze Java-implementatie maakt gebruik van priemfactorisatie-representatie van de twee getallen om de LCM te vinden.

Voor dit doel zijn onze getPrimeFactors () methode moet een integerargument accepteren en ons de priemfactorisatie-representatie geven. In Java, we kunnen priemfactorisatie van een getal weergeven met behulp van a Hash kaart waarbij elke sleutel de priemfactor aangeeft en de waarde die bij de sleutel hoort, de exponent van de overeenkomstige factor.

Laten we eens kijken naar een iteratieve implementatie van het getPrimeFactors () methode:

openbare statische kaart getPrimeFactors (int nummer) {int absNumber = Math.abs (nummer); Map primeFactorsMap = nieuwe HashMap (); for (int factor = 2; factor <= absNumber; factor ++) {while (absNumber% factor == 0) {Integer power = primeFactorsMap.get (factor); if (power == null) {power = 0; } primeFactorsMap.put (factor, vermogen + 1); absNumber / = factor; }} retourneer primeFactorsMap; }

We weten dat de priemfactorisatiekaarten van 12 en 18 respectievelijk {2 → 2, 3 → 1} en {2 → 1, 3 → 2} zijn. Laten we dit gebruiken om de bovenstaande methode te testen:

@Test openbare ongeldige testGetPrimeFactors () {Kaart verwachtPrimeFactorsMapForTwelve = nieuwe HashMap (); verwachtePrimeFactorsMapForTwelve.put (2, 2); verwachtePrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (verwachtPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); Kaart verwachtPrimeFactorsMapForEighteen = nieuwe HashMap (); verwachtePrimeFactorsMapForEighteen.put (2, 1); verwachtePrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (verwachtPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }

Onze lcm () methode gebruikt eerst de getPrimeFactors () methode om priemfactorisatiekaart voor elk getal te vinden. Vervolgens gebruikt het de priemfactorisatiekaart van beide getallen om hun LCM te vinden. Laten we een iteratieve implementatie van deze methode bekijken:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } Kaart primeFactorsForNum1 = getPrimeFactors (nummer1); Map primeFactorsForNum2 = getPrimeFactors (nummer2); Stel primeFactorsUnionSet = nieuwe HashSet (primeFactorsForNum1.keySet ()); primeFactorsUnionSet.addAll (primeFactorsForNum2.keySet ()); int lcm = 1; for (Integer primeFactor: primeFactorsUnionSet) {lcm * = Math.pow (primeFactor, Math.max (primeFactorsForNum1.getOrDefault (primeFactor, 0), primeFactorsForNum2.getOrDefault (primeFactor, 0))); } retourneer lcm; }

Als een goede gewoonte zullen we nu de logische juistheid van het lcm () methode:

@Test openbare ongeldige testLCM () {Assert.assertEquals (36, PrimeFactorizationAlgorithm.lcm (12, 18)); }

4. Het gebruik van het Euclidische algoritme

Er is een interessante relatie tussen de LCM en GCD (grootste gemene deler) van twee getallen die zegt dat de absolute waarde van het product van twee getallen is gelijk aan het product van hun GCD en LCM.

Zoals gezegd, gcd (a, b) * lcm (a, b) = | a * b |.

Bijgevolg, lcm (a, b) = | a * b | / ggd (a, b).

Met behulp van deze formule is ons oorspronkelijke probleem van het vinden van lcm (a, b) nu teruggebracht tot het vinden van gcd (a, b).

Toegegeven, er zijn meerdere strategieën om GCD te vinden van twee nummers. echter, de Euclidische algoritmen staan ​​bekend als een van de meest efficiënte van allemaal.

Laten we daarom kort de crux van dit algoritme begrijpen, dat kan worden samengevat in twee relaties:

• ggd (a, b) = ggd (| a% b |, | a |); waar | a | > = | b |
• ggd (p, 0) = ggd (0, p) = | p |

Laten we eens kijken hoe we lcm (12, 18) kunnen vinden met behulp van de bovenstaande relaties:

We hebben ggd (12, 18) = ggd (18% 12, 12) = ggd (6,12) = ggd (12% 6, 6) = ggd (0, 6) = 6

Daarom lcm (12, 18) = | 12 x 18 | / ggd (12, 18) = (12 x 18) / 6 = 36

We zullen nu een recursieve implementatie van het Euclidische algoritme:

openbare statische int gcd (int nummer1, int nummer2) {if (nummer1 == 0 || nummer2 == 0) {retour nummer1 + nummer2; } else {int absNumber1 = Math.abs (getal1); int absNumber2 = Math.abs (nummer2); int groterValue = Math.max (absNumber1, absNumber2); int smallereValue = Math.min (absNumber1, absNumber2); retourneer gcd (grotere waarde% kleinere waarde, kleinere waarde); }}

De bovenstaande implementatie gebruikt de absolute waarden van getallen - aangezien GCD het grootste positieve gehele getal is dat de twee getallen perfect deelt, zijn we niet geïnteresseerd in negatieve delers.

We zijn nu klaar om te controleren of de bovenstaande implementatie werkt zoals verwacht:

@Test public void testGCD () {Assert.assertEquals (6, EuclideanAlgorithm.gcd (12, 18)); }

4.1. LCM met twee nummers

Met behulp van de eerdere methode om GCD te vinden, kunnen we nu eenvoudig LCM berekenen. Nogmaals, onze lcm () methode moet twee gehele getallen accepteren als invoer om hun LCM te retourneren. Laten we eens kijken hoe we deze methode in Java kunnen implementeren:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) return 0; anders {int gcd = gcd (nummer1, nummer2); retourneer Math.abs (getal1 * getal2) / gcd; }}

We kunnen nu de functionaliteit van de bovenstaande methode verifiëren:

@Test openbare leegte testLCM () {Assert.assertEquals (36, EuclideanAlgorithm.lcm (12, 18)); }

4.2. LCM van grote nummers met behulp van de BigInteger Klasse

Om de LCM van grote getallen te berekenen, kunnen we de BigInteger klasse.

Intern is het ggd () methode van de BigInteger klasse gebruikt een hybride algoritme om de rekenprestaties te optimaliseren. Bovendien, aangezien de BigInteger objecten zijn onveranderlijkmaakt de implementatie gebruik van veranderlijke instanties van het MutableBigInteger class om frequente geheugenherverdelingen te voorkomen.

Om te beginnen maakt het gebruik van het conventionele Euclidische algoritme om herhaaldelijk het hogere gehele getal door zijn modulus te vervangen door het lagere gehele getal.

Als gevolg hiervan wordt het paar niet alleen kleiner en kleiner, maar ook dichter bij elkaar na opeenvolgende splitsingen. Uiteindelijk is het verschil in aantal ints vereist om de omvang van de twee te behouden MutableBigInteger objecten in hun respectieve int [] waarde-arrays bereikt ofwel 1 of 0.

In dit stadium wordt de strategie overgeschakeld naar de Binair GCD-algoritme om nog snellere berekeningsresultaten te krijgen.

Ook in dit geval berekenen we LCM door de absolute waarde van het product van de getallen te delen door hun GCD. Net als bij onze eerdere voorbeelden, is onze lcm () methode duurt twee BigInteger waarden als invoer en retourneert de LCM voor de twee getallen als een BigInteger. Laten we het in actie zien:

openbare statische BigInteger lcm (BigInteger getal1, BigInteger getal2) {BigInteger gcd = getal1.gcd (getal2); BigInteger absProduct = number1.multiply (number2) .abs (); retourneer absProduct.divide (gcd); }

Ten slotte kunnen we dit verifiëren met een testcase:

@Test public void testLCM () {BigInteger number1 = new BigInteger ("12"); BigInteger number2 = nieuwe BigInteger ("18"); BigInteger verwachteLCM = nieuwe BigInteger ("36"); Assert.assertEquals (verwachteLCM, BigIntegerLCM.lcm (nummer1, nummer2)); }

5. Conclusie

In deze zelfstudie hebben we verschillende methoden besproken om het kleinste gemene veelvoud van twee getallen in Java te vinden.

Bovendien leerden we ook over de relatie tussen het product van getallen met hun LCM en GCD. Gezien de algoritmen die de GCD van twee getallen efficiënt kunnen berekenen, hebben we ook het probleem van LCM-berekening teruggebracht tot een van GCD-berekening.

Zoals altijd is de volledige broncode voor de Java-implementatie die in dit artikel wordt gebruikt, beschikbaar op GitHub.