מציאת המחלק המשותף הגדול ביותר בג'אווה
1. סקירה כללית
במתמטיקה, ה- GCD של שני מספרים שלמים, שאינם אפסיים, הוא המספר השלם החיובי הגדול ביותר המחלק את כל המספרים השלמים באופן שווה.
במדריך זה נבחן שלוש גישות למציאת המחלק המשותף הגדול ביותר (GCD) של שני מספרים שלמים. בהמשך, נבחן את יישומם ב- Java.
2. כוח ברוט
לגישה הראשונה שלנו, אנו חוזרים מאחד למספר הקטן ביותר שניתן ובודקים האם המספרים השלמים הנתונים ניתנים לחלוקה באינדקס. המדד הגדול ביותר המחלק את המספרים הנתונים הוא ה- GCD של המספרים הנתונים:
int gcdByBruteForce (int n1, int n2) {int gcd = 1; עבור (int i = 1; i <= n1 && i <= n2; i ++) {if (n1% i == 0 && n2% i == 0) {gcd = i; }} להחזיר gcd; }כפי שאנו רואים, המורכבות של היישום הנ"ל היא O (min (n1, n2)) כי אנחנו צריכים לחזור על הלולאה בשביל נ פעמים (שווה ערך למספר הקטן יותר) כדי למצוא את ה- GCD.
3. האלגוריתם של אוקלידס
שנית, אנו יכולים להשתמש באלגוריתם של אוקלידס כדי למצוא את ה- GCD. האלגוריתם של אוקלידס אינו רק יעיל אלא גם קל להבנה וקל ליישום באמצעות רקורסיה בג'אווה.
השיטה של אוקלידס תלויה בשני משפטים חשובים:
- ראשית, אם נפחית את המספר הקטן מהמספר הגדול יותר, ה- GCD אינו משתנה - לכן, אם נמשיך לחסר את המספר, סוף סוף נגמר עם ה- GCD שלהם
- שנית, כאשר המספר הקטן יותר מחלק את המספר הגדול יותר, המספר הקטן יותר הוא ה- GCD של שני המספרים הנתונים.
שימו לב ביישום שלנו שנשתמש במודולו במקום בחיסור מכיוון שמדובר בעצם בחיסורים רבים בכל פעם:
int gcdByEuclidsAlgorithm (int n1, int n2) {if (n2 == 0) {return n1; } להחזיר gcdByEuclidsAlgorithm (n2, n1% n2); }כמו כן, שימו לב כיצד אנו משתמשים n2 ב n1למקם ולהשתמש בשארית במיקום n2 בשלב הרקורסיבי של האלגוריתם.
נוסף, המורכבות של האלגוריתם של אוקלידס היא O (יומן min (n1, n2)) וזה טוב יותר בהשוואה לשיטת Brute Force שראינו קודם.
4. האלגוריתם של שטיין או אלגוריתם GCD בינארי
לבסוף, אנו יכולים להשתמש גם באלגוריתם של שטיין המכונה אלגוריתם GCD בינארי, כדי למצוא את ה- GCD של שני מספרים שלמים שאינם שליליים. אלגוריתם זה משתמש בפעולות חשבון פשוטות כמו תזוזות חשבון, השוואה וחיסור.
האלגוריתם של שטיין מיישם שוב ושוב את הזהויות הבסיסיות הבאות הקשורות ל- GCD כדי למצוא GCD של שני מספרים שלמים שאינם שליליים:
- gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
- מתי n1 ו n2 שניהם אפילו מספרים שלמים, אם כן gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), שכן 2 הוא המחלק המשותף
- אם n1 הוא אפילו מספר שלם ו n2 הוא מספר שלם מוזר, אם כן gcd (n1, n2) = gcd (n1 / 2, n2), שכן 2 אינו המחלק המשותף ולהיפך
- אם n1 ו n2 שניהם מספרים שלמים מוזרים, וגם n1> = n2, לאחר מכן gcd (n1, n2) = gcd ((n1-n2) / 2, n2) ולהיפך
אנו חוזרים על שלבים 2-4 עד n1 שווים n2, או n1 = 0. ה- GCD הוא (2n) * n2. פה, נ הוא מספר הפעמים שנמצא 2 נפוץ ב n1 ו n2 בעת ביצוע שלב 2:
int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } אם (n2 == 0) {החזר n1; } int n; עבור (n = 0; ((n1 | n2) & 1) == 0; n ++) {n1 >> = 1; n2 >> = 1; } בעוד ((n1 & 1) == 0) {n1 >> = 1; } לעשות {תוך ((n2 & 1) == 0) {n2 >> = 1; } אם (n1> n2) {int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } בעוד (n2! = 0); החזר n1 << n; }אנו יכולים לראות כי אנו משתמשים בפעולות משמרות חשבון על מנת לחלק או להכפיל ב 2. יתר על כן, אנו משתמשים בחיסור על מנת להפחית את המספרים הנתונים.
המורכבות של האלגוריתם של שטיין מתי n1> n2 הוא O ((יומן2n1) 2) ואילו. מתי n1 <n2, זה O ((יומן2n2) 2).
5. מסקנה
במדריך זה בדקנו שיטות שונות לחישוב ה- GCD של שני מספרים. יישמנו אותם גם בג'אווה והתבוננו במהירות במורכבותם.
כמו תמיד, קוד המקור המלא של הדוגמאות שלנו כאן, כמו תמיד, הסתיים ב- GitHub.
