streamalism.org

1. Oversigt

Den mindst almindelige multiple (LCM) af to ikke-nul heltal (a, b) er det mindste positive heltal, der er helt deleligt af begge -en og b.

I denne vejledning lærer vi om forskellige tilgange til at finde LCM på to eller flere tal. Det skal vi bemærke negative heltal og nul er ikke kandidater til LCM.

2. Beregning af LCM af to tal ved hjælp af en simpel algoritme

Vi kan finde LCM på to tal ved at bruge det enkle faktum, at multiplikation gentages tilføjelse.

2.1. Algoritme

Den enkle algoritme til at finde LCM er en iterativ tilgang, der gør brug af nogle få grundlæggende egenskaber ved LCM med to tal.

For det første ved vi, at LCM for ethvert tal med nul er nul sig selv. Så vi kan gå tidligt ud af proceduren, når et af de givne heltal er 0.

For det andet kan vi også gøre brug af det faktum, at nedre grænse for LCM for to ikke-nul heltal er den største af de absolutte værdier for de to tal.

Desuden kan LCM som forklaret tidligere aldrig være et negativt heltal. Så godt Brug kun absolutte værdier for heltalene for at finde de mulige multipler, indtil vi finder et fælles multiplum.

Lad os se den nøjagtige procedure, som vi skal følge for at bestemme lcm (a, b):

1. Hvis a = 0 eller b = 0, vend derefter tilbage med lcm (a, b) = 0, ellers gå til trin 2.
2. Beregn absolutte værdier for de to tal.
3. Initialiser lcm som den højeste af de to værdier beregnet i trin 2.
4. Hvis lcm kan deles med den lavere absolutte værdi, skal du returnere.
5. Forøg lcm med den højere absolutte værdi blandt de to og gå til trin 4.

Før vi starter med implementeringen af ​​denne enkle tilgang, lad os tørre for at finde lcm (12, 18).

Da både 12 og 18 er positive, lad os hoppe til trin 3, initialisere lcm = max (12, 18) = 18, og fortsæt videre.

I vores første iteration er lcm = 18, som ikke er helt delelig med 12. Så vi øger den med 18 og fortsætter.

I den anden iteration kan vi se, at lcm = 36 og nu er helt delelig med 12. Så vi kan vende tilbage fra algoritmen og konkludere, at lcm (12, 18) er 36.

2.2. Implementering

Lad os implementere algoritmen i Java. Vores lcm () metoden skal acceptere to heltalargumenter og give deres LCM som en returværdi.

Vi kan bemærke, at ovennævnte algoritme involverer at udføre et par matematiske operationer på tallene, såsom at finde absolutte, minimale og maksimale værdier. Til dette formål kan vi bruge de tilsvarende statiske metoder til Matematik klasse som f.eks abs (), min (), og maks (), henholdsvis.

Lad os implementere vores lcm () metode:

offentlig statisk int lcm (int-nummer1, int-nummer2) {if (nummer1 == 0 || nummer2 == 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; mens (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } returner lcm; }

Lad os derefter validere denne metode:

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

Ovenstående testsag bekræfter rigtigheden af lcm () metode ved at hævde, at lcm (12, 18) er 36.

3. Brug af Prime Factorization Approach

Den grundlæggende sætning af aritmetik siger, at det er muligt entydigt at udtrykke hvert heltal større end et som et produkt af magt af primtal.

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

Ved at bruge resultatet af denne sætning, vil vi nu forstå den primære faktorisering tilgang til at finde LCM af to tal.

3.1. Algoritme

Primfaktoriseringsmetoden beregner LCM ud fra den primære nedbrydning af de to tal. Vi kan bruge primfaktorer og eksponenter fra primfaktorisering til at beregne LCM af de to tal:

Hvornår | a | = (2p1) * (3p2) * (5p3) *…

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

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

Lad os se, hvordan man beregner LCM på 12 og 18 ved hjælp af denne tilgang:

For det første skal vi repræsentere de absolutte værdier for de to tal som produkter af primære faktorer:

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

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

Vi kan her bemærke, at de primære faktorer i ovenstående repræsentationer er 2 og 3.

Lad os derefter bestemme eksponenten for hver primfaktor for LCM. Vi gør dette ved at tage dens højere magt fra de to repræsentationer.

Ved hjælp af denne strategi vil effekten af ​​2 i LCM være maks (2, 1) = 2, og effekten af ​​3 i LCM vil være maks (1, 2) = 2.

Endelig kan vi beregne LCM ved at multiplicere de primære faktorer med en tilsvarende effekt opnået i det foregående trin. Derfor har vi lcm (12, 18) = 2² * 3² = 36.

3.2. Implementering

Vores Java-implementering bruger primærfaktoriseringsrepræsentation af de to tal til at finde LCM.

Til dette formål er vores getPrimeFactors () metoden skal acceptere et heltalsargument og give os dets primære faktoriseringsrepræsentation. I Java, vi kan repræsentere primfaktorisering af et tal ved hjælp af a HashMap hvor hver nøgle betegner den primære faktor og den værdi, der er knyttet til nøglen, betyder eksponenten for den tilsvarende faktor.

Lad os se en iterativ implementering af getPrimeFactors () metode:

offentlig statisk kort getPrimeFactors (int nummer) {int absNumber = Math.abs (nummer); Kort primeFactorsMap = nyt HashMap (); for (int faktor = 2; faktor <= absNumber; faktor ++) {mens (absNumber% factor == 0) {Integer power = primeFactorsMap.get (factor); hvis (magt == null) {magt = 0; } primeFactorsMap.put (faktor, effekt + 1); absNumber / = faktor; }} returner primeFactorsMap; }

Vi ved, at primfaktoriseringskortene på 12 og 18 er henholdsvis {2 → 2, 3 → 1} og {2 → 1, 3 → 2}. Lad os bruge dette til at teste ovenstående metode:

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

Vores lcm () metoden først bruger getPrimeFactors () metode til at finde primfaktoriseringskort for hvert nummer. Dernæst bruger det primærfaktoriseringskortet for begge numre til at finde deres LCM. Lad os se en iterativ implementering af denne metode:

offentlig statisk int lcm (int-nummer1, int-nummer2) {if (nummer1 == 0 || nummer2 == 0) {return 0; } Kort primeFactorsForNum1 = getPrimeFactors (nummer1); Kort primeFactorsForNum2 = getPrimeFactors (nummer2); Indstil 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)))); } returner lcm; }

