Γενικό Λύκειο > Δομές δεδομένων

Καλύτερη υλοποίηση ουράς

(1/9) > >>

alkisg:
Απ' ότι είδα η υλοποίηση της ουράς στο συμπληρωματικό εκπαιδευτικό υλικό είναι κάπως προβληματική. Θέλετε να δούμε εάν προτιμάμε κάποια καλύτερη υλοποίηση, και εάν ναι, να την προτείνουμε στο Υπουργείο;
Προσοχή, αυτό το θέμα ΔΕΝ είναι για το πώς θα τη διδάξουμε φέτος, αλλά για το αν θέλουμε να ζητήσουμε στο Υπουργείο να αντικαταστήσει του χρόνου την υπάρχουσα υλοποίηση με αυτή που θα προτείνουμε εμείς.

Κάνω μια αρχική προσπάθεια και περιμένω παρατηρήσεις. Το ζουμί είναι:

Εισαγωγή:
    πλήθος <- πλήθος + 1
    πίσω <- Κυκλική_θέση(πίσω + 1)
    Ουρά[πίσω] <- στοιχείοΕξαγωγή:
    πλήθος <- πλήθος - 1
    στοιχείο <- Ουρά[εμπρός]
    εμπρός <- Κυκλική_θέση(εμπρός + 1)
Στα πλαίσια των ουρών, τον πίνακα τον θεωρούμε κυκλικό (θέση mod N). Αυτό είναι απαραίτητο ώστε η εισαγωγή και η εξαγωγή να γίνονται σε Ο(1), γιατί σε μερικές υλοποιήσεις που κυκλοφορούν χρησιμοποιείται ολίσθηση των στοιχείων που είναι Ο(Ν) και ακυρώνει τις ιδιότητες πολυπλοκότητας των ουρών. Αν θέλουμε να μην αναφερθούμε σε κυκλικότητα, τότε θα πρέπει να κάνουμε ό,τι κάνει και το βιβλίο και να δώσουμε ένα μικρό παράδειγμα της "εισαγωγής/εξαγωγής πριν γεμίσει ο πίνακας", χωρίς να προχωρήσουμε σε πλήρη υλοποίηση.
Το να περιλαμβάνει η δομή της ουράς και το "πλήθος" κάνει τον κώδικα απλούστερο, ενώ της επιτρέπει να κρατήσει και Ν στοιχεία αντί για Ν-1.

Μας ενδιαφέρουν μόνο η Εισαγωγή, η Εξαγωγή και η Κυκλική_θέση, και ΟΧΙ το κυρίως πρόγραμμα ούτε η Οπτικοποίηση.
Το κυρίως πρόγραμμα εισάγει τους αριθμούς 1, 2, 3, ..., 10, αλλά ταυτόχρονα κάθε τρίτο στοιχείο κάνει και μια εξαγωγή ώστε να ελεγχθεί και αυτή η λειτουργία. Στο τέλος, εξάγει όλους τους αριθμούς συν ένα, ώστε να ελεγχθεί και η αδυναμία εξαγωγής σε άδεια ουρά.
Τα σύμβολα "ε" και "π" στην Οπτικοποίηση είναι οι δείκτες "εμπρός" και "πίσω".


