ΚΕΠΛΗΝΕΤ Ηλείας

Πανελλήνιο Σχολικό Δίκτυο

Το Στέκι των Πληροφορικών

SaferInternet.gr

SafeLine.gr

 

Εφαρμογή Χαρτογράφησης Μονάδων Εκπαίδευσης Ν. Ηλείας

Ενημερωτικό Δελτίο «ΤΠΕ στην Εκπαίδευση» - ΚΕ.ΠΛΗ.ΝΕ.Τ. Ηλείας

25ος Πανελλήνιος Διαγωνισμός Πληροφορικής

2ος Πανελλήνιος Διαγωνισμός Εκπαιδευτικής Ρομποτικής WRO (World Robot Olympiad)

Ημέρα Ασφαλούς Διαδικτύου 2013

Ανακύκλωση Ηλεκτρικών και Ηλεκτρονικών Συσκευών

 

Ιστοσελίδες μονάδων

Αναφορά προβλημάτων

Διαδικτυακά εργαλεία τεχνικού ελέγχου

Σημειώσεις και σκέψεις για τον αλγόριθμο σειριακής αναζήτησης

του Νίκου Αδαμόπουλου, εκπαιδευτικού ΠΕ19
Υπεύθυνου ΚΕ.ΠΛΗ.ΝΕ.Τ. ΔΔΕ Ηλείας

Μελετώντας τα θέματα των πανελλαδικών απολυτήριων εξετάσεων των ημερήσιων και εσπερινών Γενικών Λυκείων για το μάθημα «Ανάπτυξη Εφαρμογών Σε Προγραμματιστικό Περιβάλλον» της Τεχνολογικής Κατεύθυνσης, διαπιστώνουμε ότι εμφανίζεται αρκετά συχνά το ζητούμενο να πρέπει να αναζητηθεί μια τιμή σε ένα μονοδιάστατο πίνακα, και αν βρεθεί τότε να γίνεται κάτι με τα δεδομένα που αντιστοιχούν στην τιμή που αναζητήθηκε, αλλιώς να γίνεται κάτι άλλο, π.χ. να εμφανίζεται κατάλληλο μήνυμα (βλ. Θέμα Α, Β, Γ και Δ στο Παράρτημα).

Οι μαθητές αρκετά συχνά δίνουν λύσεις που μοιάζουν με το τμήμα αλγορίθμου που ακολουθεί:

Για i από 1 μέχρι n 
  Αν table[i]=key τότε
    Εμφάνισε "Βρέθηκε στη θέση:", i
    ...
  αλλιώς
    Εμφάνισε "Δεν βρέθηκε" 
  Τέλος_αν
Τέλος_επανάληψης

Οι μαθητές θα πρέπει να κατανοήσουν τα εξής προβλήματα που προκύπτουν από μία τέτοια λύση:

  1. Για κάθε ένα στοιχείο του πίνακα θα γίνει κάτι (π.χ. θα εμφανιστεί κάποιο μήνυμα), είτε αντιστοιχεί σε αυτό που αναζητούμε είτε όχι. Αυτό γίνεται επειδή οι σχετικές εντολές εκτελούνται μέσα στον επαναληπτικό βρόχο, ενώ θα έπρεπε να εκτελούνται μετά.
  2. Αν σε κάποια θέση βρεθεί η τιμή για την οποία γίνεται η αναζήτηση τότε δεν πρέπει να συνεχιστεί ο έλεγχος μέχρι το τέλος του πίνακα (εκτός κι αν έπρεπε για να βρεθούν και άλλες εμφανίσεις της ίδιας τιμής). Κάτι τέτοιο θεωρείται πλεονασμός και, επιπλέον, είναι δυνατό να αλλοιωθεί το αποτέλεσμα της αναζήτησης αν δεν γίνει κατάλληλη χρήση των εντολών. Επομένως, δεν θεωρείται κατάλληλη η χρήση της εντολής Για στη δημιουργία του βρόχου.

Η προτεινόμενη λύση είναι να γίνεται εφαρμογή κάποιου γνωστού αλγορίθμου αναζήτησης.

Αλγόριθμος σειριακής αναζήτησης

