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

Ξεκίνησε από gpapargi, 21 Απρ 2021, 11:36:06 ΠΜ

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

gpapargi

Έχω μεγάλο πρόβλημα στο πως να διδάξω την υλοποίηση της ουράς. Αυτό που έχει μέσα το βιβλίο είναι προφανώς λάθος αφού τα στοιχεία είναι μονής χρήσεως σε κάποιες περιπτώσεις. Θα ήταν πολύ καλύτερη μια κυκλική υλοποίηση με mod ή και με "Αν" έστω και αν έφτιαχνα ένα υποπρόγραμμα που έπαιρνε την τρέχουσα τιμή του δείκτη και μου γύριζε την επόμενη (και μέσα έκρυβα το πως βρίσκω την επόμενη τιμή).
Το θέμα είναι τι διδάσκω. Δυσκολεύομαι να διδάξω κάτι που ξέρω ότι είναι λάθος. Από την άλλη φοβάμαι να διδάξω και το σωστό γιατί υπάρχουν και οι πανελλήνιες. Έχει κανείς απάντηση;
Γιώργος Παπαργύρης

andreas_p

Διδάσκουμε την ουρά  , ΟΧΙ κυκλικά , αλλά σειριακά. (Σε περίπτωση ολίσθησης)

gpapargi

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

alkisg

Τα ίδια παράπονα είχα κάνει κι εγώ σε παλιότερο θέμα: https://alkisg.mysch.gr/steki/index.php?topic=8149.0

Εντωμεταξύ, τα τετράδια μαθητή, ενδεικτικές λύσεις ασκήσεων κλπ, ΔΕΝ θεωρούνται ως εξεταστέα ύλη, σωστά; Η ολίσθηση υπάρχει μόνο στην λύση της άσκησης με το ταχυδρομείο, δεν αναφέρεται αλλού.

Νομίζω ότι το καλύτερο θα είναι:

  • Η επιτροπή να μην βάλει φέτος άσκηση με ολίσθηση.
  • Για του χρόνου, η ενδεικτική λύση της άσκησης με το ταχυδρομείο να αλλάξει ώστε να γίνει επιστημονικά σωστή, Εισαγωγή = Ο(1). Είτε ΑΝ είτε mod, όχι ΓΙΑ. Για ποιο λόγο να κάνει κανείς επανάληψη όταν δεν χρειάζεται?!
  • Προς το παρόν για τους διδάσκοντες και τους μαθητές, μάλλον ισχύει η λογική του στρατού... "εκτελώ τη διαταγή αλλά υποβάλλω αναφορά με τις αντιρρήσεις μου". Λέμε στους μαθητές τι γράφει το διδακτικό πακέτο, κι ας παραπονιόμαστε γι' αυτό.
  • Αν τώρα γίνει η στραβή και μπει τέτοιο θέμα, θα πρέπει οι βαθμολογητές να δεχτούν οπωσδήποτε ως σωστή μια κυκλική λύση, προστατεύοντας τους "υπερβολικά καλούς" μαθητές.

ApoAntonis

Παράθεση από: alkisg στις 21 Απρ 2021, 05:32:00 ΜΜ
Εντωμεταξύ, τα τετράδια μαθητή, ενδεικτικές λύσεις ασκήσεων κλπ, ΔΕΝ θεωρούνται ως εξεταστέα ύλη, σωστά;

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

Παράθεση από: alkisg στις 21 Απρ 2021, 05:32:00 ΜΜ
Η ολίσθηση υπάρχει μόνο στην λύση της άσκησης με το ταχυδρομείο, δεν αναφέρεται αλλού.

ΠΙΑΣΤΟ ΤΟ ΑΒΓΟ ΚΑΙ ΚΟΥΡΕΥΤΟ:
(από τις οδηγίες)

Να παρουσιαστεί η διαδικασία της «ολίσθησης» των στοιχείων μιας ουράς για την αξιοποίηση όλων των θέσεών
της, στην περίπτωση που ζητείται από την περιγραφή του προβλήματος. Για να μην υπάρξουν κενές, μη
αξιοποιήσιμες, θέσεις στην αρχή της ουράς, υλοποιείται «ολίσθηση». Ως «ολίσθηση» (shift) περιγράφουμε τη
μετακίνηση των περιεχομένων της ουράς, ώστε οι κενές θέσεις προς εισαγωγή νέων στοιχείων να βρίσκονται στο
πίσω μέρος της ουράς. Αν δεν πραγματοποιηθεί ολίσθηση, τότε θεωρούμε ότι η ουρά είναι γεμάτη όταν περιέχει
στοιχείο στην τελευταία της θέση.


Τι σημαίνει "να παρουσιαστεί"; Εγώ το καταλαβαίνω ότι ανήκει στην διδακτέα.

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 ανάλυση

Εβελινακι

