בנושא זה עליכם לדעת קודם על Greatest Common Divisor (GCD) ועל פעולת ה- MOD.
המחלק המשותף הגדול ביותר (GCD)
ה- GCD של שני מספרים שלמים או יותר הוא המספר השלם הגדול ביותר שמחלק את כל המספרים השלמים כך ששארם יהיה אפס.
דוגמא-
GCD של 20, 30 = 10 (10 הוא המספר הגדול ביותר שמחלק 20 ו- 30 עם שארית כ- 0)
GCD של 42, 120, 285 = 3 (3 הוא המספר הגדול ביותר שמחלק 42, 120 ו- 285 עם שארית כ- 0)
מבצע "mod"
פעולת המוד נותנת לך את השאר כאשר מחולקים שני מספרים שלמים חיוביים. אנו כותבים זאת כדלקמן-
A mod B = R
פירוש הדבר, שחלוקת A ב- B נותנת לך את שארית R, זה שונה מפעולת החלוקה שלך שנותנת לך את המנה.
דוגמא-
7 mod 2 = 1 (חלוקה 7 על 2 נותנת את השאר 1)
42 mod 7 = 0 (חלוקה 42 על 7 נותנת את השאר 0)
בעזרת שני המושגים הנ"ל מובנים תוכלו להבין בקלות את האלגוריתם האוקלידי.
אלגוריתם אוקלידי עבור המחלק הגדול ביותר (GCD)
האלגוריתם האוקלידי מוצא את ה- GCD של 2 המספרים.
תוכלו להבין טוב יותר את האלגוריתם הזה על ידי כך שתראו אותו בפעולה. בהנחה שברצונך לחשב את ה- GCD של 1220 ו- 516, ניתן להחיל את האלגוריתם האוקלידי-
בהנחה שברצונך לחשב את ה- GCD של 1220 ו- 516, מאפשר להחיל את האלגוריתם האוקלידי-
קוד פסאודו של האלגוריתם-
שלב 1: לאפשר a, b להיות שני המספרים
שלב 2: a mod b = R
שלב 3: תן a = b ו b = R
שלב 4: חזור על שלבים 2 ו -3 עד a mod b שהוא גדול מ- 0
שלב 5: GCD = b
שלב 6: סיום
קוד JavaScript לביצוע GCD-
function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } קוד JavaScript לביצוע GCD באמצעות רקורסיה-
function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); } קוד C לביצוע GCD באמצעות רקורסיה
int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } קוד C ++ לביצוע GCD-
int gcd(int a,int b) { int R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } קוד פייתון לביצוע GCD באמצעות רקורסיה
def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) קוד Java לביצוע GCD באמצעות Recursion
static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b); } אתה יכול גם להשתמש באלגוריתם האוקלידי כדי למצוא GCD של יותר משני מספרים. מכיוון ש- GCD הוא אסוציאטיבי, הפעולה הבאה תקפה- GCD(a,b,c) == GCD(GCD(a,b), c)
חשב את ה- GCD של שני המספרים הראשונים, ואז מצא את ה- GCD של התוצאה ואת המספר הבא. דוגמא- GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7
אתה יכול למצוא GCD של n מספרים באותו אופן.
מהו האלגוריתם האוקלידי המורחב?
זהו הרחבה של האלגוריתם האוקלידי. זה גם מחשב את המקדמים x, y כך ש
ax + by = gcd (a, b)
x ו- y ידועים גם כמקדמים לזהותו של בזוט.
קוד c עבור אלגוריתם אוקלידי מורחב
struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }