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

Ξεκίνησε από alkisg, 14 Φεβ 2020, 11:55:38 ΠΜ

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

alkisg

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

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



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

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

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

Κώδικας: glossa
ΠΡΟΓΡΑΜΜΑ Ουρές
ΣΤΑΘΕΡΕΣ
  ΧΟ = 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

Μια θέση, που μάλλον θα συμφωνήσουμε όλοι, είναι ότι οπωσδήποτε πρέπει να υπάρχει πρόβλεψη για όταν φτάνει στο τέλος του πίνακα, να μπορεί να γεμίζει τυχόν άδεια κελιά αντί να θεωρείται γεμάτη. Για την υλοποίηση μπορούμε να μιλάμε για μέρες, πιστεύω άκρη θα βγει.
Πάντως:
Παράθεσηαν θέλουμε να ζητήσουμε στο Υπουργείο να αντικαταστήσει του χρόνου την υπάρχουσα υλοποίηση με αυτή που θα προτείνουμε εμείς
ΕΝΝΟΕΙΤΑΙ.
"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

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

akalest0s

Ο κώδικας των λειτουργιών της ουράς, είναι αρκετά δυσκολομνημόνευτος. Από όλα όσα πρέπει να λάβεις υπόψιν σου, οι μαθητές όλο κάτι ξεχνούν. Κρύβει αρκετές περιπτώσεις που πρέπει να προβλέψεις τον χειρισμό τους, όχι πάντα προφανείς.
Νομίζω όμως ότι με καλή εξήγηση και αρκετή εξάσκηση με ασκήσεις, τα παιδιά τελικά τον κατανοούν και χρησιμοποιούν τις ουρές κατάλληλα. Μήπως ο 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

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

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

epsilonXi

Αλκη, χωρίς να το τσεκάρω προσεκτικά, η υλοποίησή σου καλύπτει και τις περιπτώσεις όπου η εισαγωγή γίνεται σε κενή ουρά, και η εξαγωγή γίνεται σε ουρά που έχει ένα στοιχείο; Το λέω επειδή περίμενα να αλλάζουν front και rear μαζί... το καλύπτεις με το πλήθος;

alkisg

Ναι, π.χ. από το αρχικό παράδειγμα:

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

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

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

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

epsilonXi

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

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

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

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

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

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

Κώδικας: bash
αν χ = 0 τότε
  γράψε 'περάστε από Δευτέρα'
αλλιώς
  π <-- (π+Ν) mod Ν + 1 ! π <-- κυκλική_θέση(π)
  Α[π] <-- Τ
  χ <-- χ - 1
  αν μ = 0 τότε
    μ <-- 1
  τέλος_αν
τέλος_αν


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

Κώδικας: bash
αν χ = Ν τότε
  γράψε 'ουκ αν λάβοις παρά του μη έχοντος'
αλλιώς
  Τ <-- Α[μ]
  μ <-- (μ + Ν) mod N + 1 ! μ <-- κυκλική_θέση(μ)
  χ <-- χ + 1
  αν χ = Ν τότε
    π <-- 0
    μ <-- 0
  τέλος_αν
τέλος_αν




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




alkisg

Παράθεση από: epsilonXi στις 16 Φεβ 2020, 05:00:42 ΜΜ
Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου.

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

Παράθεση από: epsilonXi στις 16 Φεβ 2020, 05:00:42 ΜΜ
Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν

Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:

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

akalest0s

Παράθεση από: alkisg στις 17 Φεβ 2020, 08:41:02 ΠΜ
Σε αυτό διαφωνώ. Οι βέλτιστες αρχικές τιμές είναι 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

#10
Παραθέτω εδώ, ένα pdf που έχω, σαν εναλλακτική στο σχολικό βιβλίο. Θα το παραλλάξω, για f=1, r=0, αν δεν βρω κάποιο εμπόδιο (ακόμη σπάω το κεφάλι μου, τι στο καλό με κόλλησε προχθές).
Πιο πολύ το βάζω μήπως κάποιος βοηθηθεί από τη χρήση του, δεν ξέρω αν συνεισφέρει κάτι στη κουβέντα γενικότερα περί υλοποίησης. Θα προτιμούσα αυτό, παρά αυτό που έχουμε στο βιβλίο. Αν βλέπετε κάτι λάθος, είμαι όλος αυτιά..  :angel:

Βάζω και μια εικονίτσα, για πιο γρήγορο τσεκ, μην το κατεβάζετε τσάμπα, όσοι δεν το χρειάζεστε.
"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

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

Προσωπικά όπως είπα και παραπάνω, προτιμώ την υλοποίηση με το πλήθος γιατί κάνει μικρότερο και απλούστερο τον κώδικα, δεν χρειάζεται να θυμούνται οι μαθητές ούτε "ΑΝ Μπροστά <> 0" ούτε "Μπροστά <- 0" ούτε "Μπροστά <- Πίσω".

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

akalest0s

Παράθεση από: alkisg στις 17 Φεβ 2020, 08:03:59 ΜΜ
Προσωπικά όπως είπα και παραπάνω, προτιμώ την υλοποίηση με το πλήθος γιατί κάνει μικρότερο και απλούστερο τον κώδικα, δεν χρειάζεται να θυμούνται οι μαθητές ούτε "ΑΝ Μπροστά <> 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