--- Κώδικας: ΓΛΩΣΣΑ ---ΠΡΟΓΡΑΜΜΑ ΟυρέςΣΤΑΘΕΡΕΣ  ΧΟ = 5                                    ! Χωρητικότητα ουράςΜΕΤΑΒΛΗΤΕΣ  ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείο, ιΑΡΧΗ  εμπρός <- 1  πίσω <- 0  πλήθος <- 0  ΓΡΑΨΕ "Έναρξη:  "  ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος)   ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 2*ΧΟ    ΚΑΛΕΣΕ Εισαγωγή(Ουρά, εμπρός, πίσω, πλήθος, ι) ! Για επίδειξη της Εξαγωγής, κάθε τρία στοιχεία, βγάλε ένα    ΑΝ ι MOD 3 = 0 ΤΟΤΕ      ΚΑΛΕΣΕ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)     ΤΕΛΟΣ_ΑΝ  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ πλήθος + 1    ΚΑΛΕΣΕ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ ΔΙΑΔΙΚΑΣΙΑ Εισαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο) ΣΤΑΘΕΡΕΣ  ΧΟ = 5                                    ! Χωρητικότητα ουράςΜΕΤΑΒΛΗΤΕΣ  ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείοΑΡΧΗ  ΑΝ πλήθος = ΧΟ ΤΟΤΕ    ΓΡΑΨΕ "Ουρά πλήρης, αδυναμία εισαγωγής του ", στοιχείο, ",  "  ΑΛΛΙΩΣ    πλήθος <- πλήθος + 1    πίσω <- Κυκλική_θέση(πίσω + 1)     Ουρά[πίσω] <- στοιχείο    ΓΡΑΨΕ "Εισαγωγή: ", στοιχείο, ",  "  ΤΕΛΟΣ_ΑΝ  ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος) ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ ΔΙΑΔΙΚΑΣΙΑ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο) ΣΤΑΘΕΡΕΣ  ΧΟ = 5                                    ! Χωρητικότητα ουράςΜΕΤΑΒΛΗΤΕΣ  ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείοΑΡΧΗ  ΑΝ πλήθος = 0 ΤΟΤΕ    ΓΡΑΨΕ "Ουρά άδεια, αδυναμία εξαγωγής,  "  ΑΛΛΙΩΣ    πλήθος <- πλήθος - 1    στοιχείο <- Ουρά[εμπρός]     εμπρός <- Κυκλική_θέση(εμπρός + 1)     ΓΡΑΨΕ "Εξαγωγή:  ", στοιχείο, ",  "  ΤΕΛΟΣ_ΑΝ  ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος) ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ ΣΥΝΑΡΤΗΣΗ Κυκλική_θέση(θέση): ΑΚΕΡΑΙΑ! Μετατρέπει μια γραμμική θέση, π.χ. ΧΟ+1, σε κυκλική, π.χ. 1ΣΤΑΘΕΡΕΣ  ΧΟ = 5                                    ! Χωρητικότητα ουράςΜΕΤΑΒΛΗΤΕΣ  ΑΚΕΡΑΙΕΣ: θέσηΑΡΧΗ  Κυκλική_θέση <- (θέση - 1) MOD ΧΟ + 1ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ ΔΙΑΔΙΚΑΣΙΑ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος) ! Αυτή η διαδικασία οπτικοποιεί ωραία μεν,! αλλά γι' αυτό είναι και δύσκολη και όχι προς διδασκαλίαΣΤΑΘΕΡΕΣ  ΧΟ = 5                                    ! Χωρητικότητα ουράςΜΕΤΑΒΛΗΤΕΣ  ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, ιΑΡΧΗ  ΓΡΑΨΕ "Ουρά = [ "  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ ΧΟ    ΑΝ εμπρός = ι ΤΟΤΕ      ΓΡΑΨΕ "ε "    ΤΕΛΟΣ_ΑΝ    ΑΝ πίσω = ι ΤΟΤΕ      ΓΡΑΨΕ "π "    ΤΕΛΟΣ_ΑΝ    ΑΝ ι >= εμπρός ΚΑΙ εμπρός + πλήθος > ι Η      & ι <= πίσω ΚΑΙ πίσω - πλήθος < ι ΤΟΤΕ      ΓΡΑΨΕ Ουρά[ι], " "    ΤΕΛΟΣ_ΑΝ    ΑΝ ι < ΧΟ ΤΟΤΕ      ΓΡΑΨΕ ",  "    ΑΛΛΙΩΣ      ΓΡΑΨΕ "]"    ΤΕΛΟΣ_ΑΝ  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

