Θέμα: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α

[angrits]

Καλησπέρα σας!
Πέρα από δικές μου σημειώσεις ακολουθώ συχνά το βιβλίο Παράρτημα Α που δίδεται στο σχολείο (ειδικά στις ασκήσεις). Σήμερα παρατήρησα ένα τραγικό λάθος (έχει γενικά πολλά λάθη). Σελίδα 58 ο αλγόριθμος της αναζήτησης στην Περίπτωση 1η έχει λογικό λάθος. Συγκεκριμένα αν δεν υπάρχει το στοιχείο που ψάχνουμε θα ψάξει σε μία παραπάνω θέση του πίνακα που δεν υπάρχει (αν ο πίνακας είναι Ν θέσεις η συνθήκη θα ελένξει και την Ν+1 θέση). Δεν γνωρίζω αν το έχει ανακαλύψει κανένας άλλος συνάδελφος ή αν χρεισιμοποιεί και το συγκεκριμένο βοήθημα αλλά καλό είναι να το γνωρίζουν τα παιδιά.

[P.Tsiotakis]

αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση

[angrits]

αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση

Τι λάθος έχει η δυαδική αναζήτηση;;;

[P.Tsiotakis]

Είναι λάθος να διατυπωθεί η συνθήκη της δομής Όσο όπως παρατίθεται στο τετράδιο οδηγιών μαθητή:
«Όσο (δαρχή <= δτέλος) και (table[μέσος] <> key) επανάλαβε»

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

[angrits]

Έχεις δίκιο παραθέτω την σωστή δυαδική αναζήτηση:
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
 ΑΚΕΡΑΙΕΣ: A[20], Left, Right, M, key, i,p
ΛΟΓΙΚΕΣ: done
ΑΡΧΗ
ΓΡΑΨΕ 'Οι αριθμοί που θα δοθούν πρέπει να είναι ταξινομημένοι κατά αύξουσα τάξη'
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
     ΓΡΑΨΕ 'Δώσε το', i, ' στοιχείο του πίνακα'
     ΔΙΑΒΑΣΕ table
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δωσε τιμή για αναζήτηση: '
ΔΙΑΒΑΣΕ key
Left <- 1
Right <- 20
p <- 0
done<- ΨΕΥΔΗΣ
ΟΣΟ (Left <= Right) ΚΑΙ (done=ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
     M <- (Left + Right) DIV 2
     ΑΝ table[M] = key ΤΟΤΕ
           p <- M
           done <- ΑΛΗΘΗΣ
     ΑΛΛΙΩΣ
           ΑΝ table[M] < key ΤΟΤΕ
    Left <- M + 1
           ΑΛΛΙΩΣ
                 Right <- M - 1
          ΤΕΛΟΣ_ΑΝ
     ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ done= ΑΛΗΘΗΣ ΤΟΤΕ
      ΓΡΑΨΕ "Το στοιχείο,", key, "υπάρχει στη θέση:", p
ΑΛΛΙΩΣ
      ΓΡΑΨΕ "Το στοιχείο,", key, " δεν υπάρχει στον πίνακα"
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση

Και οι δύο αυτη αλ΄γοριθμοι βγάζουν λογικό λάθος όταν το στοιχείο δεν υπάρχει στον πίνακα.

[P.Tsiotakis]

Σωστά!! Γενικά η χρήση αγκύλης (του πίνακα δηλαδή) στη συνθήκη του ΌΣΟ δημιουργεί παρενέργειες που απαιτούν προσοχή...

[bugman]

Αντί του done για σημαία εξόδου, θα μπορούσε να χρησιμοποιηθεί μια left<-right+10, πράγμα που θα έκανε να τερματίσει η επανάληψη, και επιπλέον το left επειδή σε καμία άλλη περίπτωση δεν μπορεί να έχει τιμή right+10, θα ξέρουμε στην έξοδο ότι έχουμε βρει αυτό που ψάχνουμε.
Σβήνουμε το done <- ΑΛΗΘΗΣ, βάζουμε το left<-right+10 και σβήνουμε και το ΚΑΙ (done=ΨΕΥΔΗΣ) στην ΟΣΟ, όπως και την αρχικοποίηση της done, και τον καθορισμό της ως Λογική μεταβλητή.
Αλλάζουμε και το ΑΝ done= ΑΛΗΘΗΣ ΤΟΤΕ με το ΑΝ left=right+10 ΤΟΤΕ

Επίσης το M <- (Left + Right) DIV 2 μπορεί να γίνει M <-Left + (Right-left) DIV 2
Με αυτόν τον τρόπο αποφεύγουμε υπερχείλιση για μεγάλα νούμερα left και right.