Η υλοποίηση της ουράς στο βιβλίο είναι μια χαρά, ποιος ο λόγος να αλλάξει; Επίσης το θέμα της ολίσθησης αν ζητηθεί από την εκφώνηση του προβλήματος τότε ας εφαρμόζεται και ας σκεφτούν οι μαθητές τον τροπο, υπάρχουν αρκετοί τρόποι επίλυσης για ολίσθηση σε ουρά, γιατί να συγκεκριμενοποιησουμε εναν μονο!.

bugman

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

akalest0s

Παράθεση από: fof στις 18 Φεβ 2020, 04:32:28 ΜΜ
υπάρχουν αρκετοί τρόποι επίλυσης για ολίσθηση σε ουρά, γιατί να συγκεκριμενοποιησουμε εναν μονο!.
Ποιος είπε να συγκεκριμενοποιήσουμε έναν μόνο τρόπο;
"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


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

akalest0s

#18
Παράθεση από: fof στις 18 Φεβ 2020, 11:29:17 ΜΜ
Η συζήτηση  αφορά αλλαγές στην παρούσα υλοποιηση της ουράς και της ολίσθησης (όπου δεν αναφέρεται  ως θεωρία στο βιβλίο) . Γιατί; Δεν έχω εντοπίσει το πρόβλημα ακριβώς; Μια χαρά θέμα είναι.
- Χαζή υλοποίηση σε περίπτωση γεμίσματος ουράς (που όμως δεν έχει γεμίσει.. σοβαρά τώρα;)
- Κυκλικός πίνακας ή ολίσθηση: καλό είναι να ξεκαθαρίσει τη θέση του και γιατί όχι, να τα συμπεριλάβει, με μια καλή υλοποίηση. Αν τα θέλει εντός, να τα περιγράψει με ικανό τρόπο. Αν τα θέλει εκτός, να μην τα πετάει στην λύση άσκησης που δεν τα ζητάει, αλλά μόνο αν περιγράφεται με ικανό τρόπο στην εκφώνηση.

Εμένα αυτά δεν μου φαίνονται μια χαρά. Χαζοί οι μαθητές (συνήθως) δεν είναι. Χαζοί φαινόμαστε εμείς με αυτά που καλούμαστε να τους πούμε.

- "Για r=10, θεωρούμε ότι η ουρά έχει γεμίσει"
- "Μα κύριε, αν έχουν γίνει εξαγωγές;"
- "Ναι, ξέρετε.. όντως δεν είναι πραγματικά γεμάτη, αλλά εμείς έτσι θα λέμε!"
- "..."

διάλογος-ομορφιά #2:
- "Αν f=0 και r=0 τότε η ουρά είναι άδεια"
- "Κύριε, γιατί χρειαζόμαστε να τσεκάρουμε και το f και το r, δεν είναι περιττό;"
- "Είναι όντως.."
- "Μα δεν έχετε πει ότι πρέπει να αποφεύγουμε περιττούς ελέγχους στις Αν;"
- "Εεε,..."


Σε αυτό το μάθημα, έχουμε μείνει τόσα χρόνια με τόσες συμβάσεις/παρατυπίες/ασάφειες/κλπ, που σιγά σιγά έχουμε μεταλλαχθεί. Θεωρούμε τα κακογραμμένα "μια χαρά".

Μια χαρά είναι η άσκηση που έβαλες προ ημερών σε ουρές (για την οποία, παρεμπιπτόντως, σε ευχαριστώ). Οι ασκήσεις στο σχολικό σου φαίνονται οκ, με 20 γραμμές εκφώνηση που αποτυχαίνει να ορίσει τι ακριβώς θέλει να πει, με ασάφειες ή και flat out λάθη;
"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

alkisg

@fof, το ερώτημα είναι "έχω μια ουρά με Ν θέσεις, βάζω Ν στοιχεία, βγάζω Ν στοιχεία, άρα η ουρά τώρα είναι άδεια, μπορώ λοιπόν να προσθέσω άλλα";

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

Η διόρθωση των λύσεων είναι απλή, χρειάζεται να χρησιμοποιηθεί η πράξη "mod N" και γίνονται όλα ΟΚ.

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

fof

@akalest0s έχεις δίκιο για τις ασκήσεις συμφωνώ είναι προχειρογραμμενες και γεμάτο ασάφειες. Όσον αφορά την ουρά σωστά τα λέτε .. υπάρχει πολύ καλύτερος τρόπος υλοποίησης (όχι μόνο ένας) σε σχέση με αυτή που περιγράφει το βιβλίο, ομως το βιβλίο περιγράφει μια απλη μορφή της ουρας η οποία δεν εφαρμόζεται απαραιτητα σε εφαρμογές προτεραιότητας, αλλά για παράδειγμα θα μπορουσε να χρησιμοποιηθεί στην αναγνωριση μιας συμβολοσειράς η στην εύρεση στοιχείων κατά πλατος ενός γράφου .

