Pronalaženje najmanje zajedničkog višestrukog u Javi

1. Pregled

Najmanji zajednički višekratnik (LCM) dvaju cijelih brojeva koji nisu nula (a, b) je najmanji pozitivni cijeli broj koji je savršeno djeljiv s obje a i b.

U ovom uputstvu naučit ćemo o različitim pristupima za pronalaženje LCM-a dva ili više brojeva. To moramo primijetiti negativne cijele brojeve i nula nisu kandidati za LCM.

2. Izračunavanje LCM-a dvaju brojeva pomoću jednostavnog algoritma

LCM dva broja možemo pronaći pomoću jednostavne činjenice da množenje je ponovljeno zbrajanje.

2.1. Algoritam

Jednostavni algoritam za pronalaženje LCM-a je iterativni pristup koji koristi nekoliko temeljnih svojstava LCM-a od dva broja.

Prvo, znamo da LCM bilo kojeg broja s nulom je nula sebe. Dakle, možemo izvršiti rani izlazak iz postupka kad god je bilo koji od danih cijelih brojeva 0.

Drugo, također možemo iskoristiti činjenicu da donja granica LCM-a dviju cjelina koja nije nula veća je od apsolutnih vrijednosti dva broja.

Štoviše, kao što je ranije objašnjeno, LCM nikada ne može biti negativan cijeli broj. Tako dobro koristiti samo apsolutne vrijednosti cijelih brojeva za pronalaženje mogućih višekratnika dok ne nađemo zajednički višekratnik.

Pogledajmo točan postupak koji moramo slijediti za određivanje lcm (a, b):

  1. Ako je a = 0 ili b = 0, vratite se s lcm (a, b) = 0, u suprotnom idite na korak 2.
  2. Izračunajte apsolutne vrijednosti dva broja.
  3. Inicijalizirajte lcm kao veću od dvije vrijednosti izračunate u koraku 2.
  4. Ako je lcm djeljiv s nižom apsolutnom vrijednošću, tada se vrati.
  5. Povećajte lcm za veću apsolutnu vrijednost među ta dva i prijeđite na korak 4.

Prije nego započnemo s provedbom ovog jednostavnog pristupa, napravimo pokušaj pronalaska lcm (12, 18).

Kako su i 12 i 18 pozitivni, prijeđimo na korak 3, inicijalizirajući lcm = max (12, 18) = 18 i nastavimo dalje.

U našoj prvoj iteraciji, lcm = 18, koja nije savršeno djeljiva sa 12. Dakle, povećavamo je za 18 i nastavljamo.

U drugoj iteraciji možemo vidjeti da je lcm = 36 i sada je savršeno djeljiv s 12. Dakle, možemo se vratiti iz algoritma i zaključiti da je lcm (12, 18) 36.

2.2. Provedba

Primijenimo algoritam u Javi. Naše lcm () metoda treba prihvatiti dva cjelobrojna argumenta i dati njihov LCM kao povratnu vrijednost.

Možemo primijetiti da gornji algoritam uključuje izvođenje nekoliko matematičkih operacija nad brojevima kao što su pronalaženje apsolutnih, minimalnih i maksimalnih vrijednosti. U tu svrhu možemo koristiti odgovarajuće statičke metode Matematika razred kao što su trbušnjaci (), min (), i maks. (), odnosno.

Provedimo svoje lcm () metoda:

javni statički int lcm (int broj1, int broj2) {if (broj1 == 0 || broj2 == 0) {return 0; } int absNumber1 = Math.abs (broj1); int absNumber2 = Math.abs (broj2); int absHigherNumber = Math.max (absNumber1, absNumber2); int absLowerNumber = Math.min (absNumber1, absNumber2); int lcm = absHigherNumber; while (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } povratak lcm; }

Dalje, provjerimo i ovu metodu:

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

Gornji testni slučaj potvrđuje ispravnost lcm () metoda tvrdeći da je lcm (12, 18) 36.

3. Korištenje osnovnog pristupa faktorizacije

Temeljni aritmetički teorem kaže da je moguće jedinstveno izraziti svaki veći broj od broja kao umnožak potencijala prostih brojeva.

Dakle, za bilo koji cijeli broj N> 1 imamo N = (2k1) * (3k2) * (5k3) * ...

Koristeći rezultat ovog teorema, sada ćemo razumjeti osnovni pristup faktoriziranja kako bismo pronašli LCM dva broja.

3.1. Algoritam

