Mathman.gr

  • Full Screen
  • Wide Screen
  • Narrow Screen
  • Increase font size
  • Default font size
  • Decrease font size

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

 

 

seq_search

 

 

Η μέθοδος με την οποία κάνουμε αναζήτηση σε ένα πίνακα εξαρτάται από διάφορους παράγοντες ( Θ 82 ). Η πιο απλή μέθοδος αναζήτησης είναι η Σειριακή Αναζήτηση ( Θ 83 ). Η χρήση της Σειριακής Αναζήτησης ( Θ 83 ) είναι δικαιολογημένη σε κάποιες συγκεκριμένες περιπτώσεις ( Θ 85 ), τις οποίες γνωρίζουμε για τη θεωρία, αλλά στην πράξη (για τις ασκήσεις του μαθήματος Ανάπτυξη Εφαρμογών )  μαθαίνουμε και χρησιμοποιούμε μόνο τον Αλγόριθμο της σειριακής αναζήτησης ( Ψευδοκώδικας ,  Θ 84 ), ενώ υπάρχουν κι άλλοι μέθοδοι πχ της δυαδικής αναζήτησης ( Θ 86 ).

 

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

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

 

Ο αλγόριθμος της σειριακής αναζήτησης συνδυάζει τη χρήση

 

Μετά την παρουσίαση ακολουθούν κάποιες παρατηρήσεις ...

Dim lights

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

Για παράδειγμα, όταν ολοκληρώνεται η σειριακή αναζήτηση και οι επαναλήψεις, η τιμή του i έχει παραμείνει 3, επειδή η περίπτωση αλλιώς (αύξηση του i) δεν εκτελέστηκε στην τελευταία επανάληψη. Άρα, στα αποτελέσματα θα μπορούσε να χρησιμοποιηθεί η μεταβλητή i και όχι η μεταβλητή position.

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

 

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

 

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

 

Στον αλγόριθμο της σειριακής αναζήτησης και τις παραλλαγές του , πρέπει να μπορούμε να διακρίνουμε επίσης, ανάλογα με την περίπτωση, αν και πότε εμφανίζουμε τα αποτελέσματα " Βρέθηκε στη θέση : " ... ή "Δεν βρέθηκε" ( ΑΕ-Μ19-12 ).

 

Ερώτηση: Γιατί η μεταβλητή στην οποία αποθηκεύεται η ζητούμενη τιμή ονομάζεται key;

Μπορούμε να φανταστούμε τα στοιχεία του μονοδιάστατου πίνακα (table[i]) σαν κλειδαριές και τη διαδικασία της σειριακής αναζήτησης σαν την προσπάθειά μας να ταιριάξουμε το κλειδί μας (key) σε μία από αυτές.

 

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

( εδώ θα συμπληρώσουμε περισσότερες ασκήσεις )

Ε 188 δ, E 197 β, 

E 167 ε, Ε 198 β,γ

Μια σχετική δοκιμασία για παραβίαση αλγοριθμικού κριτηρίου είναι η Κ 160 και ένα πιο προχωρημένο καθήκον για αναζήτηση σε ταξινομημένο πίνακα είναι η  E 189 .

 

 

Δείτε επίσης :

 

Μέσος όρος

mean_ave

Καταμέτρηση ιδιότητας

pie_chart

Προβλήματα Βελτιστοποίησης

optim

Έλεγχος Δεδομένων

dat_valid

Σειριακή Αναζήτηση

seq_search

Ταξινόμηση Φυσαλίδας

bub_sort

Πίνακες

mona

 Εντολή GOTO

goto1

Υποπρογράμματα

hypos

 

 

 

 

Επιστροφή στα Περιεχόμενα για την Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον

aepp_2012

 

sideBar



You are here: Mathman