streamalism.org

1. Prehľad

Najmenej spoločné násobok (LCM) dvoch nenulových celých čísel (a, b) je najmenšie kladné celé číslo, ktoré je navzájom úplne deliteľné a a b.

V tomto tutoriále sa dozvieme o rôznych prístupoch k nájdeniu LCM dvoch alebo viacerých čísel. To musíme poznamenať záporné celé čísla a nula nie sú kandidátmi na LCM.

2. Výpočet LCM dvoch čísel pomocou jednoduchého algoritmu

LCM dvoch čísel nájdeme pomocou jednoduchého faktu, že násobenie je opakované sčítanie.

2.1. Algoritmus

Jednoduchý algoritmus na vyhľadanie LCM je iteračný prístup, ktorý využíva niekoľko základných vlastností LCM dvoch čísel.

Po prvé, vieme, že LCM ľubovoľného čísla s nulou je nula sám. Z postupu teda môžeme urobiť predčasné ukončenie, kedykoľvek je ktorékoľvek z uvedených celých čísel 0.

Po druhé, môžeme tiež využiť skutočnosť, že dolná hranica LCM dvoch nenulových celých čísel je väčšia z absolútnych hodnôt týchto dvoch čísel.

Navyše, ako už bolo vysvetlené, LCM nikdy nemôže byť záporné celé číslo. Tak dobre používajte iba absolútne hodnoty celých čísel na hľadanie možných násobkov, kým nenájdeme spoločný násobok.

Pozrime sa na presný postup, ktorý musíme dodržať pri určovaní lcm (a, b):

1. Ak a = 0 alebo b = 0, potom sa vráťte s lcm (a, b) = 0, inak prejdite na krok 2.
2. Vypočítajte absolútne hodnoty dvoch čísel.
3. Inicializujte lcm ako vyššiu z dvoch hodnôt vypočítaných v kroku 2.
4. Ak je lcm deliteľné nižšou absolútnou hodnotou, potom návrat.
5. Prírastok lcm o vyššiu absolútnu hodnotu medzi týmito dvoma a prejdite na krok 4.

Predtým, ako začneme s implementáciou tohto jednoduchého prístupu, urobme suchý chod a nájdime lcm (12, 18).

Pretože 12 aj 18 sú kladné, prejdime na krok 3, inicializujeme lcm = max (12, 18) = 18 a pokračujeme ďalej.

V našej prvej iterácii lcm = 18, ktorú nie je možné úplne deliť číslom 12. Takže ju zvýšime o 18 a pokračujeme.

V druhej iterácii vidíme, že lcm = 36 a teraz je úplne deliteľný číslom 12. Takže sa môžeme vrátiť z algoritmu a dospieť k záveru, že lcm (12, 18) je 36.

2.2. Implementácia

Implementujme algoritmus v Jave. Náš lcm () metóda musí prijať dva celočíselné argumenty a uviesť ich LCM ako návratovú hodnotu.

Môžeme si všimnúť, že vyššie uvedený algoritmus zahŕňa vykonanie niekoľkých matematických operácií s číslami, ako je nájdenie absolútnych, minimálnych a maximálnych hodnôt. Na tento účel môžeme použiť zodpovedajúce statické metódy Matematika trieda ako napr abs (), min (), a max (), resp.

Realizujme naše lcm () metóda:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } int absNumber1 = Math.abs (číslo1); int absNumber2 = Math.abs (number2); int absHigherNumber = Math.max (absNumber1, absNumber2); int absLowerNumber = Math.min (absNumber1, absNumber2); int lcm = absHigherNumber; while (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } návrat lcm; }

Ďalej overíme aj túto metódu:

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

Vyššie uvedený testovací prípad overuje správnosť lcm () metóda tvrdením, že lcm (12, 18) je 36.

3. Použitie prístupu Prime Factorization

Základná veta o aritmetike hovorí, že je možné jedinečne vyjadriť každé celé číslo väčšie ako jedno ako produkt mocnin prvočísel.

Pre každé celé číslo N> 1 teda máme N = (2k1) * (3k2) * (5k3) *…

Pomocou výsledku tejto vety teraz pochopíme primárny faktorizačný prístup k nájdeniu LCM dvoch čísel.

3.1. Algoritmus

Prístup prvostupňovej faktorizácie počíta LCM z primárneho rozkladu týchto dvoch čísel. Môžeme použiť prvočíselné faktory a exponenty z prvočíselnej faktorizácie na výpočet LCM dvoch čísel:

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

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

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

