Αποστολέας Θέμα: Καλύτερη υλοποίηση ουράς  (Αναγνώστηκε 1989 φορές)

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5438
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Καλύτερη υλοποίηση ουράς
« στις: 14 Φεβ 2020, 11:55:38 πμ »
Απ' ότι είδα η υλοποίηση της ουράς στο συμπληρωματικό εκπαιδευτικό υλικό είναι κάπως προβληματική. Θέλετε να δούμε εάν προτιμάμε κάποια καλύτερη υλοποίηση, και εάν ναι, να την προτείνουμε στο Υπουργείο;
Προσοχή, αυτό το θέμα ΔΕΝ είναι για το πώς θα τη διδάξουμε φέτος, αλλά για το αν θέλουμε να ζητήσουμε στο Υπουργείο να αντικαταστήσει του χρόνου την υπάρχουσα υλοποίηση με αυτή που θα προτείνουμε εμείς.

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

Εισαγωγή:
    πλήθος <- πλήθος + 1
    πίσω <- Κυκλική_θέση(πίσω + 1)
    Ουρά[πίσω] <- στοιχείο
Εξαγωγή:
    πλήθος <- πλήθος - 1
    στοιχείο <- Ουρά[εμπρός]
    εμπρός <- Κυκλική_θέση(εμπρός + 1)

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

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

