מחלק משותף מקסימלי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q131752 |
קוריוז תכנותי + ניטפוק: לא הצירוף הלינארי הקטן ביותר, אלה הצירוף הלינארי *החיובי* הקטן ביותר. תמיד אפשר לקבל 0, שלא לדבר על שליליים. |
||
שורה 11:
== כמה תכונות של המחלק המשותף המקסימלי ==
המחלק המשותף המקסימלי של a ו- b מוגדר היטב, פרט למקרה ש- <math>\ a=b=0</math> (אז כל מספר מחלק את שניהם). מקרים מיוחדים אחרים הם: <math>\ (a,0)=a</math>; <math>\ (a,a)=a</math>; <math>\ (a,1)=1</math>. תכונה חשובה נוספת, העומדת בבסיס ההגדרה של [[חבורת אוילר]]: אם a,b זרים, אז לכל n, <math>\ (n,ab)=(n,a)(n,b)</math>. כמו כן, הוא מחלק כל צירוף לינארי במקדמים שלמים של a ו-b (ולכן בפרט הוא המספר החיובי הקטן ביותר שניתן לקבל כצירוף לינארי במקדמים שלמים שלהם).
== חישוב המחלק המשותף המקסימלי ==
שורה 84:
בין התחומים הראשיים, ה[[חוג אוקלידי|חוגים האוקלידיים]] מתאפיינים בכך שאפשר לבצע בהם חילוק עם שארית. אלו הם בדיוק החוגים שבהם אפשר לממש את האלגוריתם של אוקלידס שתואר לעיל.
==כלי להדגמת רקורסיה==
[[פונקציה (תכנות)|פונקציה]] המממשת את האלגוריתם של אוקלידס בצורה רקורסיבית משמשת לעתים קרובות כדי להדגים את העוצמה של שימוש ב[[רקורסיה]] בתכנות. הפונקציה הבאה שמחשבת gcd מפתיעה בפשטותה, בזכות השימוש ברקורסיה. התחביר מתאים למספר שפות קרובות, ביניהן [[C (שפת תכנות)|C]] ו-[[Java]]. ניתן לכתוב פונקציה דומה בכל שפה שתומכת ברקורסיה.
<source lang="c">
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
</source>
==ראו גם==
|