streamalism.org

1. Áttekintés

Két nem nulla egész szám legkevesebb közös többszöröse (LCM) (a, b) a legkisebb pozitív egész szám, amely tökéletesen osztható mindkettővel a és b.

Ebben az oktatóanyagban megismerhetünk két vagy több szám LCM-jének megkeresésére szolgáló különböző megközelítéseket. Ezt meg kell jegyeznünk a negatív egész számok és a nulla nem jelöltek az LCM-re.

2. Két szám LCM kiszámítása egyszerű algoritmus segítségével

Megtalálhatjuk két szám LCM-jét az egyszerű tény felhasználásával a szorzás megismétlődik.

2.1. Algoritmus

Az LCM megtalálásának egyszerű algoritmusa iteratív megközelítés, amely két szám LCM néhány alapvető tulajdonságát használja fel.

Először is tudjuk, hogy a Bármely nullával rendelkező szám LCM értéke nulla maga. Tehát korán kiléphetünk az eljárásból, amikor az adott egész számok bármelyike ​​0.

Másodsorban azt is felhasználhatjuk, hogy a két nem nulla egész szám LCM alsó határa a két szám abszolút értéke közül a nagyobb.

Sőt, amint azt korábban kifejtettük, az LCM soha nem lehet negatív egész szám. Olyan jól csak az egész számok abszolút értékét használja a lehetséges többszörösek megtalálásához, amíg nem találunk közös többszöröst.

Lássuk a pontos eljárást, amelyet be kell tartanunk az lcm (a, b) meghatározásához:

1. Ha a = 0 vagy b = 0, akkor térjen vissza lcm (a, b) = 0 értékre, akkor ugorjon a 2. lépésre.
2. Számítsa ki a két szám abszolút értékét.
3. Inicializálja az lcm értéket a 2. lépésben kiszámított két érték közül a magasabb értékeként.
4. Ha az lcm osztható az alsó abszolút értékkel, akkor térjen vissza.
5. Növelje az lcm-t a kettő között a magasabb abszolút értékkel, és folytassa a 4. lépéssel.

Mielőtt elkezdenénk ennek az egyszerű megközelítésnek a megvalósítását, végezzünk egy száraz futtatást az lcm (12, 18) megtalálásához.

Mivel mind a 12, mind a 18 pozitív, ugorjunk a 3. lépésre, inicializálva az lcm = max (12, 18) = 18 értéket, és folytassuk tovább.

Első iterációnkban lcm = 18, amely nem osztható tökéletesen 12-vel. Tehát 18-mal növekszünk és folytatjuk.

A második iterációban láthatjuk, hogy lcm = 36, és most tökéletesen osztható 12-vel. Tehát visszatérhetünk az algoritmusból és arra a következtetésre juthatunk, hogy lcm (12, 18) 36.

2.2. Végrehajtás

Vezessük be az algoritmust Java-ban. A mi lcm () A metódusnak két egész argumentumot kell elfogadnia, és meg kell adniuk LCM-jüket visszatérési értékként.

Észrevehetjük, hogy a fenti algoritmus magában foglal néhány matematikai műveletet a számokon, például az abszolút, a minimum és a maximális értékek megállapítását. Erre a célra használhatjuk a megfelelő statikus módszereket Math osztály, mint pl abs (), perc (), és max ()ill.

Vezessük be a mi lcm () módszer:

public static int lcm (int szám1, int szám2) {if (szám1 == 0 || szám2 == 0) {visszatér 0; } int absNumber1 = Math.abs (szám1); int absNumber2 = Math.abs (szám2); int absHigherNumber = Math.max (absNumber1, absNumber2); int absLowerNumber = Math.min (absNumber1, absNumber2); int lcm = absHigherNumber; while (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } visszatérés lcm; }

Ezután ellenőrizzük ezt a módszert is:

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

A fenti teszteset igazolja a lcm () módszer azt állítva, hogy lcm (12, 18) 36.

3. A Prime Factorization megközelítés alkalmazása

Az aritmetika alapvető tétele szerint minden egynél nagyobb egész szám egyedileg kifejezhető a prímszámok hatványának szorzataként.

Tehát bármely N> 1 egész szám esetén N = (2k1) * (3k2) * (5k3) * ...

Ennek a tételnek az eredményét felhasználva megértjük az elsődleges faktoros megközelítést két szám LCM megtalálásához.

3.1. Algoritmus

