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

giannhs555

  • Οπαδός
  • **
  • Μηνύματα: 15
ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« στις: 06 Μάρ 2010, 07:01:12 μμ »
ΚΑΛΗΣΠΕΡΑ ΣΑΣ. ΕΧΩ ΝΑ ΘΕΣΩ ΜΙΑ ΑΠΟΡΙΑ ΜΟΥ.

ΠΩΣ ΜΠΟΡΩ ΝΑ ΚΑΝΩ ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ? ΜΕ ΤΗΝ ΕΝΤΟΛΗ ΓΙΑ? ΑΝ ΘΕΛΩ ΟΠΩΣ ΣΤΟ ΜΟΝΟΔΙΑΣΤΑΤΟ ΟΙ ΕΠΑΝΑΛΗΨΕΙΣ ΝΑ ΣΤΑΜΑΤΟΥΝ ΟΤΑΝ ΤΟ ΣΤΟΙΧΕΙΟ ΒΡΕΘΕΙ ΠΩΣ ΘΑ ΤΟ ΚΑΝΩ?

ΕΥΧΑΡΙΣΤΩ.

toufeki

  • Επισκέπτης
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #1 στις: 06 Μάρ 2010, 07:41:33 μμ »
Καλησπέρα και σε σένα Γιάννη.
Έχεις προσπαθήσει καθόλου να σκεφτείς μια λογική που θα μπορούσε να σε βοηθήσει να βρεις τη λύση;

Υπάρχει κάποιος λόγος που πρέπει οπωσδήποτε να χρησιμοποιηθεί η δομή ΓΙΑ;

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1465
  • Δεν αντέχω την (συμ)-πίεσηηη .......
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #2 στις: 06 Μάρ 2010, 08:54:26 μμ »
Με διπλό Όσο αντί το Για :
.......
i <-- 1
Όσο done=ψευδής και i <=n επανάλαβε
    j <-- 1
    Όσο done=ψευδής και j <=m επανάλαβε
       Αν table[i,j]=key τότε
             done<--αληθής
              γραμμή <-- i
              στήλη <--  j
        αλλιώς
             j <--  j+1
         Τέλος_αν
       Τέλος_επανάληψης
     i <-- i +1
Τέλος_επανάληψης
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

michaeljohn

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 129
  • "Είναι παιδιά πολλών ανθρώπων τα λόγια μας"
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #3 στις: 06 Μάρ 2010, 09:15:30 μμ »
Έστω ο ΝxΜ πίνακας Α,  και Key το αναζητούμενο

…….
Found <-- Ψευδής
i <-- 1
j <-- 1
Όσο i <= N και Found = Ψευδής επανάλαβε
   Αν Α[i,j] = key τότε
      Found <-- Αληθής
      Εμφάνισε "βρέθηκε στην", i, "η γραμμή και ", j,"η στήλη"
   Αλλιώς
      j <-- j + 1
      Αν j > M τότε
         i <-- i + 1
         j <-- 1
      Τέλος_αν
   Τέλος_αν 
Τέλος_επανάληψης
……..


Αφιερωμένο στους μαθητές που αγωνίζονται !

toufeki

  • Επισκέπτης
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #4 στις: 06 Μάρ 2010, 09:29:32 μμ »
...μήπως πρέπει να μπει και κάτι άλλο στο παιχνίδι; Ίσως κάποιος ακόμα βοηθητικός μετρητής;
Μήπως το όσο θα έπρεπε να τρέξει το πολύ ΝΧΜ φορές;

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

giannhs555

  • Οπαδός
  • **
  • Μηνύματα: 15
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #5 στις: 06 Μάρ 2010, 10:48:55 μμ »
το κωδικα που εχει δωσει ο Γιωργος σκεφτομουνα και γω.

Βεβαια τα βοηθηματα χρησιμοποιουν την ΓΙΑ. Μηπως ειναι λιγο δυσκολο για τους μαθητες να χρησιμοποιουν την ΟΣΟ σε αυτη την περιπτωση και θα ηταν προτιμοτερο να συνιστουμε να χρησιμοποιουμε τη ΓΙΑ?

