ΕΥΡΕΣΗ ΜΕΓΙΣΤΟΥ - ΕΛΑΧΙΣΤΟΥ

Ξεκίνησε από arwd, 20 Οκτ 2007, 10:00:44 ΜΜ

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

arwd

Καλησπέρα!
Ο παρακάτω έλεγχος για εύρεση μεγίστου και ελαχίστου είναι λάθος;

Για ελάχιστο
Αν (α<β και α<γ) τότε
     min<--α
αλλιώς_αν (β<α και β<γ) τότε
     min<--β
αλλιώς_αν (γ<α και γ<β) τότε
     min<--γ
Τέλος_αν


Για  μέγιστο
Αν (α>β και α>γ) τότε
     max<--α
αλλιώς_αν (β>α και β>γ) τότε
     max<--β
αλλιώς_αν (γ>α και γ>β) τότε
     max<--γ
Τέλος_αν


Είναι λάθος αν μια πολλαπλή επιλογή τελειώνει με αλλιώς_αν αντι για αλλιώς;
Στα παραπάνω αν δώσουμε 2 ίδιους αριθμούς, π.χ αν θέλουμε να βρίσκει ελάχιστο και μέγιστο 3 αριθμών και δώσουμε 5,0,0 δεν θα βγάλει τίποτα.
Υπάρχει κάποιο άλλο πρόβλημα με αυτό τον τρόπο;  ???
Ευχαριστώ

alkisg

αλλιώς_αν (β<α και β<γ) τότε
     min<--β

Όπως είπες, αν βάλεις α = 5, β = 0 και γ = 0, το παραπάνω αλλιώς_αν δεν ισχύει, ενώ θα έπρεπε, και έτσι δεν βρίσκει το min.
Θα έπρεπε να βάλεις μικρότερα - ή - ίσα στις συνθήκες, δηλαδή
αλλιώς_αν (β<=α και β<=γ) τότε
     min<--β

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

arwd

Σ'ευχαριστώ πολύ για την βοήθεια!! ;)

tomemeto1

Μήπως δεν είναι τελείως σωστό, δεδομένου ότι, πχ στο πρώτο ΑΝ γίνεται σύγκριση του (α με το β) και στο δεύτερο ΑΝ επίσης γίνεται ο συγκεκριμένος έλεγχος? Δηλαδή μιλάμε για περιττό έλεγχο? (σελ 172 σχ. βιβλίου)

alkisg

Ο έλεγχος α > β είναι διαφορετικός έλεγχος από το β > α, επειδή δεν συμπεριλαμβάνεται πουθενά η ισότητα.

Με την τρέχουσα ύλη η απόδοση αλγορίθμων είναι εκτός ύλης. Η συγκεκριμένη παρατήρηση στη σελ. 172 τυχαίνει να είναι εντός ύλης.
Όμως, είναι λίγο οξύμωρο από τη μία να ασχολούμαστε με μία και μόνη ΑΝ που δεν αλλάζει την πολυπλοκότητα (και στο κάτω κάτω μπορεί να την κάνει optimize ο compiler), και από την άλλη όταν θέλουμε να βρούμε τους 2 μεγαλύτερους ενός πίνακα να κάνουμε ταξινόμηση, πηγαίνοντας από πολυπλοκότητα Ο(Ν) σε Ο(Ν2)...
Αμάν πότε θα βάλουν την πολυπλοκότητα εντός ύλης να σοβαρευτούμε!!! :)

P.Tsiotakis

Στη σελίδα 172 η λέξη λάθος για τους περιττούς ελέγχους σημαίνει οτι πρέπει να αποφεύγεται η χρήση τους γιατί αυξάνεται η πιθανότητα λάθους, και οδηγούμαστε σε δυσνόητα προγράμματα.

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

Σε αυτό το πλαίσιο πιστεύω οτι κινείται και το σχετικό ερώτημα 1Β στις επαναληπτικά θέματα του 2006 (http://users.kor.sch.gr/ptsiotakis/aepp/aepp_panel_epanen_2006.htm). Η επιτροπή ήθελε να περάσει και ένα μήνυμα σε καθηγητές και μαθητές, κατά τη γνώμη μου πάντα...

Βρακόπουλος Αθανάσιος Λ.

για το παραπάνω πρόβλημα θα πρότεινα και

Αν α<β τότε min<-α αλλιώς  min<-β
Αν γ< min τότε min <-γ

δίνω τον αλγόριθμο αυτόν σαν Εναλλακτική  λύση στο πρόβλημα εύρεσης του μικρότερου ή του μεγαλύτερου τριών αριθμών

alexis_zoure

Προσωπικα προτεινω τον παρακατω αλγοριθμο:

Αλγοριθμος Max_min
Διαβασε x,y,z
Αν x>y τοτε
     max<-x
     min<-y
Αλλιως 
     max<-y
     min<-x
Τελος_αν
Αν z>max τοτε
     max<-z
Τελος_αν
Αν z<min τοτε
      min<-z
Τελος_αν
Εμφανισε max,min
Τελος Max_min

Πιστευω οτι καλυπτει ολες τις περιπτωσεις!!! ;)
Αλεξανδρος Ζουρελιδης
Μαθητης Γ Λυκειου

gpapargi

Παράθεση από: alkisg στις 22 Οκτ 2007, 07:58:19 ΜΜ
Όμως, είναι λίγο οξύμωρο από τη μία να ασχολούμαστε με μία και μόνη ΑΝ που δεν αλλάζει την πολυπλοκότητα (και στο κάτω κάτω μπορεί να την κάνει optimize ο compiler), και από την άλλη όταν θέλουμε να βρούμε τους 2 μεγαλύτερους ενός πίνακα να κάνουμε ταξινόμηση, πηγαίνοντας από πολυπλοκότητα Ο(Ν) σε Ο(Ν2)...
Αμάν πότε θα βάλουν την πολυπλοκότητα εντός ύλης να σοβαρευτούμε!!! :)

Νομίζω πως δεν χρειάζεται να ξαναματαεπαναλάβω ότι ταυτίζομαι πλήρως με αυτήν την άποψη  ;)

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

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

Αντίθετα ο αλγόριθμος με τη μεταβλητή max και σύγκριση καθενός από τους αριθμούς με τον max γενικεύεται πανεύκολα. Την ίδια εντολή εκτελείς όσοι και να είναι οι αριθμοί. Άρα μπαίνει εύκολα σε μια εντολή επανάληψης και άρα γενικεύεται εύκολα και ανώδυνα για τυχαίο πλήθος. Ακόμα και κάποιος που δεν ενδιαφέρεται για την ποιότητα του αλγορίθμου θα αναγνωρίσει ότι θα γλιτώσει κόπο στα επόμενα κεφάλαια που θα αντιμετωπιστεί το πρόβλημα της εύρεσης μεγίστου στοιχείου πίνακα με οσοδήποτε μεγάλο πλήθος στοιχείων.