min kai max ή Ταξινομηση?

Ξεκίνησε από kiro, 24 Φεβ 2006, 05:37:44 ΜΜ

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

kiro

Γεια σας!!!

Σε μια άσκηση πχ. Ένα βιντεοκλάμπ έχει έναν αριθμό από ταινίες. Για κάθε ταινία κρατά σε δυο πίνακες τον τίτλο της και τη χρόνια έκδοσης της. Να εμφανίζεται η χρόνια έκδοσης και ο τίτλος της πιο παλιάς ταινίας καθώς και της πιο νέας.

Σ αυτήν την περίπτωση δε θα μπορούσαμε να χρησιμοποιήσουμε min και max και αντίστοιχα αν είναι min η χρονολογία να εμφανίζεται και  ο αντίστοιχος τίτλος.

Αν μπορούμε και τα δυο τι είναι καλύτερο?

alkisg

Κάνεις την κλασσική διαδικασία εύρεσης ελαχίστου (και στο ίδιο βρόχο και μέγιστου) στον πίνακα χρονιές, με τη διαφορά ότι δεν σε ενδιαφέρει να κρατήσεις το min/max αλλά το θέση_min/θέση_max.

Στη συνέχεια απλά κάνεις
ΓΡΑΨΕ ταινίες[θέση_min], χρονιές[θέση_min], ταινίες[θέση_max], χρονιές[θέση_max]

kinik

Αν δε κρατήσεις min, max δε γίνεται σωστός υπολογισμός του θεση_min, θεση_max

evry

Προφανώς ο συνάδελφος εννοούσε ότι στο τέλος δε σε ενδιαφέρει η τιμή min/max αλλά η θέση της, αφού αν ξέρεις αυτή ξέρεις και την τιμή της.
Το ότι κρατάμε το min/max είναι κομμάτι του κλασσικού αλγορίθμου


Παράθεση από: kinik στις 25 Φεβ 2006, 01:32:18 ΜΜ
Αν δε κρατήσεις min, max δε γίνεται σωστός υπολογισμός του θεση_min, θεση_max
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

alkisg

[glossa]ΠΡΟΓΡΑΜΜΑ ΜέγιστοςΚαιΕλάχιστος
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: χρονιές[10], θέσηΜεγίστου, θέσηΕλαχίστου, ι
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ χρονιές[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  θέσηΜεγίστου <- 1
  θέσηΕλαχίστου <- 1
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ 10
    ΑΝ χρονιές[ι] > χρονιές[θέσηΜεγίστου] ΤΟΤΕ
      θέσηΜεγίστου <- ι
    ΑΛΛΙΩΣ_ΑΝ χρονιές[ι] < χρονιές[θέσηΕλαχίστου] ΤΟΤΕ
      θέσηΕλαχίστου <- ι
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ χρονιές[θέσηΕλαχίστου], χρονιές[θέσηΜεγίστου]
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ[/glossa]

kiro

Την άσκηση αυτή τη λύνει στο βοήθημα με την ταξινόμηση φυσαλίδας. Η ερώτηση μου ήταν (μάλλον δεν το διατύπωσα σωστά) αν αντί της ταξινόμησης μπορούσαμε απλά να χρησιμοποιήσουμε MIN και MAX χωρίς πρώτα να ταξινομήσουμε τον πίνακα, γενικά να μη χρησιμοποιήσουμε καθόλου ταξινόμηση. Είναι σωστό? Αν μπορούμε να χρησιμοποιήσουμε και τους δύο τρόπους δεν είναι πιο χρονοβόρο να κάνουμε πρώτα ταξινόμηση.

xaidi

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

kiro


gpapargi

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

Ας φανταστούμε για λίγο τη μέθοδο ταξινόμησης της φυσσαλίδας σε ένα πίνακα 100 θέσεων.

Ξέρουμε ότι μετά την πρώτη σάρωση του πίνακα το μικρότερο στοιχείο έρχεται στην πρώτη θέση. Άρα έχουμε βρει πιο είναι το μικρότερο και μπορούμε να σταματήσουμε εδώ.

Αν τώρα συνεχίσουμε, κάνουμε τα εξής περιττά πράγματα:

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

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


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


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

.
.
.

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


Δηλαδή κάνουμε 1 χρήσιμη σάρωση 100 αριθμών και 98 περιττές σαρώσεις σε κάποιο πλήθος αριθμών που έχει μέσο όρο πλήθους γύρω στο 50.

Θα ήταν πιο παραστατικό να γράψω όλες τις σαρώσεις για να φαίνονται. Εδώ είναι λίγες γιατί ο πίνακας είναι μόνο 100 θέσεων. Για σκέψου να είχε μέγεθος 1000000 αντί για 100.

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

Η νοοτροπία του «ότι τρέχει είναι σωστό» ειναι κάτι που δεν ισχύει στην αλγοριθμική. Δυστυχώς το μάθημα έχει πάρει λάθος κατεύθυνση και δεν κόβονται πόντοι. Σε κάποιο σημείο στο τετράδιο λέει να μην βάζουμε περιττούς ελέγχους. Το συγκεκριμένο παράπτωμα της πλήρους ταξινόμησης είναι ασύγκριτα χειρότερο γιατί αλλάζεις την τάξη του αλγορίθμου.  Αν όμως δεν αρχίσουν να κόβονται πόντοι, δεν κάνουμε τίποτα. Είναι σα να προσπαθείς να καταπολεμήσεις την εγκηματικότητα σε μια χώρα τιμωρόντας τους παρανόμους με...  επίπληξη.



klitos

αν στην ταξινόμηση γραψεις Για ι απο 2 μέχρι 2 ... τοότε γλυτώνεις όλες τις περιττές επαναλήψεις .... αλλα γενικά ειναι περιττό να κάνεις ταξινόμηση για να βρεις τον ελάχιστο η τον μεγιστο...
κλητος χατζηγεωργιου

gpapargi

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

'Αλλωστε τι είναι η ταξινόμηση; Επαναλαμβανόμενες ευρέσεις ελάχίστου σε μια ολοένα και μικρότερη λίστα αριθμών.

ΥΓ. Μιλάω βέβαια για ταξινόμηση στα σχολικά πλαίσια.

EleniK

Θα συμφωνήσω ότι το να κάνεις ταξινόμηση για να βρεις min και max περιέχει πολλές περιττές και άσκοπες επαναλήψεις. Δεν είναι καλή τακτική και συνήθως το αποτρέπουμε.

Άλλο είναι να σου έχει ήδη ζητηθεί ταξινόμηση σε κάποιο άλλο ερώτημα και να την χρησιμοποιήσεις για να βρεις min και max. Τότε μάλιστα δεν κάνεις περιττή δουλειά βάζοντας και τις μεθοδολογίες του min, max και ίσα ίσα που δείχνεις ότι σκέφτεσαι. 
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

nik_gr

Όταν ζητείται απλώς min ή/και max, προτιμούμε απλή διαδικασία εύρεσης.
Όταν ζητάμε τα ν μεγαλύτερα ή ν μικρότερα στοιχεία του πίνακα (ν>=2) τότε προφανώς κάνουμε ταξινόμηση.