Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Πολυδιάστατοι πίνακες => Γ΄ Λυκείου => Αναζήτηση => Μήνυμα ξεκίνησε από: giannhs555 στις 06 Μάρ 2010, 07:01:12 μμ

Τίτλος: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: giannhs555 στις 06 Μάρ 2010, 07:01:12 μμ
ΚΑΛΗΣΠΕΡΑ ΣΑΣ. ΕΧΩ ΝΑ ΘΕΣΩ ΜΙΑ ΑΠΟΡΙΑ ΜΟΥ.

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

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

Υπάρχει κάποιος λόγος που πρέπει οπωσδήποτε να χρησιμοποιηθεί η δομή ΓΙΑ;
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: Laertis στις 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
Τέλος_επανάληψης
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: michaeljohn στις 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 στις 06 Μάρ 2010, 09:29:32 μμ
...μήπως πρέπει να μπει και κάτι άλλο στο παιχνίδι; Ίσως κάποιος ακόμα βοηθητικός μετρητής;
Μήπως το όσο θα έπρεπε να τρέξει το πολύ ΝΧΜ φορές;

Αν και ο αλγόριθμος φαίνεται να δουλεύει εντούτοις είναι φοβερό μπερδεμα για έναν μαθητή.
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: giannhs555 στις 06 Μάρ 2010, 10:48:55 μμ
το κωδικα που εχει δωσει ο Γιωργος σκεφτομουνα και γω.

Βεβαια τα βοηθηματα χρησιμοποιουν την ΓΙΑ. Μηπως ειναι λιγο δυσκολο για τους μαθητες να χρησιμοποιουν την ΟΣΟ σε αυτη την περιπτωση και θα ηταν προτιμοτερο να συνιστουμε να χρησιμοποιουμε τη ΓΙΑ?
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: toufeki στις 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 στις 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]
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: Laertis στις 07 Μάρ 2010, 01:42:50 μμ
Δίνω και εγώ μια λύση, πιο μαζεμένη αλλά με έναν μετρητή και χωρίς λογική μεταβλητή γιατί ουσιαστικά είναι περιττή, η οποία όμως δεν ξέρω αν είναι καλή ιδέα για την τάξη >:D.

Απορώ Ευριπίδη γιατί ισχυρίζεσαι ότι δεν είναι καλή ιδέα για την τάξη. Πως αλλιώς  θα "τρομάξω" τους μαθητές μου ; >:D
Άνευ πλάκας, είναι ένα πολύ καλό παράδειγμα για να δείξεις στους μαθητές ότι για να λύσουν προβλήματα χρειάζεται αντίληψη, ευριματικότητα και απλότητα. Η φαντασία στον προγραμματισμό.
Τίτλος: Απ: ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ
Αποστολή από: toufeki στις 07 Μάρ 2010, 05:25:26 μμ
Συμφωνώ απόλυτα με τον Ευριπίδη.  :)


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

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