Καλησπέρα σε όλους! Έχω πρόβλημα σε μια πολύ δύσκολη άσκηση (κατ'εμε) και θα ήθελα τη βοήθεια σας.
Η άσκηση λέει: 
Προκειμένου ένας πολίτης να πληρώσει τον λογαριασμό του στη ΔΕΗ λαμβάνει αυτόματα έναν αύξοντα διαδοχικό αριθμό προτεραιότητας που καθορίζει τη σειρά του στην ουρά του ταμείου η οποία δε μπορεί να ξεπερνάει τα 30 άτομα. Ο ταμίας εξυπηρετεί τον πρώτο πελάτη που βρίσκεται στην ουρά και η εξυπηρέτηση διαρκεί 3 λεπτά κατά μέσο όρο. Επομένως κάθε πολίτης που περιμένει στην ουρά περιμένει κατά μέσο όρο 3 λεπτά για κάθε έναν που βρίσκεται στην ουρά πριν απ' αυτόν. Να αναπτύξετε προγραμμα σε ΓΛΩΣΣΑ το οποίο: 

1) Εμφανίζει ένα μενού με τις επιλογές «ΕΙΣΑΓΩΓΗ», «ΕΞΑΓΩΓΗ», «ΤΕΡΜΑΤΙΣΜΟΣ» ως πιθανές ενέργειες. 
•Αν δοθεί η ενέργεια «ΕΙΣΑΓΩΓΗ» Πότε διαβάζει το ονοματεπώνυμό του πελάτη και αν η ουρά έχει γεμίσει εμφανίζει το μήνυμα «Ελάτε σε 3 ώρες», Διαφορετικά τον τοποθετεί σε ουρά ΟΝ 30 θέσεων και εμφανίζει το πλήθος των ατόμων που περιμένουν στην ουρά πριν από αυτόν καθώς και τον εκτιμώμενο χρόνο αναμονής.
•Αν δοθεί η ενέργεια «ΕΞΑΓΩΓΗ» Εμφανίζει το ονοματεπώνυμο του πολίτη που θα  εξυπηρετηθεί. 
(Η διαδικασία επαναλαμβάνεται μέχρι να δοθεί η επιλογή «ΤΕΡΜΑΤΙΣΜΟΣ»)

2) Μετά το τέλος την εξυπηρέτησης εμφανίζει: 
•Το πλήθος των πολιτών που εξυπηρετήθηκαν.
•Τον μέσο χρόνο αναμονής των πολιτών.

(Θεωρήστε ότι θα εισέλθει τουλάχιστον ένας πελάτης στη ΔΕΗ) 

Χρειάζομαι επείγοντος βοήθεια και ευχαριστώ πολύ εκ των προτέρων!🙏🏼

Κανένας

#10
Παράθεση από: Εβελινακι στις 18 Δεκ 2022, 05:58:49 ΜΜΚαλησπέρα σε όλους! Έχω πρόβλημα σε μια πολύ δύσκολη άσκηση (κατ'εμε) και θα ήθελα τη βοήθεια σας.
Η άσκηση λέει:
Προκειμένου ένας πολίτης να πληρώσει τον λογαριασμό του στη ΔΕΗ λαμβάνει αυτόματα έναν αύξοντα διαδοχικό αριθμό προτεραιότητας που καθορίζει τη σειρά του στην ουρά του ταμείου η οποία δε μπορεί να ξεπερνάει τα 30 άτομα. Ο ταμίας εξυπηρετεί τον πρώτο πελάτη που βρίσκεται στην ουρά και η εξυπηρέτηση διαρκεί 3 λεπτά κατά μέσο όρο. Επομένως κάθε πολίτης που περιμένει στην ουρά περιμένει κατά μέσο όρο 3 λεπτά για κάθε έναν που βρίσκεται στην ουρά πριν απ' αυτόν. Να αναπτύξετε προγραμμα σε ΓΛΩΣΣΑ το οποίο:

1) Εμφανίζει ένα μενού με τις επιλογές «ΕΙΣΑΓΩΓΗ», «ΕΞΑΓΩΓΗ», «ΤΕΡΜΑΤΙΣΜΟΣ» ως πιθανές ενέργειες.
•Αν δοθεί η ενέργεια «ΕΙΣΑΓΩΓΗ» Πότε διαβάζει το ονοματεπώνυμό του πελάτη και αν η ουρά έχει γεμίσει εμφανίζει το μήνυμα «Ελάτε σε 3 ώρες», Διαφορετικά τον τοποθετεί σε ουρά ΟΝ 30 θέσεων και εμφανίζει το πλήθος των ατόμων που περιμένουν στην ουρά πριν από αυτόν καθώς και τον εκτιμώμενο χρόνο αναμονής.
•Αν δοθεί η ενέργεια «ΕΞΑΓΩΓΗ» Εμφανίζει το ονοματεπώνυμο του πολίτη που θα  εξυπηρετηθεί.
(Η διαδικασία επαναλαμβάνεται μέχρι να δοθεί η επιλογή «ΤΕΡΜΑΤΙΣΜΟΣ»)

