Ευκλείδειος Αλγόριθμος
Είναι ένας αλγόριθμος .
Ετυμολογία[]
Πρότυπο: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 συμβολίζεται με %)
Εσωτερική Αρθρογραφία[]
- αλγόριθμος
- [[ ]]
Βιβλιογραφία[]
Ιστογραφία[]
Κίνδυνοι Χρήσης |
---|
Αν και θα βρείτε εξακριβωμένες πληροφορίες "Οι πληροφορίες αυτές μπορεί πρόσφατα Πρέπει να λάβετε υπ' όψη ότι Επίσης, |
- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν
- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)