Προτεινόμενοι Σύνδεσμοι:    greece   -   greece hotels   -   ειδησεις   -   greece news   -   ταβλι στο internet   -   livescore   -   νέα
 easypedia

Easypedia.gr
Ελλάδα
Αρχαία Ελλάδα
Ελληνες
Πρωθυπουργοί
Οικονομία
Γεωγραφία
Ιστορία
Γλώσσα
Πληθυσμός
Μυθολογία
Πολιτισμός & Τέχνες
Ζωγραφική
Θέατρο
Κινηματογράφος
Λογοτεχνία
Μουσική
Αρχιτεκτονική
Γλυπτική
Αθλητισμός
Μυθολογία
Θρησκεία
Θετικές & Φυσικές Επιστήμες
Ανθρωπολογία
Αστρονομία
Βιολογία
Γεωλογία
Επιστήμη υπολογιστών
Μαθηματικά
Τεχνολογία
Φυσική
Χημεία
Ιατρική
Φιλοσοφία & Κοινωνικ. Επιστήμες
Αρχαιολογία
Γλωσσολογία
Οικονομικά
Φιλοσοφία
Ψυχολογία
Γεωγραφία
Ασία
Αφρική
Ευρώπη
Πόλεις
Χώρες
Θάλασσες
Ιστορία
Ελληνική Ιστορία
Αρχαία Ιστορία
Βυζάντιο
Ευρωπαϊκή Ιστορία
Πόλεμοι
Ρωμαϊκή Αυτοκρατορία
Σύγχρονη Ιστορία
 

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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Στα Στοιχεία του Ευκλείδη το Βιβλίο 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.

Σημειώσεις

  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. mod είναι η πράξη του υπολοίπου (στη C και στη Java συμβολίζεται με %)

Πηγή

Το άρθρο προέρχεται από το wiki.teilar.net