Πληροφορική Ι — Εβδομάδα 11

Ευκλείδειος Αλγόριθμος, Ακριβής Υπολογισμός, Συνεχή Κλάσματα

Ο αλγόριθμος του Ευκλείδη

gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0) = 21

Κάθε βήμα: (x, y) → (y, x % y). Γεωμετρικά: μεγαλύτερο τετράγωνο που στρώνει ένα a × b ορθογώνιο.

math.gcd() υπάρχει έτοιμο — αλλά χρειαζόμαστε τη δική μας εκδοχή για παραλλαγές.

Επεκτεταμένος Ευκλείδειος

Υπολογίζει επιπλέον συντελεστές \(x,y\) με \(ax+by=\gcd(a,b)\), βήμα-βήμα:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return g, x, y

Υπολογίζει επιπλέον συντελεστές μαζί με τον ΜΚΔ.

Ακριβής (συμβολικός) υπολογισμός

Απεριόριστοι ακέραιοι + Fraction: καμία στρογγυλοποίηση, ποτέ.

Συνεχή κλάσματα ≈ Ευκλείδειος αλγόριθμος

Ίδιος βρόχος με τον gcd, απλώς καταγράφουμε το πηλίκο σε κάθε βήμα:

def continued_fraction(p, q):
    coeffs = []
    while q != 0:
        a = p // q
        coeffs.append(a)
        p, q = q, p - a * q     # ίδιο μοτίβο με τον gcd!
    return coeffs

Ίδιος αλγόριθμος, απλώς καταγράφουμε το πηλίκο σε κάθε βήμα.

Οκνηρή αποτίμηση με γεννήτριες

Άπειρη ακολουθία → παράγουμε όρους κατ’ απαίτηση, μόνο όσους χρειαζόμαστε.

Σύνοψη

• Αλγόριθμος Ευκλείδη, επεκτεταμένη εκδοχή
• Ακριβής (συμβολικός) υπολογισμός: απεριόριστοι ακέραιοι, fractions
• Αλγόριθμος σχεδόν πανομοιότυπος με τον Ευκλείδειο — ίδια λογική, άλλη καταγραφή
• Οκνηρή αποτίμηση (lazy evaluation) με γεννήτριες

⤺ Πλήρεις σημειώσεις  ·  Πρόγραμμα μαθήματος