Αποστολέας Θέμα: ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΕΤΑΒΑΛΛΟΜΕΝΗ  (Αναγνώστηκε 882 φορές)

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΕΤΑΒΑΛΛΟΜΕΝΗ
« στις: 23 Ιαν 2013, 10:50:41 πμ »
Γεια σε όλους τους φίλους του ΣτΠ. στο σχολικό βιβλίο σελ. 64 δίνεται αλγόριθμος της σειριακής αναζήτησης και αναφέρει μετά επι λέξει : "Όπως αναφέρθηκε, τα στοιχεία που περιέχονται στον πίνακα table δενείναι ταξινομημένα. Επίσης, ο προηγούμενος αλγόριθμος ισχύει για την πε-
ρίπτωση όπου κάθε στοιχείο υπάρχει μία μόνο φορά στον πίνακα" ,όπου table το όνομα του πίνακα που χρησιμοποιείται στον αλγόριθμο.
Αναφέρει αμέως παρακάτω ότι :
" Αν κάποιο στοιχείο εμφανίζεται στον πίνακα περισσότερο από μία φορές, τότε ο αλγόριθμος πρέπει να τροποποιηθεί κατά το εξής: η μεταβλητή done είναι περιττή και η αναζήτηση συνεχίζεται μέχρι το τέλος του πίνακα ελέγχοντας με τη συνθήκη i < n.
Εξ άλλου, αν τα στοιχεία του πίνακα είναι ταξινομημένα, τότε ο αλγόριθμος πρέπει να σταματήσει, μόλις συναντήσει κάποιο στοιχείο που είναι μεγαλύτερο από το αναζητούμενο."
Μπρορεί κάποιος να μου παραθέσει τον αλγόριθμο όπως υλοποιείται με τις δύο παραπάνω εκδοχές ( έναν αλγόριθμο για την περίπτωση που ένα στοιχείο εμφανίζεται στον πίνακα περισσότερες από μία φορές και ένα άλλο αλγόριθμο για την περίπτωση που τα στοιχεία του πίνακα είναι ταξινομημένα )
Σας ευχαριστώ

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2305
Απ: ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΕΤΑΒΑΛΛΟΜΕΝΗ
« Απάντηση #1 στις: 23 Ιαν 2013, 11:33:49 πμ »
Για την περίπτωση που αναζητάται μια τιμή παραπάνω από μια φορές, θα σου αναφέρω απλά ότι μπορεί να υλοποιηθεί με δομή Για, αφού δεν θέλουμε να σταματάει όταν βρει την τιμή. Η μεταβλητή done είναι περιττή

Για ι από 1 μέχρι Ν
Αν Α[ι] = ζητούμενο τότε
....
Τέλος_Αν
Τέλος_Επανάληψης

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

Όσο (ι <= N) και (done = ψευδής) και (Α[ι] <= ζητούμενο) επανάλαβε

(Για να είναι δεκτή η τρίτη συνθήκη, θα πρέπει να υπάρχει τουλάχιστον ένα μεγαλύτερο στοιχείο του ζητούμενου, αλλιώς όταν θα τελειώσει ο πίνακας, η συνθήκη δεν θα μπορεί να ελεγχθεί μετά την τελευταία επανάληψη, αλλά και αυτό διορθώνεται..)
« Τελευταία τροποποίηση: 23 Ιαν 2013, 11:44:15 πμ από petrosp13 »
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 945
Απ: ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΕΤΑΒΑΛΛΟΜΕΝΗ
« Απάντηση #2 στις: 23 Ιαν 2013, 08:39:57 μμ »
Από τις σημειώσεις μου, ελπίζω να σε βοηθήσει.

Φιλικά,
Γιώργος Θαλασσινός

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3302
  • agent romanoff you miss me?
    • P.Tsiotakis
Απ: ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΜΕΤΑΒΑΛΛΟΜΕΝΗ
« Απάντηση #3 στις: 23 Ιαν 2013, 10:54:21 μμ »
νομίζω αναλύεται καλά και στο http://ptsiotakis.mysch.gr/old/aepp/aepp_theory3b.htm