Στο σχολικό βιβλίο «Ανάπτυξη Εφαρμογών Σε Προγραμματιστικό Περιβάλλον» της Γ’ τάξης της Τεχνολογικής Κατεύθυνσης περιγράφεται ο αλγόριθμος της σειριακής αναζήτησης (sequential search).

Ο αλγόριθμος αναζητά την τιμή key στο μονοδιάστατο μη ταξινομημένο πίνακα table μεγέθους n. Για λόγους πληρότητας αντιγράφουμε τον αλγόριθμο όπως καταγράφεται στο σχολικό βιβλίο:

Αλγόριθμος Sequential_Search
Δεδομένα // n, table, key //
done ¬ ψευδής 
position ¬ 0
i ¬ 1
Όσο (done=ψευδής) και (i<=n) επανάλαβε
  Αν table[i]=key τότε
    done ¬ αληθής 
    position ¬ i
  αλλιώς
    i ¬ i + 1
  Τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα // done, position //
Τέλος Sequential_Search

Οι μαθητές θα πρέπει να κατανοήσουν τον τρόπο λειτουργίας αυτού του αλγορίθμου και να είναι σε θέση να τον εντάσσουν μέσα σε άλλους μεγαλύτερους αλγόριθμους στα πλαίσια λύσης ασκήσεων. Έτσι, θα πρέπει να είναι σε θέση να τροποποιούν και να προσαρμόζουν κατάλληλα τις μεταβλητές n, table και key.

Συνήθως, πριν από τον αλγόριθμο της αναζήτησης θα γίνεται είσοδος της τιμής που θα αναζητηθεί:

Διάβασε key

και μετά από την αναζήτηση θα ακολουθούν οι εντολές που θα εκτελούνται ανάλογα με το αποτέλεσμα της αναζήτησης:

Αν done=αληθής τότε
  Εμφάνισε "Βρέθηκε στη θέση:", position
  ...
αλλιώς
  Εμφάνισε "Δεν βρέθηκε"
Τέλος_αν
Παρατηρήσεις

Στον παραπάνω αλγόριθμο μπορούμε να κάνουμε τις εξής παρατηρήσεις:

  1. Η αρχικοποίηση της μεταβλητής position με την τιμή 0 δεν έχει καμία χρησιμότητα, και θα μπορούσε να παραλειφθεί, αφού την απάντηση για το αν βρέθηκε ή όχι η τιμή key μέσα στον πίνακα table τη δίνει η μεταβλητή done. Αν όντως βρέθηκε, τότε το position θα δείχνει σωστά τη θέση της στον πίνακα table, αλλιώς θα είναι αδιάφορο.
  2. Η λογική μεταβλητή done δεν χρησιμοποιείται με την πραγματική έννοια των λογικών μεταβλητών, χωρίς όμως αυτό να σημαίνει ότι υπάρχει συντακτικό ή λογικό λάθος. Ουσιαστικά θα μπορούσε να χρησιμοποιηθεί με ισοδύναμο αποτέλεσμα μία αλφαριθμητική μεταβλητή που να παίρνει τις τιμές "ψευδής" και "αληθής" αντίστοιχα, ή ακόμα και μία αριθμητική μεταβλητή που να παίρνει τις τιμές 0 και 1, ή -1 και 1, κ.λπ., αρκεί στην εντολή Όσο να γίνεται ο κατάλληλος έλεγχος. Ή θα μπορούσε ακόμα και να παραλειφθεί τελείως και ο έλεγχος να γίνεται αποκλειστικά με τη βοήθεια της μεταβλητής position. Σε αυτήν την περίπτωση η εντολή Όσο θα μπορούσε να διατυπωθεί:
Όσο (position=0) και (i<=n) επανάλαβε

Να τονίσουμε ότι είναι ο μοναδικός αλγόριθμος στην εξεταστέα ύλη του βιβλίου που χρησιμοποιεί λογική μεταβλητή και έτσι χάνεται η μοναδική ευκαιρία για να φανεί η αξία των μεταβλητών αυτού του τύπου.

Για να χρησιμοποιηθεί η done ως πραγματικά λογική μεταβλητή, η εντολή Όσο θα μπορούσε να διατυπωθεί:

Όσο (όχι done) και (i<=n) επανάλαβε