akalest0s

Παράθεση από: fof στις 20 Φεβ 2020, 09:57:17 ΜΜ
για παράδειγμα θα μπορουσε να χρησιμοποιηθεί στην αναγνωριση μιας συμβολοσειράς η στην εύρεση στοιχείων κατά πλατος ενός γράφου .
..με το οποίο δεν διαφωνώ καθόλου.
Και εδώ είναι ένα από τα μεγαλύτερα, αν όχι το μεγαλύτερο, κατά τη γνώμη μου, πρόβλημα, όχι μόνο της πληροφορικής, αλλά και όλων των διδακτικών προσεγγίσεων, σε όλη την υπάρχουσα εκπαίδευση. Ελλιπές ή ανύπαρκτο εμπειρικό πλαίσιο. Η μόνη σύνδεση που επιχειρεί το βιβλίο, του κώδικα με την εμπειρία των μαθητών στη θεωρία, είναι με το αρχικό παράδειγμα με τους φοιτητές και το καράβι. Στο οποίο παράδειγμα δεν έχει νόημα αυτό το "r=M, η ουρά γέμισε". (Ή, αν θεωρήσουμε, με λίγη καλή θέληση, ότι έχει νόημα, τότε αργότερα όταν δημιουργηθεί η προφανής απορία στα παιδιά σε άλλο σημείο, με ποιον τρόπο τους απαντάς;)
Δεν είναι του θέματος, και δεν θα επεκταθώ, αλλά είναι χαρακτηριστικό πως πέφτουμε σε θεωρητικολογίες και απροσδιοριστίες, όταν δεν έχει εμπειρικό αντίκρισμα αυτό που λέμε στα παιδιά. Οι ασκήσεις γίνονται αδιάφορες, και η θεωρία απρόσληπτη.
(Για να μην πω ότι πολλές φορές ούτε εμείς οι καθηγητές δεν έχουμε εμπειρία των όσων διδάσκουμε..)
"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

Τι να πεις τότε για το κεφάλαιο του αντικειμενοστραφους προγραμματισμού; Στο οποίο πετάει ασύνδετες θεωρητικές έννοιες μεσα σε όλα αυτά που έχουν διδαχθεί και έχουν εφαρμόσει όλο το χρονο. Αυτό το κεφάλαιο Ναι θεωρώ πως πρέπει επειγόντως να διορθωθεί.

akalest0s

Παράθεση από: P. TsiotakisΤο κεφάλαιο αυτό πρέπει να αφαιρεθεί από την τρέχουσα μορφή του μαθήματος της Πληροφορικής.
Αυτό να πεις.

Γενικότερα, για να πάρω μια θέση για το αρχικό ζήτημα: ως προς την υλοποίηση που συζητάμε, είτε μια από τις απλουστευμένες μορφές που προτάθηκαν, με την ολίσθηση να είναι απλά ένα δύσκολο θέμα, εκτός βασικής θεωρίας (όπως δηλ. είναι η δυαδική αναζήτηση αυτή τη στιγμή), είτε αυτό που πρότεινε ο Άλκης, με δεδομένο ότι όλος ο κώδικας αυτός μπορεί να θεωρηθεί το πιο δύσκολο σημείο του μαθήματος. Μέσα από ασκήσεις πάντως, μπορεί να εμπεδωθεί.
"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

Vangelis

Η παρουσίαση της λειτουργίας της ουράς έχει πολλά προβλήματα όπως έχει εισαχθεί.
Στον φυσικό κόσμο οι ουρές δουλεύουν με ολίσθηση άρα παιδαγωγικά και επειδή προσπαθούμε τα προβλήματα που βάζουμε να είναι πραγματικά θα έπρεπε να διδάσκεται έτσι. Δεν μπορώ να φανταστώ πρόβλημα στον πραγματικό κόσμου που να υλοποιείται με κυκλική ουρά.   Φυσικά στο τέλος του αντίστοιχου κεφαλαίου θα έπρεπε να υπάρχει η λειτουργία της κυκλικής ουράς με το mod N και να αναφέρεται η μικρότερη πολυπλοκότητα του αλγορίθμου.
Λόγω όλων αυτών των προβλημάτων υποθέτω ότι η ουρά αποτελεί απαγορευμένο θέμα για τις πανελλαδικές για  θέμα 3 ή 4.

alkisg

Παράθεση από: Vangelis στις 23 Φεβ 2020, 04:08:16 ΜΜ
Δεν μπορώ να φανταστώ πρόβλημα στον πραγματικό κόσμου που να υλοποιείται με κυκλική ουρά.

Ένα πολύ ταιριαστό είναι αυτό που είπα πιο πριν, "καθιστή ουρά τράπεζας με καρέκλες". Όταν καθόμαστε σε καρέκλες δεν κάνουμε ολίσθηση.
Επίσης και αυτό με τα νούμερα προτεραιότητας ταιριάζει μια χαρά. Δεν υπάρχει ολίσθηση στα νούμερα προτεραιότητας.
Και σίγουρα μπορούμε να βρούμε πολλά παραδείγματα ακόμα, π.χ. ουρά παιδιών στο "γύρω-γύρω" στην παιδική χαρά που είναι από μόνο του κυκλικό κλπ.

