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

Ο Ευκλείδης από την Αλεξάνδρεια (~ 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  β
 ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