Θέμα: ερώτηση για άσκηση (Edited: νέα ερώτηση)

[Πανάγος94]

για να μην γράψω όλη την εκφώνηση της άσκησης θα γράψω μόνο το κομμάτι που με ενδιαφέρει.....Έστω ότι δίνονται οι πίνακες ΟΝΟΜΑΤΑ[30],ΒΑΘΜΟΙ[30,10],ΜΟ[30] με τον πρώτο πίνακα να περιέχει τα ονόματα 30 μαθητών,τον δεύτερο τους βαθμούς του κάθε μαθητή σε 10 μαθήματα και τον τρίτο τους μέσους όρους κάθε μαθητή....το ερώτημα λέει:
"να εκτυπώνει τα ονόματα των μαθητών και τους βαθμούς τους στα 10 μαθήματα ταξινομημένους κατά φθίνουσα τάξη με βάση τον μέσο όρο τους"
δεν κατάλαβα τι εννοεί αλλά υπέθεσα (μάλλον λανθασμένα) ότι αφού ταξινομηθούν οι μαθητές με βάση τον μέσο όρο τους έπειτα να εμφανίζονται τα ονόματα τους και οι βαθμοί τους σε καθένα από τα 10 μαθήματα...η απάντηση μου βρίσκεται παρακάτω....καταρχάς θέλω αν μπορεί κάποιος να ελέγξει αν η απάντηση μου είναι σωστή (με βάση αυτό που εγώ κατάλαβα ότι εννοεί) και έπειτα να μου εξηγήσει κάποιος τι στο καλό εννοεί??? ΣΑΣ ΕΥΧΑΡΙΣΤΩ!! 

Για ι από 1 μέχρι 30
θ[ι] ← ι !Edited
Τέλος_επανάληψης
Για ι από 2 μέχρι 30
Για κ από 30 μέχρι ι με_βήμα -1
Αν ΜΟ[κ-1] < ΜΟ[κ] τότε
Αντιμετάθεσε ΜΟ[κ-1],ΜΟ[κ]
Αντιμετάθεσε θ[κ-1],θ[κ]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Για ι από 1 μέχρι 30
Για κ από 1 μέχρι 10
Εκτύπωσε ΟΝΟΜΑΤΑ[θ[ι]],ΒΑΘΜΟΙ[θ[ι],κ]
Τέλος_επανάληψης
τελος_επαναληψης

[Νίκος Αδαμόπουλος]

Από τη λύση σου θεωρώ ότι έχεις καταλάβει το ερώτημα...
Ακολουθούν μερικές διορθώσεις... Δεν τις αναλύω γιατί πιστεύω ότι κι αυτές θα τις καταλάβεις αμέσως!

Για ι από 1 μέχρι 30
  θ[ι] ← 0 ι
Τέλος_επανάληψης
Για ι από 2 μέχρι 30
  Για κ από 30 μέχρι ι με_βήμα -1
     Αν ΜΟ[κ-1] < ΜΟ[κ] τότε
        Αντιμετάθεσε ΜΟ[κ-1],ΜΟ[κ]
        Αντιμετάθεσε θ[κ-1],θ[κ]
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Για ι από 1 μέχρι 30
  Εκτύπωσε ΟΝΟΜΑΤΑ[θ[ι]]
  Για κ από 1 μέχρι 10
     Εκτύπωσε ΟΝΟΜΑΤΑ[θ[ι]], ΒΑΘΜΟΙ[θ[ι],κ]
  Τέλος_επανάληψης
Τέλος_επαναληψης

Η αλήθεια είναι ότι με εντυπωσίασε η προσέγγισή σου... Κρατάς τις αρχικές θέσεις ώστε μετά να μπορείς να προσπελάσεις τα στοιχεία του δισδιάστατου...

Μια άλλη λύση θα ήταν κατά την ταξινόμηση να κάνεις αντιμεταθέσεις και στις γραμμές κ-1 και κ του δισδιάστατου, οπότε: α) δεν χρειάζεται ο πίνακας θ, β) τα δεδομένα παραμένουν όλα τακτοποιημένα, γ) είναι πιο απλή η εμφάνιση. Βέβαια, από άποψη απόδοσης...