Παράθεση από: Vangelis στις 23 Φεβ 2020, 04:08:16 ΜΜ
Στον φυσικό κόσμο οι ουρές δουλεύουν με ολίσθηση άρα παιδαγωγικά και επειδή προσπαθούμε τα προβλήματα που βάζουμε να είναι πραγματικά θα έπρεπε να διδάσκεται έτσι.

Αυτό δεν ισχύει, απλά επιλέχθηκαν ακατάλληλα παραδείγματα, και επιπρόσθετα προσαρμόστηκαν με λάθος τρόπο. Θα πω κάτι που θα ακουστεί πολύ κουφό, αλλά με δεύτερη σκέψη ισχύει.

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

ΓΙΑ ι ΑΠΟ Ν ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
  Α[ι] <- άνθρωπος
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αυτή είναι η "ολίσθηση" που γίνεται στον φυσικό κόσμο, ενώ εμείς την αναφέρουμε ως:
  Α[1] <- άνθρωπος
...σαν αυτός να μη διέσχισε το διάδρομο αλλά να τηλεμεταφέρθηκε στη θέση 1.

Εννοείται όμως ότι ΔΕΝ θέλουμε τέτοια μοντελοποίηση. Όπως δεν θέλουμε να αναφέρουμε τη "διάσχιση του 1ου ανθρώπου", έτσι δεν θέλουμε να αναφέρουμε και την "διάσχιση=ολίσθηση των επόμενων που μπήκαν λίγη ώρα αργότερα".

Επιπρόσθετα, η λύση του συμπληρωματικού τεύχους δεν κάνει καν συνεχή ολίσθηση, όπως γίνεται στην τράπεζα, δηλαδή κάθε φορά που εξυπηρετείται ένας άνθρωπος που κάνουν όλοι ένα βήμα μπροστά. Κάνει μόνο μια μαζική ολίσθηση όταν rear=N, με πολλά βήματα μπροστά, που δεν αντιστοιχεί.

Τέλος, μπορούμε να κάνουμε όσα αυθεντικά παραδείγματα θέλουμε, αλλά αν είναι Ο(Ν), δεν μπορούμε να τα χρησιμοποιήσουμε για να διδάξουμε ουρές. Η εισαγωγή και εξαγωγή στις ουρές είναι Ο(1), δεν πρέπει να χαθεί η ορθότητα για χάρη του παραδείγματος.
Αντίστοιχα, αν βρούμε κάποιο αυθεντικό παράδειγμα ταξινόμησης σε Ο(Ν^3), δεν μπορούμε να πούμε ότι είναι bubblesort, αφού αυτός είναι Ο(Ν^2).
Ή στα μαθηματικά, αν δεν βρούμε φυσικό λόγο να διδάξουμε πενταπλό επικαμπύλιο ολοκλήρωμα, δεν σημαίνει ότι θα πρέπει να διδάξουμε κάτι άλλο και να το βαφτίσουμε όπως θέλουμε.

bagelis

Η υλοποίηση της κυκλικής ουράς είναι μία ενδιαφέρουσα ιδέα αλλά μήπως μπορεί κάποιος να κάνει σαφές καταρχάς στο πως υλοποιεί την ουρά το σχολικό;

Διαισθάνομαι ότι δεν υπάρχει μία άποψη...

alkisg

Στα περισσότερα σημεία του, το διδακτικό πακέτο δεν αναφέρει τι γίνεται "αν φτάσουμε στο δεξί άκρο του πίνακα".
Στη θεωρία ουρών δεν είναι απαραίτητο να διασαφηνιστεί αυτό, αφού οι ουρές μπορούν να υλοποιηθούν και με λίστες όπου δεν υπάρχει δεξί άκρο.

Η αποφυγή αυτή επίσης σημαίνει ότι όλα είναι καλά, δεν χρειάζεται ούτε mod Ν ούτε ολίσθηση, και οι ουρές είναι Ο(1).
Για παράδειγμα, στην άσκηση ΤΡΑΠΕΖΑ του συμπληρωματικού τεύχους δίνει τον περιορισμό ότι η τράπεζα θα εξυπηρετήσει το πολύ μέχρι 1000 πελάτες και άρα δεν θα φτάσει το δεξί άκρο του πίνακα.

Όμως, στην ενδεικτική λύση της άσκησης ΤΑΧΥΔΡΟΜΕΙΟ στη σελίδα 18 του συμπληρωματικού τεύχους αναφέρεται σε αυτό το ζήτημα και το λύνει κάνοντας ολίσθηση των στοιχείων.
Αυτό είναι προβληματικό, αφού πλέον η ουρά γίνεται Ο(Ν) και έτσι ακυρώνεται το βιβλίο μαθητή που στη σελίδα 98 λέει ότι οι ουρές είναι Ο(1).

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

ApoAntonis

