Δευτέρα 22 Ιουνίου 2009

Θέμα 3ον (και ίδιο αλλά και λίγο αλλαγμένο)

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


(α) Θέμα 3ον, όπως δόθηκε

Σε μια διαδρομή τρένου υπάρχουν 20 σταθμοί (σε αυτούς περιλαμβάνονται η αφετηρία και ο τερματικός σταθμός). Το τρένο σταματά σε όλους τους σταθμούς. Σε κάθε σταθμό επιβιβάζονται και αποβιβάζονται επιβάτες. Οι πρώτοι επιβάτες επιβιβάζονται στην αφετηρία και στον τερματικό σταθμό αποβιβάζονται όλοι οι επιβάτες.
Να κατασκευάσετε αλγόριθμο, ο οποίος να διαχειρίζεται την κίνηση των επιβατών. Συγκεκριμένα :
Α. Να ζητάει από τον χρήστη τον αριθμό των ατόμων που επιβιβάστηκαν σε κάθε σταθμό, εκτός από τον τερματικό, και να τον εισάγει σε πίνακα ΕΠΙΒ[19]. (Μονάδες 2)
Β. Να εισάγει σε πίνακα ΑΠΟΒ[19] τον αριθμό των ατόμων που αποβιβάστηκαν σε κάθε σταθμό, εκτός από τον τερματικό, ως εξής : Για την αφετηρία να εισάγει την τιμή μηδέν (0) και για τους υπόλοιπους σταθμούς να ζητάει από τον χρήστη τον αριθμό των ατόμων που αποβιβάστηκαν. (Μονάδες 4)
Γ. Να δημιουργεί πίνακα ΑΕ[19], στον οποίο να καταχωρίζει τον αριθμό των επιβατών που βρίσκονται στο τρένο, μετά από κάθε αναχώρησή του. (Μονάδες 7)
Δ. Να βρίσκει και να εμφανίζει τον σταθμό από τον οποίο το τρένο αναχωρεί με τον μεγαλύτερο αριθμό επιβατών. (Να θεωρήσετε ότι από κάθε σταθμό το τρένο αναχωρεί με διαφορετικό αριθμό επιβατών). (Μονάδες 7)

Ενδεικτική λύση με διαχωρισμό σε ερωτήματα όπως δόθηκαν στην εκφώνηση :

Αλγόριθμος Θέμα3
// ΕΠΙΒ[19], ΑΠΟΒ[19] //

! Α επιβιβαζόμενοι
Για σταθμός από 1 μέχρι 19
__Διάβασε ΕΠΙΒ[σταθμός]
Τέλος_επανάληψης

! Β αποβιβαζόμενοι
ΑΠΟΒ[1] <– 0
Για σταθμός από 2 μέχρι 19
__Διάβασε ΑΠΟΒ[σταθμός]
Τέλος_επανάληψης

! Γ παραμένοντες στο τρένο
Πλήθος <– 0
Για σταθμός από 1 μέχρι 19
__Πλήθος <– Πλήθος + ΕΠΙΒ[σταθμός] – ΑΠΟΒ[σταθμός]
__ΑΕ[σταθμός] <– Πλήθος
Τέλος_επανάληψης

! Δ σταθμός μεγίστου πλήθους
ΣταθμόςΜΠλήθους <– 1
ΜέγιστοΠλήθος <– ΑΕ[1]
Για σταθμός από 2 μέχρι 19
__Αν ΑΕ[σταθμός] > ΜέγιστοΠλήθος τότε
____ΣταθμόςΜΠλήθους <– σταθμός
____ΜέγιστοΠλήθος <– ΑΕ[σταθμός]
__Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘Σταθμός ‘,ΣταθμόςΜΠλήθους,’ με πλήθος ‘,ΜέγιστοΠλήθος

// ΣταθμόςΜΠλήθους //
Τέλος Θέμα3

Άλλη ενδεικτική λύση χωρίς διαχωρισμό σε ερωτήματα, δίνει την σωστή απάντηση αλλά δυσκολεύει τους διορθωτές :

Αλγόριθμος Θέμα3_σύντομος
// ΕΠΙΒ[19], ΑΠΟΒ[19] //
Για σταθμός από 1 μέχρι 19
__Αν σταθμός = 1 τότε
____Διάβασε ΕΠΙΒ[1]
____ΑΠΟΒ[1] <– 0
____ΑΕ[1] <– ΕΠΙΒ[1]
____ΣταθμόςΜΠλήθους <– 1
____ΜέγιστοΠλήθος <– ΑΕ[1]
__Αλλιώς
____Διάβασε ΕΠΙΒ[σταθμός], ΑΠΟΒ[σταθμός]
____ΑΕ[σταθμός] <– ΑΕ[σταθμός–1]+ΕΠΙΒ[σταθμός]-ΑΠΟΒ[σταθμός]
____Αν ΑΕ[σταθμός] > ΜέγιστοΠλήθος τότε
______ΣταθμόςΜΠλήθους <– σταθμός
______ΜέγιστοΠλήθος <– ΑΕ[σταθμός]
____Τέλος_αν
__Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘Σταθμός ‘,ΣταθμόςΜΠλήθους,’ με πλήθος ‘,ΜέγιστοΠλήθος