Az elsődleges faktoros megközelítés a két szám elsődleges bontása alapján számítja ki az LCM-et. A prímtényezőből származó prímtényezőket és kitevőket használhatjuk a két szám LCM kiszámításához:

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

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

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

Nézzük meg, hogyan lehet kiszámítani a 12-es és 18-as LCM-et ezzel a megközelítéssel:

Először is a két szám abszolút értékét kell képviselnünk, mint elsődleges tényezők szorzatát:

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

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

Itt észrevehetjük, hogy a fenti ábrázolások elsődleges tényezői 2 és 3.

Ezután határozzuk meg az LCM minden egyes prímtényezőjének kitevőjét. Ezt úgy tesszük, hogy a két ábrázolásból vesszük át magasabb hatalmát.

Ezt a stratégiát használva a 2 teljesítménye az LCM-ben max (2, 1) = 2, a 3 ereje pedig az LCM-ben max (1, 2) = 2 lesz.

Végül kiszámíthatjuk az LCM-et úgy, hogy az elsődleges tényezőket megszorozzuk az előző lépésben kapott megfelelő hatványokkal. Következésképpen lcm (12, 18) = 2² * 3² = 36.

3.2. Végrehajtás

Java megvalósításunk a két szám elsődleges faktoros ábrázolását használja az LCM megtalálásához.

Erre a célra a mi getPrimeFactors () A metódusnak el kell fogadnia egy egész argumentumot, és meg kell adnia az elsődleges faktoros ábrázolását. Java-ban egy szám prímtényezõ tényezõjét képviselhetjük az a használatával HashMap ahol minden kulcs az elsődleges tényezőt jelöli, és a kulcshoz társított érték a megfelelő tényező kitevőjét jelöli.

Lássuk a getPrimeFactors () módszer:

public static Map getPrimeFactors (int szám) {int absNumber = Math.abs (szám); Map primeFactorsMap = új HashMap (); for (int tényező = 2; tényező <= absz. szám; faktor ++) {while (absz. szám% tényező == 0) {Egész teljesítmény = primeFactorsMap.get (faktor); if (teljesítmény == null) {teljesítmény = 0; } primeFactorsMap.put (tényező, teljesítmény + 1); absNumber / = tényező; }} return primeFactorsMap; }

Tudjuk, hogy a 12-es és a 18-as elsődleges faktorizációs térképek {2 → 2, 3 → 1}, illetve {2 → 1, 3 → 2}. Használjuk ezt a fenti módszer tesztelésére:

@Test public void testGetPrimeFactors () {Térkép várhatóPrimeFactorsMapForTwelve = új HashMap (); vártPrimeFactorsMapForTwelve.put (2, 2); várhatóPrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (várhatóPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); Térkép várhatóPrimeFactorsMapForEighteen = új HashMap (); VárhatóPrimeFactorsMapForEighteen.put (2, 1); várhatóPrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (várhatóPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }

A mi lcm () módszer először a getPrimeFactors () módszer az egyes számok prímfaktorizációs térképének megtalálásához. Ezután mindkét szám elsődleges faktorszámítási térképét használja az LCM megtalálásához. Lássuk a módszer iteratív megvalósítását:

public static int lcm (int szám1, int szám2) {if (szám1 == 0 || szám2 == 0) {visszatér 0; } Térkép primeFactorsForNum1 = getPrimeFactors (szám1); Térkép primeFactorsForNum2 = getPrimeFactors (szám2); Set primeFactorsUnionSet = new 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))); } visszatérés lcm; }

Jó gyakorlatként most ellenőrizzük a logikai helyességét lcm () módszer:

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

4. Az euklideszi algoritmus használata

Érdekes összefüggés van az LCM és a két szám közötti GCD (legnagyobb közös osztó) között, amely azt mondja, hogy a két szám szorzatának abszolút értéke megegyezik a GCD és az LCM szorzatával.

Mint elmondtuk, gcd (a, b) * lcm (a, b) = | a * b |.

Következésképpen, lcm (a, b) = | a * b | / gcd (a, b).

Ennek a képletnek az alkalmazásával az lcm (a, b) megtalálásának eredeti problémája most már csak a gcd (a, b) megtalálására redukálódott.

Megadott, többféle stratégia létezik a GCD megtalálásához két számból. Azonban a Az euklideszi algoritmus az egyik leghatékonyabb mindenböl.

Ezért röviden értsük meg ennek az algoritmusnak a lényegét, amelyet két összefüggésben lehet összefoglalni:

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

Lássuk, hogyan találhatunk lcm (12, 18) -t a fenti kapcsolatok segítségével:

