Μάθημα : Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ [Β' τάξη]
Κωδικός : EL607157
Περιγραφή
Ιστορικά, ένας από τους πρώτους αλγορίθμους, είναι ο αλγόριθμος για την εύρεση του Μέγιστου Κοινού Διαιρέτη (ΜΚΔ) δύο ακεραίων αριθμών x και y. Ο αλγόριθμος αυτός μπορεί να εκφραστεί και με κωδικοποιημένο τρόπο ως εξής:
1. Αλγόριθμος Ευκλείδης
2. Διάβασε x, y
3. z ← y
4. Όσο z ≠ 0 επανάλαβε
5. z ← x mod y
6. x ← y
7. y ← z
8. Τέλος_επανάληψης
9. Εμφάνισε x
10. Τέλος Ευκλείδης
Για να υπολογιστεί ο ΜΚΔ των αριθμών 27 και 78 με τη χρήση του ευκλείδιου αλγόριθμου, μπορεί να πραγματοποιηθεί εικονική εκτέλεσή του στο χαρτί. Σε κάθε επανάληψη υπολογίζονται οι τιμές των x, y και z, οι οποίες παρουσιάζονται στον παρακάτω πίνακα. Με την ολοκλήρωση προκύπτει ότι ο ΜΚΔ των αριθμών 27 και 78 είναι ο αριθμός 3.
| Αρ. εντ. | x | y | z | z ≠ 0 | Έξοδος |
|---|---|---|---|---|---|
| 2 | 27 | 78 | |||
| 3 | 78 | ||||
| 4 | Αληθής | ||||
| 5 | 27 | ||||
| 6 | 78 | ||||
| 7 | 27 | ||||
| 4 | Αληθής | ||||
| 5 | 24 | ||||
| 6 | 27 | ||||
| 7 | 24 | ||||
| 4 | Αληθής | ||||
| 5 | 3 | ||||
| 6 | 24 | ||||
| 7 | 3 | ||||
| 4 | Αληθής | ||||
| 5 | 0 | ||||
| 6 | 3 | ||||
| 7 | 0 | ||||
| 4 | Ψευδής | ||||
| 9 | 3 |