Κώδικας: ΓΛΩΣΣΑ
  1. ΠΡΟΓΡΑΜΜΑ Ουρές
  2. ΣΤΑΘΕΡΕΣ
  3.   ΧΟ = 5                                    ! Χωρητικότητα ουράς
  4. ΜΕΤΑΒΛΗΤΕΣ
  5.   ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείο, ι
  6. ΑΡΧΗ
  7.   εμπρός <- 1
  8.   πίσω <- 0
  9.   πλήθος <- 0
  10.   ΓΡΑΨΕ "Έναρξη:  "
  11.   ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος)
  12.   ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 2*ΧΟ
  13.     ΚΑΛΕΣΕ Εισαγωγή(Ουρά, εμπρός, πίσω, πλήθος, ι)
  14. ! Για επίδειξη της Εξαγωγής, κάθε τρία στοιχεία, βγάλε ένα
  15.     ΑΝ ι MOD 3 = 0 ΤΟΤΕ
  16.       ΚΑΛΕΣΕ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)
  17.     ΤΕΛΟΣ_ΑΝ
  18.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  19.   ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ πλήθος + 1
  20.     ΚΑΛΕΣΕ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)
  21.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  22. ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
  23.  
  24. ΔΙΑΔΙΚΑΣΙΑ Εισαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)
  25. ΣΤΑΘΕΡΕΣ
  26.   ΧΟ = 5                                    ! Χωρητικότητα ουράς
  27. ΜΕΤΑΒΛΗΤΕΣ
  28.   ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείο
  29. ΑΡΧΗ
  30.   ΑΝ πλήθος = ΧΟ ΤΟΤΕ
  31.     ΓΡΑΨΕ "Ουρά πλήρης, αδυναμία εισαγωγής του ", στοιχείο, ",  "
  32.   ΑΛΛΙΩΣ
  33.     πλήθος <- πλήθος + 1
  34.     πίσω <- Κυκλική_θέση(πίσω + 1)
  35.     Ουρά[πίσω] <- στοιχείο
  36.     ΓΡΑΨΕ "Εισαγωγή: ", στοιχείο, ",  "
  37.   ΤΕΛΟΣ_ΑΝ
  38.   ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος)
  39. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
  40.  
  41. ΔΙΑΔΙΚΑΣΙΑ Εξαγωγή(Ουρά, εμπρός, πίσω, πλήθος, στοιχείο)
  42. ΣΤΑΘΕΡΕΣ
  43.   ΧΟ = 5                                    ! Χωρητικότητα ουράς
  44. ΜΕΤΑΒΛΗΤΕΣ
  45.   ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, στοιχείο
  46. ΑΡΧΗ
  47.   ΑΝ πλήθος = 0 ΤΟΤΕ
  48.     ΓΡΑΨΕ "Ουρά άδεια, αδυναμία εξαγωγής,  "
  49.   ΑΛΛΙΩΣ
  50.     πλήθος <- πλήθος - 1
  51.     στοιχείο <- Ουρά[εμπρός]
  52.     εμπρός <- Κυκλική_θέση(εμπρός + 1)
  53.     ΓΡΑΨΕ "Εξαγωγή:  ", στοιχείο, ",  "
  54.   ΤΕΛΟΣ_ΑΝ
  55.   ΚΑΛΕΣΕ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος)
  56. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
  57.  
  58. ΣΥΝΑΡΤΗΣΗ Κυκλική_θέση(θέση): ΑΚΕΡΑΙΑ
  59. ! Μετατρέπει μια γραμμική θέση, π.χ. ΧΟ+1, σε κυκλική, π.χ. 1
  60. ΣΤΑΘΕΡΕΣ
  61.   ΧΟ = 5                                    ! Χωρητικότητα ουράς
  62. ΜΕΤΑΒΛΗΤΕΣ
  63.   ΑΚΕΡΑΙΕΣ: θέση
  64. ΑΡΧΗ
  65.   Κυκλική_θέση <- (θέση - 1) MOD ΧΟ + 1
  66. ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
  67.  
  68. ΔΙΑΔΙΚΑΣΙΑ Οπτικοποίηση(Ουρά, εμπρός, πίσω, πλήθος)
  69. ! Αυτή η διαδικασία οπτικοποιεί ωραία μεν,
  70. ! αλλά γι' αυτό είναι και δύσκολη και όχι προς διδασκαλία
  71. ΣΤΑΘΕΡΕΣ
  72.   ΧΟ = 5                                    ! Χωρητικότητα ουράς
  73. ΜΕΤΑΒΛΗΤΕΣ
  74.   ΑΚΕΡΑΙΕΣ: Ουρά[ΧΟ], εμπρός, πίσω, πλήθος, ι
  75. ΑΡΧΗ
  76.   ΓΡΑΨΕ "Ουρά = [ "
  77.   ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ ΧΟ
  78.     ΑΝ εμπρός = ι ΤΟΤΕ
  79.       ΓΡΑΨΕ "ε "
  80.     ΤΕΛΟΣ_ΑΝ
  81.     ΑΝ πίσω = ι ΤΟΤΕ
  82.       ΓΡΑΨΕ "π "
  83.     ΤΕΛΟΣ_ΑΝ
  84.     ΑΝ ι >= εμπρός ΚΑΙ εμπρός + πλήθος > ι Η
  85.       & ι <= πίσω ΚΑΙ πίσω - πλήθος < ι ΤΟΤΕ
  86.       ΓΡΑΨΕ Ουρά[ι], " "
  87.     ΤΕΛΟΣ_ΑΝ
  88.     ΑΝ ι < ΧΟ ΤΟΤΕ
  89.       ΓΡΑΨΕ ",  "
  90.     ΑΛΛΙΩΣ
  91.       ΓΡΑΨΕ "]"
  92.     ΤΕΛΟΣ_ΑΝ
  93.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  94. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Παράθεση από: Οθόνη εκτέλεσης
