ΑΝΑΖΗΤΗΣΗ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ

Ξεκίνησε από giannhs555, 06 Μαρ 2010, 07:01:12 ΜΜ

« προηγούμενο - επόμενο »

giannhs555

ΚΑΛΗΣΠΕΡΑ ΣΑΣ. ΕΧΩ ΝΑ ΘΕΣΩ ΜΙΑ ΑΠΟΡΙΑ ΜΟΥ.

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

ΕΥΧΑΡΙΣΤΩ.

toufeki

Καλησπέρα και σε σένα Γιάννη.
Έχεις προσπαθήσει καθόλου να σκεφτείς μια λογική που θα μπορούσε να σε βοηθήσει να βρεις τη λύση;

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

Laertis

Με διπλό Όσο αντί το Για :
.......
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

Έστω ο Ν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

...μήπως πρέπει να μπει και κάτι άλλο στο παιχνίδι; Ίσως κάποιος ακόμα βοηθητικός μετρητής;
Μήπως το όσο θα έπρεπε να τρέξει το πολύ ΝΧΜ φορές;

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

giannhs555

το κωδικα που εχει δωσει ο Γιωργος σκεφτομουνα και γω.

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

toufeki

Μια άλλη λύση είναι η παρακάτω. Έτσι για πλουραλισμό.
Στην παρακάτω λύση ο μετρητής της ΟΣΟ είναι διαφορετικός από τους δείκτες 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

Η ενδεδειγμένη λύση είναι αυτή του Λαέρτη διότι μπορείς να καταλήξεις σε αυτή με διαδοχικούς μετασχηματισμούς από την διπλή Για σε Όσο έτσι ώστε να καταλάβει ο μαθητής το σκεπτικό. Διδακτικά δηλαδή είναι το καλύτερο που θα μπορούσαμε να κάνουμε πιστεύω.

Δίνω και εγώ μια λύση, πιο μαζεμένη αλλά με έναν μετρητή και χωρίς λογική μεταβλητή γιατί ουσιαστικά είναι περιττή, η οποία όμως δεν ξέρω αν είναι καλή ιδέα για την τάξη >: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

Παράθεση από: evry στις 07 Μαρ 2010, 11:17:12 ΠΜ
Δίνω και εγώ μια λύση, πιο μαζεμένη αλλά με έναν μετρητή και χωρίς λογική μεταβλητή γιατί ουσιαστικά είναι περιττή, η οποία όμως δεν ξέρω αν είναι καλή ιδέα για την τάξη >:D.

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

toufeki

Συμφωνώ απόλυτα με τον Ευριπίδη.  :)


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

toufeki

..Η αναζήτηση κυνηγά τον μετρητή με διαφορά σταθερή μιας θέσης πίνακα, πάνω σε ένα φιδάκι.  :D

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