Λύσεις — Κεφάλαιο 6 · Κλασικοί Αλγόριθμοι Ι — Python (σελ. 120) – ΑΡΧΕΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΥΠΟΛΟΓΙΣΤΩΝ

Λύσεις — Κεφάλαιο 6 · Κλασικοί Αλγόριθμοι Ι — Python (σελ. 120)

Απαντήσεις στις Ερωτήσεις (γνωστοί αλγόριθμοι, ιδέα Ευκλείδη για ΜΚΔ, τρόπος σειριακής αναζήτησης, λογική ταξινόμησης με επιλογή). Και οι 3 αλγόριθμοι επαληθεύτηκαν με κώδικα.

Ερ.1 — Τρεις γνωστοί αλγόριθμοι

Ερώτηση: Κατονομάστε τρεις γνωστούς αλγόριθμους.

Απάντηση:

• Αλγόριθμος του Ευκλείδη (Μέγιστος Κοινός Διαιρέτης).
• Σειριακή (γραμμική) αναζήτηση.
• Ταξινόμηση με επιλογή (selection sort).
• (Άλλοι: δυαδική αναζήτηση, ταξινόμηση φυσαλίδας, εύρεση min/max/αθροίσματος.)

Σύνοψη: (ενδεικτική) Π.χ. αλγόριθμος Ευκλείδη (ΜΚΔ), σειριακή αναζήτηση, ταξινόμηση με επιλογή.

Κριτήρια αξιολόγησης:

• ΕΝΔΕΙΚΤΙΚΗ: δεκτοί κι άλλοι υπαρκτοί αλγόριθμοι. Κριτήριο: 3 υπαρκτοί/κλασικοί.

Ερ.2 — Ιδέα του αλγορίθμου του Ευκλείδη

Ερώτηση: Σε ποια ιδέα βασίζεται ο υπολογισμός του ΜΚΔ στον αλγόριθμο του Ευκλείδη;

Απάντηση:

• Στην ιδέα ότι ο ΜΚΔ δύο αριθμών δεν αλλάζει αν αντικαταστήσουμε τον μεγαλύτερο με το υπόλοιπο της διαίρεσής του με τον μικρότερο: ΜΚΔ(a,b)=ΜΚΔ(b, a mod b).
• Επαναλαμβάνουμε μέχρι το υπόλοιπο να γίνει 0· ο ΜΚΔ είναι ο τελευταίος μη μηδενικός αριθμός.

Σύνοψη: (ενδεικτική) ΜΚΔ(a,b)=ΜΚΔ(b, a mod b): αντικαθιστούμε τον μεγαλύτερο με το υπόλοιπο, μέχρι υπόλοιπο 0.

Κριτήρια αξιολόγησης:

• Κριτήριο: αντικατάσταση με το υπόλοιπο + τερματισμός στο υπόλοιπο 0. Π.χ. 48,18→12→6→0 → ΜΚΔ 6 (επαληθευμένο).

Ερ.3 — Τρόπος σειριακής αναζήτησης

Ερώτηση: Αν χρησιμοποιήσουμε τη σειριακή αναζήτηση, με ποιο τρόπο θα γίνει η αναζήτηση;

Απάντηση:

• Συγκρίνουμε το ζητούμενο στοιχείο διαδοχικά με κάθε στοιχείο της συλλογής, από την αρχή.
• Σταματάμε μόλις το βρούμε (επιστρέφουμε τη θέση) ή όταν τελειώσει η συλλογή (δεν υπάρχει).
• Δουλεύει και σε αταξινόμητη συλλογή.

Σύνοψη: (ενδεικτική) Διαδοχική σύγκριση με κάθε στοιχείο από την αρχή, μέχρι να βρεθεί ή να τελειώσει η συλλογή.

Κριτήρια αξιολόγησης:

• Κριτήριο: «διαδοχικά ένα-ένα από την αρχή» + τερματισμός στην εύρεση/τέλος.

Ερ.4 — Λογική ταξινόμησης με επιλογή

Ερώτηση: Σε ποια λογική σειρά βημάτων στηρίζεται ο αλγόριθμος ταξινόμησης με επιλογή;

Απάντηση:

• Σε κάθε πέρασμα βρίσκουμε το ελάχιστο από τα αταξινόμητα στοιχεία.
• Το τοποθετούμε στη σωστή θέση (ανταλλαγή με το πρώτο αταξινόμητο).
• Επαναλαμβάνουμε για τα υπόλοιπα, μέχρι να ταξινομηθούν όλα.

Σύνοψη: (ενδεικτική) Βρίσκουμε επαναληπτικά το ελάχιστο των αταξινόμητων και το βάζουμε στη σειρά του (με ανταλλαγή), ώσπου να ταξινομηθούν όλα.

Κριτήρια αξιολόγησης:

• Κριτήριο: εύρεση ελαχίστου + τοποθέτηση/ανταλλαγή + επανάληψη. Π.χ. [5,3,8,1,9]→[1,3,5,8,9] (επαληθευμένο).