toufeki

  • Επισκέπτης
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #6 στις: 07 Μάρ 2010, 10:31:02 πμ »
Μια άλλη λύση είναι η παρακάτω. Έτσι για πλουραλισμό.
Στην παρακάτω λύση ο μετρητής της ΟΣΟ είναι διαφορετικός από τους δείκτες i, j του πίνακα Α[Ν,Μ]. 

…….
βρέθηκε <- Ψευδής
i <- 1
j <- 1
k <- 1
ΟΣΟ (k <= N*M) και βρέθηκε = Ψευδής ΕΠΑΝΕΛΑΒΕ
   Αν Α[i,j] = key ΤΟΤΕ
      βρέθηκε <- Αληθής
      γραμμή <-  i
      στήλη <- j
   ΑΛΛΙΩΣ
       j <- j + 1
      ΑΝ (k mod M) = 0 TOTE
         i <- (k div Μ ) + 1 ! θα μπορούσε να είναι και i <- i +1, αλλά έτσι για κάτι διαφορετικό
         j <- 1
      ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΑΝ
   k <- k + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
........
         

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3135
  • to Iterate is human to Recurse divine
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #7 στις: 07 Μάρ 2010, 11:17:12 πμ »
Η ενδεδειγμένη λύση είναι αυτή του Λαέρτη διότι μπορείς να καταλήξεις σε αυτή με διαδοχικούς μετασχηματισμούς από την διπλή Για σε Όσο έτσι ώστε να καταλάβει ο μαθητής το σκεπτικό. Διδακτικά δηλαδή είναι το καλύτερο που θα μπορούσαμε να κάνουμε πιστεύω.

Δίνω και εγώ μια λύση, πιο μαζεμένη αλλά με έναν μετρητή και χωρίς λογική μεταβλητή γιατί ουσιαστικά είναι περιττή, η οποία όμως δεν ξέρω αν είναι καλή ιδέα για την τάξη >:D.

θέση <- 0
k<-1
ΟΣΟ (k <= N*M) και (θέση = 0) ΕΠΑΝΑΛΑΒΕ
     ΑΝ  Α[((k-1) div M)+1,  ((k-1) mod M)+1] = key ΤΟΤΕ   θέση <- k
     k <- k + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Λογικά πρέπει να δουλεύει. Στη συνέχεια ελέγχουμε τη μεταβλητή θέση αν είναι θετική (βρέθηκε) ή 0 (δεν βρέθηκε) και σε περίπτωση που βρέθηκε το στοιχείο μας είναι το
Α[((θέση-1) div M)+1,  ((θέση-1) mod M)+1]
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1465
  • Δεν αντέχω την (συμ)-πίεσηηη .......
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #8 στις: 07 Μάρ 2010, 01:42:50 μμ »
Δίνω και εγώ μια λύση, πιο μαζεμένη αλλά με έναν μετρητή και χωρίς λογική μεταβλητή γιατί ουσιαστικά είναι περιττή, η οποία όμως δεν ξέρω αν είναι καλή ιδέα για την τάξη >:D.

Απορώ Ευριπίδη γιατί ισχυρίζεσαι ότι δεν είναι καλή ιδέα για την τάξη. Πως αλλιώς  θα "τρομάξω" τους μαθητές μου ; >:D
Άνευ πλάκας, είναι ένα πολύ καλό παράδειγμα για να δείξεις στους μαθητές ότι για να λύσουν προβλήματα χρειάζεται αντίληψη, ευριματικότητα και απλότητα. Η φαντασία στον προγραμματισμό.
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

toufeki

  • Επισκέπτης
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #9 στις: 07 Μάρ 2010, 05:25:26 μμ »
Συμφωνώ απόλυτα με τον Ευριπίδη.  :)


Σημ: Δεν θα μπορούσα να κάνω διαφορετικά.
.....
Ευριπίδη, δώσε και σε μας τον αλγόριθμο συμπίεσης αλγορίθμου. Μη μας κρατάς σε αγωνία. >:D

toufeki

  • Επισκέπτης
Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
« Απάντηση #10 στις: 07 Μάρ 2010, 05:43:44 μμ »
..Η αναζήτηση κυνηγά τον μετρητή με διαφορά σταθερή μιας θέσης πίνακα, πάνω σε ένα φιδάκι.  :D

Χαίρομαι πολύ που έχω αγιάτρευτη εξάρτηση από το ΣΤΕΚΙ. >:D