Για ι από 2 μέχρι 30
  Για κ από 30 μέχρι ι με_βήμα -1
     Αν ΜΟ[κ-1] < ΜΟ[κ] τότε
        Αντιμετάθεσε ΟΝΟΜΑΤΑ[κ-1], ΟΝΟΜΑΤΑ[κ]
        Αντιμετάθεσε ΜΟ[κ-1], ΜΟ[κ]
        Για λ από 1 μέχρι 10
           Αντιμετάθεσε ΒΑΘΜΟΙ[κ-1,λ], ΒΑΘΜΟΙ[κ,λ]
        Τέλος επανάληψης
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Για ι από 1 μέχρι 30
  Εκτύπωσε ΟΝΟΜΑΤΑ[ι]
  Για κ από 1 μέχρι 10
     Εκτύπωσε ΒΑΘΜΟΙ[ι, κ]
  Τέλος_επανάληψης
Τέλος_επαναληψης

[Πανάγος94]

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

[Πανάγος94]

έχω μια νέα απορία....αν μπορούσατε να μου την λύσετε θα το εκτιμούσα.... η άσκηση είναι η εξής....

Για την πρώτη φάση της Ολυμπιάδας Πληροφορικής δήλωσαν συμμετοχή 500 μαθητές. Οι μαθητές διαγωνίζονται σε δύο γραπτές εξετάσεις τεστ και βαθμολογούνται σε βαθμολογική κλίμακα από 0 εώς 100.

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

το ερώτημα που με "καίει" είναι το (ε)...είναι και η εκφώνηση λίγο μπερδεμένη....η λύση μου είναι παρακάτω (για το ε) και στο τέλος εξηγώ τι έκανα

καταρχάς χρησιμοποίησα τους πίνακες ον[500],β1[500],β2[500],μο[500]

!ε
Για ι από 2 μέχρι 500
Για κ από 500 μέχρι ι με_βήμα -1
Αν ΜΟ[κ-1] < ΜΟ[κ] τότε
Αντιμετάθεσε ΜΟ[κ-1],ΜΟ[κ]
Αντιμετάθεσε ον[κ-1],ον[κ]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
μο1 ← 0
Για ι από 1 μέχρι 500
μο1 ← μο1 + β1[ι]
Τέλος_επανάληψης
μο1 ← μο1/500
πλ ← -1
ι ← 0
Αρχή_επανάληψης
ι ← ι + 1
πλ ← πλ + 1
Μέχρις_ότου ΜΟ[ι] ≤ μο1
Για ι από 2 μέχρι πλ
Για κ από πλ μέχρι ι με_βήμα -1
Αν ον[κ-1] > ον[κ] τότε
Αντιμετάθεσε ον[κ-1],ον[κ]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Για ι από 1 μέχρι πλ
Εμφάνισε ον[ι]
τελος_επαναληψης


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

[evry]

Τι θα έλεγες να έκανες μόνο μια ταξινόμηση στην οποία θα ταξινομούσες μόνο όσους είναι μεγαλύτεροι από τον μέσο όρο?
Υπόδειξη: Τη στιγμή της αντιμετάθεσης θα πρέπει να προσθέσεις άλλη μια συνθήκη στο Αν

[Νίκος Αδαμόπουλος]

Τι θα έλεγες να έκανες μόνο μια ταξινόμηση στην οποία θα ταξινομούσες μόνο όσους είναι μεγαλύτεροι από τον μέσο όρο?
Υπόδειξη: Τη στιγμή της αντιμετάθεσης θα πρέπει να προσθέσεις άλλη μια συνθήκη στο Αν

@evry: Για να καταλάβω, ποια συνθήκη θα έβαζες και ποια ζεύγη κάθε φορά θα αντιμετάθετες;

Πιο απλά εγώ θα έλεγα να ταξινομήσεις από την αρχή μόνο μία φορά όλο τον πίνακα βάσει αλφαβητικής σειράς με παράλληλες αντιμεταθέσεις στους παράλληλους πίνακες. Και στη συνέχεια να εμφανίσεις με Για και Αν μόνο όσους ικανοποιούν το κριτήριο.

Πάντως και η αρχική σου λύση σωστή μου φαίνεται... αν και κάνει πολλά που θα μπορούσες να αποφύγεις...

Βέβαια στο σημείο:

ι ← 0
Αρχή_επανάληψης
  ι ← ι + 1
  πλ ← πλ + 1
Μέχρις_ότου ΜΟ[ι] ≤ μο1

... και αν τύχει να έχουν όλοι βαθμό (ΜΟ) πάνω από το μέσο όρο του 1ου τεστ (μο1) τότε "το ι θα βγει εκτός πίνακα"... οπότε είναι λίγο πρόβλημα αυτό!