Som god praksis skal vi nu kontrollere den logiske rigtighed af lcm () metode:

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

4. Brug af den euklidiske algoritme

Der er et interessant forhold mellem LCM og GCD (Greatest Common Divisor) med to tal, der siger, at den absolutte værdi af produktet med to tal er lig med produktet af deres GCD og LCM.

Som nævnt er gcd (a, b) * lcm (a, b) = | a * b |.

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

Ved hjælp af denne formel er vores oprindelige problem med at finde lcm (a, b) nu blevet reduceret til bare at finde gcd (a, b).

Indrømmet, der er flere strategier for at finde GCD af to tal. Men den Euklidisk algoritme er kendt for at være en af ​​de mest effektive Af alle.

Lad os af denne grund kort forstå kernen i denne algoritme, som kan sammenfattes i to forhold:

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

Lad os se, hvordan vi kan finde lcm (12, 18) ved hjælp af ovenstående forhold:

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 ser nu en rekursiv implementering af den euklidiske algoritme:

public static int gcd (int number1, int number2) {if (number1 == 0 || number2 == 0) {return number1 + number2; } andet {int absNumber1 = Math.abs (nummer1); int absNumber2 = Math.abs (nummer2); int largerValue = Math.max (absNumber1, absNumber2); int smallerValue = Math.min (absNumber1, absNumber2); returner gcd (størreVærdi% mindreVærdi, mindreVærdi); }}

Ovenstående implementering bruger de absolutte talværdier - da GCD er det største positive heltal, der perfekt deler de to tal, er vi ikke interesseret i negative divisorer.

Vi er nu klar til at kontrollere, om ovenstående implementering fungerer som forventet:

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

4.1. LCM med to numre

Ved hjælp af den tidligere metode til at finde GCD kan vi nu let beregne LCM. Igen, vores lcm () metoden skal acceptere to heltal som input for at returnere deres LCM. Lad os se, hvordan vi kan implementere denne metode i Java:

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

Vi kan nu kontrollere funktionaliteten af ​​ovenstående metode:

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

4.2. LCM for store numre ved hjælp af BigInteger Klasse

For at beregne LCM for store tal kan vi udnytte BigInteger klasse.

Internt er den gcd () metode til BigInteger klasse bruger en hybrid algoritme for at optimere beregningsydelsen. Desuden, da den BigInteger genstande er uforanderlige, implementeringen udnytter mutable forekomster af MutableBigInteger klasse for at undgå hyppige allokeringer af hukommelse.

Til at begynde med bruger den den konventionelle euklidiske algoritme at gentagne gange erstatte det højere heltal med dets modul med det lavere heltal.

Som et resultat bliver parret ikke kun mindre og mindre, men også tættere på hinanden efter successive opdelinger. Til sidst er forskellen i antallet af ints kræves for at holde størrelsen af ​​de to MutableBigInteger genstande i deres respektive int [] værdi arrays når enten 1 eller 0.

På dette stadium skiftes strategien til Binær GCD-algoritme for at få endnu hurtigere beregningsresultater.

I dette tilfælde beregner vi også LCM ved at dividere den absolutte værdi af produktet af numrene med deres GCD. Svarende til vores tidligere eksempler, vores lcm () metoden tager to BigInteger værdier som input og returnerer LCM for de to tal som a BigInteger. Lad os se det i aktion:

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

Endelig kan vi bekræfte dette med en test sag:

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

5. Konklusion

I denne vejledning diskuterede vi forskellige metoder til at finde det mindst almindelige multiplum af to tal i Java.

Desuden lærte vi også om forholdet mellem talproduktet med deres LCM og GCD. I betragtning af algoritmer, der kan beregne GCD af to tal effektivt, har vi også reduceret problemet med LCM-beregning til en af ​​GCD-beregning.

Som altid er den komplette kildekode til Java-implementeringen, der bruges i denne artikel, tilgængelig på GitHub.