Έναρξη: Ουρά = [ε, , , , ]
Εισαγωγή: 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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #1 στις: 14 Φεβ 2020, 01:28:01 μμ »
Μια θέση, που μάλλον θα συμφωνήσουμε όλοι, είναι ότι οπωσδήποτε πρέπει να υπάρχει πρόβλεψη για όταν φτάνει στο τέλος του πίνακα, να μπορεί να γεμίζει τυχόν άδεια κελιά αντί να θεωρείται γεμάτη. Για την υλοποίηση μπορούμε να μιλάμε για μέρες, πιστεύω άκρη θα βγει.
Πάντως:
Παράθεση
αν θέλουμε να ζητήσουμε στο Υπουργείο να αντικαταστήσει του χρόνου την υπάρχουσα υλοποίηση με αυτή που θα προτείνουμε εμείς
ΕΝΝΟΕΙΤΑΙ.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2303
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #2 στις: 14 Φεβ 2020, 01:37:14 μμ »
Η δική μου άποψη είναι ότι για το επίπεδο των μαθητών που έχουμε, η καλύτερη λύση (προς το παρόν τουλάχιστον) είναι να μην διδάσκεται προγραμματιστική εφαρμογή ουράς, λόγω της πολυπλοκότητας της (περιπτώσεις μετακίνησης δεικτών σε εισαγωγή-εξαγωγή, ολίσθηση στοιχείων κτλ.)
Η στοίβα υλοποιείται εύκολα και διδάσκεται και εύκολα
Με την ουρά, μπλέκουμε σε υλοποιήσεις που αφορούν στην καλύτερη περίπτωση φοιτητές πληροφορικής..
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #3 στις: 14 Φεβ 2020, 02:31:27 μμ »
Ο κώδικας των λειτουργιών της ουράς, είναι αρκετά δυσκολομνημόνευτος. Από όλα όσα πρέπει να λάβεις υπόψιν σου, οι μαθητές όλο κάτι ξεχνούν. Κρύβει αρκετές περιπτώσεις που πρέπει να προβλέψεις τον χειρισμό τους, όχι πάντα προφανείς.
Νομίζω όμως ότι με καλή εξήγηση και αρκετή εξάσκηση με ασκήσεις, τα παιδιά τελικά τον κατανοούν και χρησιμοποιούν τις ουρές κατάλληλα. Μήπως ο bubblesort στην αρχή δεν τους φαίνεται αλλόκοτος; Αλλά με τον καιρό, τον πάνε τυφλοσούρτι, και οι καλοί, ξέρουν να στον εξηγήσουν μια χαρά.

Γιατί όμως λες ότι είναι για φοιτητές πληροφορικής;
Η αντικειμενοστρέφεια είναι αναβάθμιση του μαθήματος, ενώ η υλοποίηση της ουράς όχι;
Ίσως κάνω λάθος σε αυτό, αλλά προσωπικά θεωρώ πολύ καλύτερο να δίνω τις φετινές παραπάνω ώρες σε κωδικοποιήσεις/ασκήσεις ουράς, παρά σε συζητήσεις αντικειμενοστρέφειας, που πλησιάζουν το "να πιούμε καφεδάκι να τα πούμε".
Αν το υπουργείο παρείχε μια πιο σφιχτή τοποθέτηση στο τι είναι ουρά και πως υλοποιείται, νομίζω δε θα χρειαζόταν όλος αυτός ο ντόρος.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

ilias_s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 392
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #4 στις: 14 Φεβ 2020, 03:00:08 μμ »
Ναι, εννοείται πως καλό θα ήταν να αλλάξουν όλες αυτές οι ανοησίες που υπάρχουν στο μάθημα (τι κάνουν οι Σύμβουλοί/ΣΕΕ του κλάδου τόσα χρόνια?). Προσωπικά στην τάξη σχολίασα την υλοποίηση της Ουράς ακριβώς έτσι (προβληματική).

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

epsilonXi

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 150
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #5 στις: 14 Φεβ 2020, 10:08:11 μμ »
Αλκη, χωρίς να το τσεκάρω προσεκτικά, η υλοποίησή σου καλύπτει και τις περιπτώσεις όπου η εισαγωγή γίνεται σε κενή ουρά, και η εξαγωγή γίνεται σε ουρά που έχει ένα στοιχείο; Το λέω επειδή περίμενα να αλλάζουν front και rear μαζί... το καλύπτεις με το πλήθος;

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5438
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #6 στις: 14 Φεβ 2020, 10:39:58 μμ »
Ναι, π.χ. από το αρχικό παράδειγμα:

Έναρξη: Ουρά = [ε, , , , ]
Εισαγωγή: 1, Ουρά = [επ1, , , , ]

