תכנות - שיעור 4 10/April/2005    

מציאת המחלק המשותף המקסימלי Greatest Common Divisor (gcd) . נתונים מספרים טבעיים . המספר , הוא המספר הגדול ביותר שמחלק גם את m וגם את n.

דוגמאות

התחלנו לראות את האלגוריתם של אוקלידס . הרעיון הוא לפשט את הבעיה צעד צעד, על ידי חלוקה עם שארית, והחלפת המספר הגדול בשארית. לדוגמא המקרה הבא: .

ראינו שיטה ב-python להחליף בין ערכי שני משתנים, על ידי 3 השמות:

# Let x and y  exchange values
t = x
x = y
y = t

חידה
נניח כי x ו y מכילים מספרים. כתוב סדרת השמות כך ש-x ו-y יתחלפו בערכים, כמו למעלה, אבל הפעם מבלי להשתמש במשתנה זכרון נוסף.