--- Παράθεση από: Οθόνη εκτέλεσης ---Έναρξη: Ουρά = [ε, , , , ]
Εισαγωγή: 1, Ουρά = [επ1, , , , ]
Εισαγωγή: 2, Ουρά = [ε1, π2, , , ]
Εισαγωγή: 3, Ουρά = [ε1, 2, π3, , ]
Εξαγωγή:  1, Ουρά = [, ε2, π3, , ]
Εισαγωγή: 4, Ουρά = [, ε2, 3, π4, ]
Εισαγωγή: 5, Ουρά = [, ε2, 3, 4, π5]
Εισαγωγή: 6, Ουρά = [π6, ε2, 3, 4, 5]
Εξαγωγή:  2, Ουρά = [π6, , ε3, 4, 5]
Εισαγωγή: 7, Ουρά = [6, π7, ε3, 4, 5]
Ουρά πλήρης, αδυναμία εισαγωγής του 8, Ουρά = [6, π7, ε3, 4, 5]
Ουρά πλήρης, αδυναμία εισαγωγής του 9, Ουρά = [6, π7, ε3, 4, 5]
Εξαγωγή:  3, Ουρά = [6, π7, , ε4, 5]
Εισαγωγή: 10, Ουρά = [6, 7, π10, ε4, 5]
Εξαγωγή:  4, Ουρά = [6, 7, π10, , ε5]
Εξαγωγή:  5, Ουρά = [ε6, 7, π10, , ]
Εξαγωγή:  6, Ουρά = [, ε7, π10, , ]
Εξαγωγή:  7, Ουρά = [, , επ10, , ]
Εξαγωγή:  10, Ουρά = [, , π, ε, ]
Ουρά άδεια, αδυναμία εξαγωγής, Ουρά = [, , π, ε, ]
--- Τέλος παράθεσης ---

akalest0s:
Μια θέση, που μάλλον θα συμφωνήσουμε όλοι, είναι ότι οπωσδήποτε πρέπει να υπάρχει πρόβλεψη για όταν φτάνει στο τέλος του πίνακα, να μπορεί να γεμίζει τυχόν άδεια κελιά αντί να θεωρείται γεμάτη. Για την υλοποίηση μπορούμε να μιλάμε για μέρες, πιστεύω άκρη θα βγει.
Πάντως:

--- Παράθεση ---αν θέλουμε να ζητήσουμε στο Υπουργείο να αντικαταστήσει του χρόνου την υπάρχουσα υλοποίηση με αυτή που θα προτείνουμε εμείς
--- Τέλος παράθεσης ---
ΕΝΝΟΕΙΤΑΙ.

petrosp13:
Η δική μου άποψη είναι ότι για το επίπεδο των μαθητών που έχουμε, η καλύτερη λύση (προς το παρόν τουλάχιστον) είναι να μην διδάσκεται προγραμματιστική εφαρμογή ουράς, λόγω της πολυπλοκότητας της (περιπτώσεις μετακίνησης δεικτών σε εισαγωγή-εξαγωγή, ολίσθηση στοιχείων κτλ.)
Η στοίβα υλοποιείται εύκολα και διδάσκεται και εύκολα
Με την ουρά, μπλέκουμε σε υλοποιήσεις που αφορούν στην καλύτερη περίπτωση φοιτητές πληροφορικής..

akalest0s:
Ο κώδικας των λειτουργιών της ουράς, είναι αρκετά δυσκολομνημόνευτος. Από όλα όσα πρέπει να λάβεις υπόψιν σου, οι μαθητές όλο κάτι ξεχνούν. Κρύβει αρκετές περιπτώσεις που πρέπει να προβλέψεις τον χειρισμό τους, όχι πάντα προφανείς.
Νομίζω όμως ότι με καλή εξήγηση και αρκετή εξάσκηση με ασκήσεις, τα παιδιά τελικά τον κατανοούν και χρησιμοποιούν τις ουρές κατάλληλα. Μήπως ο bubblesort στην αρχή δεν τους φαίνεται αλλόκοτος; Αλλά με τον καιρό, τον πάνε τυφλοσούρτι, και οι καλοί, ξέρουν να στον εξηγήσουν μια χαρά.

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

ilias_s:
Ναι, εννοείται πως καλό θα ήταν να αλλάξουν όλες αυτές οι ανοησίες που υπάρχουν στο μάθημα (τι κάνουν οι Σύμβουλοί/ΣΕΕ του κλάδου τόσα χρόνια?). Προσωπικά στην τάξη σχολίασα την υλοποίηση της Ουράς ακριβώς έτσι (προβληματική).

Σε κάθε περίπτωση η πρόταση καλό είναι να γίνει. Η αδράνεια δεν οφέλησε μακροπρόθεσμ κανένα. Παρόλαυτά δεν ελπίζω σε κάποια αλλαγή, ειδικά αυτή την περίοδο που το υπουργείο ετοιμάζεται (σύμφωνα με την υπουργό μας) για κατάργηση των 7ώρων και εισαγωγή της ρομποτικής "πιλατικά" στην προσχολική εκπαίδευση...

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση