ψευδοκώδικας

[MarakiL0ve]

Καλησπερα θα ηθελα αν μπορει καποιος να με βοηθησει να τελειωσω τον ψευδοκώδικα γιατι εχω μπλεξει λιγο...
η ασκσηση μου ζηταει στο προγραμμα που εχω να προσθεση ενα  binary search και ενα seq search..
 

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

Α. Να υλοποιηθεί σε ψευδοκώδικα μια διαδικασία με όνομα BINARY_SEARCH_2D, η οποία θα εκτελεί διαδοχικά (Ν φορές) τη δυαδική αναζήτηση καλώντας την συνάρτηση BINARY_SEARCH σε κάθε γραμμή του πίνακα Α, μέχρις ότου βρεθεί το επιθυμητό στοιχείο. Η διαδικασία θα δέχεται ως παράμετρο τον πίνακα Α και το στοιχείο προς αναζήτηση Χ και θα εμφανίζει τη θέση του στοιχείου στον πίνακα εάν αυτό έχει βρεθεί, διαφορετικά θα εμφανίζει ένα κατάλληλο μήνυμα. Θεωρήστε ότι το Ν είναι σταθερά του προγράμματος.

Β. Να υλοποιηθεί η διαδικασία με όνομα SEQ_SEARCH_2D, η οποία θα παίρνει ως παράμετρο τον πίνακα Α και το στοιχείο προς αναζήτηση Χ, και θα εκτελεί τα παρακάτω βήματα για την αναζήτηση του στοιχείου Χ στον πίνακα A

ΒΗΜΑ 1: Αρχικοποίησε τη βοηθητική μεταβλητή key με την τιμή A[1,N].

ΒΗΜΑ 2: Σύγκρινε την τιμή του στοιχείου προς αναζήτηση X με το στοιχείο key.

ΒΗΜΑ 3: Εάν η τιμή τους είναι ίση, τότε το στοιχείο βρέθηκε.

ΒΗΜΑ 4: Εάν η τιμή του Χ είναι μεγαλύτερη από την τιμή του key, τότε θέσε το key ίσο με το στοιχείο του πίνακα Α της ίδιας στήλης αλλά της επόμενης γραμμής (εάν έχει βγει εκτός ορίων των γραμμών του πίνακα τότε το στοιχείο δεν υπάρχει).

ΒΗΜΑ 5: Εάν η τιμή του Χ είναι μικρότερη από την τιμή του key, τότε θέσε το key ίσο με το στοιχείο του πίνακα Α της ίδιας γραμμής αλλά της προηγούμενης στήλης (εάν έχει βγει εκτός ορίων των στηλών του πίνακα τότε το στοιχείο δεν υπάρχει στον πίνακα).

ΒΗΜΑ 6: Επανάλαβε τα βήματα 2 έως 5

Θεωρήστε ότι το Ν είναι σταθερά του προγράμματος.

ο πινακας -->        3    4    8    9    15
                             5    6   13   20   22
                       Α= 7  12   16   21   27

                                        10  14   17  23   31

                                        11   18   28  33  40

και το προγραμμα που εχω μεχρι στιγμης και πρεπει να συμπληρωσω το binary και seq search