Έτσι η εντολή είναι πιο κοντά στη φυσική γλώσσα: «Όσο ακόμα δεν βρέθηκε η τιμή, και δεν εξαντλήσαμε τα στοιχεία του πίνακα, συνεχίζουμε να ελέγχουμε». Ομοίως, στη συνέχεια, ο έλεγχος για το αν βρέθηκε ή όχι η τιμή key θα μπορούσε να διατυπωθεί:

Αν done τότε
  ...
αλλιώς
  ...
Τέλος_αν

Ωστόσο, με δεδομένη την προσέγγιση του σχολικού βιβλίου, ίσως τελικά δεν είναι σκόπιμο να ενθαρρύνουμε τους μαθητές στην παραπάνω χρήση των λογικών μεταβλητών. Για τον ίδιο λόγο παρακάτω εφαρμόζεται η μέθοδος του σχολικού βιβλίου.

Σειριακή αναζήτηση σε ταξινομημένο πίνακα

Αν ο πίνακας table είναι ταξινομημένος τότε ο αλγόριθμος σειριακής αναζήτησης μπορεί να προσαρμοστεί εύκολα, έτσι ώστε αν ελέγχοντας τα στοιχεία του πίνακα φτάσει σε στοιχείο που ξεπερνά την τιμή που αναζητά τότε να μη συνεχίζει ελέγχοντας και τα υπόλοιπα.

Για πίνακα με αύξουσα ταξινόμηση μπορεί να προστεθεί ο εξής έλεγχος στο εσωτερικό του βρόχου:

    ...
  αλλιώς_αν table[i]>key τότε 
    i ¬ n+1
  ...

ή για φθίνουσα ταξινόμηση:

    ...
  αλλιώς_αν table[i]<key τότε 
    i ¬ n+1
  ...

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

Σειριακή αναζήτηση σε δισδιάστατο πίνακα

Αν ο πίνακας table είναι δισδιάστατος τότε ο αλγόριθμος της σειριακής αναζήτησης μπορεί να χρησιμοποιηθεί, με λίγες αλλαγές, ώστε η αναζήτηση να εκτελεστεί σε μία μόνο γραμμή ή στήλη του πίνακα. Έτσι, αν η αναζήτηση πρέπει να γίνει στην 1η στήλη του πίνακα, o αλγόριθμος θα έχει ως εξής:

Διάβασε Key

done ¬ ψευδής 
position ¬ 0
i ¬ 1
Όσο (done=ψευδής) και (i<=n) επανάλαβε
  Αν table[i,1]=key τότε
    done ¬ αληθής 
    position ¬ i
  αλλιώς
    i ¬ i + 1
  Τέλος_αν
Τέλος_επανάληψης

Αν done=αληθής τότε
  Εμφάνισε "Βρέθηκε στη θέση:", position
  ...
αλλιώς
  Εμφάνισε "Δεν βρέθηκε"
Τέλος_αν

Αν η αναζήτηση πρέπει να εκτελεστεί σε ολόκληρο τον πίνακα, και όχι σε μία μόνο γραμμή ή στήλη αυτού, τότε η πολυπλοκότητα του απαιτούμενου αλγορίθμου μεγαλώνει πολύ. Επιπλέον, θα πρέπει να καταχωρείται ο αριθμός της γραμμής (positionΓ) αλλά και της στήλης (positionΣ) όπου βρέθηκε η τιμή key.

Διερεύνηση υπόθεσης σε πίνακες

Αν πρέπει να γίνει διερεύνηση για το αν ικανοποιείται ή όχι κάποια συνθήκη από όλα τα στοιχεία ενός πίνακα (π.χ. αν είναι θετικοί αριθμοί, ή αν είναι άρτιοι αριθμοί, ή αν είναι ίσα με τα αντίστοιχα στοιχεία άλλου πίνακα, κ.λπ.), τότε πάλι μπορεί να χρησιμοποιηθεί κάποια παραλλαγή του αλγορίθμου σειριακής αναζήτησης.

Και σε αυτήν την περίπτωση ο έλεγχος των στοιχείων του πίνακα θα πρέπει να σταματήσει αν βρεθεί ένα στοιχείο που δεν ικανοποιεί τη συνθήκη. Επίσης, το πιο πιθανό είναι να μη χρειάζεται η μεταβλητή position. Ο αλγόριθμος θα μπορούσε να είναι ο εξής:

