Ευκλείδειος Αλγόριθμος

Ετυμολογία[]

Πρότυπο:Algorithms Η ονομασία "Ευκλείδειος " σχετίζεται ετυμολογικά με το όνομα Ευκλείδης .

Στα Στοιχεία του Ευκλείδη το Βιβλίο VII αρχίζει με τον αλγόριθμο του Ευκλείδη^[1], με τον οποίο βρίσκουμε το μέγιστο κοινό διαιρέτη (ΜΚΔ) δύο αριθμών. Είναι ένας από τους παλαιότερους αλγόριθμους με μεγάλη σπουδαιότητα, καθώς για την εύρεση του MΚΔ δεν απαιτείται παραγοντοποίηση των ακεραίων.

Αλγόριθμος[]

GCD(a, b)
1 IF b = 0 THEN 
2   RETURN a
3 ELSE 
4   RETURN GCD(b, a mod b)

Με δεδομένους δύο φυσικούς αριθμούς α και β με α>β (αν ισχύει α<β άλλαζουμε τη σειρά τους):

αν ο β είναι 0 τότε ο α είναι ο ΜΚΔ
αν ο β δεν είναι 0 τότε επαναλαμβάνουμε τη διαδικασία^[2] χρησιμοποιώντας τον β και το υπόλοιπο της διαίρεσης α/β

Παράδειγμα[]

Έστω ότι έχουμε τους αριθμούς 124, 34 και θέλουμε να βρούμε το μέγιστο κοινό διαιρέτη τους.

α	β	Επεξήγηση
124	34	124 > 34
34	22	22 = 124 mod^[3] 34 (δηλαδή το 22 είναι το υπόλοιπο του 124/34)
22	12	12 = 34 mod 22 (το 12 είναι το υπόλοιπο του 34/22)
12	10	κλπ.
10	2
2	0	αφού το β γίνεται 0 ο αλγόριθμος τερματίζει και το α (εδώ το 2) είναι ο μέγιστος κοινός διαιρέτης

Επομένως ο αριθμός 2 είναι ο μέγιστος κοινός διαιρέτης (ΜΚΔ) των 124, 34.

Σημειώσεις[]

↑
Αρχικός αλγόριθμος. Ο αρχικός αλγόριθμος όπως περιγράφηκε από τον Ευκλείδη αντιμετώπιζε το πρόβλημα γεωμετρικά, χρησιμοποιώντας επαναλαμβανόμενες αφαιρέσεις αντί για το υπόλοιπο της διαίρεσης (mod).
```
 GCD(a, b)
 1 WHILE b ≠ 0
 2   IF a > b THEN
 3     a := a - b
 4   ELSE
 5     b := b - a
 6 RETURN a
```
↑ με αναδρομή
↑ mod είναι η πράξη του υπολοίπου (στη C και στη Java συμβολίζεται με %)

Εσωτερική Αρθρογραφία[]

αλγόριθμος
[[ ]]

Βιβλιογραφία[]

Ιστογραφία[]

Κίνδυνοι Χρήσης

Αν και θα βρείτε εξακριβωμένες πληροφορίες
σε αυτήν την εγκυκλοπαίδεια
ωστόσο, παρακαλούμε να λάβετε σοβαρά υπ' όψη ότι
η "Sciencepedia" δεν μπορεί να εγγυηθεί, από καμιά άποψη,
την εγκυρότητα των πληροφοριών που περιλαμβάνει.

"Οι πληροφορίες αυτές μπορεί πρόσφατα
να έχουν αλλοιωθεί, βανδαλισθεί ή μεταβληθεί από κάποιο άτομο,
η άποψη του οποίου δεν συνάδει με το "επίπεδο γνώσης"
του ιδιαίτερου γνωστικού τομέα που σας ενδιαφέρει."

Πρέπει να λάβετε υπ' όψη ότι
όλα τα άρθρα μπορεί να είναι ακριβή, γενικώς,
και για μακρά χρονική περίοδο,
αλλά να υποστούν κάποιο βανδαλισμό ή ακατάλληλη επεξεργασία,
ελάχιστο χρονικό διάστημα, πριν τα δείτε.

Επίσης,
Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)"
(όχι μόνον, της Sciencepedia
αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)),
αν και άκρως απαραίτητοι,
είναι αδύνατον να ελεγχθούν
(λόγω της ρευστής φύσης του Web),
και επομένως είναι ενδεχόμενο να οδηγήσουν
σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο.
Ο αναγνώστης πρέπει να είναι
εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

>>Διαμαρτυρία προς την wikia<<

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)

[1] Αρχικός αλγόριθμος. Ο αρχικός αλγόριθμος όπως περιγράφηκε από τον Ευκλείδη αντιμετώπιζε το πρόβλημα γεωμετρικά, χρησιμοποιώντας επαναλαμβανόμενες αφαιρέσεις αντί για το υπόλοιπο της διαίρεσης (mod).
GCD(a, b) 1 WHILE b ≠ 0 2 IF a > b THEN 3 a := a - b 4 ELSE 5 b := b - a 6 RETURN a

[2] με αναδρομή

[3] είναι η πράξη του υπολοίπου (στη C και στη Java συμβολίζεται με %)

[1]

[2]

[3]