ευρεση αριθμου σε πινακα

Ξεκίνησε από GEORGIA_LIAMA, 26 Μαΐου 2008, 12:39:32 ΠΜ

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

GEORGIA_LIAMA

ΜΗΠΩΣ ΞΕΡΕTE ΤΙ ΠΡΕΠΕΙ ΝΑ ΚΑΝΩ?

ΠΡΕΠΕΙ ΝΑ ΓΡΑΨΩ ΕΝΑΝ ΑΛΓΟΡΙΘΜΟ: ΠΟΥ ΣΕ ΕΝΑΝ ΠΙΝΑΚΑ ΝΑ ΕΝΤΩΠΙΖΕΙ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ Ή ΤΟΝ ΔΕΥΤΕΡΟ ΜΙΚΡΟΤΕΡΟ ΑΡΙΘΜΟ!

ΕΓΩ ΤΟ ΕΛΥΣΑ  ΑΛΛΑ ΔΕΝ ΞΕΡΩ ΝΑ ΒΡΩ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ. ΒΡΙΣΚΩ ΜΟΝΟ ΤΟΝ ΠΡΩΤΟ ΜΕΓΑΛΥΤΕΡΟ.ΕΝΩ ΑΥΤΟΣ ΘΕΛΕΙ ΚΑΤΕΥΘΕΙΑΝ ΟΤΑΝ ΤΟ ΤΡΕΧΩ ΤΟ ΠΡΟΓΡΑΜΜΑ ΝΑ ΜΟΥ ΔΙΝΕΙ ΤΟΝ ΔΕΥΤΕΡΟ ΜΕΓΑΛΥΤΕΡΟ ΑΡΙΘΜΟ


ΛΥΣΗ (ΕΒΑΛΑ ΟΤΙ Ο ΠΙΝΑΚΑΣ ΕΙΝΑΙ ΜΟΝΟΔΙΑΣΤΑΤΟΣ)


ΑΛΓΟΡΙΘΜΟΣ

ΕΥΡΕΣΗ_ΔΕΥΤΕΡΟΥ_ΜΕΓΑΛΥΤΕΡΟΥ


    ΔΕΔΟΜΕΝΑ // Ν,Α //
 
    ΜΕΓΙΣΤΟΣ<------ Α[1]
   
    ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
   
         ΑΝ ΜΕΓΙΣΤΟΣ<Α

    ΤΟΤΕ

               ΜΕΓΙΣΤΟΣ<-----Α
             
         ΤΕΛΟΣ_ΑΝ 

     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

     ΑΠΟΤΕΛΕΣΜΑ // ΜΕΓΙΣΤΟΣ //

ΤΕΛΟΣ ΕΥΡΕΣΗ_ΔΕΥΤΕΡΟΥ_ΜΕΓΑΛΥΤΕΡΟΥ




ΕΙΠΑ ΕΣΤΩ ΟΤΙ ΤΟ ΠΡΩΤΟ ΣΤΟΙΧΕΙΟ ΤΟΥ ΠΙΝΑΚΑ ΕΙΝΑΙ ΤΟ ΜΕΓΙΣΤΟ

ΤΟΤΕ ΝΑ ΚΑΝΕΙ ΣΥΓΚΡΙΣΗ ΤΟΥ ΥΠΟΤΙΘΕΜΕΝΟΥ ΜΕΓΙΣΤΟΥ ΜΕ ΤΟΥΣ ΥΠΟΛΟΙΠΟΥΣ ΑΡΙΘΜΟΥΣ ΤΟΥ ΠΙΝΑΚΑ.

ΚΑΙ ΑΝ ΒΡΕΙ ΜΕΓΑΛΥΤΕΡΟ ΑΡΙΘΜΟ ΑΠΟ ΤΟΝ ΥΠΟΤΙΘΕΜΕΝΟ ΔΙΚΟ ΜΟΥ ΜΕΓΙΣΤΟ ΝΑ ΘΕΩΡΗΣΕΙ ΑΥΤΟΝ ΣΑΝ ΜΕΓΙΣΤΟ.

ΣΑΣ ΕΥΧΑΡΙΣΤΩ

P.Tsiotakis

Τα πιο απλά βήματα που μπόρεσα να σκεφτώ για επίλυση της άσκησης, είναι:

1. Φθίνουσα ταξινόμηση του πίνακα
2. Εντοπισμό όλων των στοιχείων που είναι ίσα με το μέγιστο (πρώτο στοιχείο)
3. Το αμέσως επόμενο στοιχείο (αν υπάρχει) είναι το δεύτερο μεγαλύτερο

Αλγόριθμος Δυο
  Δεδομένα // Ν, Α //
  ! φθίνουσα ταξινόμηση πίνακα Α[Ν]
  ......................................
  μ ← 0
  Για ι απο 1 μέχρι Ν
    Αν Α[ι] = Α[1] τότε ! ίσα με το μέγιστο
      μ ← μ + 1
    Τέλος_αν
  Τέλος_επανάληψης

  Αν μ = Ν τότε
    Εμφάνισε "Όλα τα στοιχεία ίσα"
  Αλλιώς
   Εμφάνισε Α[μ+1]
  Τέλος_αν