Pozrime sa, ako vypočítať LCM 12 a 18 pomocou tohto prístupu:

Najskôr musíme reprezentovať absolútne hodnoty týchto dvoch čísel ako súčin prvočíselných faktorov:

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

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

Môžeme si všimnúť, že prvoradé faktory vo vyššie uvedených znázorneniach sú 2 a 3.

Ďalej určíme exponent každého hlavného faktora pre LCM. Robíme to tak, že jej vyššiu moc vezmeme z dvoch reprezentácií.

Pri použití tejto stratégie bude sila 2 v LCM max (2, 1) = 2 a sila 3 v LCM bude max (1, 2) = 2.

Nakoniec môžeme vypočítať LCM vynásobením hlavných faktorov zodpovedajúcou silou získanou v predchádzajúcom kroku. V dôsledku toho máme lcm (12, 18) = 2² * 3² = 36.

3.2. Implementácia

Naša implementácia Java využíva na hľadanie LCM primárne faktorizačné znázornenie týchto dvoch čísel.

Z tohto dôvodu naše getPrimeFactors () metóda musí prijať celočíselný argument a poskytnúť nám jej hlavné faktorizačné zastúpenie. V Jave môžeme reprezentovať prvočíselnú faktorizáciu čísla pomocou a HashMap kde každý kľúč označuje prime faktor a hodnota spojená s kľúčom znamená exponent zodpovedajúceho faktora.

Pozrime sa na iteračnú implementáciu getPrimeFactors () metóda:

verejná statická mapa getPrimeFactors (int číslo) {int absNumber = Math.abs (číslo); Mapa primeFactorsMap = nová HashMap (); for (int factor = 2; factor <= absNumber; factor ++) {while (absNumber% factor == 0) {Integer power = primeFactorsMap.get (factor); if (power == null) {power = 0; } primeFactorsMap.put (faktor, výkon + 1); absNumber / = faktor; }} vratit primeFactorsMap; }

Vieme, že primárne faktorizačné mapy 12 a 18 sú {2 → 2, 3 → 1} a {2 → 1, 3 → 2}. Použijeme to na otestovanie vyššie uvedenej metódy:

@Test public void testGetPrimeFactors () {Mapa expectPrimeFactorsMapForTwelve = nový HashMap (); expectPrimeFactorsMapForTwelve.put (2, 2); expectPrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (expectPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); Mapa expectPrimeFactorsMapForEighteen = nový HashMap (); expectPrimeFactorsMapForEighteen.put (2, 1); expectPrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (expectPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }

Náš lcm () metóda najskôr použije getPrimeFactors () metóda na vyhľadanie primárnej faktorizačnej mapy pre každé číslo. Ďalej použije primárnu faktorizačnú mapu oboch čísel na nájdenie ich LCM. Pozrime sa na iteračnú implementáciu tejto metódy:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } Mapa primeFactorsForNum1 = getPrimeFactors (číslo1); Mapa primeFactorsForNum2 = getPrimeFactors (číslo2); Nastaviť primeFactorsUnionSet = nový HashSet (primeFactorsForNum1.keySet ()); primeFactorsUnionSet.addAll (primeFactorsForNum2.keySet ()); int lcm = 1; pre (Integer primeFactor: primeFactorsUnionSet) {lcm * = Math.pow (primeFactor, Math.max (primeFactorsForNum1.getOrDefault (primeFactor, 0), primeFactorsForNum2.getOrDefault (primeFactor, 0))); } návrat lcm; }

Ako dobrý postup teraz overíme logickú správnosť súboru lcm () metóda:

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

4. Použitie euklidovského algoritmu

Medzi LCM a GCD (Najväčší spoločný deliteľ) dvoch čísel je zaujímavý vzťah, ktorý hovorí, že absolútna hodnota súčinu dvoch čísel sa rovná súčinu ich GCD a LCM.

Ako je uvedené, gcd (a, b) * lcm (a, b) = | a * b |.

V dôsledku toho lcm (a, b) = | a * b | / gcd (a, b).

Pomocou tohto vzorca sa náš pôvodný problém nájsť lcm (a, b) teraz zmenšil na iba nájdenie gcd (a, b).

Udelené, Existuje niekoľko stratégií hľadania GCD z dvoch čísel. Avšak Euklidovský algoritmus je známy ako jeden z najefektívnejších zo všetkých.

