Καλησπέρα σας!
Πέρα από δικές μου σημειώσεις ακολουθώ συχνά το βιβλίο Παράρτημα Α που δίδεται στο σχολείο (ειδικά στις ασκήσεις). Σήμερα παρατήρησα ένα τραγικό λάθος (έχει γενικά πολλά λάθη). Σελίδα 58 ο αλγόριθμος της αναζήτησης στην Περίπτωση 1η έχει λογικό λάθος. Συγκεκριμένα αν δεν υπάρχει το στοιχείο που ψάχνουμε θα ψάξει σε μία παραπάνω θέση του πίνακα που δεν υπάρχει (αν ο πίνακας είναι Ν θέσεις η συνθήκη θα ελένξει και την Ν+1 θέση). Δεν γνωρίζω αν το έχει ανακαλύψει κανένας άλλος συνάδελφος ή αν χρεισιμοποιεί και το συγκεκριμένο βοήθημα αλλά καλό είναι να το γνωρίζουν τα παιδιά.
αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση
Παράθεση από: Παναγιώτης Τσιωτάκης στις 04 Μαρ 2019, 08:15:58 ΜΜ
αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση
Τι λάθος έχει η δυαδική αναζήτηση;;; :-\
Είναι λάθος να διατυπωθεί η συνθήκη της δομής Όσο όπως παρατίθεται στο τετράδιο οδηγιών μαθητή:
«Όσο (δαρχή <= δτέλος) και (table[μέσος] <> key) επανάλαβε»
διότι υπάρχει περίπτωση να παραβιαστούν τα όρια του πίνακα. Πιο συγκεκριμένα, αν αναζητείται τιμή μικρότερη από το πρώτο στοιχείο, τότε τελικά θα είναι δαρχή = 1, δτέλος = 0 και μέσος = 0 και θα προσπελαστεί η θέση 0 του πίνακα, που δεν ορίζεται!!!
Έχεις δίκιο παραθέτω την σωστή δυαδική αναζήτηση:
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: 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, " δεν υπάρχει στον πίνακα"
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση
Και οι δύο αυτη αλ΄γοριθμοι βγάζουν λογικό λάθος όταν το στοιχείο δεν υπάρχει στον πίνακα.
Σωστά!! Γενικά η χρήση αγκύλης (του πίνακα δηλαδή) στη συνθήκη του ΌΣΟ δημιουργεί παρενέργειες που απαιτούν προσοχή...
Αντί του 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.