α. Το πρώτο βήμα είναι η δημιουργία του πίνακα ΨΗΦΙΣΤΗΚΑΝ, το μέγεθος του οποίου είναι το πολύ 250*5=1250. Ωστόσο, δεν είναι σίγουρο ότι όλοι οι μαθητές θα εξαντλήσουν το δικαίωμά τους, έτσι το μέγεθος του πίνακα μπορεί να είναι μικρότερο. Απαιτείται η χρήση δυο δομών επανάληψης, καθώς πρέπει για κάθε έναν από τους 250 μαθητές να διαβαστούν το πολύ 5 επιλογές. Ο εξωτερικός βρόχος, θα υλοποιηθεί με τη δομή Για και για τον εσωτερικό η δομή επανάληψης Όσο (πρέπει να επιλεγεί ένα κριτήριο για τον τερματισμό σε περίπτωση που δεν υπάρχουν 5 ψήφοι. Το κριτήριο αυτό είναι αν δοθεί ως όνομα το κενό). Το τμήμα αλγορίθμου που επιλύει το ερώτημα (α) είναι το εξής:
Ν ← 0
Για i από 1 μέχρι 250
πλήθος ← 0
Διάβασε όνομα
Όσο (όνομα <> " ") και (πλήθος < 5) επανάλαβε ! μέχρι 5 ψήφους ή τελευταίο όνομα το κενό
Ν ← Ν + 1
ΨΗΦΙΣΤΗΚΑΝ[Ν] ← όνομα
πλήθος ← πλήθος + 1
Διάβασε όνομα
Τέλος_επανάληψης
Τέλος_επανάληψης
Στο τέλος της διαδικασίας η μεταβλητή Ν περιέχει το συνολικό πλήθος των ονομάτων που ψηφίστηκαν, το μέγεθος δηλαδή του ομώνυμου πίνακα.
β. Πρέπει να δημιουργηθεί ο πίνακας ΥΠΟΨΗΦΙΟΣ, που θα περιέχει ουσιαστικά τα στοιχεία του πίνακα ΨΗΦΙΣΤΗΚΑΝ που είναι μοναδικά... Πρέπει για κάθε ένα στοιχείο του πίνακα ΨΗΦΙΣΤΗΚΑΝ, να αναζητείται στον πίνακα ΥΠΟΨΗΦΙΟΣ και αν δεν εντοπιστεί να περνάει, αλλιώς να συνεχίζεται η διαδικασία με το επόμενο όνομα. Άρα, ο σκελετός του αλγορίθμου με ελεύθερο κείμενο θα είναι:
Πέρασε το πρώτο στοιχείο του πίνακα ΥΠΟΨΗΦΙΟΣ
Για k από 2 μέχρι Ν ! θα εξετάσουμε τα υπόλοιπα
Ψάξε αν το στοιχείο ΨΗΦΙΣΤΗΚΑΝ[k], υπάρχει ήδη στον πίνακα ΥΠΟΨΗΦΙΟΣ ! σειριακή αναζήτηση
Αν (δεν βρέθηκε προηγουμένως) τότε
Πέρασε το στοιχείο k του πίνακα ΨΗΦΙΣΤΗΚΑΝ στον πίνακα ΥΠΟΨΗΦΙΟΣ
Τέλος_αν
Τέλος_επανάληψης
Άρα, το τμήμα αλγορίθμου θα είναι:
ΥΠΟΨΗΦΙΟΣ[1] ← ΨΗΦΙΣΤΗΚΑΝ[1] ! περνάμε το πρώτο όνομα
υποψ ← 1
Για k από 2 μέχρι Ν ! θα εξετάσουμε τα υπόλοιπα
βρέθηκε ← ψευδής
i ← 1
Όσο (βρέθηκε = ψευδής) και (i <= υποψ) επανάλαβε ! έχει εξεταστεί μέχρι τη θέση υποψ, όσα στοιχεία υπάρχουν
Αν (ΥΠΟΨΗΦΙΟΣ[i] = ΨΗΦΙΣΤΗΚΑΝ[k]) τότε
βρέθηκε ← αληθής
Αλλιώς
i ← i + 1
Τέλος_αν
Τέλος_επανάληψης ! τέλος σειριακής αναζήτησης
Αν (βρέθηκε = ψευδής) τότε ! αν δεν υπάρχει ήδη στον πίνακα, να το βάλουμε
υποψ ← υποψ + 1
ΥΠΟΨΗΦΙΟΣ[υποψ] ← ΨΗΦΙΣΤΗΚΑΝ[k] ! περνάμε το επόμενο όνομα
Τέλος_αν
Τέλος_επανάληψης
γ. Σύμφωνα με το προηγούμενο ερώτημα, το πλήθος των υποψηφίων περιέχεται στην μεταβλητή υποψ. Αυτό είναι και το μέγεθος του νέου πίνακα ΚΑΤΑΜΕΤΡΗΣΗ που θα περιέχει το πλήθος των ψήφων κάθε υποψηφίου, πρόκειται για πίνακα μετρητή. Για να δημιουργηθεί ο πίνακας αυτός πρέπει να χρησιμοποιηθεί παρόμοια λογική με αυτή του προηγούμενου ερωτήματος. Θα εξετάσουμε ένα-ένα τα στοιχεία και θα κρατήσουμε από την αναζήτηση τη θέση, αυξάνονοντας τον αντίστοιχο μετρητή. Ο σκελετός του αλγορίθμου με ελεύθερο κείμενο θα είναι:
αρχικοποίησε τους μετρητές
Για k από 1 μέχρι Ν ! θα εξετάσουμε ένα-ένα όλα τα στοιχεία
Βρες το στοιχείο ΨΗΦΙΣΤΗΚΑΝ[k], σε ποια θέση υπάρχει στον πίνακα ΥΠΟΨΗΦΙΟΣ ! σειριακή αναζήτηση
αύξησε τον αντίστοιχο μετρητή (σίγουρα θα έχει βρεθεί)
Τέλος_επανάληψης
Άρα, το τμήμα αλγορίθμου θα είναι:
Για k από 1 μέχρι Ν
ΚΑΤΑΜΕΤΡΗΣΗ[k] ← 0 ! καταμέτρηση
Τέλος_επανάληψης
Για k από 1 μέχρι Ν
βρέθηκε ← ψευδής
θέση ← 0
i ← 1
Όσο (βρέθηκε = ψευδής) και (i <= υποψ) επανάλαβε ! σίγουρα θα βρεθεί
Αν (ΥΠΟΨΗΦΙΟΣ[i] = ΨΗΦΙΣΤΗΚΑΝ[k]) τότε
βρέθηκε ← αληθής
θέση ← i
Αλλιώς
i ← i + 1
Τέλος_αν
Τέλος_επανάληψης ! τέλος σειριακής αναζήτησης
ΚΑΤΑΜΕΤΡΗΣΗ[θέση] ← ΚΑΤΑΜΕΤΡΗΣΗ[θέση] + 1
Τέλος_επανάληψης
Τα ερωτήματα β και γ μπορούσαν να συγχωνευτούν. ΠΩΣ ? Δείτε την ολοκληρωμένη άσκηση στο τέλος της σελίδας...
δ. Για την επιλογή των μελών του 15μελούς πρέπει αρχικά να ταξινομηθεί ο πίνακας ΚΑΤΑΜΕΤΡΗΣΗ (με φθίνουσα διάταξη) με ταυτόχρονη αντιμετάθεση του πίνακα ΥΠΟΨΗΦΙΟΣ ώστε να παραμείνουν παράλληλοι
Για i από 2 μέχρι υποψ ! ταξινόμηση του πίνακα ΚΑΤΑΜΕΤΡΗΣΗ
Για j από υποψ μέχρι i με_βήμα –1
Αν ΚΑΤΑΜΕΤΡΗΣΗ[j-1] < ΚΑΤΑΜΕΤΡΗΣΗ[j] τότε ! φθίνουσα ταξινόμηση
βοηθητική1 ← ΚΑΤΑΜΕΤΡΗΣΗ[j-1] ! βοηθητική, αλφαριθμητικού τύπου
ΚΑΤΑΜΕΤΡΗΣΗ[j-1] ← ΚΑΤΑΜΕΤΡΗΣΗ[j]
ΚΑΤΑΜΕΤΡΗΣΗ[j] ← βοηθητική1
! αντίστοιχη αντιμετάθεση των στοιχείων του πίνακα ΥΠΟΨΗΦΙΟΣ, ώστε να παραμείνουν οι πίνακες παράλληλοι
βοηθητική2← ΥΠΟΨΗΦΙΟΣ[j-1] ! βοηθητική1, αριθμητικού τύπου
ΥΠΟΨΗΦΙΟΣ[j-1] ← ΥΠΟΨΗΦΙΟΣ[j]
ΥΠΟΨΗΦΙΟΣ[j] ← βοηθητική2
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Απομένει η δημιουργία του πίνακα ΜΕΛΗ_15 που θα περιέχει τα ονόματα των 15 μελών του νέου μαθητικού συμβουλίου. Πρέπει να δοθεί προσοχή στο ότι υπάρχει πάντα το ενδεχόμενο ισοψηφίας. Επομένως, πρέπει να βρεθεί αν υπάρχουν και πόσοι στις τελευταίες θέσεις. Η λογική που θα ακολουθήσουμε είναι απλή: θα μελετήσουμε πόσοι υποψήφιοι έχουν ίδιο βαθμό με αυτόν που υπάρχει στην 15 θέση (σε προηγούμενες και επόμενες θέσεις). Θα περάσουμε πρώτα τα ονόματα των εκλεγέντων πριν από αυτόν. Στη συνέχεια, θα πρέπει να διαβαστούν τα ονόματα που κληρώθηκαν ώστε να συμπληρωθεί η 15άδα. Θα δημιουργήσουμε νέο πίνακα που θα περιέχει τα ονόματα όσων υποψηφίων έχουν βαθμολογία, ίση με αυτή του 15ου στην κατάταξη, όπως επίσης και νέου πίνακα που θα περιέχει τα στοιχεία όσων υποψηφίων έχουν σίγουρα εκλεγεί (έχουν περισσότερες ψήφους απόες αυτές του 15 στην κατάταξη).
μέλη ← 0
κλήρ ← 0
διακοπή ← ψευδής
i ← 1
Όσο (διακοπή = ψευδής) και (i <= υποψ) επανάλαβε
Αν (ΚΑΤΑΜΕΤΡΗΣΗ[i] > ΚΑΤΑΜΕΤΡΗΣΗ[15]) τότε ! αν έχει περισσότερες ψήφους, εκλέγεται
μέλη ← μέλη + 1
ΜΕΛΗ_15[τελευτ] ← ΥΠΟΨΗΦΙΟΣ[i]
i ← i + 1
Αλλιώς_αν (ΚΑΤΑΜΕΤΡΗΣΗ[i] = ΚΑΤΑΜΕΤΡΗΣΗ[15]) τότε ! πίνακας για κλήρωση
κλήρ ← κλήρ + 1
ΓΙΑ_ΚΛΗΡΩΣΗ[κλήρ] ← ΥΠΟΨΗΦΙΟΣ[i]
i ← i + 1
Αλλιώς ! με λιγότερες ψήφους, σταμάτα την επανάληψη
διακοπή ← ψευδής
Τέλος_αν
Τέλος_επανάληψης
Πρέπει να γίνει κλήρωση για να καλυφθούν οι τελευταίες θέσεις (έχουν απομείνει 15 - μέλη). Έτσι, ζητείται από το χρήστη να δώσει τα ονόματα όσων απομένουν... Θα γίνει έλεγχος δεδομένων ώστε τα ονόματα που θα διαβαστούν να ανήκουν στον πίνακα ΓΙΑ_ΚΛΗΡΩΣΗ, ώστε σε διαφορετική περίπτωση να επαναλαμβάνεται η είσοδος. Αν δοθεί ένα έγκυρο όνομα, περνάει στον πίνακα ΜΕΛΗ_15 και "φεύγει" από τον πίνακα ΓΙΑ_ΚΛΗΡΩΣΗ, ώστε να μην δοθεί ξανά
Αν (κλήρ = 1) τότε ! δεν υπήρξαν ισοβαθμίες
μέλη ← μέλη + 1
ΜΕΛΗ_15[15] ← ΓΙΑ_ΚΛΗΡΩΣΗ[1] ! θα μπορούσε και ΥΠΟΨΗΦΙΟΙ[15]
Αλλιώς
Εκτύπωσε 15 - μέλη
Για i από 1 μέχρι κλήρ ! ποιοι θα κληρωθούν
Εκτύπωσε ΓΙΑ_ΚΛΗΡΩΣΗ[i]
Τέλος_επανάληψης
Για k από μέλη+1 μέχρι 15 ! να συμπληρωθούν οι υπόλοιποι
Αρχή_επανάληψης
Αρχή_επανάληψης
Διάβασε όνομα
Μέχρις_ότου όνομα <> " "
βρέθηκε ← ψευδής ! υπάρχει το όνομα; σειριακή αναζήτηση
θέση ← 0
i ← 1
Όσο (βρέθηκε = ψευδής) και (i <= κλήρ) επανάλαβε ! σίγουρα θα βρεθεί
Αν (ΓΙΑ_ΚΛΗΡΩΣΗ[i] = όνομα) τότε
βρέθηκε ← αληθής
θέση ← i
Αλλιώς
i ← i + 1
Τέλος_αν
Τέλος_επανάληψης ! τέλος σειριακής αναζήτησης
Μέχρις_ότου βρέθηκε = αληθής
ΜΕΛΗ_15[k] ← ΓΙΑ_ΚΛΗΡΩΣΗ[θέση] ! θα μπορούσε να είναι και "όνομα"
ΓΙΑ_ΚΛΗΡΩΣΗ[θέση]← " " ! φεύγει το όνομα από τον πίνακα
Τέλος_επανάληψης
Τέλος_αν
Τέλος, θα εκτυπώσουμε τα στοιχεία του πίνακα ΜΕΛΗ_15
Για i από 1 μέχρι 15
Εκτύπωσε ΜΕΛΗ_15[i]
Τέλος_επανάληψης
|
Άσκηση 1. Η εταιρεία "Προαστιακός Τενεούπολης" προσέλαβε τον γιο του κου Αρβίλογλου με κύρια απασχόληση στις πληροφορίες δρομολογίων. Έχει στη διάθεσή του πίνακα ΣΤΑΘΜΟΣ[12], που περιέχει τα ονόματα των ισάριθμων σταθμών του τραίνου (περιέχονται και ο πρώτος και τελευταίος σταθμός). Επίσης, υπάρχει διαθέσιμος ο πίνακας ΚΟΣΤΟΣ[12, 12], όπου το στοιχείο ΚΟΣΤΟΣ[i, j] περιέχει το κόστος του εισιτηρίου για τη διαδρομή ΣΤΑΘΜΟΣ[i] -> ΣΤΑΘΜΟΣ[j], πίνακας ΚΟΣΤΟΣ είναι δηλαδή παράλληλος και ως προς τις γραμμές αλλά και ως προς τις στήλες με τον πίνακα ΣΤΑΘΜΟΣ. Είναι ευνότητο πως η κύρια διαγώνιος του πίνακα ΚΟΣΤΟΣ περιέχει 0 καθώς δεν γίνεται κάποιος να ταξιδέψει στο μέρος που ήδη βρίσκεται. Επίσης, πρέπει να έχει γίνει αντιληπτό ότι ο πίνακας ΚΟΣΤΟΣ είναι συμμετρικό ως προς την κύρια διαγώνιο. Να αναπτύξετε αλγόριθμο όπου θα διαβάζει τα στοιχεία των παραπάνω πινάκων και στη συνέχεια: θα διαβάζει το όνομα του σταθμού αφετηρίας ενός επιβάτη και το όνομα του τερματικού σταθμού και θα εκτυπώνει το κόστος του ταξιδιού. Ο αλγόριθμος θα πρέπει στη συνέχεια να διαβάζει αν ο επιβάτης επιθυμεί εισιτήριο μετ' επιστροφής και σε περίπτωση καταφατικής απάντησης να εκτυπώνει το συνολικό κόστος του εισιτηρίου. Δίδεται πως σε περίπτωση που εκδοθεί εισιτήριο μετ' επιστροφής υπάρχει έκπτωση 20%.
