streamalism.org

1. Oversikt

Minst felles multiplum (LCM) av to ikke-heltall (a, b) er det minste positive heltallet som er helt delelig av begge en og b.

I denne opplæringen lærer vi om forskjellige tilnærminger for å finne LCM for to eller flere tall. Vi må merke oss det negative heltall og null er ikke kandidater for LCM.

2. Beregne LCM av to tall ved hjelp av en enkel algoritme

Vi kan finne LCM på to tall ved å bruke det enkle faktum at multiplikasjon er gjentatt tilsetning.

2.1. Algoritme

Den enkle algoritmen for å finne LCM er en iterativ tilnærming som bruker noen få grunnleggende egenskaper av LCM med to tall.

For det første vet vi at LCM for et hvilket som helst tall med null er null seg selv. Så vi kan ta en tidlig avslutning fra prosedyren når et av de angitte heltallene er 0.

For det andre kan vi også benytte oss av det faktum at nedre grense av LCM for to ikke-null heltall er den største av de absolutte verdiene til de to tallene.

Dessuten, som forklart tidligere, kan LCM aldri være et negativt heltall. Så vel bruk bare absolutte verdier for heltallene for å finne mulige multipler til vi finner et felles multiplum.

La oss se den nøyaktige prosedyren vi må følge for å bestemme lcm (a, b):

1. Hvis a = 0 eller b = 0, så returner med lcm (a, b) = 0, ellers går du til trinn 2.
2. Beregn absolutte verdier for de to tallene.
3. Initialiser lcm som den høyeste av de to verdiene beregnet i trinn 2.
4. Hvis lcm er delelig med den lavere absolutte verdien, så returner.
5. Øk lcm med den høyere absolutte verdien blant de to, og gå til trinn 4.

Før vi begynner med implementeringen av denne enkle tilnærmingen, la oss tørke for å finne lcm (12, 18).

Ettersom både 12 og 18 er positive, la oss hoppe til trinn 3, initialisere lcm = max (12, 18) = 18, og fortsett videre.

I vår første iterasjon, lcm = 18, som ikke er helt delelig med 12. Så, øker vi den med 18 og fortsetter.

I den andre iterasjonen kan vi se at lcm = 36 og nå er helt delelig med 12. Så vi kan komme tilbake fra algoritmen og konkludere med at lcm (12, 18) er 36.

2.2. Gjennomføring

La oss implementere algoritmen i Java. Våre lcm () metoden må godta to heltallargumenter og gi LCM som en returverdi.

Vi kan merke at ovennevnte algoritme innebærer å utføre noen få matematiske operasjoner på tallene, for eksempel å finne absolutte, minimum og maksimale verdier. For dette formålet kan vi bruke de tilsvarende statiske metodene til Matte klasse som f.eks abs (), min (), og maks (), henholdsvis.

La oss implementere vår lcm () metode:

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

La oss også validere denne metoden:

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

Ovennevnte testtilfelle verifiserer riktigheten av lcm () metode ved å hevde at lcm (12, 18) er 36.

3. Bruke Prime Factorization Approach

Den grunnleggende teoremet for aritmetikk sier at det er mulig å unikt uttrykke hvert heltall større enn ett som et produkt av krefter av primtall.

Så for ethvert heltall N> 1 har vi N = (2k1) * (3k2) * (5k3) * ...

Ved å bruke resultatet av denne teoremet, vil vi nå forstå hovedfaktoriseringsmetoden for å finne LCM på to tall.

3.1. Algoritme

Primfaktoriseringsmetoden beregner LCM fra primærnedbrytningen av de to tallene. Vi kan bruke primfaktorene og eksponentene fra primfaktoriseringen til å beregne LCM av de to tallene:

Når, | a | = (2p1) * (3p2) * (5p3) * ...

og | b | = (2q1) * (3q2) * (5q3) * ...

deretter, lcm (a, b) = (2max (s₁, q₁)) * (3maks (s₂, q₂)) * (5maks (s₃, q₃)) …