Van gcd (12, 18) = gcd (18% 12, 12) = gcd (6,12) = gcd (12% 6, 6) = gcd (0, 6) = 6

Ezért lcm (12, 18) = | 12 x 18 | / gcd (12, 18) = (12 x 18) / 6 = 36

Most meglátjuk a az euklideszi algoritmus rekurzív megvalósítása:

public static int gcd (int szám1, int szám2) {if (szám1 == 0 || szám2 == 0) {visszatérési szám1 + szám2; } else {int absNumber1 = Math.abs (szám1); int absNumber2 = Math.abs (szám2); int nagyobbValue = Math.max (absNumber1, absNumber2); int kisebbValue = Math.min (absNumber1, absNumber2); return gcd (nagyobbValue% kisebbValue, kisebbValue); }}

A fenti megvalósítás a számok abszolút értékeit használja - mivel a GCD a legnagyobb pozitív egész szám, amely tökéletesen elosztja a két számot, ezért a negatív osztók nem érdekelnek minket.

Most készen állunk ellenőrizni, hogy a fenti megvalósítás a várt módon működik-e:

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

4.1. Két szám LCM

A korábbi módszer segítségével megkereshetjük a GCD-t, és most könnyen kiszámíthatjuk az LCM-et. Ismét a mi lcm () A metódusnak két egész számot kell elfogadnia inputként az LCM visszaadásához. Lássuk, hogyan tudjuk megvalósítani ezt a módszert a Java-ban:

public static int lcm (int szám1, int szám2) {if (szám1 == 0 || szám2 == 0) visszatér 0; else {int gcd = gcd (szám1, szám2); visszatér Math.abs (szám1 * szám2) / gcd; }}

Most ellenőrizhetjük a fenti módszer működését:

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

4.2. LCM nagy számok használatával BigInteger Osztály

A nagy számok LCM kiszámításához felhasználhatjuk a BigInteger osztály.

Belsőleg az gcd () módszere BigInteger osztály hibrid algoritmust használ a számítási teljesítmény optimalizálása érdekében. Sőt, mivel a BigInteger a tárgyak megváltoztathatatlanok, a megvalósítás kihasználja a MutableBigInteger osztályban, hogy elkerüljék a gyakori memória-átcsoportosításokat.

Először is a hagyományos euklideszi algoritmust használja hogy a magasabb egész számot többször kicserélje annak modulusára az alacsonyabb egész számra.

Ennek eredményeként a pár nemcsak egyre kisebb és kisebb, hanem az egymás utáni megosztások után is közelebb kerül egymáshoz. Végül a különbség a számban ints szükséges a kettő nagyságának megtartásához MutableBigInteger tárgyakat int [] értéktömbök eléri az 1-et vagy a 0-t.

Ebben a szakaszban a stratégia átáll a Bináris GCD algoritmus a még gyorsabb számítási eredmények eléréséhez.

Ebben az esetben is kiszámítjuk az LCM-et úgy, hogy elosztjuk a számok szorzatának abszolút értékét a GCD-vel. Korábbi példáinkhoz hasonlóan a mi lcm () módszer kettőt vesz igénybe BigInteger értékeket ad meg inputként, és a két szám LCM-jét a-ként adja vissza BigInteger. Lássuk működés közben:

nyilvános statikus BigInteger lcm (BigInteger szám1, BigInteger szám2) {BigInteger gcd = szám1.gcd (szám2); BigInteger absProduct = szám1.többszörözés (szám2) .abs (); return absProduct.divide (gcd); }

Végül ezt tesztesettel ellenőrizhetjük:

@Test public void testLCM () {BigInteger number1 = new BigInteger ("12"); BigInteger number2 = új BigInteger ("18"); BigInteger várhatóLCM = új BigInteger ("36"); Assert.assertEquals (várható LCM, BigIntegerLCM.lcm (szám1, szám2)); }

5. Következtetés

Ebben az oktatóanyagban különböző módszereket vitattunk meg, hogy megtaláljuk a Java két számának legkevésbé gyakori többszörösét.

Sőt, megismerhettük a számok szorzata közötti összefüggést az LCM-mel és a GCD-vel. Adott algoritmusokkal, amelyek hatékonyan kiszámíthatják két szám GCD-jét, az LCM számításának problémáját a GCD számítás egyikére is csökkentettük.

Mint mindig, a cikkben használt Java-implementáció teljes forráskódja elérhető a GitHubon.