תכנות — שיעור 39 18/December/2007    

מחלק משותף גדול ביותר — GCD

פתרנו פתרון תמים ואיטי למציאת מחלק משותף גדול ביותר Greatest Common Divisor (gcd)

תרגילים

קודמים

תוכלו להוריד דוגמת פתרון למציאת שורש מסדר כלשהו .

חדשים

  1. קרא את דוגמת הפתרון והבן אותה.

  2. לכל מספר יש אינסוף כפולות. ולכל שני מספרים יש אינסוף כפולות משותפות. לדוגמא: הכפולות של 2 הן

    lteq1.png
    הכפולות של 3 הן
    lteq2.png
    והכפולות המשותפות הן
    lteq3.png

    אנו מעונינים לחפש את הכפולה המשותפת הקטנה ביותר Least Common Multiple (lcm). לדוגמא:

    lteq4.png

    כתוב תכנית lcm1.py שמקבלת שני מספרים ומחשבת את הכפולה המשותפת הקטנה ביותר. השתמש בשתי פונקציות, האחת:

    gcd(m, n)

    ופונקציה שניה:
    lcm(m, n)

    שקוראת לפונקציה הראשונה ומשתמשת בנוסחה:

    lteq5.png
חזרה לעמוד האם