La oss se hvordan vi beregner LCM på 12 og 18 ved hjelp av denne tilnærmingen:

For det første må vi representere de absolutte verdiene til de to tallene som produkter av hovedfaktorer:

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

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

Vi kan her merke at hovedfaktorene i representasjonene ovenfor er 2 og 3.

La oss deretter bestemme eksponenten for hver primærfaktor for LCM. Vi gjør dette ved å ta sin høyere kraft fra de to representasjonene.

Ved å bruke denne strategien vil kraften til 2 i LCM være maks (2, 1) = 2, og kraften til 3 i LCM vil være maks (1, 2) = 2.

Til slutt kan vi beregne LCM ved å multiplisere hovedfaktorene med en tilsvarende kraft oppnådd i forrige trinn. Derfor har vi lcm (12, 18) = 2² * 3² = 36.

3.2. Gjennomføring

Vår Java-implementering bruker hovedfaktorisering av de to tallene for å finne LCM.

For dette formålet, vår getPrimeFactors () metoden trenger å akseptere et heltallargument og gi oss dens viktigste faktoriseringsrepresentasjon. I Java, vi kan representere primfaktorisering av et tall ved hjelp av a HashMap der hver nøkkel betegner hovedfaktoren og verdien som er knyttet til nøkkelen, betyr eksponenten for den tilsvarende faktoren.

La oss se en iterativ implementering av getPrimeFactors () metode:

offentlig statisk kart getPrimeFactors (int number) {int absNumber = Math.abs (number); Kart primeFactorsMap = nytt HashMap (); for (int factor = 2; factor <= absNumber; factor ++) {while (absNumber% factor == 0) {Integer power = primeFactorsMap.get (factor); hvis (power == null) {power = 0; } primeFactorsMap.put (faktor, effekt + 1); absNumber / = faktor; }} returner primeFactorsMap; }

Vi vet at primfaktoriseringskartene på 12 og 18 er henholdsvis {2 → 2, 3 → 1} og {2 → 1, 3 → 2}. La oss bruke dette til å teste metoden ovenfor:

@Test offentlig ugyldig testGetPrimeFactors () {Map expectedPrimeFactorsMapForTwelve = new HashMap (); expectPrimeFactorsMapForTwelve.put (2, 2); expectPrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (expectedPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); Kart forventetPrimeFactorsMapForEighteen = ny HashMap (); expectPrimeFactorsMapForEighteen.put (2, 1); expectPrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (expectedPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }

Våre lcm () metoden først bruker getPrimeFactors () metode for å finne primfaktoriseringskart for hvert tall. Deretter bruker den primærfaktoriseringskartet for begge tallene for å finne LCM. La oss se en iterativ implementering av denne metoden:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } Kart primeFactorsForNum1 = getPrimeFactors (nummer1); Kartlegg primeFactorsForNum2 = getPrimeFactors (nummer2); Sett primeFactorsUnionSet = ny 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)))); } returnere lcm; }

Som en god praksis skal vi nå kontrollere den logiske korrektheten av lcm () metode:

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

4. Bruke den euklidiske algoritmen

Det er en interessant sammenheng mellom LCM og GCD (Greatest Common Divisor) med to tall som sier at den absolutte verdien av produktet med to tall er lik produktet av deres GCD og LCM.

Som nevnt, gcd (a, b) * lcm (a, b) = | a * b |.

Følgelig lcm (a, b) = | a * b | / gcd (a, b).

Ved å bruke denne formelen er vårt opprinnelige problem med å finne lcm (a, b) nå redusert til bare å finne gcd (a, b).

Gitt, det er flere strategier for å finne GCD av to tall. Imidlertid, den Euklidisk algoritme er kjent for å være en av de mest effektive av alle.

La oss av denne grunn kort forstå kjernen i denne algoritmen, som kan oppsummeres i to forhold:

• gcd (a, b) = gcd (| a% b |, | a |); hvor | a | > = | b |
• gcd (p, 0) = gcd (0, p) = | p |