Παράθεση από: alkisg στις 27 Φεβ 2020, 07:39:05 ΠΜ
Για παράδειγμα, στην άσκηση ΤΡΑΠΕΖΑ του συμπληρωματικού τεύχους δίνει τον περιορισμό ότι η τράπεζα θα εξυπηρετήσει το πολύ μέχρι 1000 πελάτες και άρα δεν θα φτάσει το δεξί άκρο του πίνακα.

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

Το έχω ξαναγράψει, η έλλειψη τόνων σε επίσημο υλικό είναι απαράδεκτη (και δημιουργεί προηγούμενα, αφού δεν νομίζω ότι έγινε κατά λάθος).

Vangelis

Παράθεση από: alkisg στις 17 Φεβ 2020, 08:41:02 ΠΜ
Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:

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

Vangelis

Παράθεση από: alkisg στις 23 Φεβ 2020, 05:40:25 ΜΜ
Ένα πολύ ταιριαστό είναι αυτό που είπα πιο πριν, "καθιστή ουρά τράπεζας με καρέκλες". Όταν καθόμαστε σε καρέκλες δεν κάνουμε ολίσθηση.
Επίσης και αυτό με τα νούμερα προτεραιότητας ταιριάζει μια χαρά. Δεν υπάρχει ολίσθηση στα νούμερα προτεραιότητας.
Και σίγουρα μπορούμε να βρούμε πολλά παραδείγματα ακόμα, π.χ. ουρά παιδιών στο "γύρω-γύρω" στην παιδική χαρά που είναι από μόνο του κυκλικό κλπ.

Αυτό δεν ισχύει, απλά επιλέχθηκαν ακατάλληλα παραδείγματα, και επιπρόσθετα προσαρμόστηκαν με λάθος τρόπο. Θα πω κάτι που θα ακουστεί πολύ κουφό, αλλά με δεύτερη σκέψη ισχύει.

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

ΓΙΑ ι ΑΠΟ Ν ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
  Α[ι] <- άνθρωπος
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αυτή είναι η "ολίσθηση" που γίνεται στον φυσικό κόσμο, ενώ εμείς την αναφέρουμε ως:
  Α[1] <- άνθρωπος
...σαν αυτός να μη διέσχισε το διάδρομο αλλά να τηλεμεταφέρθηκε στη θέση 1.

Εννοείται όμως ότι ΔΕΝ θέλουμε τέτοια μοντελοποίηση. Όπως δεν θέλουμε να αναφέρουμε τη "διάσχιση του 1ου ανθρώπου", έτσι δεν θέλουμε να αναφέρουμε και την "διάσχιση=ολίσθηση των επόμενων που μπήκαν λίγη ώρα αργότερα".

Επιπρόσθετα, η λύση του συμπληρωματικού τεύχους δεν κάνει καν συνεχή ολίσθηση, όπως γίνεται στην τράπεζα, δηλαδή κάθε φορά που εξυπηρετείται ένας άνθρωπος που κάνουν όλοι ένα βήμα μπροστά. Κάνει μόνο μια μαζική ολίσθηση όταν rear=N, με πολλά βήματα μπροστά, που δεν αντιστοιχεί.
Θεωρώ ότι στο παράδειγμα με πελατών τράπεζα που κάθονται σε καρέκλες ή έχουν αριθμούς προτεραιότητας πάλι οι πελάτες χρησιμοποιούν ολίσθηση  ανεξάρτητα από τον αριθμό που έχουν ή την καρέκλα που κάθονται σκέπτονται "τώρα είμαι τρίτος  στη σειρά" , "τώρα είμαι δεύτερος" κ.λπ. Δηλαδή πάλι κάνουν μια ολίσθηση.  Η ολίσθηση θα μπορούσε να γίνεται κάθε φορά που εξάγεται ένα στοιχείο.
Τα παραπάνω πάντα από άποψη διδακτικής. Επαναλαμβάνω ότι θα έπρεπε στο τέλος να διδάσκεται και η πραγματική υλοποίηση της ουράς με κυκλική λειτουργία.
Δεν σχολιάζω την "τηλεμεταφορά" γιατί σε όλες τις υλοποιήσεις ουράς μπορεί να λέμε ότι ένα νέο στοιχείο εισάγεται στο "πίσω μέρος" της ουράς αλλά δεν θεωρούμε ότι  διασχίζει την ουρά μέχρι να φτάσει στο σημείο εισαγωγής. 

alkisg

Στο παράδειγμα με τις καρέκλες δεν θα γίνει καμία μετακίνηση. Μάλιστα οι πελάτες δεν πρέπει καν να σκέπτονται "είμαι τρίτος στη σειρά κλπ". Δεν έχουν μυαλό / επεξεργαστές, είναι απλά "δεδομένα" στο πρόβλημα αυτό. Αν τους παρομοιάσουμε με CPUs, τότε δεν μιλάμε πια για ουρές αλλά για παράλληλο προγραμματισμό με Ν επεξεργατές.

Θα χρειαστεί όμως να παρομοιάσουμε την CPU με έναν ταξιθέτη. Με το που μπαίνει κάποιος πελάτης στην τράπεζα, τον τοποθετεί στην κατάλληλη καρέκλα (=θέση "rear" του πίνακα), ενώ όταν είναι ώρα να φύγει κάποιος από την ουρά και να πάει στο ταμείο, παίρνει αυτόν από τη θέση "front".

