Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Μονοδιάστατοι πίνακες => Γ΄ Λυκείου => Εισαγωγή στοιχείων, εμφάνιση και υπολογισμοί => Μήνυμα ξεκίνησε από: kiro στις 24 Φεβ 2006, 05:37:44 μμ

Τίτλος: min kai max ή Ταξινομηση?
Αποστολή από: kiro στις 24 Φεβ 2006, 05:37:44 μμ
Γεια σας!!!

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

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

Αν μπορούμε και τα δυο τι είναι καλύτερο?
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: alkisg στις 25 Φεβ 2006, 09:58:50 πμ
Κάνεις την κλασσική διαδικασία εύρεσης ελαχίστου (και στο ίδιο βρόχο και μέγιστου) στον πίνακα χρονιές, με τη διαφορά ότι δεν σε ενδιαφέρει να κρατήσεις το min/max αλλά το θέση_min/θέση_max.

Στη συνέχεια απλά κάνεις
ΓΡΑΨΕ ταινίες[θέση_min], χρονιές[θέση_min], ταινίες[θέση_max], χρονιές[θέση_max]
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: kinik στις 25 Φεβ 2006, 01:32:18 μμ
Αν δε κρατήσεις min, max δε γίνεται σωστός υπολογισμός του θεση_min, θεση_max
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: evry στις 25 Φεβ 2006, 02:10:56 μμ
Προφανώς ο συνάδελφος εννοούσε ότι στο τέλος δε σε ενδιαφέρει η τιμή min/max αλλά η θέση της, αφού αν ξέρεις αυτή ξέρεις και την τιμή της.
Το ότι κρατάμε το min/max είναι κομμάτι του κλασσικού αλγορίθμου


Αν δε κρατήσεις min, max δε γίνεται σωστός υπολογισμός του θεση_min, θεση_max
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: alkisg στις 25 Φεβ 2006, 04:19:37 μμ
[glossa]ΠΡΟΓΡΑΜΜΑ ΜέγιστοςΚαιΕλάχιστος
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: χρονιές[10], θέσηΜεγίστου, θέσηΕλαχίστου, ι
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ χρονιές[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  θέσηΜεγίστου <- 1
  θέσηΕλαχίστου <- 1
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ 10
    ΑΝ χρονιές[ι] > χρονιές[θέσηΜεγίστου] ΤΟΤΕ
      θέσηΜεγίστου <- ι
    ΑΛΛΙΩΣ_ΑΝ χρονιές[ι] < χρονιές[θέσηΕλαχίστου] ΤΟΤΕ
      θέσηΕλαχίστου <- ι
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ χρονιές[θέσηΕλαχίστου], χρονιές[θέσηΜεγίστου]
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ[/glossa]
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: kiro στις 26 Φεβ 2006, 11:06:09 μμ
Την άσκηση αυτή τη λύνει στο βοήθημα με την ταξινόμηση φυσαλίδας. Η ερώτηση μου ήταν (μάλλον δεν το διατύπωσα σωστά) αν αντί της ταξινόμησης μπορούσαμε απλά να χρησιμοποιήσουμε MIN και MAX χωρίς πρώτα να ταξινομήσουμε τον πίνακα, γενικά να μη χρησιμοποιήσουμε καθόλου ταξινόμηση. Είναι σωστό? Αν μπορούμε να χρησιμοποιήσουμε και τους δύο τρόπους δεν είναι πιο χρονοβόρο να κάνουμε πρώτα ταξινόμηση.
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: xaidi στις 27 Φεβ 2006, 12:14:29 μμ
Μπορείς να κάνεις ταξινόμηση του πίνακα χρονολογιών με ταυτόχρονη αλλαγή και του πίνακα των τίτλων, και κατόπιν να εκτυπώσεις τα κελιά που σε ενδιαφέρουν.
Νομίζω ότι σαν λύσεις είναι και οι δύο αποδεκτές (αυτή και εκείνη που παρουσιάζεις).
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: kiro στις 27 Φεβ 2006, 04:08:23 μμ
eyxaristw!
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: gpapargi στις 27 Φεβ 2006, 08:47:57 μμ
Θα προσπαθήσω να το πω όσο γίνεται πιο απλά χωρίς να μπλέξω με τεχνικούς όρους. Έστω ότι θέλουμε να βρούμε το μικρότερο στοιχείο ενός πίνακα 100 θέσεων και αποφασίζουμε να το λύσουμε με πλήρη ταξινόμηση.

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

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

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

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

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


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


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

.
.
.

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


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

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

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

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


Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: klitos στις 28 Φεβ 2006, 08:32:19 πμ
αν στην ταξινόμηση γραψεις Για ι απο 2 μέχρι 2 ... τοότε γλυτώνεις όλες τις περιττές επαναλήψεις .... αλλα γενικά ειναι περιττό να κάνεις ταξινόμηση για να βρεις τον ελάχιστο η τον μεγιστο...
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: gpapargi στις 28 Φεβ 2006, 09:10:44 πμ
Αυτό είναι ισοδύναμο με το να βγάλεις τελείως τον εξωτερικό βρόχο. Και τότε τι μένει; Η εύρεση ελαχίστου με τη μέθοδο της φυσαλλίδας (που σπρώχνει τα μικρά επάνω σαν τις φυσαλίδες στο νερό).

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

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

Άλλο είναι να σου έχει ήδη ζητηθεί ταξινόμηση σε κάποιο άλλο ερώτημα και να την χρησιμοποιήσεις για να βρεις min και max. Τότε μάλιστα δεν κάνεις περιττή δουλειά βάζοντας και τις μεθοδολογίες του min, max και ίσα ίσα που δείχνεις ότι σκέφτεσαι. 
Τίτλος: Απ: min kai max ή Ταξινομηση?
Αποστολή από: nik_gr στις 18 Δεκ 2009, 10:04:01 πμ
Όταν ζητείται απλώς min ή/και max, προτιμούμε απλή διαδικασία εύρεσης.
Όταν ζητάμε τα ν μεγαλύτερα ή ν μικρότερα στοιχεία του πίνακα (ν>=2) τότε προφανώς κάνουμε ταξινόμηση.