La oss se hvordan vi kan finne lcm (12, 18) ved hjelp av forholdene ovenfor:

Vi har gcd (12, 18) = gcd (18% 12, 12) = gcd (6,12) = gcd (12% 6, 6) = gcd (0, 6) = 6

Derfor er lcm (12, 18) = | 12 x 18 | / gcd (12, 18) = (12 x 18) / 6 = 36

Vi får nå se en rekursiv implementering av den euklidiske algoritmen:

offentlig statisk int gcd (int nummer1, int nummer2) {if (nummer1 == 0 || nummer2 == 0) {retur nummer1 + nummer2; } annet {int absNumber1 = Math.abs (nummer1); int absNumber2 = Math.abs (number2); int largerValue = Math.max (absNumber1, absNumber2); int smallerValue = Math.min (absNumber1, absNumber2); returner gcd (largeValue% smallerValue, smallerValue); }}

Ovennevnte implementering bruker de absolutte verdiene av tall - siden GCD er det største positive heltallet som perfekt deler de to tallene, er vi ikke interessert i negative delere.

Vi er nå klare til å verifisere om implementeringen ovenfor fungerer som forventet:

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

4.1. LCM med to tall

Ved å bruke den tidligere metoden for å finne GCD, kan vi nå enkelt beregne LCM. Igjen, vår lcm () metoden må godta to heltall som input for å returnere LCM. La oss se hvordan vi kan implementere denne metoden i Java:

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

Vi kan nå bekrefte funksjonaliteten til metoden ovenfor:

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

4.2. LCM for store tall ved bruk av BigInteger Klasse

For å beregne LCM for store tall, kan vi utnytte BigInteger klasse.

Internt, den gcd () metoden for BigInteger klasse bruker en hybrid algoritme for å optimalisere beregningsytelsen. Dessuten, siden BigInteger gjenstander er uforanderligeimplementeringen utnytter foranderlige forekomster av MutableBigInteger klasse for å unngå hyppige omdisponeringer av minne.

Til å begynne med bruker den den konvensjonelle euklidiske algoritmen å erstatte det høyere heltallet gjentatte ganger med dets modul med det nedre heltallet.

Som et resultat blir paret ikke bare mindre og mindre, men også nærmere hverandre etter påfølgende divisjoner. Etter hvert kan forskjellen i antall inter nødvendig for å holde størrelsen på de to MutableBigInteger gjenstander i deres respektive int [] verdiordninger når enten 1 eller 0.

På dette stadiet byttes strategien til Binær GCD-algoritme for å få enda raskere beregningsresultater.

I dette tilfellet vil vi også beregne LCM ved å dele den absolutte verdien av produktet av tallene med deres GCD. I likhet med våre tidligere eksempler, vår lcm () metoden tar to BigInteger verdier som inngang og returnerer LCM for de to tallene som a BigInteger. La oss se det i aksjon:

offentlig statisk BigInteger lcm (BigInteger number1, BigInteger number2) {BigInteger gcd = number1.gcd (number2); BigInteger absProduct = number1.multiply (number2) .abs (); return absProduct.divide (gcd); }

Til slutt kan vi bekrefte dette med en testtilfelle:

@Test offentlig ugyldig testLCM () {BigInteger number1 = new BigInteger ("12"); BigInteger number2 = new BigInteger ("18"); BigInteger forventetLCM = nytt BigInteger ("36"); Assert.assertEquals (forventetLCM, BigIntegerLCM.lcm (nummer1, nummer2)); }

5. Konklusjon

I denne veiledningen diskuterte vi forskjellige metoder for å finne det minst vanlige multiplumet av to tall i Java.

Videre lærte vi også om forholdet mellom tallproduktet og deres LCM og GCD. Gitt algoritmer som kan beregne GCD av to tall effektivt, har vi også redusert problemet med LCM-beregning til en av GCD-beregninger.

Som alltid er den fullstendige kildekoden for Java-implementeringen som brukes i denne artikkelen tilgjengelig på GitHub.