תכנות — שיעור 40 25/December/2007    

האלגוריתם של אוקלידס Euclidean Algorithm (GCD)

למדנו את האלגוריתם של אוקלידס למציאת מחלק משותף גדול ביותר (gcd). האלגוריתם הזה הוא עתיק, קצר, מבריק ומהיר.

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

lteq1.png
כשמחלקים את המספר lteq2.png במספר lteq3.png מקבלים מנה lteq4.png (quotient) ושארית lteq5.png (residue).

אפשר לתאר זאת בנוסחאות:

lteq6.png

קל לראות שתי תכונות:

הדבר נכון כמובן גם למחלק הגדול ביותר. לכן
lteq15.png
השויון הזה הוא עיקר האלגוריתם. במקום לחשב את צד שמאל של המשואה, מחשבים את צד ימין, עם מספרים יותר קטנים. חוזרים על התהליך עד ש lteq16.png ומשתמשים בעובדה ש
lteq17.png


תרגילים

  1. כתוב תכנית lcm.py שמחשבת כפולה משותפת קטנה ביותר (lcm) כמו בתרגיל של שעור קודם אבל הפעם הפונקציה לחישוב המחלק המשותף הגדול ביותר מיושמת על ידי האלגוריתם של אוקלידס.

חזרה לעמוד האם