Κεφάλαιο 04.3 – Σελίδα 80 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 4 (σελ. 86)

Να περιγραφεί με βήματα η μέθοδος της προσέγγισης Διαίρει και Βασίλευε για τη σχεδίαση αλγορίθμων.

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση περιγραφής — τα 4 βήματα της μεθόδου δίνονται ρητά στο §4.3.

Λύση:

Ανατρέχουμε στα 4 βήματα του §4.3 και τα αποδίδουμε με τη σειρά τους.

Απάντηση: Η μέθοδος Διαίρει και Βασίλευε περιλαμβάνει 4 βήματα: (1) δίνεται προς επίλυση ένα στιγμιότυπο του προβλήματος, (2) το στιγμιότυπο υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος, (3) κάθε υπο-στιγμιότυπο λύνεται ανεξάρτητα, (4) οι επιμέρους λύσεις συνδυάζονται ώστε να προκύψει η συνολική λύση.

Πρόσεξε:

• Να τηρηθεί η σειρά των 4 βημάτων — η υποδιαίρεση προηγείται της ανεξάρτητης επίλυσης, που με τη σειρά της προηγείται της σύνθεσης.

Ερώτηση 6 (σελ. 86)

Να περιγραφεί η μέθοδος της δυαδικής αναζήτησης και να δοθεί ένα παράδειγμα επίλυσης προβλήματος με τη μέθοδο αυτή.

Σκέψη / Μεθοδολογία: Ερώτηση περιγραφής + παράδειγμα — το παράδειγμα του τηλεφωνικού καταλόγου δίνεται ρητά στο §4.3.

Λύση:

1. Περιγράφουμε τη λογική της δυαδικής αναζήτησης: σε κάθε βήμα συγκρίνουμε το ζητούμενο στοιχείο με το μεσαίο στοιχείο του (ταξινομημένου) πίνακα και «πετάμε» το μισό που σίγουρα δεν το περιέχει.
2. Παραθέτουμε το παράδειγμα του τηλεφωνικού καταλόγου του §4.3.

Απάντηση: Η δυαδική αναζήτηση εφαρμόζεται σε ταξινομημένο πίνακα: σε κάθε βήμα συγκρίνουμε το ζητούμενο στοιχείο με το μεσαίο στοιχείο του πίνακα· αν δεν ταιριάζει, «κρατάμε» μόνο το μισό του πίνακα (αριστερό ή δεξιό) όπου θα μπορούσε να βρίσκεται το στοιχείο, και επαναλαμβάνουμε. Παράδειγμα: σε έναν αλφαβητικά ταξινομημένο τηλεφωνικό κατάλογο names[1..n]/phones[1..n], για να βρούμε το τηλέφωνο ενός ονόματος συγκρίνουμε το όνομα με το μεσαίο στοιχείο του πίνακα names — αν είναι ίσο, βρέθηκε· αν είναι αλφαβητικά μικρότερο, συνεχίζουμε την αναζήτηση στο πρώτο μισό· αλλιώς στο δεύτερο μισό, μέχρι να βρεθεί.

Πρόσεξε:

• Η δυαδική αναζήτηση προϋποθέτει ταξινομημένο πίνακα — να αναφερθεί ρητά.
• Το παράδειγμα πρέπει να δείχνει τη σύγκριση με το μεσαίο στοιχείο και τη «διχοτόμηση» του χώρου αναζήτησης, όχι απλώς να αναφέρει το όνομα της μεθόδου.