Ο Ευκλείδης από την Αλεξάνδρεια (~ 325 π.Χ. – 265 π.Χ.), ήταν Έλληνας μαθηματικός, που δίδαξε και πέθανε στην Αλεξάνδρεια της Αιγύπτου, περίπου κατά την διάρκεια της βασιλείας του Πτολεμαίου Α΄ (323 π.Χ. – 283 π.Χ.). Στις μέρες μας είναι γνωστός ως ο «πατέρας» της Γεωμετρίας.
Εφηύρε έναν αλγόριθμο για τον υπολογισμό του Μεγίστου Κοινού Διαιρέτη (Greatest Common Divisor – GCD) δύο ακεραίων α, β. GCD(α,β).
Απέδειξε ότι:
GCD(α,β) = GCD(β,α MOD β)
Όπου MOD είναι το modulo, δηλαδή το υπόλοιπο της ακέραιας διαίρεσης.
Με αποτέλεσμα να προκύψει ο εξής αλγόριθμος:
Αλγόριθμος Ευκλείδης Διάβασε α, β Αν α>β τότε maxα min
β Αλλιώς max
β min
α Τέλος_αν υ
max MOD min Όσο υ>0 επανάλαβε temp
max max
min min
temp MOD min υ
min Τέλος_επανάληψης Εμφάνισε max Τέλος Ευκλείδης
Ο παραπάνω αλγόριθμος θα μπορούσε να γίνει ως εξής με χρήση αναδρομής (ricursion):
ΣΥΝΑΡΤΗΣΗ gcd(α,β): ΑΚΕΡΑΙΑ ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: α, β, Υ ΑΡΧΗ Υmax(α,β) MOD min(α,β) ΑΝ Υ=0 ΤΟΤΕ gcd
min(α,β) ΑΛΛΙΩΣ gcd
gcd(min(α,β), max(α,β) MOD min(α,β)) ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
ΣΥΝΑΡΤΗΣΗ max(α,β): ΑΚΕΡΑΙΑ ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: α, β ΑΡΧΗ ΑΝ α>β ΤΟΤΕ maxα ΑΛΛΙΩΣ max
β ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
ΣΥΝΑΡΤΗΣΗ min(α,β): ΑΚΕΡΑΙΑ ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: α, β ΑΡΧΗ ΑΝ α<β ΤΟΤΕ minα ΑΛΛΙΩΣ min
β ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