מציאת הכפול הנפוץ ביותר בג'אווה
1. סקירה כללית
הכפל הנפוץ ביותר (LCM) של שני מספרים שלמים שאינם אפסיים (א, ב) הוא המספר השלם החיובי הקטן ביותר הניתן לחלוקה מושלמת על ידי שניהם א ו ב.
במדריך זה נלמד על גישות שונות למציאת ה- LCM של שניים או יותר מספרים. עלינו לציין זאת מספרים שלמים שליליים ואפס אינם מועמדים ל- LCM.
2. חישוב LCM של שני מספרים באמצעות אלגוריתם פשוט
אנו יכולים למצוא את ה- LCM של שני מספרים באמצעות העובדה הפשוטה ש הכפל הוא תוספת חוזרת.
2.1. אַלגוֹרִיתְם
האלגוריתם הפשוט למצוא את ה- LCM הוא גישה איטרטיבית המשתמשת בכמה מאפיינים בסיסיים של LCM של שני מספרים.
ראשית, אנו יודעים כי LCM של כל מספר עם אפס הוא אפס את עצמה. לכן, אנו יכולים לצאת מההליך המוקדם בכל פעם שמספר השלמים הנתון הוא 0.
שנית, אנו יכולים גם להשתמש בעובדה שה- הגבול התחתון של ה- LCM של שני מספרים שלמים שאינם אפסים הוא הגדול מבין הערכים המוחלטים של שני המספרים.
יתר על כן, כפי שהוסבר קודם לכן, ה- LCM לעולם אינו יכול להיות מספר שלם שלילי. כל כך טוב השתמש רק בערכים מוחלטים של המספרים השלמים למציאת הכפולות האפשריות עד שנמצא מכפיל משותף.
בואו נראה את הנוהל המדויק שעלינו לבצע לצורך קביעת lcm (a, b):
- אם a = 0 או b = 0, אז חזור עם lcm (a, b) = 0, אחרת עבור לשלב 2.
- חשב את הערכים המוחלטים של שני המספרים.
- אתחל את lcm כגבוה משני הערכים שחושב בשלב 2.
- אם lcm ניתן לחלוקה לפי הערך המוחלט התחתון, ואז החזר.
- הגדל את lcm לפי הערך המוחלט הגבוה יותר בין השניים ועבר לשלב 4.
לפני שנתחיל ביישום הגישה הפשוטה הזו, בואו נעשה ריצה יבשה כדי למצוא lcm (12, 18).
מכיוון שגם 12 וגם 18 חיוביים, נקפוץ לשלב 3, אתחול lcm = max (12, 18) = 18 ונמשיך הלאה.
באיטרציה הראשונה שלנו, lcm = 18, שאינו ניתן לחלוקה לחלוטין ב -12. אז אנו מגדילים אותו ב- 18 וממשיכים.
באיטרציה השנייה אנו יכולים לראות ש- lcm = 36 וכעת הוא מתחלק לחלוטין ב- 12. אז נוכל לחזור מהאלגוריתם ולהסיק ש- lcm (12, 18) הוא 36.
2.2. יישום
בואו ניישם את האלגוריתם ב- Java. שֶׁלָנוּ lcm () השיטה צריכה לקבל שני ארגומנטים שלמים ולתת את ה- LCM שלהם כערך החזר.
אנו יכולים להבחין כי האלגוריתם הנ"ל כולל ביצוע מספר פעולות מתמטיות במספרים כגון מציאת ערכים מוחלטים, מינימום ומקסימום. לצורך כך אנו יכולים להשתמש בשיטות הסטטיות המתאימות של ה- מתמטיקה כיתה כגון שרירי בטן(), דקה (), ו מקסימום (), בהתאמה.
בואו ליישם את שלנו lcm () שיטה:
ציבורי סטטי ציבורי 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; בעוד (lcm% absLowerNumber! = 0) {lcm + = absHigherNumber; } להחזיר לק"מ; }לאחר מכן, בואו נאמת שיטה זו:
@Test ציבורי בטל LCM () {Assert.assertEquals (36, lcm (12, 18)); }מקרה הבדיקה הנ"ל מאמת את נכונותו של ה- lcm () שיטה על ידי טענה כי lcm (12, 18) הוא 36.
3. שימוש בגישת ה- Prime Factorization
משפט היסוד של חשבון קובע כי ניתן לבטא באופן ייחודי כל מספר שלם גדול מאחד כתוצר של כוחות של מספרים ראשוניים.
לכן, עבור כל מספר שלם N> 1, יש לנו N = (2k1) * (3k2) * (5k3) * ...
בעזרת התוצאה של משפט זה נבין כעת את גישת הפקטוריזציה העיקרית לאיתור ה- LCM של שני מספרים.
3.1. אַלגוֹרִיתְם
גישת הפקטורציה הראשונית מחשבת את ה- LCM מפירוק ראשוני של שני המספרים. אנו יכולים להשתמש בגורמים הראשוניים ובמעריכים מהגורם העיקרי כדי לחשב LCM של שני המספרים:
מתי, | א | = (2p1) * (3p2) * (5p3) * ...
ו- | ב | = (2q1) * (3q2) * (5q3) * ...
לאחר מכן, lcm (a, b) = (2max (p1, ש1)) * (3max (עמ '2, ש2)) * (5max (עמ '3, ש3)) …
בואו נראה כיצד לחשב את ה- LCM של 12 ו- 18 באמצעות גישה זו:
ראשית, עלינו לייצג את הערכים המוחלטים של שני המספרים כמוצרים של גורמים ראשוניים:
12 = 2 * 2 * 3 = 2² * 3¹
18 = 2 * 3 * 3 = 2¹ * 3²
אנו יכולים להבחין כאן כי הגורמים העיקריים בייצוגים לעיל הם 2 ו -3.
לאחר מכן, נקבע את המעריך של כל גורם ראשוני עבור ה- LCM. אנו עושים זאת על ידי לקיחת כוחו הגבוה יותר משתי הייצוגים.
באמצעות אסטרטגיה זו, העוצמה של 2 ב- LCM תהיה מקסימאלית (2, 1) = 2, והעוצמה של 3 ב- LCM תהיה מקסימלית (1, 2) = 2.
לבסוף, אנו יכולים לחשב את ה- LCM על ידי הכפלת הגורמים הראשוניים עם הספק מקביל שהתקבל בשלב הקודם. כתוצאה מכך, יש לנו lcm (12, 18) = 2² * 3² = 36.
3.2. יישום
יישום Java שלנו משתמש בייצוג פקטוריזציה ראשוני של שני המספרים כדי למצוא את ה- LCM.
למטרה זו, שלנו getPrimeFactors () השיטה צריכה לקבל טיעון שלם ולתת לנו את ייצוג הגורם העיקרי שלו. בג'אווה, אנו יכולים לייצג פקטורציה ראשונית של מספר באמצעות a מפת גיבוב כאשר כל מפתח מציין את הגורם העיקרי והערך המשויך למפתח מסמל את המעריך של הגורם המתאים.
בואו נראה יישום איטרטיבי של ה- getPrimeFactors () שיטה:
מפה סטטית ציבורית getPrimeFactors (int מספר) {int absNumber = Math.abs (number); מפה primeFactorsMap = HashMap חדש (); עבור (גורם int = 2; גורם <= absNumber; גורם ++) {ואילו (absNumber% factor == 0) {כוח שלם = primeFactorsMap.get (גורם); אם (כוח == null) {כוח = 0; } primeFactorsMap.put (גורם, כוח + 1); absNumber / = גורם; }} להחזיר primeFactorsMap; }אנו יודעים שמפות הגורם העיקרי של 12 ו- 18 הן {2 → 2, 3 → 1} ו- {2 → 1, 3 → 2} בהתאמה. בואו נשתמש בזה כדי לבדוק את השיטה הנ"ל:
@Test מבטל בטל ציבורי GetPrimeFactors () {Map expectedPrimeFactorsMapForTwelve = HashMap חדש (); expectPrimeFactorsMapForTwelve.put (2, 2); expectPrimeFactorsMapForTwelve.put (3, 1); Assert.assertEquals (expectPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors (12)); מפה expectPrimeFactorsMapForEighteen = HashMap חדש (); expectPrimeFactorsMapForEighteen.put (2, 1); expectPrimeFactorsMapForEighteen.put (3, 2); Assert.assertEquals (expectPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors (18)); }שֶׁלָנוּ lcm () השיטה משתמשת לראשונה ב getPrimeFactors () שיטה לאיתור מפת פקטוריזציה ראשונית לכל מספר. לאחר מכן, היא משתמשת במפת הגורם העיקרי של שני המספרים כדי למצוא את ה- LCM שלהם. בואו נראה יישום איטרטיבי של שיטה זו:
int lcm סטטי ציבורי (int number1, int number2) {if (number1 == 0 || number2 == 0) {return 0; } מפה primeFactorsForNum1 = getPrimeFactors (מספר 1); מפה primeFactorsForNum2 = getPrimeFactors (מספר 2); הגדר primeFactorsUnionSet = חדש HashSet (primeFactorsForNum1.keySet ()); primeFactorsUnionSet.addAll (primeFactorsForNum2.keySet ()); int lcm = 1; עבור (Integer primeFactor: primeFactorsUnionSet) {lcm * = Math.pow (primeFactor, Math.max (primeFactorsForNum1.getOrDefault (primeFactor, 0), primeFactorsForNum2.getOrDefault (primeFactor, 0)))); } להחזיר לק"מ; }כנוהג טוב, כעת נוודא את נכונותו ההגיונית של ה- lcm () שיטה:
@Test מבטל בטל ציבורי LCM () {Assert.assertEquals (36, PrimeFactorizationAlgorithm.lcm (12, 18)); }4. שימוש באלגוריתם האוקלידי
יש קשר מעניין בין ה- LCM ל- GCD (המחלק המשותף הגדול ביותר) של שני מספרים שאומר כי ה- הערך המוחלט של המוצר של שני מספרים שווה למוצר של ה- GCD וה- LCM שלהם.
כאמור, gcd (a, b) * lcm (a, b) = | a * b |.
כתוצאה מכך, lcm (a, b) = | a * b | / gcd (a, b).
באמצעות נוסחה זו, הבעיה המקורית שלנו במציאת lcm (a, b) צומצמה כעת רק למציאת gcd (a, b).
נכון, ישנן מספר אסטרטגיות למציאת GCD של שני מספרים. אולם, ה ידוע כי האלגוריתם האוקלידי הוא אחד היעילים ביותר מכל.
מסיבה זו, בואו ונבין בקצרה את עיקרו של האלגוריתם הזה, שניתן לסכם בשני יחסים:
- gcd (a, b) = gcd (| a% b |, | a |); איפה | א | > = | ב |
- gcd (p, 0) = gcd (0, p) = | p |
בואו נראה כיצד אנו יכולים למצוא lcm (12, 18) באמצעות היחסים שלעיל:
יש לנו gcd (12, 18) = gcd (18% 12, 12) = gcd (6,12) = gcd (12% 6, 6) = gcd (0, 6) = 6
לכן, lcm (12, 18) = | 12 x 18 | / gcd (12, 18) = (12 x 18) / 6 = 36
כעת נראה א יישום רקורסיבי של האלגוריתם האוקלידי:
gcd סטטי ציבורי ציבורי (int number1, int number2) {if (number1 == 0 || number2 == 0) {return number1 + number2; } אחר {int absNumber1 = Math.abs (number1); int absNumber2 = Math.abs (number2); int largeValue = Math.max (absNumber1, absNumber2); int smallValue = Math.min (absNumber1, absNumber2); החזר gcd (largeValue% smallerValue, smallerValue); }}היישום לעיל משתמש בערכים מוחלטים של מספרים - מכיוון ש- GCD הוא המספר השלם החיובי הגדול ביותר המחלק את שני המספרים בצורה מושלמת, איננו מעוניינים במחלקים שליליים.
כעת אנו מוכנים לאמת אם היישום הנ"ל פועל כצפוי:
@ מבחן הריק הציבורי testGCD () {Assert.assertEquals (6, EuclideanAlgorithm.gcd (12, 18)); }4.1. LCM של שני מספרים
בעזרת השיטה הקודמת לאיתור GCD, כעת אנו יכולים לחשב בקלות LCM. שוב, שלנו lcm () השיטה צריכה לקבל שני מספרים שלמים כקלט להחזרת ה- LCM שלהם. בואו נראה כיצד נוכל ליישם שיטה זו ב- Java:
ציבורי סטטי ציבורי lcm (int number1, int number2) {if (number1 == 0 || number2 == 0) return 0; אחרת {int gcd = gcd (number1, number2); להחזיר את Math.abs (number1 * number2) / gcd; }}כעת אנו יכולים לאמת את הפונקציונליות של השיטה הנ"ל:
@Test מבטל בטל ציבורי LCM () {Assert.assertEquals (36, EuclideanAlgorithm.lcm (12, 18)); }4.2. LCM של מספרים גדולים המשתמשים ב- ביג-שלם מעמד
כדי לחשב את ה- LCM של מספרים גדולים, אנו יכולים למנף את ה- ביג-שלם מעמד.
באופן פנימי, gcd () שיטת ה- ביג-שלם בכיתה משתמשת באלגוריתם היברידי כדי לייעל את ביצועי החישוב. יתר על כן, מאז ביג-שלם עצמים הם בלתי ניתנים לשינוי, היישום ממנף מקרים ניתנים לשינוי של MutableBigInteger בכיתה כדי למנוע הקצאות תכופות של זיכרון.
ראשית, הוא משתמש באלגוריתם האוקלידי המקובל להחליף שוב ושוב את המספר השלם הגבוה במודול שלו במספר השלם התחתון.
כתוצאה מכך, הזוג לא רק הולך וקטן יותר אלא גם מתקרב זה לזה לאחר חלוקות עוקבות. בסופו של דבר, ההבדל במספר intנדרש להחזיק את גודל השניים MutableBigInteger חפצים בהתאמה שלהם int [] מערכי הערכים מגיעים ל -1 או ל 0.
בשלב זה האסטרטגיה עוברת ל אלגוריתם GCD בינארי לקבל תוצאות חישוב מהירות עוד יותר.
גם במקרה זה נחשב LCM על ידי חלוקת הערך המוחלט של המוצר של המספרים לפי ה- GCD שלהם. בדומה לדוגמאות הקודמות שלנו, שלנו lcm () השיטה לוקחת שניים ביג-שלם ערכים כקלט ומחזיר את ה- LCM עבור שני המספרים כ- ביג-שלם. בואו נראה את זה בפעולה:
BigInteger lcm ציבורי ציבורי (BigInteger number1, BigInteger number2) {BigInteger gcd = number1.gcd (number2); BigInteger absProduct = number1.multiply (number2) .abs (); החזר absProduct.divide (gcd); }לבסוף, אנו יכולים לאמת זאת באמצעות מקרה מבחן:
@Test ציבורי בטל LCM () {BigInteger number1 = BigInteger חדש ("12"); מספר מספרי ביג-מספר 2 = ביג-שלם חדש ("18"); BigInteger הצפויLCM = BigInteger חדש ("36"); Assert.assertEquals (expectLCM, BigIntegerLCM.lcm (number1, number2)); }5. מסקנה
במדריך זה דנו בשיטות שונות לאיתור המכפיל הפחות נפוץ מבין שני מספרים ב- Java.
יתר על כן, למדנו גם על הקשר בין תוצר המספרים עם ה- LCM שלהם ל- GCD. בהינתן אלגוריתמים שיכולים לחשב את ה- GCD של שני מספרים ביעילות, צמצמנו גם את בעיית חישוב LCM לאחד מחישובי GCD.
כמו תמיד, קוד המקור השלם ליישום Java המשמש במאמר זה זמין ב- GitHub.