Τέλος Δυο


Ελπίζω να μην έκανα κάποιο λάθος, βιασύνης  ;)
Καλή συνέχεια,

koniordos

Μία λύση με δύο περάσματα στον πίνακα

    μεγ1 <- Α[1]
    μιν <- Α[1]
    ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
        ΑΝ Α[ι] > μεγ1 ΤΟΤΕ
           μεγ1 <- Α[ι]
        ΤΕΛΟΣ_ΑΝ
        ΑΝ Α[ι] < μιν ΤΟΤΕ
           μιν <- Α[ι]
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    !Αρχικοποιώ στον ελάχιστο, ώστε να μην πέσω πάνω στο μεγαλύτερο όλων
    μεγ2 <- μιν
    ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
        ΑΝ Α[ι] > μεγ2 ΚΑΙ Α[ι] <> μεγ1 ΤΟΤΕ
           μεγ2 <- Α[ι]
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    !στη δυσμενέστερη περίπτωση που όλα τα στοιχεία είναι ίσα, είμαι καλυμένος
    ΑΝ μεγ1 = μεγ2 ΤΟΤΕ
        ΓΡΑΨΕ 'Πλήρης ισότητα'
    ΤΕΛΟΣ_ΑΝ
Τσορώνης Τάκης
Ηλ.Μηχ. & Μηχ. Η/Υ ΕΜΠ

sstergou

#3
edit: Διορθωμένος κώδικας

Κώδικας: ψευδογλώσσα
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό

Για ι από 1 μέχρι Ν
  Αν α[ι] > max1 τότε
    max2 <- max1
    max1 <- α[ι]
  αλλιώς αν α[ι] > max2 τότε
    max2 <- α[ι]
  τέλος_αν
Τέλος_επανάληψης

Εμφάνισε max2

potato

#4
  @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: ίδιος τρόπος με τον από πάνω  :( (γραψαμε την ίδια στιγμή)
Be open source. Knowledge belongs to the world.

evry

Ο παρακάτω θα ήταν ένας πολύ καλός τρόπος για να εισάγεις τα παιδιά στην ταξινόμηση και πιο συγκεκριμένα στην ταξινόμηση με εισαγωγή αν αυτή ήταν εντός ύλης. Αν το δοκιμάσεις για 3 μεγαλύτερους γενικεύεται στην insertion sort στον πίνακα max[ ].

Παράθεση από: sstergou στις 26 Μαΐου 2008, 08:35:48 ΜΜ
Κώδικας: ψευδογλώσσα
max1 <- α[1]
max2 <- α[1]

Για ι από 2 μέχρι Ν
  Αν α[ι] > max1 τότε
    max2 <- max1
    max1 <- α[ι]
  αλλιώς αν α[ι] > max2 τότε
    max2 <- α[ι]
  τέλος_αν
Τέλος_επανάληψης

Εμφάνισε max2

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Laertis

Υπάρχει αντίστοιχη λυμένη άσκηση στο Τετράδιο μαθητή σελ. 39 Παράδειγμα 3 για την εύρεση των 2 ελαχίστων.
Μια ακόμη λύση (απλοϊκή)-έτσι για την ιστορία - είναι η εύρεση του μεγίστου , η ανταλλαγή του με το στοιχείο της 1ης θέσης (αν δεν έχει βρεθεί εκεί) του πίνακα και η εκ νέου σάρωση για την εύρεση του 2ου μεγίστου απο την 2η θέση και μετά.
Georgia έχεις ήδη 5 λύσεις, διάλεξε και πάρε  ;)

max <- Α[1]
θέση<- 1
    ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
        ΑΝ Α[ι] > max ΤΟΤΕ
           max <- Α[ι]
           θέση<- ι
        ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Αν θέση<>1 τότε αντιμετάθεσε Α[θέση], Α[1]
max2 <- Α[2]
    ΓΙΑ ι ΑΠΟ 3 ΜΕΧΡΙ Ν
        ΑΝ Α[ι] > max2 ΤΟΤΕ
           max2 <- Α[ι]
        ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Εμφάνισε max2
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

sstergou