Pristup proste faktorizacije izračunava LCM iz proste dekompozicije dva broja. Za izračunavanje LCM dva broja možemo koristiti proste faktore i eksponente iz proste faktorizacije.

Kada, | a | = (2p1) * (3p2) * (5p3) * ...

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

zatim, lcm (a, b) = (2max (str1, q1)) * (3max (str2, q2)) * (5max (str3, q3)) …

Pogledajmo kako izračunati LCM od 12 i 18 pomoću ovog pristupa:

Prvo, moramo predstaviti apsolutne vrijednosti dvaju brojeva kao produkte prostih čimbenika:

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

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

Ovdje možemo primijetiti da su glavni čimbenici u gornjim prikazima 2 i 3.

Dalje, odredimo eksponent svakog glavnog faktora za LCM. To radimo uzimajući njegovu višu snagu iz dva prikaza.

Koristeći ovu strategiju, snaga 2 u LCM-u bit će max (2, 1) = 2, a snaga 3 u LCM-u bit će max (1, 2) = 2.

Konačno, LCM možemo izračunati množenjem glavnih faktora s odgovarajućom snagom dobivenom u prethodnom koraku. Slijedom toga imamo lcm (12, 18) = 2² * 3² = 36.

3.2. Provedba

Naša Java implementacija koristi osnovni faktorizacijski prikaz dva broja za pronalaženje LCM-a.

U tu svrhu naš getPrimeFactors () metoda treba prihvatiti cjelobrojni argument i dati nam svoj glavni faktorizatorski prikaz. U Javi, možemo predstaviti faktorizaciju broja pomoću a HashMap gdje svaki ključ označava glavni faktor, a vrijednost povezana s ključem označava eksponent odgovarajućeg faktora.

Pogledajmo iterativnu provedbu getPrimeFactors () metoda:

javna statička karta getPrimeFactors (int broj) {int absNumber = Math.abs (broj); Mapa primeFactorsMap = novi HashMap (); za (int faktor = 2; faktor <= absNumber; faktor ++) {while (absNumber% faktor == 0) {Integer power = primeFactorsMap.get (faktor); if (snaga == null) {snaga = 0; } primeFactorsMap.put (faktor, snaga + 1); absBroj / = faktor; }} return primeFactorsMap; }

Znamo da su glavne faktorizacijske mape 12 i 18 {2 → 2, 3 → 1} odnosno {2 → 1, 3 → 2}. Upotrijebimo ovo za testiranje gore navedene metode:

@Test public void testGetPrimeFactors () {Mapa očekujePrimeFactorsMapForTwelve = nova HashMap (); očekivaniPrimeFactorsMapForTwelve.put (2, 2); očekivaniPrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (očekivaniPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); Karta se očekujePrimeFactorsMapForEighteen = nova HashMap (); očekivaniPrimeFactorsMapForEighteen.put (2, 1); očekuje sePrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (očekuje sePrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }

Naše lcm () metoda prvo koristi getPrimeFactors () metoda za pronalaženje proste faktorizacijske karte za svaki broj. Dalje, koristi glavnu faktorizacijsku mapu oba broja kako bi pronašao njihov LCM. Pogledajmo iterativnu provedbu ove metode:

javni statički int lcm (int broj1, int broj2) {if (broj1 == 0 || broj2 == 0) {return 0; } Mapa primeFactorsForNum1 = getPrimeFactors (broj1); Mapa primeFactorsForNum2 = getPrimeFactors (broj2); Postavi primeFactorsUnionSet = novi HashSet (primeFactorsForNum1.keySet ()); primeFactorsUnionSet.addAll (primeFactorsForNum2.keySet ()); int lcm = 1; za (Integer primeFactor: primeFactorsUnionSet) {lcm * = Math.pow (primeFactor, Math.max (primeFactorsForNum1.getOrDefault (primeFactor, 0), primeFactorsForNum2.getOrDefault (primeFactor, 0))); } povratak lcm; }

Kao dobru praksu, sada ćemo provjeriti logičku ispravnost lcm () metoda:

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

4. Korištenje euklidskog algoritma

Postoji zanimljiva veza između LCM-a i GCD-a (Najveći zajednički djelitelj) dvaju brojeva koji kažu da apsolutna vrijednost umnoška dva broja jednaka je umnošku njihovih GCD i LCM.

Kao što je navedeno, gcd (a, b) * lcm (a, b) = | a * b |.

Slijedom toga, lcm (a, b) = | a * b | / gcd (a, b).

Koristeći ovu formulu, naš se izvorni problem pronalaska lcm (a, b) sveo na samo pronalaženje gcd (a, b).

Odobreno, postoji više strategija za pronalaženje GCD-a od dva broja. Međutim Poznato je da je euklidski algoritam jedan od najučinkovitijih od svega.

Iz tog razloga, hajde da ukratko shvatimo srž ovog algoritma, koji se može sažeti u dvije relacije:

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

Pogledajmo kako možemo pronaći lcm (12, 18) pomoću gornjih odnosa:

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

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

Sad ćemo vidjeti rekurzivna provedba euklidskog algoritma:

javni statički int gcd (int broj1, int broj2) {if (broj1 == 0 || broj2 == 0) {povratak broj1 + broj2; } else {int absNumber1 = Math.abs (broj1); int absNumber2 = Math.abs (broj2); int largerValue = Math.max (absNumber1, absNumber2); int largerValue = Math.min (absNumber1, absNumber2); vrati gcd (većiVrijednost% manjiVrijednost, manjiVrijednost); }}

Gornja implementacija koristi apsolutne vrijednosti brojeva - budući da je GCD najveći pozitivni cijeli broj koji savršeno dijeli dva broja, negativni djelitelji nas ne zanimaju.

Sada smo spremni provjeriti radi li gornja implementacija kako se očekivalo:

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

4.1. LCM od dva broja

Koristeći raniju metodu za pronalaženje GCD-a, sada možemo lako izračunati LCM. Opet, naša lcm () metoda treba prihvatiti dvije cijele brojeve kao ulazne podatke da bi vratila svoj LCM. Pogledajmo kako ovu metodu možemo implementirati u Javi:

javni statički int lcm (int broj1, int broj2) {if (broj1 == 0 || broj2 == 0) return 0; else {int gcd = gcd (broj1, broj2); return Math.abs (broj1 * broj2) / gcd; }}

Sada možemo provjeriti funkcionalnost gore navedene metode:

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

4.2. LCM velikih brojeva pomoću BigInteger Razred

Da bismo izračunali LCM velikih brojeva, možemo iskoristiti BigInteger razred.

Interno, gcd () metoda BigInteger klasa koristi hibridni algoritam za optimizaciju izvedbe računanja. Štoviše, od BigInteger predmeti su nepromjenjivi, implementacija koristi promjenjive primjerke MutableBigInteger klase kako bi se izbjegla česta preraspodjela memorije.

Za početak koristi uobičajeni euklidski algoritam da više puta zamijeni veći cijeli broj svojim modulom s nižim cijelim brojem.

Kao rezultat, par ne samo da postaje sve manji i manji, već i bliži jedni drugima nakon uzastopnih podjela. Na kraju, razlika u broju ints potrebne za držanje veličine dva MutableBigInteger predmeti u njihovim odnosima int [] nizovi vrijednosti dosežu ili 1 ili 0.

U ovoj je fazi strategija prebačena na Binarni GCD algoritam za postizanje još bržih rezultata izračuna.

I u ovom ćemo slučaju izračunati LCM dijeljenjem apsolutne vrijednosti umnoška brojeva s njihovim GCD-om. Slično našim prethodnim primjerima, i naš lcm () metoda traje dvoje BigInteger vrijednosti kao ulaz i vraća LCM za dva broja kao a BigInteger. Pogledajmo na djelu:

javni statički BigInteger lcm (BigInteger broj1, BigInteger broj2) {BigInteger gcd = broj1.gcd (broj2); BigInteger absProduct = number1.multiply (number2) .abs (); vratiti absProduct.divide (gcd); }

Napokon, to možemo provjeriti test slučajem:

@Test public void testLCM () {BigInteger number1 = new BigInteger ("12"); BigInteger number2 = novi BigInteger ("18"); BigInteger se očekujeLCM = novi BigInteger ("36"); Assert.assertEquals (očekuje seLCM, BigIntegerLCM.lcm (broj1, broj2)); }

5. Zaključak

U ovom uputstvu raspravljali smo o raznim metodama za pronalaženje najmanjeg zajedničkog višekratnika dva broja u Javi.

Štoviše, također smo saznali o povezanosti umnoška brojeva s njihovim LCM-om i GCD-om. S obzirom na algoritme koji mogu učinkovito izračunati GCD dva broja, također smo problem izračuna LCM sveli na jedan od GCD izračuna.

Kao i uvijek, cjeloviti izvorni kod za implementaciju Jave korišten u ovom članku dostupan je na GitHubu.