Είναι αντίστοιχο με το bubble sort, που τους κάνουμε ένα σχηματάκι για να τους εξηγήσουμε. Κι εδώ θα χρειαστεί μια μικρή εξήγηση για το "mod N", την κυκλική θεώρηση των καρεκλών.

Θεωρώ ότι είναι λάθος να διδάξουμε ολίσθηση στις ουρές. Με τον όρο "ολίσθηση" εννοούμε να απασχολήσουμε την CPU Ν φορές σε μία Εισαγωγή. Δηλαδή αν μια ουρά έχει 1 τρις στοιχεία, και μπει ένα ακόμα, η διαφορά είναι αν θα μετακινηθούν 1 τρις στοιχεία ή κανένα. Το Ο(1) με το Ο(Ν) είναι μέρα με τη νύχτα.

thaaanos

από τις τρεις υλοποιήσεις, του βιβλίου είναι νομίζω η χειρότερη,

προσωπικά δεν βλέπω κανένα πρόβλημα, με την κυκλική ουρά -είναι η πιο 'καθαρη'- και την απλή χρήση του τελεστή mod. Αν μη τι  άλλο να δείξουμε και σε τι χρησιμεύει...
Τώρα για ολίσθηση δεν το συζητάω καν
παραθέτω συνημμένα.
Αυτό που με προβλημάτισε είναι οι έλεγχοι για γεμάτη/άδεια δομή, ευθύνη του χρήστη; η της δομής;

junior

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

Βάζω και μια εικονίτσα, για πιο γρήγορο τσεκ, μην το κατεβάζετε τσάμπα, όσοι δεν το χρειάζεστε.

Μήπως στην προτεινόμενη υλοποίηση της εισαγωγής ΜΕ ολίσθηση έχει γίνει κάποιο λάθος ;

ΑΝ r = N ΤΟΤΕ               ! Αν r στο τέλος του πίνακα
  ΑΝ f > 1 ΤΟΤΕ              ! αλλά υπάρχει χώρος
    k <- 1
    ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r
      Q[k] <- Q             !ολίσθηση
      k <- k + 1               !    >>
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ       !Στο τέλος της επανάληψης η μεταβλητή k θα έχει τιμή +1 παραπάνω από το σύνολο των στοιχείων της ουράς
    f <- 1
    r <- k                  !οπότε εδώ ο δείκτης r δείχνει όχι στο τέλος της ουράς αλλά σε +1
    r <- r + 1            ! εισαγωγή
    Q[r] <- input       !      >>
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ " Ουρά γεμάτη, αδυναμία εισαγωγής "
  ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ ...
 
Μήπως το σωστό θα ήταν

ΑΝ r = N ΤΟΤΕ              ! Αν r στο τέλος του πίνακα
  ΑΝ f > 1 ΤΟΤΕ            ! αλλά υπάρχει χώρος
    k <- 0
    ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r
      k <- k + 1                !ολίσθηση
      Q[k] <- Q             !    >>
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ   
    f <- 1             
    r <- k             
    ΔΙΑΒΑΣΕ input         !εισαγωγή
    r <- r + 1                !    >>
    Q[r] <- input           !   >>
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ " Ουρά γεμάτη, αδυναμία εισαγωγής "
  ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ ...

mousipower