ΑΛΓΟΡΙΘΜΟΣ 3H_YPOERGASIA
ΣΤΑΘΕΡΕΣ N=5;
ΔΕΔΟΜΕΝΑ A: ARRAY [1..N,1..N] OF INTEGER;
I,J:INTEGER;
ΣΥΝΑΡΤΗΣΗ BINARY_SEARCH(B, X):INTEGER
ΔΙΕΠΑΦΗ
ΕΙΣΟΔΟΣ
B: ARRAY [1..N] OF INTEGER;
/* Η γραμμή του αρχικού πίνακα που αναζητούμε το στοιχείο */
X: INTEGER;
/* Το στοιχείο προς αναζήτηση */
ΕΞΟΔΟΣ BINARY_SEARCH:INTEGER;
ΔΕΔΟΜΕΝΑ L,H,MIDDLE:INTEGER;
FOUND:BOOLEAN;
/* Η μεταβλητή FOUND χρησιμοποιείται για τον τερματισμό της */
/* επανάληψης όταν έχει βρεθεί το στοιχείο στον πίνακα */
ΑΡΧΗ
L:=1;
H:=N;
FOUND:=FALSE;
ΕΝΟΣΩ (L<=H AND FOUND=FALSE) ΕΠΑΝΑΛΑΒΕ
MIDDLE:=(L+H) DIV 2;
ΕΑΝ (B[MIDDLE]=X) ΤΟΤΕ
BINARY_SEARCH:=MIDDLE;
FOUND:=TRUE
/* Το στοιχείο βρέθηκε. Επιστρέφεται η θέση του στη γραμμή */
ΑΛΛΙΩΣ ΕΑΝ (B[MIDDLE]<X) ΤΟΤΕ
L:=MIDDLE+1
ΑΛΛΙΩΣ
H:=MIDDLE-1
ΕΑΝ-ΤΕΛΟΣ
ΕΑΝ-ΤΕΛΟΣ
ΕΝΟΣΩ-ΤΕΛΟΣ;
ΕΑΝ (FOUND=FALSE) ΤΟΤΕ
BINARY_SEARCH:=-1
/* Εάν δεν βρεθεί το στοιχείο επέστρεψε -1 */
ΕΑΝ-ΤΕΛΟΣ
ΤΕΛΟΣ-ΣΥΝΑΡΤΗΣΗΣ
ΔΙΑΔΙΚΑΣΙΑ BINARY_SEARCH_2D(A,X)
/* Εδώ υλοποιείτε τη διαδικασία της δυαδικής αναζήτησης για */
/* πίνακα δύο διαστάσεων του ερωτήματος Α */
ΤΕΛΟΣ-ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ SEQ_SEARCH_2D(A,X)
/* Εδώ υλοποιείτε τη διαδικασία της αναζήτησης πίνακα δύο */
/* διαστάσεων του ερωτήματος Β */
ΤΕΛΟΣ-ΔΙΑΔΙΚΑΣΙΑΣ



ΑΡΧΗ/* Κυρίως πρόγραμμα */
ΤΥΠΩΣΕ("Εισαγωγή στοιχείων του πίνακα:\n");
/* Θεωρούμε πως ο χρήστης δίνει τα στοιχεία του πίνακα κατά */
/* αύξουσα σειρά κατά στήλες και κατά γραμμές, καθώς και */
/* ότι κάθε στοιχείο είναι μοναδικό στον πίνακα */
ΓΙΑ I:=1 ΕΩΣ N ΕΠΑΝΑΛΑΒΕ
ΓΙΑ J:=1 ΕΩΣ N ΕΠΑΝΑΛΑΒΕ
ΤΥΠΩΣΕ("Δώστε το στοιχείο A[",I,",",J,"]:");
ΔΙΑΒΑΣΕ(A[i,J])
ΓΙΑ-ΤΕΛΟΣ
ΓΙΑ-ΤΕΛΟΣ;
ΕΠΑΝΑΛΑΒΕ
ΤΥΠΩΣΕ("\nΔώστε το στοιχείο προς αναζήτηση:");
ΔΙΑΒΑΣΕ(J);
ΤΥΠΩΣΕ("\nΕπιλογή μεθόδου:\n");
ΤΥΠΩΣΕ("1. BINARY_SEARCH_2D\n");
ΤΥΠΩΣΕ("2. SEQ_SEARCH_2D\n");
ΤΥΠΩΣΕ("3. ΕΞΟΔΟΣ\n");
ΔΙΑΒΑΣΕ(I);
ΕΑΝ (I=1) ΤΟΤΕ
ΥΠΟΛΟΓΙΣΕ BINARY_SEARCH_2D(A,J)
ΑΛΛΙΩΣ
ΕΑΝ (I=2) ΤΟΤΕ
ΥΠΟΛΟΓΙΣΕ SEQ_SEARCH_2D(A,J)
ΕΑΝ-ΤΕΛΟΣ
ΕΑΝ-ΤΕΛΟΣ
ΜΕΧΡΙ(I=3)
ΤΕΛΟΣ

καμια ιδεα κανενας? :$

 

 

 

και καλες γιορτες να εχετε ολοι σας  :D  σας ευχομαι τα καλυτερα

[Kercyn]