done ¬ αληθής
i ¬ 1
Όσο (done=αληθής) και (i<=n) επανάλαβε
  Αν όχι <συνθήκη> τότε
    done ¬ ψευδής 
  αλλιώς
    i ¬ i + 1
  Τέλος_αν
Τέλος_επανάληψης

Αν done=αληθής τότε
  Εμφάνισε "Η υπόθεση ισχύει"
αλλιώς
  Εμφάνισε "Η υπόθεση δεν ισχύει"
Τέλος_αν

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

Αν Β[i]≠(Α[i]+Α[i+1])/2 τότε

Ειδική περίπτωση αποτελεί η διερεύνηση για το αν ικανοποιείται ή όχι κάποια συνθήκη ανάμεσα στα στοιχεία του ίδιου πίνακα (π.χ. αν είναι ταξινομημένα με αύξουσα σειρά). Τα στοιχεία θα πρέπει να ελεγχθούν μεταξύ τους ανά δύο, οπότε απαιτούνται n-1 έλεγχοι:

done ¬ αληθής
i ¬ 1
Όσο (done=αληθής) και (i<=n-1) επανάλαβε
  Αν table[i]>table[i+1] τότε
    ...
Επίλογος

Κλείνοντας, παραθέτουμε θέματα πανελλαδικών εξετάσεων των τελευταίων ετών στις λύσεις των οποίων θα μπορούσαν να εφαρμοστούν τα παραπάνω.


ΠΑΡΑΡΤΗΜΑ – Θέματα Πανελλαδικών Εξετάσεων
Θέμα Α (2004, Επαν. Εξετ. Εσπερ. Ε.Λ., Θέμα 4)

Σ’ ένα διαγωνισµό συµµετέχουν 5000 διαγωνιζόµενοι και εξετάζονται σε δύο µαθήµατα. Να γράψετε αλγόριθµο που:

1. να διαβάζει και να καταχωρίζει σε κατάλληλους πίνακες για κάθε διαγωνιζόµενο τον αριθµό µητρώου, το ονοµατεπώνυµο και τους βαθµούς που πήρε στα δύο µαθήµατα. Οι αριθµοί µητρώου θεωρούνται µοναδικοί. Η βαθµολογική κλίµακα είναι από 0 έως και 100.

2. να εµφανίζει κατάσταση επιτυχόντων µε την εξής µορφή:

Αριθ. Μητρώου Ονοµατεπώνυµο Μέσος Όρος

Επιτυχών θεωρείται ότι είναι αυτός που έχει µέσο όρο βαθµολογίας µεγαλύτερο ή ίσο του 60.

3. να διαβάζει έναν αριθµό µητρώου και

α) σε περίπτωση που ο αριθµός µητρώου είναι καταχωρισµένος στον πίνακα, να εµφανίζεται ο αριθµός µητρώου, το ονοµατεπώνυµο, ο µέσος όρος βαθµολογίας και η ένδειξη «ΕΠΙΤΥΧΩΝ» ή «ΑΠΟΤΥΧΩΝ», ανάλογα µε τον µέσο όρο.

β) σε περίπτωση που ο αριθµός µητρώου δεν είναι καταχωρισµένος στον πίνακα, να εµφανίζεται το µήνυµα «Ο αριθµός µητρώου δεν αντιστοιχεί σε διαγωνιζόµενο».

Σηµείωση: Δεν απαιτείται έλεγχος εγκυρότητας καταχώρισης δεδοµένων.

Θέμα Β (2005, Εξετ. Εσπερ. Ε.Λ., Θέμα 3)

Για την εύρεση πόρων προκειμένου οι μαθητές της ∆΄ τάξης Εσπερινού Λυκείου να συμμετάσχουν σε εκδρομή οργανώνεται λαχειοφόρος αγορά. Οι μαθητές του Λυκείου διαθέτουν λαχνούς στα σχολεία της περιοχής τους. ∆ιακόσιοι μαθητές από δεκαπέντε διαφορετικά σχολεία αγόρασαν ο καθένας από έναν μόνο λαχνό. Μετά από κλήρωση ένας μαθητής κερδίζει τον πρώτο λαχνό. Να γίνει τμήμα αλγορίθμου που:

α) για κάθε μαθητή που αγόρασε λαχνό να εισάγει σε μονοδιάστατο πίνακα Α 200 θέσεων το επώνυμό του και στην αντίστοιχη θέση μονοδιάστατου πίνακα Β 200 θέσεων το όνομα του σχολείου του,

β) να εισάγει σε μονοδιάστατο πίνακα Σ 15 θέσεων τα ονόματα όλων των σχολείων της περιοχής και στις αντίστοιχες θέσεις μονοδιάστατου πίνακα M 15 θέσεων τις ηλεκτρονικές διευθύνσεις των σχολείων,

γ) να διαβάζει το επώνυμο του μαθητή, που κέρδισε τον πρώτο λαχνό,

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

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

στ) να εμφανίζει το επώνυμο του τυχερού μαθητή, το όνομα του σχολείου του και τη διεύθυνση του ηλεκτρονικού ταχυδρομείου του σχολείου του.

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

Θέμα Γ (2006, Εξετ. Ημερ. Ε.Λ., Θέμα 4)

Για την παρακολούθηση των θερμοκρασιών της επικράτειας κατά το μήνα Μάιο καταγράφεται κάθε μέρα η θερμοκρασία στις 12:00 το μεσημέρι για 20 πόλεις. Να σχεδιάσετε αλγόριθμο που:

α) θα διαβάζει τα ονόματα των 20 πόλεων και τις αντίστοιχες θερμοκρασίες για κάθε μία από τις ημέρες του μήνα και θα καταχωρεί τα στοιχεία σε πίνακες.

β) θα διαβάζει το όνομα μίας πόλης και θα εμφανίζει τη μέγιστη θερμοκρασία της στη διάρκεια του μήνα. Αν δεν υπάρχει η πόλη στον πίνακα, θα εμφανίζει κατάλληλα διαμορφωμένο μήνυμα.

γ) θα εμφανίζει το πλήθος των ημερών που η μέση θερμοκρασία των 20 πόλεων ξεπέρασε τους 20° C, αλλά όχι τους 30° C.

Θέμα Δ (2006, Επαν. Εξετ. Ημερ. Ε.Λ., Θέμα 4)

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

α) καταχωρίζει σε πίνακα τις ονομασίες των τριών αγωνισμάτων, όπως αυτές δίνονται παραπάνω.

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

γ) διαβάζει το όνομα και το επίθετο ενός αθλητή και θα εμφανίζει το όνομα του αλόγου με το οποίο αγωνίστηκε και τη συνολική του βαθμολογία στα τρία αγωνίσματα. Αν δεν υπάρχει ο αθλητής, θα εμφανίζει κατάλληλα διαμορφωμένο μήνυμα.

δ) εμφανίζει την ονομασία του αγωνίσματος (ή των αγωνισμάτων) με το μεγαλύτερο «άνοιγμα βαθμολογίας». Ως «άνοιγμα βαθμολογίας» να θεωρήσετε τη διαφορά ανάμεσα στην καλύτερη και στη χειρότερη βαθμολογία του αγωνίσματος.

Θέμα Ε (2005, Εξετ. Ημερ. Ε.Λ., Θέμα 3)

∆ίνεται πίνακας Α[Ν] ακέραιων και θετικών αριθμών, καθώς και πίνακας Β[Ν-1] πραγματικών και θετικών αριθμών.

Να γραφεί αλγόριθμος, ο οποίος να ελέγχει αν κάθε στοιχείο Β[i] είναι ο μέσος όρος των στοιχείων Α[i] και Α[i+1], δηλαδή αν Β[i] = (Α[i] + Α[i+1])/2.

Σε περίπτωση που ισχύει, τότε να εμφανίζεται το μήνυμα «Ο πίνακας Β είναι ο τρέχων μέσος του Α», διαφορετικά να εμφανίζεται το μήνυμα «Ο πίνακας Β δεν είναι ο τρέχων μέσος του Α».

Για παράδειγμα:

Έστω ότι τα στοιχεία του πίνακα Α είναι: 1, 3, 5, 10, 15 και ότι τα στοιχεία του πίνακα Β είναι: 2, 4, 7.5, 12.5.

Τότε ο αλγόριθμος θα εμφανίσει το μήνυμα «Ο πίνακας Β είναι ο τρέχων μέσος του Α», διότι 2 = (1+3)/2, 4=(3+5)/2, 7.5= (5+10)/2, 12.5=(10+15)/2.