Αλγόριθμος
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 συμβολίζεται με %)
Ανάλυση Ορθότητας
Έστω, x και y οι αριθμοί των οποίων μας ενδιαφέρει η εύρεση του ΜΚΔ, με . Ισχύει ότι x = π * y + υ, όπου π είναι το πηλίκο και υ το υπόλοιπο της Ευκλείδιας διαίρεσης του x με το y. Μπορούμε εύκολα να παρατηρήσουμε ότι κάθε κοινός διαιρέτης του x και του y θα είναι και κοινός διαιρέτης του y και του υ. Για να το δούμε αυτό, παίρνουμε την x = π * y + υ και την γράφουμε ως υ = x − π * y και έστω δ ένας κοινός διαιρέτης των x και y. Επειδή ακριβώς, ο δ διαιρεί ακριβώς τόσο τον x όσο και τον y, ισχύει x = k * δ και y = l * δ, όπου τα k, l είναι ακέραιοι. Άρα, υ = x − π * y = k * δ − π * l * δ = (k − π * l) * δ, όμως και το π είναι ακέραιος, αφού εκφράζει πηλίκο και επομένως, η ποσότητα (k − π * l) είναι ακέραιος αριθμός και μάλιστα μεγαλύτερος ή ίσος του μηδενός. Άρα, το υ είναι και αυτό ίσο με κάποιο ακέραιο πολλαπλάσιο του δ, και συνεπώς το δ είναι διαιρέτης του υ. Ακόμα, με τον ίδιο περίπου τρόπο μπορούμε να δείξουμε ότι κάθε κοινός διαιρέτης του y και του υ θα είναι και κοινός διαιρέτης των x και y (των οποίων η διαίρεση έδωσε το υ). Παρατηρούμε, επομένως, ότι τα ζεύγη (x,y) και (y,υ) έχουν ακριβώς τους ίδιους κοινούς διαιρέτες. Άρα, μπορούμε αναδρομικά να αναζητούμε τους κοινούς διαιρέτες σε μικρότερους αριθμούς και είμαστε βέβαιοι ότι η διαδικασία θα ολοκληρωθεί μετά από πεπερασμένο αριθμό βημάτων, αφού το υ είναι πάντοτε μικρότερο από το y και η αρχική είσοδος είναι πάντοτε πεπερασμένη. Το προτελευταίο αναδρομικό βήμα του αλγορίθμου είναι πάντοτε αυτό κατά το οποίο η διαίρεση του x με το y δίνει υπόλοιπο μηδέν. Άρα, στο επόμενο και τελευταίο αναδρομικό βήμα θα επιστραφεί το y ορθά ως ο μέγιστος κοινός διαιρέτης των αρχικών x και y, αφού είναι των τρέχοντων και ως εκ τούτου όλων των προηγούμενων ζευγών που έχουν παρουσιαστεί στην αναδρομή (με βάση το προηγούμενό μας επιχείρημα).
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου