Φάση Σεναρίου
Πληροφορική (Γενικό Λύκειο)
Εισαγωγικές δραστηριότητες
Στην πρώτη φάση, επιχειρούμε μία εισαγωγή στην ιδέα της αναζήτησης και στη συνέχεια με μία σκαλωσιά μάθησης εστιάζουμε στην ανάπτυξη του αλγορίθμου σειριακής αναζήτησης σε πίνακα, ο οποίος εμφανίζει κατάλληλο μήνυμα σε περίπτωση που βρεθεί ή σε περίπτωση που δε βρεθεί το ζητούμενο στοιχείο.
Η προσέγγιση των παραπάνω, γίνεται με τη βοήθεια του επισυναπτόμενου φύλλου εργασίας. Στην πρώτη δραστηριότητα επιχειρούμε να εντοπίσουμε σε έναν πίνακα το πλήθος των θετικών, μηδενικών και αρνητικών στοιχείων και αναδεικνύουμε ότι σε μία γνωστή άσκηση που έχουμε δουλέψει χωρίς πίνακα στη δομή επανάληψης, πραγματοποιείται σειριακή αναζήτηση όταν χρησιμοποιούμε πίνακα.
Στη δεύτερη δραστηριότητα αναζητούμε σε έναν πίνακα που όλα τα στοιχεία του είναι διαφορετικά μεταξύ τους και δεν είναι ταξινομημένα, αν υπάρχει συγκεκριμένο στοιχείο που δίνεται από το χρήστη. Κατά την υλοποίηση της δεύτερης δραστηριότητας του φύλλου εργασίας, μπορεί:
α) να αναπτύχθηκε ο αλγόριθμος με τη χρήση της εντολής ΓΙΑ ή
β) να αναπτύχθηκε με τη χρήση της εντολής ΓΙΑ αλλά λανθασμένα όπως φαίνεται στο ακόλουθο πρόγραμμα.
ΠΡΟΓΡΑΜΜΑ ΛΑΝΘΑΣΜΕΝΗ_ΑΝΑΖΗΤΗΣΗ
!Προσοχή έχει λάθος ο κώδικας
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: i
ΠΡΑΓΜΑΤΙΚΕΣ: Π[5], Ζητούμενο
ΑΡΧΗ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
ΓΡΑΨΕ 'Δώστε το στοιχείο:', i
ΔΙΑΒΑΣΕ Π[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ Ζητούμενο
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
ΑΝ Π[i] = Ζητούμενο ΤΟΤΕ
ΓΡΑΨΕ 'Υπάρχει'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Δεν υπάρχει'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣΣτον παραπάνω αλγόριθμο εμφανίζεται το μήνυμα της ύπαρξης ή μη του ζητούμενου κατά τη λειτουργία της αναζήτησης. Με τον τρόπο αυτό, το μήνυμα Υπάρχει θα εμφανιστεί εφόσον στον πίνακα υπάρχει το στοιχείο και το μήνυμα Δεν υπάρχει θα εμφανιστεί όσες φορές δεν υπάρχει το στοιχείο.
Εφόσον υπερβούμε το παραπάνω εμπόδιο και είμαστε σε θέση να περιγράψουμε ότι μόνο μία φορά απαιτείται ο αλγόριθμος να εμφανίζει το σχετικό μήνυμα, επιχειρούμε να διαπραγματευτούμε τη χρήση της εντολής ΓΙΑ. Για το λόγο αυτό, είναι σημαντικό να παρακολουθήσουμε το διαδραστικό βίντεο που ακολουθεί.
Με την παρακολούθηση του βίντεο αναδεικνύουμε ότι με τον αλγόριθμο που αναπτύξαμε επιτυγχάνεται η αναζήτηση. Ταυτόχρονα όμως παρατηρούμε ότι γίνονται περιττά περάσματα στον πίνακα, μιας και αν βρεθεί ότι υπάρχει το ζητούμενο στοιχείο, η εντολή επανάληψης συνεχίζει να εκτελείται. Ωστόσο, αν το στοιχείο εντοπιστεί, θα ήταν προτιμότερο η εντολή επανάληψης να ολοκληρωθεί χωρίς να ελέγξει άλλα-επόμενα στοιχεία (εφόσον υπάρχουν). Ο έλεγχος είναι σημαντικό να σταματήσει, μιας και όλα τα επόμενα στοιχεία (εφόσον υπάρχουν) δεν θα είναι ίσα με το ζητούμενο, αφού αυτό αν υπάρχει στον πίνακα είναι μοναδικό. Ωστόσο, αν το ζητούμενο στοιχείο δεν υπάρχει στον πίνακα, τότε είναι απαραίτητο να ελεγχθούν όλα τα στοιχεία του πίνακα.
Συνεπώς, η αναζήτηση σε έναν πίνακα που έχει όλα τα στοιχεία του διαφορετικά και δεν είναι ταξινομημένος. δεν είναι απαραίτητο να ελέγξει όλο τον πίνακα, αν αυτό που ζητείται είναι αν υπάρχει κάποιο ζητούμενο στοιχείο. Αν το στοιχείο εντοπιστεί σε κάποια θέση μικρότερη του πλήθους των στοιχείων του πίνακα, τότε ο αλγόριθμος της αναζήτησης είναι προτιμότερο να ολοκληρωθεί, αλλιώς θα κάνει περιττά περάσματα.
Στόχος, λοιπόν, είναι η βελτίωση του αλγορίθμου, ώστε να μην γίνονται περιττά περάσματα.
Έτσι, η εντολή επανάληψης ΓΙΑ που χρησιμοποιήθηκε δεν αποτελεί την καταλληλότερη λύση, μιας και η αναζήτηση θα εκτελεστεί υποχρεωτικά για όλα τα στοιχεία του πίνακα. Μία άλλη εντολή επανάληψης είναι προτιμότερο να χρησιμοποιηθεί στη συγκεκριμένη περίπτωση. Η συνθήκη θα περιλαμβάνει τη συνθήκη της εντολής επανάληψης ΓΙΑ και θα περιλαμβάνει επίσης μία συνθήκη που θα ελέγχει αν βρέθηκε το ζητούμενο στοιχείο, ώστε να σταματήσει η επανάληψη. Για να σταματήσει η επανάληψη (η διαδικασία αναζήτησης) αν εντοπιστεί το ζητούμενο στοιχείο, μπορεί να χρησιμοποιηθεί μία λογική μεταβλητή που αρχικά θα έχει την ΨΕΥΔΗΣ (που σημαίνει ότι το ζητούμενο δεν έχει εντοπιστεί ακόμα). Σε περίπτωση που βρεθεί το ζητούμενο στοιχείο, η λογική μεταβλητή λαμβάνει την τιμή ΑΛΗΘΗΣ. Στη συνέχεια ελέγχεται η σύνθετη συνθήκη της εντολής ΟΣΟ, η οποία είναι ΨΕΥΔΗΣ, και ο βρόχος τερματίζεται. Σε περίπτωση που δε βρεθεί στοιχείο του πίνακα ίσο με την τιμή του ζητούμενου στοιχείου, η λογική μεταβλητή θα παραμείνει ΨΕΥΔΗΣ μέχρι τη λήξη της εκτέλεσης του αλγορίθμου και η επανάληψη θα γίνει ΨΕΥΔΗΣ επειδή ξεπεράστηκαν τα όρια του πίνακα.
Μετά από αυτή τη συζήτηση καλούμαστε στην 3η δραστηριότητα, να βελτιώσουμε τον αλγόριθμο που αναπτύξαμε στην 2η δραστηριότητα.