Τυχαία πέτυχα την ωραία "θεωρητική" συζήτηση που κάνετε από πέρσι για την προσέγγιση-υλοποίηση που πρέπει να κάνουμε σε μια ουρά. Εγώ μόλις τελείωσα τη λύση των ασκήσεων  σε ουρές αποτρέποντας τους μαθητές μου να κοιτούν τα εκτρώματα των "ενδεικτικών " ευτυχώς λύσεων του βιβλίου της ουράς ειδικά στην άσκηση 6 .
Πέρυσι αποφύγαμε την ολίσθηση με οδηγίες άνωθεν φέτος σε επικοινωνία με τον σύμβουλο,  το έθεσε πολύ ευγενικά, πρέπει να την εξηγήσουμε-υλοποιήσουμε οπότε αναγκαστικά την εξήγησα.
Η κοινή λογική με αναγκάζει να αναφέρω ότι η υλοποίηση μιας "κυκλικής ουράς" είναι αρκετά δυσκολοχώνευτη υπόθεση για τους  μαθητές, ειδικά με την τηλεκπαίδευση, μιας και δεν μπορώ να δω τον τρόμο και την απόγνωση στα πρόσωπά τους τη ώρα που θα την εξηγώ. Μπορώ όμως να υλοποιήσω μια ολίσθηση η οποία βασίζεται στην πρακτική που χρησιμοποιούν καθημερινά στη ζωή τους: δεν περιμένουμε να γεμίσει η ουρά (στην εισαγωγή) και τότε να μετακινήσουμε  όλη την ουρά στις άδειες θέσεις στην αρχή της ουράς, αν υπάρχουν, αλλά με την εξυπηρέτηση (στην εξαγωγή) του πρώτου της ουράς μετακινούνται όλοι μια θέση μπροστά και έτσι ο δείκτης front είναι πάντα 1! και προσέχουμε να αλλάξουμε rear <-- rear - 1.
Από τη ζωή βγαλμένο και γλιτώνουμε τους μαθητές μας από μια επίπονη διαδικασία, εκτός αν η κουβέντα γίνεται αποκλειστικά για την δική μας επάρκεια οπότε ζητώ συγνώμη δεν θέλω να  θεωρηθώ εξυπνάκιας (άλλωστε είμαι πολύ γέρος γι' αυτό).
Παραθέτω τρείς λύσεις που έχω δώσει στα παιδιά μου και θα ήθελα feedback αν θεωρεί κάποιος ότι υπάρχει κάποια χοντράδα ή κάτι πραγματικά μου ξέφυγε και λόγω ηλικίας δεν το βλέπω. Προσπαθώ να είμαι όσο πιο κοντά στην εισαγωγή-εξαγωγή του βιβλίου σελ. 26 και φυσικά δεν υπάρχει ποτέ περίπτωση να ελέγξω front > rear προτιμώ να πάω σε μια γραμματεία να συμπληρώνω φύλλα excel, αυτό δυστυχώς είναι μπηχτή για τις απείρου κάλλους "ενδεικτικές" λύσεις που  τους το δώσαν και σε βιβλίο..
Υ.Γ. Για να αποφύγουμε τα 5 και 6 φωλιασμένα επίπεδα ελέγχων σε ουρές - στοίβες  είναι απαραίτητο να διδάσκονται  πρώτα τα  υποπρογράμματα, γιατί μετά από 2 -3 σελίδες πρόγραμμα έχουν χάσει όλα τα Τελος_αν και Τέλος_επανάληψης και πάντα ξεχνάνε να κλείσουν κάτι.(θυμάμαι στη σχολή μάς λέγανε μέχρι 3 επίπεδα να κατεβαίνουμε στο 4ο καιγόμαστε). Σίγουρα  θα ξανακάνω 2 ασκήσεις με χρήση διαδικασιών αργότερα για να σπάσει αυτό το "σεντόνι".
Αν σας κούρασα συγνώμη, θα ξαναμπώ στη τρύπα μου και θα σας αφήσω ήσυχους να συνεχίσετε να "ψάχνεστε", καλό είναι να έχεις όρεξη. Καλή δύναμη!!

mousipower

Αφού δεν το διόρθωσε κανείς το ξαναστέλνω διορθωμένο και τέλος.... >:D

mousipower

Ο ΔΑΙΜΩΝ του τυπογραφείου ξαναχτύπησε και φυσικά λείπει ένα ΤΕΛΟΣ_ΑΝ, αυτά που έλεγα (πάνω από 3 επίπεδα κάνει τζιζ)  ..

Γιάννης Αναγνωστάκης

Μετακινήθηκε σε άλλο thread..

tsioulak

Παράθεση από: mousipower στις 18 Φεβ 2021, 01:58:58 ΜΜ
Τυχαία πέτυχα την ωραία "θεωρητική" συζήτηση που κάνετε από πέρσι για την προσέγγιση-υλοποίηση που πρέπει να κάνουμε σε μια ουρά. Εγώ μόλις τελείωσα τη λύση των ασκήσεων  σε ουρές αποτρέποντας τους μαθητές μου να κοιτούν τα εκτρώματα των "ενδεικτικών " ευτυχώς λύσεων του βιβλίου της ουράς ειδικά στην άσκηση 6 .
Πέρυσι αποφύγαμε την ολίσθηση με οδηγίες άνωθεν φέτος σε επικοινωνία με τον σύμβουλο,  το έθεσε πολύ ευγενικά, πρέπει να την εξηγήσουμε-υλοποιήσουμε οπότε αναγκαστικά την εξήγησα.
Η κοινή λογική με αναγκάζει να αναφέρω ότι η υλοποίηση μιας "κυκλικής ουράς" είναι αρκετά δυσκολοχώνευτη υπόθεση για τους  μαθητές, ειδικά με την τηλεκπαίδευση, μιας και δεν μπορώ να δω τον τρόμο και την απόγνωση στα πρόσωπά τους τη ώρα που θα την εξηγώ. Μπορώ όμως να υλοποιήσω μια ολίσθηση η οποία βασίζεται στην πρακτική που χρησιμοποιούν καθημερινά στη ζωή τους: δεν περιμένουμε να γεμίσει η ουρά (στην εισαγωγή) και τότε να μετακινήσουμε  όλη την ουρά στις άδειες θέσεις στην αρχή της ουράς, αν υπάρχουν, αλλά με την εξυπηρέτηση (στην εξαγωγή) του πρώτου της ουράς μετακινούνται όλοι μια θέση μπροστά και έτσι ο δείκτης front είναι πάντα 1! και προσέχουμε να αλλάξουμε rear <-- rear - 1.
Από τη ζωή βγαλμένο και γλιτώνουμε τους μαθητές μας από μια επίπονη διαδικασία, εκτός αν η κουβέντα γίνεται αποκλειστικά για την δική μας επάρκεια οπότε ζητώ συγνώμη δεν θέλω να  θεωρηθώ εξυπνάκιας (άλλωστε είμαι πολύ γέρος γι' αυτό).
Παραθέτω τρείς λύσεις που έχω δώσει στα παιδιά μου και θα ήθελα feedback αν θεωρεί κάποιος ότι υπάρχει κάποια χοντράδα ή κάτι πραγματικά μου ξέφυγε και λόγω ηλικίας δεν το βλέπω. Προσπαθώ να είμαι όσο πιο κοντά στην εισαγωγή-εξαγωγή του βιβλίου σελ. 26 και φυσικά δεν υπάρχει ποτέ περίπτωση να ελέγξω front > rear προτιμώ να πάω σε μια γραμματεία να συμπληρώνω φύλλα excel, αυτό δυστυχώς είναι μπηχτή για τις απείρου κάλλους "ενδεικτικές" λύσεις που  τους το δώσαν και σε βιβλίο..
Υ.Γ. Για να αποφύγουμε τα 5 και 6 φωλιασμένα επίπεδα ελέγχων σε ουρές - στοίβες  είναι απαραίτητο να διδάσκονται  πρώτα τα  υποπρογράμματα, γιατί μετά από 2 -3 σελίδες πρόγραμμα έχουν χάσει όλα τα Τελος_αν και Τέλος_επανάληψης και πάντα ξεχνάνε να κλείσουν κάτι.(θυμάμαι στη σχολή μάς λέγανε μέχρι 3 επίπεδα να κατεβαίνουμε στο 4ο καιγόμαστε). Σίγουρα  θα ξανακάνω 2 ασκήσεις με χρήση διαδικασιών αργότερα για να σπάσει αυτό το "σεντόνι".
Αν σας κούρασα συγνώμη, θα ξαναμπώ στη τρύπα μου και θα σας αφήσω ήσυχους να συνεχίσετε να "ψάχνεστε", καλό είναι να έχεις όρεξη. Καλή δύναμη!!

Παράθεση από: mousipower στις 19 Φεβ 2021, 10:31:17 ΠΜ
Αφού δεν το διόρθωσε κανείς το ξαναστέλνω διορθωμένο και τέλος.... >:D

Παράθεση από: Γιάννης Αναγνωστάκης στις 28 Φεβ 2021, 06:12:26 ΜΜ
Μετακινήθηκε σε άλλο thread..

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

tsioulak

#39
Παράθεση από: thaaanos στις 10 Απρ 2020, 06:44:57 ΜΜ
από τις τρεις υλοποιήσεις, του βιβλίου είναι νομίζω η χειρότερη,

προσωπικά δεν βλέπω κανένα πρόβλημα, με την κυκλική ουρά -είναι η πιο 'καθαρη'- και την απλή χρήση του τελεστή mod. Αν μη τι  άλλο να δείξουμε και σε τι χρησιμεύει...
Τώρα για ολίσθηση δεν το συζητάω καν
παραθέτω συνημμένα.
Αυτό που με προβλημάτισε είναι οι έλεγχοι για γεμάτη/άδεια δομή, ευθύνη του χρήστη; η της δομής;

Είναι η ιδέα μου ή στην πρώτη εισαγωγή δεν το βάζεις στην θέση 1 αλλά στην θέση 2;
Στην υλοποίηση της κυκλικής ουράς αναφέρομαι.

mousipower

Παράθεση από: tsioulak στις 28 Φεβ 2021, 08:31:08 ΜΜ
Αν κατάλαβα καλά στην 2η υλοποίηση κάνεις ολίσθηση κάθε φορά που κάνεις εξαγωγή, αυτό αυξάνει κατά πολύ την πολυπλοκότητα του κώδικα, να υποθέσω ότι το έκανες επειδή είναι κάπως πιο εύκολο για να το καταλάβουν οι μαθητές; ή μήπως το έκανες για να δείξεις στους μαθητές και αυτήν την περίπτωση; (μήπως και πέσει)

Νομίζω είναι πιο κατανοητό και εύκολο (οι ίδιοι μου το είπαν, ευτυχώς δεν κάνουμε πολυπλοκότητα ή βελτιστοποίηση αλγόριθμου), αλλιώς η λύση του βιβλίου και αν ήταν δυσνόητη και πολύπλοκη!!

thanasisgr

θεωρώ ότι η κυκλική ουρά ξεφεύγει από τους σκοπούς του μαθήματος.

Φιλικά
Θανάσης

thaaanos

Παράθεση από: tsioulak στις 01 Μαρ 2021, 12:12:12 ΠΜ
Είναι η ιδέα μου ή στην πρώτη εισαγωγή δεν το βάζεις στην θέση 1 αλλά στην θέση 2;
Στην υλοποίηση της κυκλικής ουράς αναφέρομαι.
Ναι αν θυμάμαι καλά θυσιάζεται μια θέση για να γίνεται ο διαχωρισμός μεταξύ των καταστάσεων γεμάτη-άδεια η θέση με το *, μπορεί να κρατηθεί σε ξεχωριστή μεταβλητή αυτό αλλά θα πρεπει να προστεθεί στην και στη λίστα ορισμάτων