Αυτό ήταν εισαγωγή σε κενή ουρά. Το "πίσω" έδειχνε στη θέση 0 και έγινε 1. Το "εμπρός" έδειχνε στη θέση 1 και παρέμεινε 1. Στην εισαγωγή, μπαίνει ένα στοιχείο (εδώ το "1") στο τέλος της ουράς, οπότε αλλάζει μόνο το πίσω, όχι το εμπρός.

Εξαγωγή:  7, Ουρά = [, , επ10, , ]
Εξαγωγή:  10, Ουρά = [, , π, ε, ]

Αυτό ήταν εξαγωγή σε ουρά με ένα στοιχείο. Και το εμπρός και το πίσω έδειχναν στη θέση 3. Το εμπρός μας δείχνει το πρώτο στοιχείο της ουράς και το πίσω το τελευταίο, οπότε όταν υπάρχει ένα μόνο στοιχείο (εδώ το "10"), δείχνουν και τα δύο σε αυτό. Κατά την εξαγωγή αλλάζει μόνο το εμπρός και αυξάνεται κυκλικά κατά ένα.

epsilonXi

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 150
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #7 στις: 16 Φεβ 2020, 05:00:42 μμ »
βιβλίο σελ.61
«ο εμπρός (front) και ο πίσω (rear) δείκτης, που μας δίνουν τη θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί και τη θέση του στοιχείου που μόλις εισήλθε»

συμπληρωματικό υλικό σελ. 24
«Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου. Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν»

Προφανώς και μπορούν αυτές οι περιγραφές να αλλάξουν αν προταθεί ένας άλλος αλγόριθμος υλοποίησης της ουράς, αλλά προσωπικά δεν θα ήθελα να αλλάξουν γιατί μου φαίνεται ότι είναι ορθές:
- ο front δείχνει τη θέση του στοιχείου που είναι έτοιμο να φύγει
- ο rear δείχνει τη θέση του στοιχείου που που μπήκε πιο πρόσφατα στην ουρά

θέλοντας να είμαι πιο πιστός σε αυτούς τους «ορισμούς» θα προτείνω τα ακόλουθα:

όπου χ = ο ελεύθερος χώρος της ουράς (αρχικά ίσο με το μέγεθός της)
όπου μ = ο δείκτης front (αρχικά μηδέν)
όπου π = ο δείκτης rear (αρχικά μηδέν)

για την εισαγωγή της τιμής Τ στην ουρά A με μέγεθος Ν:

Κώδικας: Bash
  1. αν χ = 0 τότε
  2.   γράψε 'περάστε από Δευτέρα'
  3. αλλιώς
  4.   π <-- (π+Ν) mod Ν + 1 ! π <-- κυκλική_θέση(π)
  5.   Α[π] <-- Τ
  6.   χ <-- χ - 1
  7.   αν μ = 0 τότε
  8.     μ <-- 1
  9.   τέλος_αν
  10. τέλος_αν

για την εξαγωγή στην μεταβλητή Τ από την ουρά Α με μέγεθος Ν:

Κώδικας: Bash
  1. αν χ = Ν τότε
  2.   γράψε 'ουκ αν λάβοις παρά του μη έχοντος'
  3. αλλιώς
  4.   Τ <-- Α[μ]
  5.   μ <-- (μ + Ν) mod N + 1 ! μ <-- κυκλική_θέση(μ)
  6.   χ <-- χ + 1
  7.   αν χ = Ν τότε
  8.     π <-- 0
  9.     μ <-- 0
  10.   τέλος_αν
  11. τέλος_αν



επίσης, αν είναι τις στοίβες και τις ουρές να τις υλοποιούμε με υποπρογράμματα, προσωπικά θα ήθελα και κάτι του στυλ:
διαδικασία αρχικοποίηση(ουρά, εμπρός, πίσω, ελεύθερος_χώρος)
μόνο και μόνο για να μην υπάρχει στον κώδικα του προγράμματος καμμία εντολή εκχώρησης τιμής στις 3 μεταβλητές που θέλω, κι έτσι να έχω την ψευδαίσθηση κάποιας «αυτονομίας» αν το δω ως υποπρόγραμμα, ή κάποιας «ενθυλάκωσης» αν το δω σαν μέθοδο αντικειμένου




alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5438
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #8 στις: 17 Φεβ 2020, 08:41:02 πμ »
Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου.

Σε αυτό νομίζω συμφωνούμε όλοι.

Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν

Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:
  • Μετά την πρώτη εισαγωγή, θέλουμε να δείχνουν και οι δύο δείκτες το πρώτο στοιχείο, rear=1 και front=1.
  • Στις εισαγωγές, θέλουμε να μεταβάλλουμε μόνο τον δείκτη rear. Δεν έχει νόημα να μεταβάλλουμε και τον front. Έτσι και γλυτώνουμε μια ΑΝ και κάνουμε τον κώδικα απλούστατο, μόνο 3 γραμμές.
  • Από τα δύο προηγούμενα bullets συνεπάγεται ότι οι καλύτερες αρχικές τιμές και από πλευράς υλοποίησης και από πλευράς διδασκαλίας είναι rear=0 και front=1.
Αντίστοιχα στις εξαγωγές εννοείται ότι θέλουμε να μεταβάλλουμε μόνο τον δείκτη front.

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #9 στις: 17 Φεβ 2020, 02:32:42 μμ »
Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:
Προ ημερών, αυτή τη σκέψη έκανα, αλλά μετά κάποιο πρόβλημα βρήκα και σταμάτησα, νομίζοντας ότι δεν δουλεύει σωστά. Τώρα που το είπες, ξαναέτρεξα τον κώδικά μου και δεν μπορώ να δω σε τι είχα κολλήσει. Αν όντως δεν υπάρχει πρόβλημα (που δεν βλέπω τι μπορεί να υπάρχει), είναι σαφώς πολύ καλύτερο έτσι.
Όχι μόνο γλιτώνεις μία Αν, αλλά είναι και λίγο "η Αν του ταχυδαχτυλουργού", γιατί δεν σου πάει το μυαλό ότι την χρειάζεσαι. Δύσκολα την θυμάται ο μαθητής.
Έχω σκαλώσει τώρα, γιατί προσπαθώ να θυμηθώ σε τι κόλλησα προχθές και εγκατέλειψα αυτή τη σκέψη...  :( :(
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #10 στις: 17 Φεβ 2020, 03:32:17 μμ »
Παραθέτω εδώ, ένα pdf που έχω, σαν εναλλακτική στο σχολικό βιβλίο. Θα το παραλλάξω, για f=1, r=0, αν δεν βρω κάποιο εμπόδιο (ακόμη σπάω το κεφάλι μου, τι στο καλό με κόλλησε προχθές).
Πιο πολύ το βάζω μήπως κάποιος βοηθηθεί από τη χρήση του, δεν ξέρω αν συνεισφέρει κάτι στη κουβέντα γενικότερα περί υλοποίησης. Θα προτιμούσα αυτό, παρά αυτό που έχουμε στο βιβλίο. Αν βλέπετε κάτι λάθος, είμαι όλος αυτιά..  :angel:

Βάζω και μια εικονίτσα, για πιο γρήγορο τσεκ, μην το κατεβάζετε τσάμπα, όσοι δεν το χρειάζεστε.
« Τελευταία τροποποίηση: 17 Φεβ 2020, 03:44:00 μμ από akalest0s »
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 489
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #11 στις: 17 Φεβ 2020, 04:59:05 μμ »
Το έχω δώσει ξανά. Δεν χρειάζεται η μεταβλητή πλήθος. Μας είναι αδιάφορο το πόσα στοιχεία έχει η ουρά, εκτός από δυο καταστάσεις, ότι η ουρά είναι άδεια, και ότι η ουρά είναι γεμάτη.
Μια περίπτωση είναι το Μπροστά να είναι 0 (Null), δηλαδή η ουρά είναι άδεια.
Η άλλη περίπτωση είναι να έχουμε το Πίσω = Μπροστά που σημαίνει ότι η ουρά είναι γεμάτη.
Έτσι οι αρχικές συνθήκες είναι:
Μπροστά=0 Και Πίσω=1

Αν θέλω να διαβάσω, το Μπροστά=0 θα το αποκλείσει και θα βγει μήνυμα "Λάθος Εξαγωγής, Η ουρά είναι άδεια"
Αν βάλω ένα και το Μπροστά είναι 0 τότε το Μπροστά θα γίνει ίσο με το Πίσω, εδώ 1, θα βάλω στο 1 το στοιχείο και θα μεταβάλλω το Πίσω, στο νέο Πίσω  (1 mod 10)+1, θα δώσει 2.
Ας πούμε ότι συνεχίζω να βάζω δέκα φορές ακόμα. Με την τελευταία εισαγωγή που γεμίζει η ουρά, το Πίσω θα γίνει όσο το Μπροστά και αυτή είναι η συνθήκη που δεν θα επιτρέψει να μπει κάτι άλλο.

Η ουρά θα κρατήσει 10 στοιχεία (αν Ν=10, τότε θα κρατήσει 10 στοιχεία, και όχι Ν-1).
Οι δείκτες Μπροστά και Πίσω παίζουν σε τιμές από 1 έως Ν, και επιπλέον το Μπροστά έχει την τιμή 0 για να δηλώνει την άδεια ουρά.

Αν διαβάσουμε όλα τα στοιχεία, είτε έχουμε ένα, είτε Ν, θα γίνει κάποια στιγμή το Μπροστά=Πίσω, και έτσι το Μπροστά θα γίνει 0.
Με μια δεύτερη ανάγνωση, στην Εξαγωγή από την ουρά ελέγχουμε πρώτα αν το Μπροστά είναι μηδέν, και αν δεν είναι διαβάζουμε το εξαγόμενο από το Μπροστά και αλλάζουμε τιμή στο Μπροστά, και μετά ελέγχουμε αν το ΝΕΟ Μπροστά είναι ίσο με το Πίσω και αν ναι τότε μηδενίζουμε το Μπροστά.
Στην Εισαγωγή, πρώτα κοιτάμε το ΤΩΡΙΝΟ Μπροστά αν είναι ίσο με το Πίσω. Αν ναι τότε δεν μπορούμε να βάλουμε τίποτα. Αν όχι τότε κοιτάμε αν το Μπροστά είναι 0, και αν ναι τότε βάζουμε τιμή στο Μπροστά την ΤΩΡΙΝΗ Πίσω, και μετά παράγουμε την ΝΕΑ Πίσω.

Έτσι μια κυκλική ουρά έχει σχέση με δυο μόνο δείκτες, οι οποίοι έχουν να κάνουν με το πότε τους αλλάζουμε, και τι κατάσταση δηλώνουν πριν και μετά την αλλαγή (το πριν ως ΤΩΡΙΝΗ τιμή και το μετά ως ΝΕΑ τιμή).

Στο προγραμματισμό το να αντιλαμβάνεσαι το τρέχον και το νέο είναι το Α και το Ω.

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


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

ΔΙΑΔΙΚΑΣΙΑ Εισαγωγή_Στοιχείου(Α, Πίσω, Μπροστά, Ουρα)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α, Πίσω, Μπροστά, Ουρα[10]
ΑΡΧΗ
  ΑΝ Πίσω = Μπροστά ΤΟΤΕ
    ΓΡΑΨΕ "Η ουρά γέμισε, δεν θα βάλω το ", Α
  ΑΛΛΙΩΣ
    ΑΝ Μπροστά = 0 ΤΟΤΕ
      Μπροστά <- Πίσω
    ΤΕΛΟΣ_ΑΝ
    Ουρα[Πίσω] <- Α
    Πίσω <- Πίσω mod 10 + 1
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Εξαγωγή_Στοιχείου(Α, Πίσω, Μπροστά, Ουρα)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α, Πίσω, Μπροστά, Ουρα[10]
ΑΡΧΗ
  ΑΝ Μπροστά > 0 ΤΟΤΕ
    Α <- Ουρα[Μπροστά]
    Μπροστά <- Μπροστά mod 10 + 1
    ΑΝ Μπροστά = Πίσω ΤΟΤΕ
      Μπροστά <- 0
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Δείξε(Πίσω, Μπροστά, Ουρα)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Πίσω, Μπροστά, Ουρα[10], ι
ΑΡΧΗ
  ΑΝ Μπροστά = 0 ΤΟΤΕ
    ΓΡΑΨΕ "Η ουρά είναι άδεια"
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ "Αρχή Ουράς ", Μπροστά
    ΑΝ Μπροστά = Πίσω ΤΟΤΕ
      ΓΡΑΨΕ Ουρα[Μπροστά]
      ι <- Μπροστά mod 10 + 1
    ΑΛΛΙΩΣ
      ι <- Μπροστά
    ΤΕΛΟΣ_ΑΝ
    ΟΣΟ ι <> Πίσω ΕΠΑΝΑΛΑΒΕ
      ΓΡΑΨΕ Ουρα[ι]
      ι <- ι mod 10 + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ "Τέλος ουράς ", Πίσω
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5438
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #12 στις: 17 Φεβ 2020, 08:03:59 μμ »
Προσωπικά όπως είπα και παραπάνω, προτιμώ την υλοποίηση με το πλήθος γιατί κάνει μικρότερο και απλούστερο τον κώδικα, δεν χρειάζεται να θυμούνται οι μαθητές ούτε "ΑΝ Μπροστά <> 0" ούτε "Μπροστά <- 0" ούτε "Μπροστά <- Πίσω".

Εννοείται όμως ότι είναι πολύ ανώτερη από με την υλοποίηση με την ολίσθηση, η οποία χρησιμοποιεί ΓΙΑ χωρίς να υπάρχει λόγος και έτσι γίνεται μεγάλη και δυσνόητη. :)

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #13 στις: 17 Φεβ 2020, 09:30:50 μμ »
Προσωπικά όπως είπα και παραπάνω, προτιμώ την υλοποίηση με το πλήθος γιατί κάνει μικρότερο και απλούστερο τον κώδικα, δεν χρειάζεται να θυμούνται οι μαθητές ούτε "ΑΝ Μπροστά <> 0" ούτε "Μπροστά <- 0" ούτε "Μπροστά <- Πίσω".

Εννοείται όμως ότι είναι πολύ ανώτερη από με την υλοποίηση με την ολίσθηση, η οποία χρησιμοποιεί ΓΙΑ χωρίς να υπάρχει λόγος και έτσι γίνεται μεγάλη και δυσνόητη. :)
Δεν τίθεται θέμα. Και για να δώσω μια απάντηση στο op, σαφώς θα προτιμούσα κυκλική υλοποίηση για τις ουρές, στο σχολικό βιβλίο. Επίσης, στις λύσεις ασκήσεων, να προτιμάται από το διδακτικό πακέτο η χρήση υποπρογραμμάτων.

Αν όμως θέλουμε να μείνουμε πιο κοντά στην αρχική υλοποίηση του σχολικού, τότε τουλάχιστον να ζητήσουμε κάτι όπως αυτό που έχω στο pdf, ή με την απλοποίηση f=1, r=0, που το κάνει πραγματικά πανεύκολο (έστω και αν διατηρεί τη γνωστή αδυναμία γεμίσματος/ολίσθησης).
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

fof

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 303
Απ: Καλύτερη υλοποίηση ουράς
« Απάντηση #14 στις: 18 Φεβ 2020, 04:32:28 μμ »
Η υλοποίηση της ουράς στο βιβλίο είναι μια χαρά, ποιος ο λόγος να αλλάξει; Επίσης το θέμα της ολίσθησης αν ζητηθεί από την εκφώνηση του προβλήματος τότε ας εφαρμόζεται και ας σκεφτούν οι μαθητές τον τροπο, υπάρχουν αρκετοί τρόποι επίλυσης για ολίσθηση σε ουρά, γιατί να συγκεκριμενοποιησουμε εναν μονο!.