Η εκφώνηση είναι ξεκάθαρη (ειδικά το 2ο ερώτημα). Πού ακριβώς κολλάς;

[MarakiL0ve]

στο binary search kai to seq ...τα αλλα τα  εχω κανει ειναι τα μονα 2 υποερωτηματα που μου εμειναν...και δεν μπορω να τα κανω ...¨/

[Kercyn]

Αυτό ρωτάω, γιατί; Η εκφώνηση σού λέει ποια βήματα πρέπει ν' ακολουθήσεις για να τα υλοποιήσεις. Υπάρχει κάποιο σημείο που δεν καταλαβαίνεις;

[MarakiL0ve]

δεν μπορω να κανω αυτα τα δυο βηματα.. Η εκφωνηση ηταν πιο μεγαλη μου ζητουσε κι αλλα πραγματα..τα εκανα απλα αυτα τα δυο μου χουνε μεινει και δεν μπορω να τα κανω! και δεν εχω και pc για να μπορω να κανω compile να τα ελεγξω! μπορεις καπως να με βοηθησεις μ αυτα τα δυο βηματα? <3

[Kercyn]

δεν μπορω να κανω αυτα τα δυο βηματα.. Η εκφωνηση ηταν πιο μεγαλη μου ζητουσε κι αλλα πραγματα..τα εκανα απλα αυτα τα δυο μου χουνε μεινει και δεν μπορω να τα κανω! και δεν εχω και pc για να μπορω να κανω compile να τα ελεγξω! μπορεις καπως να με βοηθησεις μ αυτα τα δυο βηματα? <3

Όταν λες "να με βοηθήσει" εννοείς "να μου τα δώσει έτοιμα";

[MarakiL0ve]

Νομιζω πως κατι τετοιο θα ηταν αρκετα δυσκολο..οποτε θα ηθελα απλα μια καθοδηγηση! αν βεβαια σου ειναι ευκολη η λυση δε θα ελεγα οχι γιατι, εχω παιδευτει αρκετα και τα εχω βρει πολυ σκουρα! :/ ...θα εκτιμουσα πολυ τη βοηθεια σου..

[Kercyn]

Για να δούμε...

 

Ερώτημα Α

 

Η συνάρτηση BINARY_SEARCH_2D παίρνει ως παραμέτρους τον πίνακα Α (αυτόν που σου δίνει η εκφώνηση) και το στοιχείο Χ που θέλεις να βρεις.

Εκτελεί Ν φορές τη δυαδική αναζήτηση (δηλαδή έχεις μια επανάληψη ΕΝΟΣΩ, μέσα στην οποία καλείται η συνάρτηση BINARY_SEARCH). Η επανάληψη τερματίζει όταν εκτελεστεί Ν φορές ή όταν βρεθεί το στοιχείο (δηλαδή υλοποιείται με παρόμοιο τρόπο όπως εδώ: ΕΝΟΣΩ (L<=H AND FOUND=FALSE) ΕΠΑΝΑΛΑΒΕ)

Σε κάθε εκτέλεση της επανάληψης, η BINARY_SEARCH θα σου επιστρέψει είτε -1 είτε τη θέση του στοιχείου. Εάν επιστρέψει -1, τότε η επανάληψη συνεχίζει. Αν επιστρέψει κάτι διαφορετικό (δηλαδή τη θέση του στοιχείου, η οποία αναγκαστικά θα είναι διάφορη του -1), τότε οι συντεταγμένες του στοιχείου που ψάχνεις είναι (i, j), όπου i ο αύξων αριθμός που χρησιμοποιείς στην επανάληψη ΕΝΟΣΩ (στη συνάρτηση BINARY_SEARCH έχεις ονομάσει αυτόν τον αριθμό L), και j η τιμή που σου επέστρεψε η BINARY_SEARCH.

 

Στο ερώτημα Β σου γράφει ακριβώς τα βήματα που πρέπει να ακολουθήσεις, δε μπορώ να στα γράψω πιο αναλυτικά.

 

Ακόμα δεν έχεις γράψει συγκεκριμένα ποιο πρόβλημα έχεις με την υλοποίηση των ερωτημάτων, μόνο ένα "δε μπορώ", το οποίο παραπέμπει σε "fuck this shit".