// ΣταθμόςΜΠλήθους //
Τέλος Θέμα3_σύντομος



(β) Θέμα 3ον, λίγο αλλαγμένο

Ένα τρένο επιτρέπεται να μεταφέρει ένα μέγιστο όριο επιβατών. Το Όριο_επιβατών δίδεται όταν φεύγει το τρένο από το Αμαξοστάσιο.
Στην πρώτη στάση, στην Αφετηρία, ανεβαίνουν επιβάτες. Το τρένο μετά την Αφετηρία κάνει 18 ενδιάμεσες στάσεις και φτάνει στο Τέρμα. Στις ενδιάμεσες στάσεις πρώτα κατεβαίνουν οι επιβαίνοντες και μετά ανεβαίνουν νέοι επιβάτες. Στο Τέρμα κατεβαίνουν όλοι οι επιβάτες.
Ζητείται αλγόριθμος που να διαχειρίζεται την κίνηση των επιβατών. Θα διαβάζει πόσοι κατέβηκαν (ΑΠΟΒ[19]) και πόσοι ανέβηκαν (ΕΠΙΒ[19]), αλλά θα ελέγχει τις τιμές να είναι πάντοτε επιτρεπτές. Θα παρακολουθεί το πλήθος επιβατών (ΑΕ[19]).
Να εμφανιστεί ο αριθμός της τελευταίας στάσης που αναχώρησε το τρένο με τους περισσότερους επιβάτες, το μέγιστο αυτό πλήθος επιβατών, και το πλήθος επιβατών που κατέβηκαν στο Τέρμα.

Αλγόριθμος Θέμα3_αλλαγμένος
// Όριο_Επιβατών, ΕΠΙΒ[19], ΑΠΟΒ[19] //

! Καθορίζεται το όριο επιβατών στο Αμαξοστάσιο
Αρχή_επανάληψης
__Διάβασε Όριο_επιβατών
Μέχρις_ότου Όριο_επιβατών > 0

! Στην πρώτη στάση μπορεί να γεμίσει από επιβάτες
Αρχή_επανάληψης
__Διάβασε ΕΠΙΒ[1]
Μέχρις_ότου ΕΠΙΒ[1]>=0 και ΕΠΙΒ[1]<=Όριο_επιβατών
ΑΠΟΒ[1] <– 0
ΑΕ[1] <– ΕΠΙΒ[1]
ΣτάσηΜΠλήθους <– 1
ΜέγιστοΠλήθος <– ΑΕ[1]
Για στάση από 2 μέχρι 19

! Σε επόμενη στάση αποβιβάζονται το πολύ όλοι όσοι επιβαίνουν
__Αρχή_επανάληψης
____Διάβασε ΑΠΟΒ[στάση]
__Μέχρις_ότου ΑΠΟΒ[στάση]>=0 και ΑΠΟΒ[στάση]<=ΑΕ[στάση–1]

! Βρίσκουμε πόσοι παρέμειναν μέσα στο όχημα
__ΑΕ[στάση] <– ΑΕ[στάση–1]–ΑΠΟΒ[στάση]

! Μετά επιβιβάζονται σε όσες ελεύθερες θέσεις υπάρχουν, μέχρι το όριο επιβατών __Αρχή_επανάληψης
____Διάβασε ΕΠΙΒ[στάση]
__Μέχρις_ότου ΕΠΙΒ[στάση]>=0 και ΕΠΙΒ[στάση]<=(Όριο_επιβατών–ΑΕ[στάση])

! Βρίσκουμε πόσοι έγιναν οι επιβάτες, πριν ξεκινήσει το όχημα
____ΑΕ[στάση] <– ΑΕ[στάση]+ΕΠΙΒ[στάση]
____Αν ΑΕ[στάση] > ΜέγιστοΠλήθος τότε
______ΣτάσηΜΠλήθους <– στάση
______ΜέγιστοΠλήθος <– ΑΕ[στάση]
____Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘Στάση ‘,ΣτάσηΜΠλήθους,’ με μέγιστο πλήθος ‘,ΜέγιστοΠλήθος
Αν ΑΕ[19]>0 τότε
__Εμφάνισε ‘Στο τέρμα κατεβαίνουν ‘,ΑΕ[19],’ επιβάτες
αλλιώς
__Εμφάνισε ‘Δεν υπάρχουν επιβάτες που κατεβαίνουν στο Τέρμα’
Τέλος_αν

// ΣτάσηΜΠλήθους, ΜέγιστοΠλήθος, ΑΕ[19] //
Τέλος Θέμα3_αλλαγμένος