תכנות
—
שיעור 40
25/December/2007
האלגוריתם של אוקלידס
—
Euclidean Algorithm (GCD)
למדנו את
האלגוריתם של אוקלידס
למציאת
מחלק משותף גדול ביותר
(gcd).
האלגוריתם הזה הוא עתיק, קצר, מבריק ומהיר.
נתאר את הרעיון. נניח שקימים המספרים הטבעיים הבאים:
כשמחלקים את המספר
במספר
מקבלים מנה
(quotient)
ושארית
(residue).
אפשר לתאר זאת בנוסחאות:
קל לראות שתי תכונות:
-
אם
מספר
מחלק את
וגם את
אז
הוא מחלק
גם
את
.
-
אם
מספר
מחלק את
וגם את
אז
הוא מחלק
גם
את
.
הדבר נכון כמובן גם למחלק הגדול ביותר. לכן
השויון הזה הוא עיקר האלגוריתם. במקום לחשב את צד שמאל של המשואה, מחשבים את צד ימין,
עם מספרים יותר קטנים. חוזרים על התהליך עד ש
ומשתמשים בעובדה ש
תרגילים
-
כתוב תכנית
lcm.py
שמחשבת כפולה משותפת קטנה ביותר
(lcm)
כמו בתרגיל של
שעור קודם
אבל הפעם הפונקציה לחישוב המחלק המשותף הגדול ביותר מיושמת
על ידי האלגוריתם של אוקלידס.
חזרה לעמוד האם