ΜΗΠΩΣ ΞΕΡΕTE ΤΙ ΠΡΕΠΕΙ ΝΑ ΚΑΝΩ?
ΠΡΕΠΕΙ ΝΑ ΓΡΑΨΩ ΕΝΑΝ ΑΛΓΟΡΙΘΜΟ: ΠΟΥ ΣΕ ΕΝΑΝ ΠΙΝΑΚΑ ΝΑ ΕΝΤΩΠΙΖΕΙ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ Ή ΤΟΝ ΔΕΥΤΕΡΟ ΜΙΚΡΟΤΕΡΟ ΑΡΙΘΜΟ!
ΕΓΩ ΤΟ ΕΛΥΣΑ ΑΛΛΑ ΔΕΝ ΞΕΡΩ ΝΑ ΒΡΩ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ. ΒΡΙΣΚΩ ΜΟΝΟ ΤΟΝ ΠΡΩΤΟ ΜΕΓΑΛΥΤΕΡΟ.ΕΝΩ ΑΥΤΟΣ ΘΕΛΕΙ ΚΑΤΕΥΘΕΙΑΝ ΟΤΑΝ ΤΟ ΤΡΕΧΩ ΤΟ ΠΡΟΓΡΑΜΜΑ ΝΑ ΜΟΥ ΔΙΝΕΙ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ ΑΡΙΘΜΟ
ΛΥΣΗ (ΕΒΑΛΑ ΟΤΙ Ο ΠΙΝΑΚΑΣ ΕΙΝΑΙ ΜΟΝΟΔΙΑΣΤΑΤΟΣ)
ΑΛΓΟΡΙΘΜΟΣ
ΕΥΡΕΣΗ_ΔΕΥΤΕΡΟΥ_ΜΕΓΑΛΥΤΕΡΟΥ
ΔΕΔΟΜΕΝΑ // Ν,Α //
ΜΕΓΙΣΤΟΣ<------ Α[1]
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
ΑΝ ΜΕΓΙΣΤΟΣ<Α
ΤΟΤΕ
ΜΕΓΙΣΤΟΣ<-----Α
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΠΟΤΕΛΕΣΜΑ // ΜΕΓΙΣΤΟΣ //
ΤΕΛΟΣ ΕΥΡΕΣΗ_ΔΕΥΤΕΡΟΥ_ΜΕΓΑΛΥΤΕΡΟΥ
ΕΙΠΑ ΕΣΤΩ ΟΤΙ ΤΟ ΠΡΩΤΟ ΣΤΟΙΧΕΙΟ ΤΟΥ ΠΙΝΑΚΑ ΕΙΝΑΙ ΤΟ ΜΕΓΙΣΤΟ
ΤΟΤΕ ΝΑ ΚΑΝΕΙ ΣΥΓΚΡΙΣΗ ΤΟΥ ΥΠΟΤΙΘΕΜΕΝΟΥ ΜΕΓΙΣΤΟΥ ΜΕ ΤΟΥΣ ΥΠΟΛΟΙΠΟΥΣ ΑΡΙΘΜΟΥΣ ΤΟΥ ΠΙΝΑΚΑ.
ΚΑΙ ΑΝ ΒΡΕΙ ΜΕΓΑΛΥΤΕΡΟ ΑΡΙΘΜΟ ΑΠΟ ΤΟΝ ΥΠΟΤΙΘΕΜΕΝΟ ΔΙΚΟ ΜΟΥ ΜΕΓΙΣΤΟ ΝΑ ΘΕΩΡΗΣΕΙ ΑΥΤΟΝ ΣΑΝ ΜΕΓΙΣΤΟ.
ΣΑΣ ΕΥΧΑΡΙΣΤΩ
Τα πιο απλά βήματα που μπόρεσα να σκεφτώ για επίλυση της άσκησης, είναι:
1. Φθίνουσα ταξινόμηση του πίνακα
2. Εντοπισμό όλων των στοιχείων που είναι ίσα με το μέγιστο (πρώτο στοιχείο)
3. Το αμέσως επόμενο στοιχείο (αν υπάρχει) είναι το δεύτερο μεγαλύτερο
Αλγόριθμος Δυο
Δεδομένα // Ν, Α //
! φθίνουσα ταξινόμηση πίνακα Α[Ν]
......................................
μ ← 0
Για ι απο 1 μέχρι Ν
Αν Α[ι] = Α[1] τότε ! ίσα με το μέγιστο
μ ← μ + 1
Τέλος_αν
Τέλος_επανάληψης
Αν μ = Ν τότε
Εμφάνισε "Όλα τα στοιχεία ίσα"
Αλλιώς
Εμφάνισε Α[μ+1]
Τέλος_αν
Τέλος Δυο
Ελπίζω να μην έκανα κάποιο λάθος, βιασύνης ;)
Καλή συνέχεια,
Μία λύση με δύο περάσματα στον πίνακα
μεγ1 <- Α[1]
μιν <- Α[1]
ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
ΑΝ Α[ι] > μεγ1 ΤΟΤΕ
μεγ1 <- Α[ι]
ΤΕΛΟΣ_ΑΝ
ΑΝ Α[ι] < μιν ΤΟΤΕ
μιν <- Α[ι]
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!Αρχικοποιώ στον ελάχιστο, ώστε να μην πέσω πάνω στο μεγαλύτερο όλων
μεγ2 <- μιν
ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
ΑΝ Α[ι] > μεγ2 ΚΑΙ Α[ι] <> μεγ1 ΤΟΤΕ
μεγ2 <- Α[ι]
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!στη δυσμενέστερη περίπτωση που όλα τα στοιχεία είναι ίσα, είμαι καλυμένος
ΑΝ μεγ1 = μεγ2 ΤΟΤΕ
ΓΡΑΨΕ 'Πλήρης ισότητα'
ΤΕΛΟΣ_ΑΝ
edit: Διορθωμένος κώδικας
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό
Για ι από 1 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς αν α[ι] > max2 τότε
max2 <- α[ι]
τέλος_αν
Τέλος_επανάληψης
Εμφάνισε max2
@GEORGIA_LIAMA: Εκ των προταίρων προτείνω να χρησιμοποιήσεις τον αλγόριθμο του κυρίου Τσιωτάκη.
Ένας 2ος Τρόπος.
------------------------
Αλγόριθμος Οτιναναι
Δεδομένα // Ν, Α//
! Ο αλγόριθμος αυτός κάνει χρήση 2 δεικτών, ο ένας δείχνει τον max ( pos1 )
! και ο δεύτερος ( pos2 ) τον αμέσως επόμενο.
Αν ( Α[1] > A[2]) τότε
pos1<--1
pos2<--2
Aλλιώς
pos1<--2
pos2<--1
Tέλος_αν
Για i από 3 μέχρι Ν
Αν ( Α[i] > Α[pos1] ) τότε ! Σύγκριση με τον μαξ. Αν ισχύει η συνθήκη τότε το νέο στοιχείο είναι μαξ
! και αυτό που ήταν μαξ μπαίνει στη 2η θέση( του αμέσως μεγαλύτερου)
pos2 <-- pos1
pos1 <-- i
Αλλιώς_αν ( A[i] > A[pos2] ) ! Αν δεν μπει στην πρώτη περίπτωση τότε υπάρχει περίπτωση να είναι
! μικρότερο από αυτό που έχουμε ως 2ο και έτσι το αντικαθιστούμε.
pos2 <-- i
Τέλος_αν
Τέλος_επανάληψης
! Οι μεταβλητές pos1 και pos2 τώρα έχουν αποθηκευμένη τη θέση του μεγαλύτερου και του αμέσως
! μεγαλύτερου στοιχείου του πίνακα αντίστοιχα.
Μπορεί να υλοποιηθεί και με χρήση συνάρτησης, που επιστρέφει τη θέση του μεγαλύτερου στοιχείου, είτε ίσως συνάρτησης που θα ταξινομεί 3 στοιχεία και διάφορες παραλλαγές τεσπα. Δεν ήθελα να μπερδέψω άλλο, γι'αυτό δεν το έκανα, όποιος θέλει για εξάσκηση να κάνει αυτό τον κώδικα όσο πιο τμηματικά μπορεί καλό θα του κάνει :D.
edit: ίδιος τρόπος με τον από πάνω :( (γραψαμε την ίδια στιγμή)
Ο παρακάτω θα ήταν ένας πολύ καλός τρόπος για να εισάγεις τα παιδιά στην ταξινόμηση και πιο συγκεκριμένα στην ταξινόμηση με εισαγωγή αν αυτή ήταν εντός ύλης. Αν το δοκιμάσεις για 3 μεγαλύτερους γενικεύεται στην insertion sort στον πίνακα max[ ].
Παράθεση από: sstergou στις 26 Μαΐου 2008, 08:35:48 ΜΜ
max1 <- α[1]
max2 <- α[1]
Για ι από 2 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς αν α[ι] > max2 τότε
max2 <- α[ι]
τέλος_αν
Τέλος_επανάληψης
Εμφάνισε max2
Υπάρχει αντίστοιχη λυμένη άσκηση στο Τετράδιο μαθητή σελ. 39 Παράδειγμα 3 για την εύρεση των 2 ελαχίστων.
Μια ακόμη λύση (απλοϊκή)-έτσι για την ιστορία - είναι η εύρεση του μεγίστου , η ανταλλαγή του με το στοιχείο της 1ης θέσης (αν δεν έχει βρεθεί εκεί) του πίνακα και η εκ νέου σάρωση για την εύρεση του 2ου μεγίστου απο την 2η θέση και μετά.
Georgia έχεις ήδη 5 λύσεις, διάλεξε και πάρε ;)
max <- Α[1]
θέση<- 1
ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
ΑΝ Α[ι] > max ΤΟΤΕ
max <- Α[ι]
θέση<- ι
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Αν θέση<>1 τότε αντιμετάθεσε Α[θέση], Α[1]
max2 <- Α[2]
ΓΙΑ ι ΑΠΟ 3 ΜΕΧΡΙ Ν
ΑΝ Α[ι] > max2 ΤΟΤΕ
max2 <- Α[ι]
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Εμφάνισε max2
Δυστυχώς Ευριπίδη στο βιβλίο υπάρχει μόνο ο bubble sort :( , ο οποίος εξηγείται σχετικά δύσκολα σε σχέση με άλλους αλγόριθμους που κατά καιρούς έχουν δημοσιευτεί στο στέκι.
Το κόλπο που έκλεψα (από ένα βιντεάκι στο youtube) για να εξηγήσω την φυσαλίδα είναι το εξής:
Σηκώνω 6-7 μαθητές όρθιους και τους βάζω με μια ευνοϊκή για την φυσαλίδα σειρά. Στη συνέχεια τους αντιμεταθέτω σύμφωνα με τον αλγόριθμο του βιβλίου με σκοπό να φτιάξω μια σειρά από μαθητές ταξινομημένους με φθίνουσα σειρά.
Αν τους ταξινομήσω και στη συνέχεια εξακολουθώ να κάνω ελέγχους για αντιμεταθέσεις αυτοί ρωτάνε το γιατί...!
Μάλλον οι αλγόριθμοι λύνουν διαφορετικά πρόβληματα :-X
Κάποιοι βρίσκουν τον δεύτερο μεγαλύτερο ο οποίος είναι διαφορετικός από τον πρώτο ενώ κάποιοι άλλοι απλά τον δεύτερο μεγαλύτερο.
Αν όντως αυτό που ζητείται είναι το πρώτο τότε ο αλγόριθμος που έστειλα πρέπει να τροποποιηθεί για να βρίσκει τον δεύτερο μεγαλύτερο διαφορετικό από τον πρώτο.
edit:Διορθωμένος κώδικας
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό
Για ι από 1 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς_αν α[ι] > max2 και α[ι] <> max1 τότε
max2 <- α[ι]
Τέλος_αν
Τέλος_επανάληψης
Αν max2 <> κάτι_πολύ_μικρό τότε
Εμφάνισε max2
αλλιώς
Εμφάνισε "..."
Τέλος_αν
Έχεις δίκιο Στάθη, θα πρέπει να διευκρινιστεί αν όλα τα στοιχεία του πίνακα είναι διαφορετικά ή μπορεί να επαναλαμβάνονται περισσότερες φορές. Ο αλγόριθμος που έδωσα παραπάνω ισχύει για την 1η περίπτωση.
Για την 2η περίπτωση πρέπει να τροποποιηθεί όπως στο παράδειγμα που έδωσε ο koniordos.
.......................
ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
ΑΝ Α[ι] > μεγ2 ΚΑΙ Α[ι] <> μεγ1 ΤΟΤΕ
μεγ2 <- Α[ι]
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
........................
Παιδιά ένα ωραίο ασκησάκι που τους βάζω για να δω ποιοι στροφάρουν είναι το εξής:
Πριν μπω στους πίνακες και όσο είμαι στις εντολές επανάληψης τους βάζω να διαβάσουν 100 αριθμούς και να βρουν τους 2 μεγαλύτερους. Θα εκπλαγείτε από το πόσο λίγοι το λύνουν. Αν θυμάμαι καλά μόνο φέτος είχα έναν που το έλυσε και αυτός με την πρώτη το υποτίμησε και το πήγε βιαστικά. Τα προηγούμενα χρόνια τίποτα.
Δε θυμάμαι ποτέ κάποιον που να του το έδωσα για το σπίτι και να μου έφερε τη λύση με την πρώτη σωστά.
Εννοείται πως τους τσιγκλάω και κατάλληλα: "τη συγκεκριμένη άσκηση δε μου την έχει λύσει ποτέ κανείς... ποιος θα είναι ο πρώτος που θα γίνει ήρωας κλπ" ;)
Την άλλη φορά πριν μπεις στους πίνακες βάλτους την εξής άσκηση:
Να γράψετε αλγόριθμο ο οποίος να διαβάζει αριθμούς μέχρι το άθροισμά τους να ξεπεράσει το 1000 και στη συνέχεια να εμφανίζει ποια θα ήταν η θέση του 1ου αριθμού που δόθηκε αν αριθμοί ήταν ταξινομημένοι.
Μπορείς να βελτιώσεις λίγο την διατύπωση γιατί κάπου χάνει μου φαίνεται
Στο http://users.kor.sch.gr/ptsiotakis/aepp/aepp_files/om1/diag_ep_ola_1.doc Θέμα 4, ερώτημα 4
εκτιμώ οτι υπάρχει μια ωραία πρακτική εφαρμογή της ερώτησης του θέματος αυτού.
Ελπίζω να το δούμε και στις εξετάσεις. ;)
Λύση: http://users.kor.sch.gr/ptsiotakis/aepp/aepp_diag1.htm (10.διαγώνισμα 1)
Καλησπέρα.. Έχω μια ένσταση στην αρχικοποίηση του max2.
Παράθεση από: sstergou στις 26 Μαΐου 2008, 08:35:48 ΜΜ
max1 <- α[1]
max2 <- α[1]
Για ι από 2 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς αν α[ι] > max2 τότε
max2 <- α[ι]
τέλος_αν
Τέλος_επανάληψης
Εμφάνισε max2
Αν το μέγιστο στοιχείο του πίνακα βρίσκεται στην πρώτη θέση του πίνακα, ο αλγόριθμός σου κρατάει πάντα σα δεύτερο μεγαλύτερο το α[1].. Γι'αυτό θα το άλλαζα σε:
Αν α[2]>α[1] τότε
max1 <- α[2]
max2 <- α[1]
αλλιώς
max1 <- α[1]
max2 <- α[2]
Τέλος_αν
Για ι από 3 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς_αν α[ι] > max2 τότε
max2 <- α[ι]
Τέλος_αν
Τέλος_επανάληψης
Φιλικά Γιάννης
Ναι έχεις δίκιο. Ανακάλυψα και άλλο πρόβλημα όμως:
Αν ο μέγιστος είναι στο α[1] και στο α[2] πάλι λάθος !
Τελικά το σωστό είναι :
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό
Για ι από 1 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς_αν α[ι] > max2 και α[ι] <> max1 τότε
max2 <- α[ι]
Τέλος_αν
Τέλος_επανάληψης
Αν max2 <> κάτι_πολύ_μικρό τότε
Εμφάνισε max2
αλλιώς
Εμφάνισε "..."
Τέλος_αν
Ουφ! Ελπίζω να είναι εντάξει τώρα. Η αλλαγή ισχύει πάντα στην περίπτωση που θέλουμε το max1 με το max2 να είναι διαφορετικές ποσότητες.
Μα αν ο μέγιστος περιέχεται 2 φορές στον πίνακα, τότε είναι και δεύτερος μεγαλύτερος !!
Ωστόσο αν θέλουμε να βρούμε τον δεύτερο μεγαλύτερο που είναι διαφορετικός από τον πρώτο, θα πρότεινα ταξινόμηση. Διαφορετικά υπάρχουν πολλές παράμετροι που πρέπει να λάβεις υπόψιν και γίνεται δύσκολο
Παράθεση από: sstergou στις 28 Μαΐου 2008, 12:56:43 ΜΜ
Ναι έχεις δίκιο. Ανακάλυψα και άλλο πρόβλημα όμως:
Αν ο μέγιστος είναι στο α[1] και στο α[2] πάλι λάθος !
Τελικά το σωστό είναι :
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό
Για ι από 1 μέχρι Ν
Αν α[ι] > max1 τότε
max2 <- max1
max1 <- α[ι]
αλλιώς Αν α[ι] > max2 τότε
max2 <- α[ι]
Τέλος_αν
Τέλος_επανάληψης
Αν max2 <> κάτι_πολύ_μικρό τότε
Εμφάνισε max2
αλλιώς
Εμφάνισε "..."
Τέλος_αν
Ουφ! Ελπίζω να είναι εντάξει τώρα. Η αλλαγή ισχύει πάντα στην περίπτωση που θέλουμε το max1 με το max2 να είναι διαφορετικές ποσότητες.
Μετά κόπων και βασάνων....
Ο δαίμων του κεφαλιού μου έκανε τη δουλειά μου και η πρώτη διόρθωση δεν μπήκε στο δεύτερο post.
Άλλαξα το τελευταίο post και τώρα είναι εντάξει. (ή μέχρι να ξαναβρεί κάποιος κάτι.)
ΠαράθεσηΩστόσο αν θέλουμε να βρούμε τον δεύτερο μεγαλύτερο που είναι διαφορετικός από τον πρώτο, θα πρότεινα ταξινόμηση
Αυτό επισήμανα σε προηγούμενο post και για αυτό το λόγο έκανα την αρχική αλλαγή από
αλλιώς_αν α[ι] > max2 τότε... σε
αλλιώς_αν α[ι] > max2 και α[ι] <> max1 τότε...Έχω την εντύπωση ότι δεν χρειάζεται ταξινόμηση.
Παράθεση από: GEORGIA_LIAMA στις 26 Μαΐου 2008, 12:39:32 ΠΜ
ΠΡΕΠΕΙ ΝΑ ΓΡΑΨΩ ΕΝΑΝ ΑΛΓΟΡΙΘΜΟ: ΠΟΥ ΣΕ ΕΝΑΝ ΠΙΝΑΚΑ ΝΑ ΕΝΤΩΠΙΖΕΙ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ Ή ΤΟΝ ΔΕΥΤΕΡΟ ΜΙΚΡΟΤΕΡΟ ΑΡΙΘΜΟ!
Δεν προσδιορίζει αν θέλει να είναι διαφορετικός από τον πρώτο, άρα κάλλιστα μπορεί ο δεύτερος μεγαλύτερος ίσος με τον πρώτο. Παραθέτω και πάλι τη δικιά μου υλοποιήση.
Αλγόριθμος Οτιναναι
Δεδομένα // Ν, Α//
! Ο αλγόριθμος αυτός κάνει χρήση 2 δεικτών, ο ένας δείχνει τον max ( pos1 )
! και ο δεύτερος ( pos2 ) τον αμέσως επόμενο.
Αν ( Α[1] > A[2]) τότε
pos1<--1
pos2<--2
Aλλιώς
pos1<--2
pos2<--1
Tέλος_αν
Για i από 3 μέχρι Ν
Αν ( Α[i] > Α[pos1] ) τότε ! Σύγκριση με τον μαξ. Αν ισχύει η συνθήκη τότε το νέο στοιχείο είναι μαξ
! και αυτό που ήταν μαξ μπαίνει στη 2η θέση( του αμέσως μεγαλύτερου)
pos2 <-- pos1
pos1 <-- i
Αλλιώς_αν ( A[i] > A[pos2] ) ! Αν δεν μπει στην πρώτη περίπτωση τότε υπάρχει περίπτωση να είναι
! μικρότερο από αυτό που έχουμε ως 2ο και έτσι το αντικαθιστούμε.
pos2 <-- i
Τέλος_αν
Τέλος_επανάληψης
! Οι μεταβλητές pos1 και pos2 τώρα έχουν αποθηκευμένη τη θέση του μεγαλύτερου και του αμέσως
! μεγαλύτερου στοιχείου του πίνακα αντίστοιχα.