2) Μετά το τέλος την εξυπηρέτησης εμφανίζει:
•Το πλήθος των πολιτών που εξυπηρετήθηκαν.
•Τον μέσο χρόνο αναμονής των πολιτών.

(Θεωρήστε ότι θα εισέλθει τουλάχιστον ένας πελάτης στη ΔΕΗ)

Χρειάζομαι επείγοντος βοήθεια και ευχαριστώ πολύ εκ των προτέρων!🙏🏼
ΠΡΟΓΡΑΜΜΑ ΔΕΗ
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: ΟΥΡΑ[30],ΟΝΟΜΑ
ΑΚΕΡΑΙΕΣ: choice,front,rear,π,Ι,Σ
ΠΡΑΓΜΑΤΙΚΕΣ: Μέσος_χρόνος
ΛΟΓΙΚΕΣ:done
ΑΡΧΗ
! Η επεξεργασία της ουράς γίνεται χωρίς ολίσθηση των στοιχείων της
! κατά μιά θέση μπροστά μετά από κάθε εξαγωγή (όπως γίνεται πραγματικά)
front ← 0
rear ← 0
π ← 0
ΓΡΑΨΕ 'ΔΩΣΕ 1 ΓΙΑ ΕΙΣΑΓΩΓΗ, 2 ΓΙΑ ΕΞΑΓΩΓΗ, 3 ΓΙΑ ΤΕΡΜΑΤΙΣΜΟ'
ΔΙΑΒΑΣΕ choice
ΟΣΟ choice<>3 ΕΠΑΝΑΛΑΒΕ
ΑΝ choice=1 ΤΟΤΕ
ΔΙΑΒΑΣΕ ΟΝΟΜΑ
ΚΑΛΕΣΕ ΕΙΣΑΓΩΓΗ(ΟΥΡΑ,ΟΝΟΜΑ,front,rear,done)
ΑΝ done=ΨΕΥΔΗΣ ΤΟΤΕ
ΓΡΑΨΕ 'Ελάτε σε 3 ώρες'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Προηγούνται ',rear-front,'άτομα'
ΓΡΑΨΕ 'Χρόνος αναμονής ',(rear-front)*3,'λεπτά'
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ_ΑΝ choice=2 ΤΟΤΕ
ΚΑΛΕΣΕ ΕΞΑΓΩΓΗ(ΟΥΡΑ,ΟΝΟΜΑ,front,rear,done)
ΑΝ done=ΑΛΗΘΗΣ ΤΟΤΕ
ΓΡΑΨΕ ΟΝΟΜΑ
π ← π + 1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΓΡΑΨΕ 'ΔΩΣΕ 1 ΓΙΑ ΕΙΣΑΓΩΓΗ, 2 ΓΙΑ ΕΞΑΓΩΓΗ, 3 ΓΙΑ ΤΕΡΜΑΤΙΣΜΟ'
ΔΙΑΒΑΣΕ choice
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ π
Σ ← 0
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ π
Σ ← Σ + Ι*3
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! π<>0 (από εκφώνηση)
Μέσος_χρόνος ← Σ/π
ΓΡΑΨΕ Μέσος_χρόνος
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΔΙΑΔΙΚΑΣΙΑ ΕΙΣΑΓΩΓΗ(ΟΥΡΑ,ΟΝΟΜΑ,front,rear,done)
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ:ΟΥΡΑ[30],ΟΝΟΜΑ
ΑΚΕΡΑΙΕΣ:front,rear
ΛΟΓΙΚΕΣ:done
ΑΡΧΗ
ΑΝ rear = 30 ΤΟΤΕ
done ← ΨΕΥΔΗΣ
ΑΛΛΙΩΣ_ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
front ← 1
rear ← 1
ΟΥΡΑ[rear] ← ΟΝΟΜΑ
done ← ΑΛΗΘΗΣ
ΑΛΛΙΩΣ
rear ← rear + 1
ΟΥΡΑ[rear] ← ΟΝΟΜΑ
done ← ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΕΞΑΓΩΓΗ(ΟΥΡΑ,ΟΝΟΜΑ,front,rear,done)
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ:ΟΥΡΑ[30],ΟΝΟΜΑ
ΑΚΕΡΑΙΕΣ:front,rear
ΛΟΓΙΚΕΣ:done
ΑΡΧΗ
ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
done ← ΨΕΥΔΗΣ
ΑΛΛΙΩΣ_ΑΝ (front=rear) ΤΟΤΕ
ΟΝΟΜΑ ← ΟΥΡΑ[front]
front ← 0
rear ← 0
done ← ΑΛΗΘΗΣ
ΑΛΛΙΩΣ
ΟΝΟΜΑ ← ΟΥΡΑ[front]
front ← front + 1
done ← ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

 
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/