#7
Δυστυχώς Ευριπίδη στο βιβλίο υπάρχει μόνο ο bubble sort  :( , ο οποίος εξηγείται σχετικά δύσκολα σε σχέση με άλλους αλγόριθμους που κατά καιρούς έχουν δημοσιευτεί στο στέκι.

Το κόλπο που έκλεψα (από ένα βιντεάκι στο youtube) για να εξηγήσω την φυσαλίδα είναι το εξής:
Σηκώνω 6-7 μαθητές όρθιους και τους βάζω με μια ευνοϊκή για την φυσαλίδα σειρά. Στη συνέχεια τους αντιμεταθέτω σύμφωνα με τον αλγόριθμο του βιβλίου με σκοπό να φτιάξω μια σειρά από μαθητές ταξινομημένους με φθίνουσα σειρά.

Αν τους ταξινομήσω και στη συνέχεια εξακολουθώ να κάνω ελέγχους για αντιμεταθέσεις αυτοί ρωτάνε το γιατί...!

sstergou

#8
Μάλλον οι αλγόριθμοι λύνουν διαφορετικά πρόβληματα  :-X
Κάποιοι βρίσκουν τον δεύτερο μεγαλύτερο ο οποίος είναι διαφορετικός από τον πρώτο ενώ κάποιοι άλλοι απλά τον δεύτερο μεγαλύτερο.

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

edit:Διορθωμένος κώδικας


Κώδικας: ψευδογλώσσα
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό
Για ι από 1 μέχρι Ν
  Αν α[ι] > max1 τότε
    max2 <- max1
    max1 <- α[ι]
  αλλιώς_αν α[ι] > max2 και α[ι] <> max1 τότε
    max2 <- α[ι]
  Τέλος_αν
Τέλος_επανάληψης

Αν max2 <> κάτι_πολύ_μικρό τότε
   Εμφάνισε max2
αλλιώς
  Εμφάνισε "..."
Τέλος_αν

Laertis

Έχεις δίκιο Στάθη, θα πρέπει να διευκρινιστεί αν όλα τα στοιχεία του πίνακα είναι διαφορετικά ή μπορεί να επαναλαμβάνονται περισσότερες φορές. Ο αλγόριθμος που έδωσα παραπάνω ισχύει για την 1η περίπτωση.
Για την 2η περίπτωση πρέπει να τροποποιηθεί όπως στο παράδειγμα που έδωσε ο koniordos.
.......................
ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
        ΑΝ Α[ι] > μεγ2 ΚΑΙ Α[ι] <> μεγ1 ΤΟΤΕ
           μεγ2 <- Α[ι]
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
........................
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

gpapargi

Παιδιά ένα ωραίο ασκησάκι που τους βάζω για να δω ποιοι στροφάρουν είναι το εξής:
Πριν μπω στους πίνακες και όσο είμαι στις εντολές επανάληψης τους βάζω να διαβάσουν 100 αριθμούς και να βρουν τους 2 μεγαλύτερους. Θα εκπλαγείτε από το πόσο λίγοι το λύνουν. Αν θυμάμαι καλά μόνο φέτος είχα έναν που το έλυσε και αυτός με την πρώτη το υποτίμησε και το πήγε βιαστικά. Τα προηγούμενα χρόνια τίποτα.

Δε θυμάμαι ποτέ κάποιον που να του το έδωσα για το σπίτι  και να μου έφερε τη λύση με την πρώτη σωστά.

Εννοείται πως τους τσιγκλάω και κατάλληλα: "τη συγκεκριμένη άσκηση δε μου την έχει λύσει ποτέ κανείς... ποιος θα είναι ο πρώτος που θα γίνει ήρωας κλπ"  ;)

evry


  Την άλλη φορά πριν μπεις στους πίνακες βάλτους την εξής άσκηση:

Να γράψετε αλγόριθμο ο οποίος να διαβάζει αριθμούς μέχρι το άθροισμά τους να ξεπεράσει το 1000 και στη συνέχεια να εμφανίζει ποια θα ήταν η θέση του 1ου αριθμού που δόθηκε αν αριθμοί ήταν ταξινομημένοι.

Μπορείς να βελτιώσεις λίγο την διατύπωση γιατί κάπου χάνει μου φαίνεται
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

Στο 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)

Juan

Καλησπέρα.. Έχω μια ένσταση στην αρχικοποίηση του 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 <- α[ι]
  Τέλος_αν
Τέλος_επανάληψης


Φιλικά Γιάννης

sstergou

#14
Ναι έχεις δίκιο. Ανακάλυψα και άλλο πρόβλημα όμως:
Αν ο μέγιστος είναι στο α[1] και στο α[2] πάλι λάθος !

Τελικά το σωστό είναι :
Κώδικας: ψευδογλώσσα
max1 <- κάτι_πολύ_μικρό !π.χ. -(2^60)
max2 <- κάτι_πολύ_μικρό

Για ι από 1 μέχρι Ν
  Αν α[ι] > max1 τότε
    max2 <- max1
    max1 <- α[ι]
  αλλιώς_αν α[ι] > max2 και α[ι] <> max1 τότε
    max2 <- α[ι]
  Τέλος_αν
Τέλος_επανάληψης

Αν max2 <> κάτι_πολύ_μικρό τότε
  Εμφάνισε max2
αλλιώς
  Εμφάνισε "..."
Τέλος_αν


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