Ευκλείδιο αλγόριθμος εύρεσης ΜΚΔ

[polysot]

Για την εύρεση του Μέγιστου κοινού διαιρέτη δύο ακεραίων αριθμών ο Ευκλείδειος αλγόριθμος λειτουργεί ως εξής :

πχ ΜΚΔ(1547,560)

1547 : 560 -> 1547 = 2 Χ 560 + 427
560 : 427 -> 560 = 1 Χ 427 + 133
427 : 133 -> 427 = 3 Χ 133 + 28
133 : 28 -> 133 = 4 Χ 28 +21
28 : 21 -> 28 = 1 Χ 21 + 7
Το 7 διαιρεί το 21, ο αλγόριθμος τερματίζει : ΜΚΔ(1547,560) = 7

Γνωρίζει κάποιος αν μπορεί να προσαρμοστεί ο αλγόριθμος αυτός για την εύρεση ΜΚΔ περισσοτέρων αριθμών;

[nsmavrogiannis]

Ξεκινάμε με τον πιο μικρό αριθμό και εναποθέτουμε
- κάτω από αυτόν τον εαυτό του
-κάτω από τους άλλους το υπόλοιπο της διαίρεσης με αυτόν.
Συνεχίζουμε.
'Οταν βρούμε μηδενικά στις άλλες θέσεις έχουμε τερματίσει.
Παράδειγμα

Ο ΜΚΔ είναι ο 3
Μαυρογιάννης

[polysot]

Α πολύ ωραία Νίκο
Εγώ είχα στο μυαλό μου μία μέθοδο παρόμοια με αυτή του ΕΚΠ, με χρήση πρώτων διαιρετών, η οποία έχει και το μειονέκτημα βέβαια ότι δεν μπορείς να τους βρεις εύκολα, ιδιαίτερα αν είναι μεγάλοι. Συγκεκριμένα :

ΕΚΠ(60,120,84)

60 120 84 | 2 : Βάζω τον μικρότερο πρώτο, ο οποίος διαιρεί τουλάχιστον έναν από τους αριθμούς
30 60 42 | 2 : στην επόμενη γραμμή έβαλα τα πηλίκα όσων διαιρούνται και τους ίδιους όταν δεν διαιρούνται και συνεχίζω ομοίως:
15 30 21| 2
15 15 21 | 3
5 5 7 | 5
1 1 7 | 7 Σταματώ όταν όλα τα πηλίκα είναι 1 και το ΕΚΠ είναι το γινόμενο των πρώτων
1 1 1 ΕΚΠ(60,120,84) = 2. 2. 2. 3. 5. 7 = 840

ΜΚΔ(60,120,64)

60 120 84 | 2 Βάζω το μικρότερο πρώτο, ο οποίος διαιρεί ΟΛΟΥΣ τους αριθμούς
30 60 42 | 2 στην επόμενη γραμμή βάζω τα πηλίκα των διαιρέσεων
15 30 21 | 3 και ο αλγόριθμος τελειώνει όταν υπάρξουν δύο σχετικά πρώτοι μεταξύ τους αριθμοί.
5 10 7 ΜΚΔ(60,120,84) = 2 . 2 . 3 = 12

Αλλά όπως είπα και οι δύο διαδικασίες έχουν το μειονέκτημα ότι σε αριθμούς με παράγοντες μεγάλους πρώτους "δυσκολεύουν".
Έχουν βέβαια και το πλεονέκτημα ότι "μοιάζουν" ως μέθοδοι και ενδεχομένως να είναι ευκολότερα "απομνημονεύσιμοι" στη χρήση τους από παιδιά, αν τους αναφέρει κανείς ότι: για το ΕΚΠ θέλουμε να διαιρεί τουλάχιστον έναν αριθμό, ενώ για τον ΜΚΔ θέλουμε να τους διαιρεί όλους...

[gerassimosm]

Κάνεις λάθος. Η εύρεση Μ.Κ.Δ. με Ε.Κ.Π. γίνεται μόνο όταν οι αριθμοί είναι πρώτοι δηλαδή διαιρούνται μόνο με το 1 και τον εαυτό τους.

:9sta9:

[Mihalis_Lambrou]

Κάνεις λάθος. Η εύρεση Μ.Κ.Δ. με Ε.Κ.Π. γίνεται μόνο όταν οι αριθμοί είναι πρώτοι δηλαδή διαιρούνται μόνο με το 1 και τον εαυτό τους.

Καλώς στο φόρουμ.

Στο παραπάνω δεν έχεις δίκιο γιατί ισχύει με το γινόμενο των Μ.Κ.Δ. και Ε.Κ.Π.. Οπότε αν ξέρεις το ένα, βρίσκεις το άλλο (ανεξάρτητα από το αν είναι ή δεν είναι πρώτοι μεταξύ τους οι .)