Mathman.gr

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

AE-M19-10

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

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

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

Dim lights

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

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

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

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

 

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

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

 

sideBar



You are here: MAIN PAGE