Αποστολέας Θέμα: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ  (Αναγνώστηκε 1267 φορές)

theoni

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 105
ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« στις: 05 Φεβ 2018, 12:42:52 μμ »
Γειά σας δυο ερωτήσεις θα ήθελα να κάνω πάνω στην δυαδική αναζήτηση. Πρώτον διδάσκετε την δυαδική αναζήτηση σε δισδιάστατους πίνακες (κατά γραμμές ή κατά στήλες) ; και δεύτερον  στο παράτημα ο αλγόριθμος τησ δυαδικής αναζήτησης  εφαρμόζεται στην ουσια για μοναδικα στοιχεία αφου μόλις βρεθεί το στοιχέιο η αναζήτηση τερματίζει στην περίπτωση όπου το στοιχείο βρίσκεται παραπάνω απο μια φορές στον πίνακα τι κάνουμε ;

eris_st

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 3
    • eris_st@jabb3r.org
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #1 στις: 05 Φεβ 2018, 01:35:01 μμ »
καλησπέρα. η δυαδική αναζήτηση διδάσκεται μόνο σε μονοδιάστατους πίνακες.
Αν το προς αναζήτηση στοιχείο υπάρχει πάνω από μια φορά μέσα στον πίνακα τότε ελέγχεις τα προηγούμενα και τα επόμενα στοιχεία από το μέσο που βρήκες για να δεις ποια ικανοποιούν τη συνθήκη.

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 259
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #2 στις: 05 Φεβ 2018, 04:34:34 μμ »
Δυαδική αναζήτηση με όμοια "κλειδιά" δεν έτυχε να δω ακόμα! Ποιο κριτήριο θα μας σταματήσει στο σωστό όμοιο κλειδί; Και γιατί αυτό να μην είναι μέρος του κλειδιού;


gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2421
  • I 'm not young enough to know everything
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #3 στις: 06 Φεβ 2018, 11:11:42 πμ »
Γειά σας δυο ερωτήσεις θα ήθελα να κάνω πάνω στην δυαδική αναζήτηση. Πρώτον διδάσκετε την δυαδική αναζήτηση σε δισδιάστατους πίνακες (κατά γραμμές ή κατά στήλες) ; και δεύτερον  στο παράτημα ο αλγόριθμος τησ δυαδικής αναζήτησης  εφαρμόζεται στην ουσια για μοναδικα στοιχεία αφου μόλις βρεθεί το στοιχέιο η αναζήτηση τερματίζει στην περίπτωση όπου το στοιχείο βρίσκεται παραπάνω απο μια φορές στον πίνακα τι κάνουμε ;

Στο δισδιάστατο δεν είναι ορισμένη η διάταξη των κελιών, οπότε θα πρέπει κάπως να οριστεί. Από κει και πέρα γίνεται αλλά μπλέκεις με την αριθμητική των δεικτών. Μια απλή προσέγγιση είναι να τα πετάξεις σε μονοδιάστατο και να κάνεις εκεί την αναζήτηση. Έτσι κι αλλιώς η ταξινόμηση είναι μονοδιάστατη διαδικασία υπό την έννοια ότι τα κελιά πρέπει να μπουν σε μια σειρά, δηλαδή να οριστεί η διάταξη σε αυτά.
Γιώργος Παπαργύρης (gpapargi@hotmail.com)

epsilonXi

  • Βετεράνος
  • ****
  • Μηνύματα: 89
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #4 στις: 26 Μάρ 2018, 04:13:46 μμ »
σε ένα διαγώνισμα προ καιρού, έχοντας δεδομένο τον αλγόριθμο της δυαδικής, ζήτησα να προσθέσουν εντολές ώστε να τσεκάρουν αν η αναζητούμενη τιμή υπάρχει δύο φορές αντί για μία...

οι περισσότεροι δεν απάντησαν καν...

ένα άτομο σκέφτηκε μετά την αναζήτηση, στην περίπτωση που υπήρξε επιτυχής, να βάλει ένα μετρητή να σκανάρει τον πίνακα εκ νέου για να μετρήσει...

αυτό που σκεφτόμουν εγώ, δυστυχώς δεν το σκέφτηκε κανείς:
...
ΑΝ table[mid] = key ΤΟΤΕ
   ΑΝ mid = 1 ΚΑΙ table[2] = key TOTE
      found <-- ΑΛΗΘΗΣ
   ΑΛΛΙΩΣ_ΑΝ mid = Ν ΚΑΙ table[Ν-1] = key TOTE
      found <-- ΑΛΗΘΗΣ
   ΑΛΛΙΩΣ_ΑΝ table[mid-1] = X Ή table[μιδ+1] = key TOTE
      found <-- ΑΛΗΘΗΣ
   ΤΕΛΟΣ_ΑΝ
...

pvs

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 104
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #5 στις: 29 Μάρ 2018, 02:13:18 μμ »
Γειά σας δυο ερωτήσεις θα ήθελα να κάνω πάνω στην δυαδική αναζήτηση. Πρώτον διδάσκετε την δυαδική αναζήτηση σε δισδιάστατους πίνακες (κατά γραμμές ή κατά στήλες) ; και δεύτερον  στο παράτημα ο αλγόριθμος τησ δυαδικής αναζήτησης  εφαρμόζεται στην ουσια για μοναδικα στοιχεία αφου μόλις βρεθεί το στοιχέιο η αναζήτηση τερματίζει στην περίπτωση όπου το στοιχείο βρίσκεται παραπάνω απο μια φορές στον πίνακα τι κάνουμε ;
Κατά την άποψη μου μπορεί να ζητηθεί δυαδική σε συγκεκριμένη γραμμή ή στήλη.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 879
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #6 στις: 30 Μάρ 2018, 10:52:09 πμ »
Κατά τη γνώμη μου, ΔΕ μπορεί να ζητηθεί δυαδική αναζήτηση, παραμόνο σε συμπλήρωση κενών και τέτοια πράγματα.
Και φυσικά αφού πρώτα τους δοθεί η περιγραφή του αλγορίθμου.
Βάσει των "μπαλωμάτων" που τελευταία έχει στείλει το Υπουργείο, αν θυμάμαι και έχω καταλάβει καλά, λέει ότι οι μαθητές πρέπει να έχουν δει τον αλγόριθμο αυτό μέσω μιας άσκησης.
Αυτό δε σημαίνει ότι πρέπει να τον ξέρουν απ' έξω ως θεωρία τους, όπως πχ συμβαίνει με τη σειριακή και τη φυσαλίδα που τους δίνονται ως θεωρία στο βιβλίο.
Φιλικά,
Γιώργος Θαλασσινός

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 173
Απ: ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ
« Απάντηση #7 στις: 24 Μάι 2018, 10:25:50 μμ »
κατα τη γνωμη μου η δυαδικη αναζητηση ειναι ευκολο να γινει κατανοητη αν την παρουσιασεις στα παιδια σαν ενα ειδους παιχνιδι.οσοι θελετε να τη διδαξετε καντε το εξης.πειτε στους μαθητες  σας: θα σκεφτω εναν αριθμο απο το 1 μεχρι 1000  και ο αριθμος αυτος θα ειναι ακεραιος.εσεις μπορειτε να μου λετε εναν αριθμο και γω θα σας απανταω αν ειναι μεγαλυτερος  απο αυτον  που σκεφτηκα,αν ειναι  μικροτερος η αν τον βρηκατε.αν τον βρειτε με τις λιγοτερες προσπαθειες κερδιζετε