אלגוריתם אוקלידס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Laugh Tough (שיחה | תרומות) ←דרך פעולת האלגוריתם: ניסוח לשיפור הקריאות, תיקון ההצגה הרקורסיבית, הוספת כתיב מתמטי |
Laugh Tough (שיחה | תרומות) ←דוגמה: הוספת המחשה גרפית, שינוי המספרים בהתאם |
||
שורה 32:
==דוגמה==
[[קובץ:Euclidean algorithm 1071 462.gif|ממוזער|שמאל|הדגמה מונפשת של שימוש באלגוריתם אוקלידס לחישוב (1071,462)]]
*230/100=2 בשארית 30. לפיכך עלינו למצוא את (30,100).▼
נחשב את המחלק המשותף המקסימלי של 1071 ו-462, או (1071,462):
*462 נכנס ב-1071 פעמיים, והשארית היא 147. לפיכך עלינו למצוא את (462,174).
*174 נכנס ב-462 שלוש פעמים, והשארית היא 21. לפיכך עלינו למצוא את (174,21).
*מאחר שהמספר הקטן הוא 0, התשובה היא 7, וזו גם התשובה לשאלה המקורית.
לפתרון ניתן לתת משמעות גאומטרית כמודגם באיור: 7 הוא אורך הצלע של האריח הריבועי הגדול ביותר שמאפשר לרצף במדויק את המלבן שצלעותיו הן 1071 ו-462.
==יעילות==
| |||