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

[tanius76]

θα ήθελα να μου πείτε τι γνώμη σας
για τον παρακάτω αλγόριθμο

Αλγόριθμος Search
Δεδομένα // table, n, key //
i <- 1
position <-  0
Όσο i<=n και key>table επανέλαβε
     αν table = key τότε
           position<- i
     αλλιώς
           i<- i+1
     τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα //position//
Τέλος Search

πιστεύω ότι είναι λάθος  γιατί δεν τερματίζεται ο αλγόριθμος

και η σωστή εκδοχή είναι αυτή

Όσο i<=n και key>table επανέλαβε
     αν table = key τότε
           position<- i
                τέλος αν      
           i<- i+1
Τέλος_επανάληψης
     
τί λέτε ?
περιμένω την γνώμη σας

[gpapargi]

Τώρα βέβαια δεν ξέρω αν φταίει το ότι δεν έχω πιει καφέ ακόμα αλλά αυτό που βλέπω είναι ακόμα χειρότερο:

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

Αυτό που βλέπω εγώ είναι ότι για να αλλάξει τιμή η position θα πρέπει να ισχύει
Key>table (για να μπει στην Όσο) και key=table (για να μπει στην Αν).
Αυτές οι δύο συνθήκες είναι αμοιβαία αποκλειόμενες οπότε η position  δε θα αλλάξει ποτέ τιμή. Αυτό ισχύει και στους 2 αλγορίθμους που γράφεις.

[Laertis]

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

 ............
Όσο key>=table και i <=n επανάλαβε
 ............

Αυτό πάλι είναι σωστό αν ο πίνακας είναι ταξινομημένος κατά αύξουσα σειρά. Σε φθίνουσα διάταξη πρέπει να τροποποιηθεί.

[Βρακόπουλος Αθανάσιος]

Ούτε και η εκδοχή που αναφέρετε είναι σωστή.
Διότι όταν δεν υπάρχει η τιμή του Key στον πίνακα table και η αναζητούμενη τιμή του Key είναι μεγαλύτερη της τελευταίας θέσης του πίνακα table, τότε για να τερματίσει ο αλγόριθμος θα εξετασθεί η Ν+1 θέση του πίνακα, η οποία δεν υφίσταται

Θα πρότεινα τον παρακάτω αλγόριθμο με την προϋπόθεση ότι ο πίνακας  table θα είναι σε αύξουσα διάταξη:
Αλγόριθμος Search
Δεδομένα // table, n, key //

Ι<- 1
Όσο i<n και key>table επανέλαβε
 I<- I+1
Τέλος_επανάληψης

Αν table = key τότε
 pos<- I
Αλλιώς
 pos<- 0
τέλος_αν  
Αποτελέσματα //pos//
! η τιμή 0 της pos σημαίνει δεν υπάρχει το Key στον πίνακα table
! άλλη τιμή της pos σημαίνει ότι υπάρχει το Key στον πίνακα table
Τέλος Search

[Laertis]

Χμμ, επανερχόμαστε στις προηγούμενες μακρές συζητήσεις ...
Έχεις δίκιο συνάδελφε όσον αφορά τη θεωρηρική προσέγγιση της άσκησης. Κανονικά πρέπει να μπει λογική συνθήκη όπως γίνεται και στην σειριακή αναζήτηση σε μη ταξινομημένο πίνακα (πχ.
                         Όσο done=ψευδής και i<=n επανάλαβε
                                 Αν table=key τότε
                                      pos <-- i  ( ή ότι άλλο θέλετε να κάνει)
                                 Τέλος_αν
                                  i <-- i + 1
                                 Αν table>key  τότε
                                      done <--αληθής
                                 Τέλος_αν
                                Τέλος_επανάληψης

Στην πράξη όμως δουλεύει  (πχ στην Pascal) και αυτό που  πρότεινα, ακόμα και στο σενάριο που περιγράφεις συνάδελφε Θανάση. Παλιότερα έγινε μια κουβέντα για την προτεραιότητα λογικών πράξεων και την ασάφεια του βιβλίου ... Νομίζω δεν είναι η μόνη.
Στην περίπτωση που αναφέρεις, δηλ. όταν το key είναι μεγαλύτερο και απο το τελευταίο στοιχείο του πίνακα και χρειάζεται να ελεγχθεί σύνθετη συνθήκη , το i<=n θα είναι πάντα ψευδές (για i=n+1) οπότε το αποτέλεσμα της συνθήκης θα είναι ψευδές (έστω και αν το στοιχείο n+1 του πίνακα δεν υπάρχει). Θέλω να πω δηλαδή ότι αρκετές γλώσσες αντιμετωπίζουν πιο ευέλικτα το θέμα κάποιων συνθηκών. Το κακό είναι ότι υπάρχει ασάφεια στο πως το αντιμετωπίζει η γλώσσα και οι εντολές του βιβλίου.
Φιλικά   :-/

[tanius76]

Ευχαριστώ παιδιά για τις απαντήσεις σας!
Μάλλον ο Laertis παρουσιάζει την ποιό ιδανική λύση..
ομως πολύ προχωρημένο θέμα βρε παιδιά για τους μαθητές.

Εσείς το διδάσκετε αυτό?
(Δηλαδή την αναζήτηση σε ταξινομημένο πίνακα???)
Και αν ναί πώς? Με ποιόν Αλγόριθμο?

[tanius76]

πρός τον gpapargi
εστω πίνακας Α με 6 στοιχεία :3-4-5-6-8-10
και key=6
Οταν ι=4 τότε key>A(4) {6>6} ---> Ψευδής και έτσι τερματίζεται η επαναληπτική διαδικασία, χωρίς να βρεί το στοιχείο που ζητάμε

[tanius76]

τώρα όσον αφορά τον παραπάνω πίνακα ισχύει ο αλγόριθμος

i <- 1
position <-  0  

Όσο i<=n και key>=table επανέλαβε
αν table = key τότε
 position<- i
      τέλος αν  
 i<- i+1
Τέλος_επανάληψης

Ομως στην περίπτωση που αναφέρει ο Βρακόπουλος έχουμε όντως πρόβλημα!!

[P.Tsiotakis]

Αλγόριθμος Sequential_Search_Sorted
  Δεδομένα // n, table, key //
  done <- ψευδής
  position <- 0
  i <- 1
  ! για αύξουσα ταξινόμηση
  Όσο (done = ψευδής) και (i <= n) επανάλαβε
                   Αν (table > key) τότε ! σταμάτα την επανάληψη, δεν θα βρεθεί
                     done <- αληθής
              Αλλιώς_Αν (table = key) τότε ! σταμάτα την επανάληψη, βρέθηκε
                      done <- αληθής
                                position <- i    
              Αλλιώς ! συνέχισε την επανάληψη
                      i <- i + 1
            Τέλος_αν
  Τέλος_επανάληψης
  Αν (position <> 0) τότε
          Εκτύπωσε "Το στοιχείο ", key, " ευρέθη στη θέση ", position
  Αλλιώς
          Εκτύπωσε "Το στοιχείο ", key, " δεν ευρέθη στον δοθέντα πίνακα"      
  Τέλος_Αν
  Αποτελέσματα // position //
Τέλος Sequential_Search_Sorted

[redhata]

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

[Βασίλης Φ.]

Πιο απλά, μπορούμε να έχουμε μόνο μια συνθήκη:

Αλγόριθμος Sequential_Search_Sorted
  Δεδομένα // n, table, key //
  done <- ψευδής

  i <- 1
  ! για αύξουσα ταξινόμηση
  Όσο (done = ψευδής) και (i <= n) ΚΑΙ table<=key επανάλαβε
   AN (table = key) τότε ! σταμάτα την επανάληψη
       done <- αληθής
       position <- i    
    Αλλιώς ! συνέχισε την επανάληψη
       i <- i + 1  
  Τέλος_αν
  Τέλος_επανάληψης

  Αν (done=Αληθής) τότε  
     Εκτύπωσε "Το στοιχείο ", key, " ευρέθη στη θέση ", position
  Αλλιώς
     Εκτύπωσε "Το στοιχείο ", key, " δεν ευρέθη στον δοθέντα πίνακα"  
  Τέλος_Αν
  Αποτελέσματα // position //
Τέλος Sequential_Search_Sorted

Θεωρώ επίσης όπως θα καταλάβατε ότι ο έλεγχος για το αν βρέθηκε ή όχι το στοιχείο γίνεται με έλεγχο του flag done και όχι του position. Προσωπικά θεωρώ άσκοπο να πούμε position<--0 αφού καταρχήν δεν έχει νόημη η θέση 0 σε έναν πίνακα, και αφού την δουλειά σου μπορείς να την κάνεις με το flag πιο όμορφα! Συμφωνείτε;