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

Υλοποίηση ουράς

<< < (2/2)

George Eco:

--- Παράθεση από: alkisg στις 21 Απρ 2021, 05:32:00 μμ ---Αν τώρα γίνει η στραβή και μπει τέτοιο θέμα, θα πρέπει οι βαθμολογητές να δεχτούν οπωσδήποτε ως σωστή μια κυκλική λύση, προστατεύοντας τους "υπερβολικά καλούς" μαθητές

--- Τέλος παράθεσης ---
Συμφωνώ απόλυτα.
Αλλά αυτό ΔΕ συνέβη το 2018. Θέλω να πω το 2018 αν στο Β2 έλεγες πως είναι αδύνατο να υλοποιηθεί τμήμα προγράμματος σε ΓΛΩΣΣΑ που να εκτελεί ακριβώς την ίδια ακολουθία εντολών (βημάτων) με το αδόμητο διάγραμμα ροής, θα υπήρχαν εξεταστές που θα μηδένιζαν το θέμα αντί να δώσουν άριστα. Κι όμως, ένα παιδί που θα έλεγε αυτό και θα επεξηγούσε την απαίτηση να υπάρχει GOTO, αλλά λόγω απουσίας της στη ΓΛΩΣΣΑ δε γίνεται το αδόμητο να υλοποιηθεί ΑΚΡΙΒΩΣ, καταλήγουμε σε μεγάλη αδικία.

Ας αποφύγουν επίμαχα σημεία.


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


thaaanos:
Ύστερα από αρκετή σκέψη κατέληξα οτι η ολίσθηση δεν είναι και "τόσο κακή" αρκεί να γίνεται μόνο όποτε χρειάζεται όταν πχ ο δείκτης rear φτάσει στο max και ο front>1 και όχι σε κάθε απώθηση που αλλοιώνει την πολυπλοκότητα.
Δεν είναι εξάλλου λίγες οι δομές που αναδιάτασουν τα δεδομένα τους η προβαίνουν σε εργασίες "συντήρησης" όποτε χρειαστεί.
Θα μπορούσε κάποιος να πεί οτι είναι ένα είδος garbage collection.

Για μένα η μέγαλύτερη χαζομάρα είναι η
Α) Η αρχικοποιηση στο (f,r)=(0,0) με αποτέλεσμα την ανάγκη έξτρα συνθήκης στην μετάβαση από και πρός κενη ουρά, αν αρχικοποιουνταν οι δείκτες στο  (f,r)=(1,0) θα ήταν πίο απλός ο αλγόριθμος εισαγωγής και εξαγωγής.

Β) Η μή χρήση υποπρογραμμάτων για τις λειτουργίες της. Εγώ έτσι το διδάσκω πάντως και ας επιμένουν τα παιδία να προτιμούν να τις ενσωματώνουν στο κυρίως πρόγραμμα (δύσκολο να πας κόντρα στο βιβλίο και στο φροντιστήριο).

Η κύκλική ουρά όσες φορές και αν την έδειξα μάλλον μάταιος κόπος.

alkisg:

--- Παράθεση από: thaaanos στις 11 Μαΐ 2021, 02:03:34 μμ ---Ύστερα από αρκετή σκέψη κατέληξα οτι η ολίσθηση δεν είναι και "τόσο κακή" αρκεί να γίνεται μόνο όποτε χρειάζεται όταν πχ ο δείκτης rear φτάσει στο max και ο front>1 και όχι σε κάθε απώθηση που αλλοιώνει την πολυπλοκότητα.

--- Τέλος παράθεσης ---

Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:


--- Παράθεση από: https://en.wikipedia.org/wiki/Time_complexity ---...one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity,...
--- Τέλος παράθεσης ---

Για την κυκλική, δεν είναι απαραίτητο να χρησιμοποιηθεί mod, γίνεται και με ΑΝ, π.χ. "Αν δείκτης < Ν, τότε δείκτης <- Ν+1, αλλιώς δείκτης <- 1`. Δηλαδή καταλαβαίνουν την ευκλείδεια διαίρεση και όχι μια τέτοια ΑΝ;

thaaanos:

--- Παράθεση από: alkisg στις 11 Μαΐ 2021, 02:57:35 μμ ---Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:

Για την κυκλική, δεν είναι απαραίτητο να χρησιμοποιηθεί mod, γίνεται και με ΑΝ, π.χ. "Αν δείκτης < Ν, τότε δείκτης <- Ν+1, αλλιώς δείκτης <- 1`. Δηλαδή καταλαβαίνουν την ευκλείδεια διαίρεση και όχι μια τέτοια ΑΝ;

--- Τέλος παράθεσης ---

--- Παράθεση από: alkisg στις 11 Μαΐ 2021, 02:57:35 μμ ---Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:

--- Τέλος παράθεσης ---
Νομίζω οτι στις πράξεις των δομών πάμε με amortized ανάλυση

Πλοήγηση

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

[*] Προηγούμενη σελίδα

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