Αποστολέας Θέμα: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α  (Αναγνώστηκε 776 φορές)

angrits

  • Θαμώνας
  • ***
  • Μηνύματα: 24
ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« στις: 04 Μάρ 2019, 06:30:13 μμ »
Καλησπέρα σας!
Πέρα από δικές μου σημειώσεις ακολουθώ συχνά το βιβλίο Παράρτημα Α που δίδεται στο σχολείο (ειδικά στις ασκήσεις). Σήμερα παρατήρησα ένα τραγικό λάθος (έχει γενικά πολλά λάθη). Σελίδα 58 ο αλγόριθμος της αναζήτησης στην Περίπτωση 1η έχει λογικό λάθος. Συγκεκριμένα αν δεν υπάρχει το στοιχείο που ψάχνουμε θα ψάξει σε μία παραπάνω θέση του πίνακα που δεν υπάρχει (αν ο πίνακας είναι Ν θέσεις η συνθήκη θα ελένξει και την Ν+1 θέση). Δεν γνωρίζω αν το έχει ανακαλύψει κανένας άλλος συνάδελφος ή αν χρεισιμοποιεί και το συγκεκριμένο βοήθημα αλλά καλό είναι να το γνωρίζουν τα παιδιά.

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3160
  • Dracarys
    • Panagiotis Tsiotakis
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #1 στις: 04 Μάρ 2019, 08:15:58 μμ »
αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση

angrits

  • Θαμώνας
  • ***
  • Μηνύματα: 24
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #2 στις: 04 Μάρ 2019, 11:45:47 μμ »
αντίστοιχα υλοποιείται λάθος και η δυαδική αναζήτηση

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

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3160
  • Dracarys
    • Panagiotis Tsiotakis
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #3 στις: 05 Μάρ 2019, 09:10:43 πμ »
Είναι λάθος να διατυπωθεί η συνθήκη της δομής Όσο όπως παρατίθεται στο τετράδιο οδηγιών μαθητή:
«Όσο (δαρχή <= δτέλος) και (table[μέσος] <> key) επανάλαβε»

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

angrits

  • Θαμώνας
  • ***
  • Μηνύματα: 24
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #4 στις: 05 Μάρ 2019, 06:56:08 μμ »
Έχεις δίκιο παραθέτω την σωστή δυαδική αναζήτηση:
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
 ΑΚΕΡΑΙΕΣ: 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, " δεν υπάρχει στον πίνακα"
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση

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

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3160
  • Dracarys
    • Panagiotis Tsiotakis
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #5 στις: 05 Μάρ 2019, 10:21:12 μμ »
Σωστά!! Γενικά η χρήση αγκύλης (του πίνακα δηλαδή) στη συνθήκη του ΌΣΟ δημιουργεί παρενέργειες που απαιτούν προσοχή...

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 355
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: ΛΑΘΗ ΠΑΡΑΡΤΗΜΑ Α
« Απάντηση #6 στις: 05 Μάρ 2019, 11:34:44 μμ »
Αντί του 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.