Z tohto dôvodu poďme stručne pochopiť podstata tohto algoritmu, ktorú možno zhrnúť do dvoch vzťahov:

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

Pozrime sa, ako nájdeme lcm (12, 18) pomocou vyššie uvedených vzťahov:

Máme gcd (12, 18) = gcd (18% 12, 12) = gcd (6,12) = gcd (12% 6, 6) = gcd (0, 6) = 6

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

Teraz uvidíme a rekurzívna implementácia euklidovského algoritmu:

public static int gcd (int number1, int number2) {if (number1 == 0 || number2 == 0) {return number1 + number2; } else {int absNumber1 = Math.abs (number1); int absNumber2 = Math.abs (number2); int largerValue = Math.max (absNumber1, absNumber2); int smallerValue = Math.min (absNumber1, absNumber2); návrat gcd (greaterValue% smallerValue, smallerValue); }}

Vyššie uvedená implementácia využíva absolútne hodnoty čísel - keďže GCD je najväčšie kladné celé číslo, ktoré dokonale rozdeľuje tieto dve čísla, nezaujímajú nás záporné delitele.

Teraz sme pripravení overiť, či vyššie uvedená implementácia funguje podľa očakávaní:

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

4.1. LCM dvoch čísel

Použitím staršej metódy na nájdenie GCD môžeme teraz ľahko vypočítať LCM. Opäť naša lcm () metóda musí prijať dve celé čísla ako vstup, aby vrátila svoju LCM. Pozrime sa, ako môžeme implementovať túto metódu v Jave:

public static int lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) return 0; else {int gcd = gcd (cislo1, cislo2); návrat Math.abs (číslo1 * číslo2) / gcd; }}

Teraz môžeme overiť funkčnosť vyššie uvedenej metódy:

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

4.2. LCM veľkých čísel pomocou BigInteger Trieda

Na výpočet LCM veľkých čísel môžeme využiť BigInteger trieda.

Vnútorne gcd () metóda BigInteger trieda používa hybridný algoritmus optimalizovať výpočtový výkon. Navyše, keďže BigInteger objekty sú nemenné, implementácia využíva premenlivé inštancie MutableBigInteger triedy, aby sa zabránilo častému prerozdeleniu pamäte.

Najprv používa konvenčný euklidovský algoritmus opakovane nahradiť vyššie celé číslo jeho modulom za nižšie celé číslo.

Výsledkom je, že dvojica sa nielen zmenšuje a zmenšuje, ale aj postupne zbližuje. Nakoniec bude rozdiel v počte intje požadované na udržanie veľkosti týchto dvoch MutableBigInteger predmetov int [] hodnotové polia dosahujú buď 1 alebo 0.

V tejto fáze sa stratégia mení na Binárny algoritmus GCD na získanie ešte rýchlejších výsledkov výpočtu.

Aj v tomto prípade vypočítame LCM vydelením absolútnej hodnoty súčinu čísel ich GCD. Podobné našim predchádzajúcim príkladom, našim lcm () metóda trvá dva BigInteger hodnoty ako vstup a vráti LCM pre dve čísla ako a BigInteger. Pozrime sa na to v akcii:

public static BigInteger lcm (BigInteger number1, BigInteger number2) {BigInteger gcd = number1.gcd (number2); BigInteger absProduct = number1.multiply (number2) .abs (); návrat absProduct.divide (gcd); }

Nakoniec to môžeme overiť pomocou testovacieho prípadu:

@Test public void testLCM () {BigInteger number1 = new BigInteger ("12"); BigInteger number2 = nový BigInteger ("18"); BigInteger očakávaný LCM = nový BigInteger ("36"); Assert.assertEquals (expectLCM, BigIntegerLCM.lcm (number1, number2)); }

5. Záver

V tomto tutoriáli sme diskutovali o rôznych metódach hľadania najmenšieho spoločného násobku dvoch čísel v Jave.

Ďalej sme sa tiež dozvedeli o vzťahu medzi produktom čísel s ich LCM a GCD. Vzhľadom na algoritmy, ktoré dokážu efektívne vypočítať GCD dvoch čísel, sme tiež znížili problém výpočtu LCM na jeden z výpočtov GCD.

Úplný zdrojový kód implementácie Java použitý v tomto článku je ako vždy k dispozícii na GitHub.