Αποστολέας Θέμα: min kai max ή Ταξινομηση?  (Αναγνώστηκε 6211 φορές)

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
min kai max ή Ταξινομηση?
« στις: 24 Φεβ 2006, 05:37:44 μμ »
Γεια σας!!!

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

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6008
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: min kai max ή Ταξινομηση?
« Απάντηση #1 στις: 25 Φεβ 2006, 09:58:50 πμ »
Κάνεις την κλασσική διαδικασία εύρεσης ελαχίστου (και στο ίδιο βρόχο και μέγιστου) στον πίνακα χρονιές, με τη διαφορά ότι δεν σε ενδιαφέρει να κρατήσεις το min/max αλλά το θέση_min/θέση_max.

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

kinik

  • Επισκέπτης
Απ: min kai max ή Ταξινομηση?
« Απάντηση #2 στις: 25 Φεβ 2006, 01:32:18 μμ »
Αν δε κρατήσεις min, max δε γίνεται σωστός υπολογισμός του θεση_min, θεση_max

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3609
  • to Iterate is human to Recurse divine
Απ: min kai max ή Ταξινομηση?
« Απάντηση #3 στις: 25 Φεβ 2006, 02:10:56 μμ »
Προφανώς ο συνάδελφος εννοούσε ότι στο τέλος δε σε ενδιαφέρει η τιμή min/max αλλά η θέση της, αφού αν ξέρεις αυτή ξέρεις και την τιμή της.
Το ότι κρατάμε το min/max είναι κομμάτι του κλασσικού αλγορίθμου


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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6008
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: min kai max ή Ταξινομηση?
« Απάντηση #4 στις: 25 Φεβ 2006, 04:19:37 μμ »
[glossa]ΠΡΟΓΡΑΜΜΑ ΜέγιστοςΚαιΕλάχιστος
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: χρονιές[10], θέσηΜεγίστου, θέσηΕλαχίστου, ι
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ χρονιές[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  θέσηΜεγίστου <- 1
  θέσηΕλαχίστου <- 1
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ 10
    ΑΝ χρονιές[ι] > χρονιές[θέσηΜεγίστου] ΤΟΤΕ
      θέσηΜεγίστου <- ι
    ΑΛΛΙΩΣ_ΑΝ χρονιές[ι] < χρονιές[θέσηΕλαχίστου] ΤΟΤΕ
      θέσηΕλαχίστου <- ι
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ χρονιές[θέσηΕλαχίστου], χρονιές[θέσηΜεγίστου]
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ[/glossa]

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: min kai max ή Ταξινομηση?
« Απάντηση #5 στις: 26 Φεβ 2006, 11:06:09 μμ »
Την άσκηση αυτή τη λύνει στο βοήθημα με την ταξινόμηση φυσαλίδας. Η ερώτηση μου ήταν (μάλλον δεν το διατύπωσα σωστά) αν αντί της ταξινόμησης μπορούσαμε απλά να χρησιμοποιήσουμε MIN και MAX χωρίς πρώτα να ταξινομήσουμε τον πίνακα, γενικά να μη χρησιμοποιήσουμε καθόλου ταξινόμηση. Είναι σωστό? Αν μπορούμε να χρησιμοποιήσουμε και τους δύο τρόπους δεν είναι πιο χρονοβόρο να κάνουμε πρώτα ταξινόμηση.

xaidi

  • Ομάδα διαγωνισμάτων 2009
  • *
  • Μηνύματα: 111
  • who is WHO!!!!!!
Απ: min kai max ή Ταξινομηση?
« Απάντηση #6 στις: 27 Φεβ 2006, 12:14:29 μμ »
Μπορείς να κάνεις ταξινόμηση του πίνακα χρονολογιών με ταυτόχρονη αλλαγή και του πίνακα των τίτλων, και κατόπιν να εκτυπώσεις τα κελιά που σε ενδιαφέρουν.
Νομίζω ότι σαν λύσεις είναι και οι δύο αποδεκτές (αυτή και εκείνη που παρουσιάζεις).
Ευχαριστώ,

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: min kai max ή Ταξινομηση?
« Απάντηση #7 στις: 27 Φεβ 2006, 04:08:23 μμ »
eyxaristw!

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2466
  • I 'm not young enough to know everything
Απ: min kai max ή Ταξινομηση?
« Απάντηση #8 στις: 27 Φεβ 2006, 08:47:57 μμ »
Θα προσπαθήσω να το πω όσο γίνεται πιο απλά χωρίς να μπλέξω με τεχνικούς όρους. Έστω ότι θέλουμε να βρούμε το μικρότερο στοιχείο ενός πίνακα 100 θέσεων και αποφασίζουμε να το λύσουμε με πλήρη ταξινόμηση.

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

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

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

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

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


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


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

.
.
.

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


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

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

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

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



klitos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 133
Απ: min kai max ή Ταξινομηση?
« Απάντηση #9 στις: 28 Φεβ 2006, 08:32:19 πμ »
αν στην ταξινόμηση γραψεις Για ι απο 2 μέχρι 2 ... τοότε γλυτώνεις όλες τις περιττές επαναλήψεις .... αλλα γενικά ειναι περιττό να κάνεις ταξινόμηση για να βρεις τον ελάχιστο η τον μεγιστο...
κλητος χατζηγεωργιου

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2466
  • I 'm not young enough to know everything
Απ: min kai max ή Ταξινομηση?
« Απάντηση #10 στις: 28 Φεβ 2006, 09:10:44 πμ »
Αυτό είναι ισοδύναμο με το να βγάλεις τελείως τον εξωτερικό βρόχο. Και τότε τι μένει; Η εύρεση ελαχίστου με τη μέθοδο της φυσαλλίδας (που σπρώχνει τα μικρά επάνω σαν τις φυσαλίδες στο νερό).

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

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

EleniK

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 708
Απ: min kai max ή Ταξινομηση?
« Απάντηση #11 στις: 28 Φεβ 2006, 10:20:14 πμ »
Θα συμφωνήσω ότι το να κάνεις ταξινόμηση για να βρεις min και max περιέχει πολλές περιττές και άσκοπες επαναλήψεις. Δεν είναι καλή τακτική και συνήθως το αποτρέπουμε.

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

nik_gr

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 15
Απ: min kai max ή Ταξινομηση?
« Απάντηση #12 στις: 18 Δεκ 2009, 10:04:01 πμ »
Όταν ζητείται απλώς min ή/και max, προτιμούμε απλή διαδικασία εύρεσης.
Όταν ζητάμε τα ν μεγαλύτερα ή ν μικρότερα στοιχεία του πίνακα (ν>=2) τότε προφανώς κάνουμε ταξινόμηση.