[evry]

Θα έκανα κάτι τέτοιο

Αν  ( ΜΟ[j] > μο και ΜΟ[j-1] > μο και Ον[j] < Ον[j-1] ) ή ( ΜΟ[j] > μο και  MO[j-1] <= μο)    Τότε
    Αντιμετάθεσε ΜΟ[j], MO[j-1]
    Αντιμετάθεσε Ον[j], Ον[j-1]
Τέλος_αν


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

@evry: Για να καταλάβω, ποια συνθήκη θα έβαζες και ποια ζεύγη κάθε φορά θα αντιμετάθετες;

[Νίκος Αδαμόπουλος]

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

Και μόνο που το βλέπω με πιάνει κρύος ιδρώτας...!

[evry]

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

Τέλος πάντων, η ταξινόμηση της φυσαλίδας κατά τη γνώμη μου κακώς διδάσκεται, δεν νομίζω ότι έχει κάποιο "άμεσο" διδακτικό όφελος που να αξίζει όλη αυτή τη φασαρία
Το βασικό πρόβλημα δεν είναι μόνο ότι είναι δυσνόητος ο κώδικας ούτε ότι δεν προκύπτει από κάποιον προϋπάρχον αλγόριθμο , ούτε ότι δεν είναι ο φυσικός τρόπος με τον οποίο οι μαθητές θα ταξινομούσαν μια σειρά αντικείμενα με τα χέρια.
Το βασικό πρόβλημα κατά τη γνώμη μου είναι ότι δεν είναι προφανής η ορθότητα του αλγόριθμου. Δηλαδή δεν σε σε πείθει με την πρώτη ματιά ότι αυτό το πράγμα κάνει πράγματι ταξινόμηση, σε αντίθεση με τις ταξινομήσεις με επιλογή/εισαγωγή όπου και πιο φυσικός είναι ο τρόπος και μπορείς πιο εύκολα να χτίσεις στην έννοια του μεγίστου/ελαχίστου που τα παιδιά έχουν διδαχθεί. Εκεί μάλιστα θα είχε πιο πολύ νόημα να χρησιμοποιήσεις υποπρόγραμμα.
τέλος πάντων, τόσοι ωραίοι αλγόριθμοι υπάρχουν αλλά εμείς μείναμε με την bs

[nikosx]

συμφωνώ evry

[Πανάγος94]

άμα η συνθήκη ήταν όμως μέχρις_ότου ΜΟ[ι] <= μο1 ή ι = 500 δεν θα ήταν ολόσωστο??? όσον αφορά τον αλγόριθμο που έγραψα το ξέρω ότι είναι μεγάλος και αργός αλλά εξεταζόμαστε ως προς την αποτελεσματικότητά του και όχι ως προς την αποδοτικότητά του.....

[evry]

βασικά ούτε ως προς την αποτελεσματικότητα εξετάζεστε, αλλά ας το αφήσουμε αυτό.
Όπως και να έχει εδώ δεν εξετάζει κανένας κανέναν, κουβέντα κάνουμε. Δεν είπε κανείς ότι η λύση σου δεν θα γινόταν δεκτή, προφανώς και είναι ολόσωστη.
Άσε που και από πλευράς απόδοσης αν το δεις θεωρητικά, δηλαδή κάνεις ανάλυση πολυπλοκότητας στην χειρότερη περίπτωση οι 2 αλγόριθμοι δεν απέχουν και τόσο πολύ, είναι και οι 2 O(n²)*.

Επίσης δεν κατάλαβα, από που προκύπτει το i=50 ?

άμα η συνθήκη ήταν όμως μέχρις_ότου ΜΟ[ι] <= μο1 ή ι = 50 δεν θα ήταν ολόσωστο??? όσον αφορά τον αλγόριθμο που έγραψα το ξέρω ότι είναι μεγάλος και αργός αλλά εξεταζόμαστε ως προς την αποτελεσματικότητά του και όχι ως προς την αποδοτικότητά του.....

*μετά τις εξετάσεις ρίξε μια ματιά στο κεφάλαιο 5 

[Πανάγος94]

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

[Νίκος Αδαμόπουλος]

μέχρις_ότου ΜΟ[ι] <= μο1 ή ι = 500

OK

[Vangelis]

Αν κάποτε ! επεκταθεί  η ύλη του μαθήματος θα πρέπει να μπούν και άλλοι αλγόριθμοι ταξινόμησης (και πολλά άλλα).