Εύρεση δύο μέγιστων τιμών μονοδιάστατου πίνακα χωρίς ταξιμόνηση

Ξεκίνησε από Cloud_Strife, 21 Απρ 2010, 09:41:19 ΠΜ

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

Cloud_Strife

Εδώ είναι ένα πρόγραμμα που βρίσκει τις δύο μέγιστες τιμές max1 και max2 ενός μονοδιάστατου πίνακα (με την κατάλληλη αλλαγή του κώδικα, βρίσκει τρεις, τέσσερις ή περισσότερες) αποφεύγοντας την ταξινόμησή του. Για την θέση μπορουμε να βάλουμε και βοηθητικές μεταβλητές pos1 και pos2 αντίστοιχα.

ΥΓ: Ξέρω μπορεί να είναι πιο γρήγορο η φθίνουσα ταξινόμηση για την εύρεση των μέγιστων τιμών αλλά σας παρουσιάζω μια εναλλακτική λύση, διευρύνοντας τον προγραμματισμό.

ΙΣΧΥΕΙ ΓΙΑ ΑΡΙΘΜΟΥΣ ΜΕΓΑΛΥΤΕΡΟΥΣ Ή ΙΣΟΥΣ ΜΕ ΤΟ ΜΗΔΕΝ!
Το δουλεύω και για αρνητικούς, ίσως πετύχω και κάποια γενίκευση.
Οι αλλαγές θα επισημαίνονται με κόκκινο χρώμα.

ΠΡΟΓΡΑΜΜΑ Εύρεση_2_Μέγιστών_Τιμών
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:  Α[10], j, max1, max2
ΑΡΧΗ
  ΓΙΑ  j ΑΠΟ  1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ  Α[j]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!  Εύρεση πρώτης μέγιστης τιμή μονοδιάστατου πίνακα
  max1 <-- Α[1]
  ΓΙΑ  j ΑΠΟ  2 ΜΕΧΡΙ  10
    ΑΝ  max1<Α[j] ΤΟΤΕ
      max1 <-- Α[j]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!  Εύρεση δεύτερης μέγιστης τιμή μονοδιάστατου πίνακα
max2 <-- -max1! Διόρθωση εκχώρησης τιμής στην μεταβλητή max2 (Αρχική εκχώρηση: max2 <-- Α[1])
  ΓΙΑ  j ΑΠΟ  1 ΜΕΧΡΙ  10
    ΑΝ  max1<>Α[j] ΚΑΙ max2<Α[j] ΤΟΤΕ
      max2 <-- Α[j]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Πρώτη μέγιστή τιμή',max1,' και δεύτερη μέγιστή τιμή',max2
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Εύρεση_2_Μέγιστών_Τιμών

Αλέξανδρος Καουνάς
Μαθητής Γ' Λυκείου
5ο Γενικό Λύκειο Λάρισας

Λάμπρος Μπουκουβάλας

Συγχαρητήρια για την προσπάθεια Αλέξανδρε. Εύχομαι επιτυχία στις εξετάσεις σου!
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

gpapargi

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

Υπάρχουν αρκετές ιδέες για τη λύση αυτής της άσκησης.

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

Στη λύση που έγραψες υπάρχει ένα μικρό μειονέκτημα. Δε γενικεύεται για τυχαίο πλήθος μεγαλύτερων  γιατί θέλει μεταβλητό μέγεθος κώδικα. Δηλαδή δεν μπορείς να διαβάζεις το πλήθος των μεγαλύτερων που θα πρέπει να βρεις και να το βρίσκεις με τον αλγόριθμο που έγραψες. Μπορείς όμως να πας ένα βήμα παρακάτω και να φτιάξεις μια λύση που γενικεύεται για τυχαίο πλήθος.

Σάρωσε από την τυχαία θέση ι και κάτω και βρες τη θέση του μεγαλύτερου. Στη συνέχεια αντιμετάθεσε τα στοιχεία της θέσης ι και αυτής που βρήκες. Μετά γενίκευση για κάθε ι (εξωτερικό αγκάλιασμα Για ι από 1 μέχρι ...).
Έτσι θα καταλήξεις σε μια άλλη μέθοδο ταξινόμησης που λέγεται ταξινόμηση επιλογής. Μετά κάνε 2 εξωτερικές επαναλήψεις.

evry

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

100   1    2    3    4    5    6    7    8    9
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Cloud_Strife

Παράθεση από: evry στις 21 Απρ 2010, 10:43:48 ΠΜ
Καλή η σκέψη σου αλλά αν τύχει ο μεγαλύτερος αριθμός να είναι και ο πρώτος φοβάμαι ότι δεν δουλεύει.
Για παράδειγμα σκέψου τι θα βγάλει για τους παρακάτω αριθμούς

100   1    2    3    4    5    6    7    8    9
Ευχαριστώ για την εύστοχη παρατήρηση ήδη το διόρθωσα αλλά κάνω κάποιες αλλαγές επέκτασης ώστε να ισχύει και για αρνητικούς αριθμούς. Ίσως καταφέρω να το γενικεύσω για Ν αριθμούς κάθε φύσεως, προσπαθώντας φυσικά να γράψω το μικρότερο δυνατό πρόγραμμα. Ώστε να βρίσκει εφαρμογή...
Σύντομα, θα ανανεώσω την αρχική μου δημοσίευση.

Cloud_Strife

Παράθεση από: gpapargi στις 21 Απρ 2010, 10:35:26 ΠΜ
Συγχαρητήρια από μένα για τη διάθεσή σου να βρεις τους 2 μεγαλύτερους χωρίς πλήρη ταξινόμηση. Δείχνει ότι καταλαβαίνεις το πόσο σημαντικό είναι το πλήθος των βημάτων του αλγορίθμου κι ας μην εξετάζεται φέτος.

Υπάρχουν αρκετές ιδέες για τη λύση αυτής της άσκησης.

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

Στη λύση που έγραψες υπάρχει ένα μικρό μειονέκτημα. Δε γενικεύεται για τυχαίο πλήθος μεγαλύτερων  γιατί θέλει μεταβλητό μέγεθος κώδικα. Δηλαδή δεν μπορείς να διαβάζεις το πλήθος των μεγαλύτερων που θα πρέπει να βρεις και να το βρίσκεις με τον αλγόριθμο που έγραψες. Μπορείς όμως να πας ένα βήμα παρακάτω και να φτιάξεις μια λύση που γενικεύεται για τυχαίο πλήθος.

Σάρωσε από την τυχαία θέση ι και κάτω και βρες τη θέση του μεγαλύτερου. Στη συνέχεια αντιμετάθεσε τα στοιχεία της θέσης ι και αυτής που βρήκες. Μετά γενίκευση για κάθε ι (εξωτερικό αγκάλιασμα Για ι από 1 μέχρι ...).
Έτσι θα καταλήξεις σε μια άλλη μέθοδο ταξινόμησης που λέγεται ταξινόμηση επιλογής. Μετά κάνε 2 εξωτερικές επαναλήψεις.
Γιώργο σωστές οι συμβουλές σου, αλλά προσπάθησα να αποφύγω την χρήση πίνακα, χρησιμοποιώντας μεταβλητές, γιατί κάτι τέτοιο θα ήταν αποτελούσε τρόπο ταξινόμηση.
Ωστόσο η γενίκευση γίνεται για πίνακα Ν θέσεων Α[Ν], όπου με έλεγχο θα τοποθετούνται με σειρά στον πίνακα ΜΑΧ[Ν], τα στοιχεία του πίνακα Α, και τελικά θα προβάλλονται Κ στοιχεία (όπου Κ το πλήθος των μέγιστων αριθμών προς εμφάνιση με Κ<=Ν) στοιχεία του πίνακα ΜΑΧ. Απλά επείδη σε κάποια προβλήματα χρειάζονται 2-3 μέγιστα στοιχεία πίνακα, σκέφτηκα αυτό με τις μεταβλητες, με αφορμή τα θέματα του ΟΕΦΕ για φέτος, ψάχνοντας έτσι πάραλληλους τρόπους επίλυσης των προβλημάτων, θέλοντας να παίξω με την ΓΛΩΣΣΑ.

gpapargi

Δε μίλησα καθόλου για δεύτερο πίνακα. Μίλησα μόνο για τον αρχικό πίνακα ή και καθόλου πίνακα (για εύρεση 2 μεγαλύτερων)

Ξέρεις ότι η φυσαλίδα με την πρώτη σάρωση του πίνακα (από κάτω προς τα πάνω) θα φέρει το πρώτο στοιχείο στην πρώτη θέση. Με τη δεύτερη σάρωση θα φέρει το δεύτερο στοιχείο στη δεύτερη θέση. Άρα αν απλά να κάνεις 2 εξωτερικές επαναλήψεις στη φυσαλίδα τελείωσες. Δηλαδή

Για ι από 2 μέχρι 3
  Για j από Ν μέχρι ι με_βήμα -1

Θα σου φέρει τα 2 πρώτα στις 2 πρώτες θέσεις.

Γίνεται επίσης να διαβάζεις Ν αριθμούς και να βρεις τους 2 μεγαλύτερους χωρίς να τα βάζεις καθόλου σε πίνακα. Δες προηγούμενο μήνυμα μου στο σημείο που λέω για τις 2 μεταβλητές.

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

Max_pos<-ι
Για j από ι+1 μέχρι Ν
   Αν α[j] > α[Max_pos] τότε
      Max_pos<-j
   Τέλος_αν
Τέλος_επανάληψης
Αντιμετάθεσε α[ι], α[Max_pos]

Πως θα πεις «Θέλω το παραπάνω κομμάτι κώδικα να εκτελείται για κάθε ι»; Απλά θα το αγκαλιάσεις με μια Για ι.
Αν βάλεις Για ι από 1 μέχρι Ν-1 έχεις κάνει πλήρη ταξινόμηση. Αν βάλεις Για ι από 1 μέχρι κ έχει φέρει τα κ μεγαλύτερα στις κ πρώτες θέσεις. Αν βάλεις Για ι από 1 μέχρι 1 έχει κάνεις εύρεση (θέσεως) μεγίστου.

Cloud_Strife

Παράθεση από: gpapargi στις 21 Απρ 2010, 01:57:04 ΜΜ
Δε μίλησα καθόλου για δεύτερο πίνακα. Μίλησα μόνο για τον αρχικό πίνακα ή και καθόλου πίνακα (για εύρεση 2 μεγαλύτερων)

Ξέρεις ότι η φυσαλίδα με την πρώτη σάρωση του πίνακα (από κάτω προς τα πάνω) θα φέρει το πρώτο στοιχείο στην πρώτη θέση. Με τη δεύτερη σάρωση θα φέρει το δεύτερο στοιχείο στη δεύτερη θέση. Άρα αν απλά να κάνεις 2 εξωτερικές επαναλήψεις στη φυσαλίδα τελείωσες. Δηλαδή

Για ι από 2 μέχρι 3
  Για j από Ν μέχρι ι με_βήμα -1

Θα σου φέρει τα 2 πρώτα στις 2 πρώτες θέσεις.

Γίνεται επίσης να διαβάζεις Ν αριθμούς και να βρεις τους 2 μεγαλύτερους χωρίς να τα βάζεις καθόλου σε πίνακα. Δες προηγούμενο μήνυμα μου στο σημείο που λέω για τις 2 μεταβλητές.

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

Max_pos<-ι
Για j από ι+1 μέχρι Ν
   Αν α[j] > α[Max_pos] τότε
      Max_pos<-j
   Τέλος_αν
Τέλος_επανάληψης
Αντιμετάθεσε α[ι], α[Max_pos]

Πως θα πεις «Θέλω το παραπάνω κομμάτι κώδικα να εκτελείται για κάθε ι»; Απλά θα το αγκαλιάσεις με μια Για ι.
Αν βάλεις Για ι από 1 μέχρι Ν-1 έχεις κάνει πλήρη ταξινόμηση. Αν βάλεις Για ι από 1 μέχρι κ έχει φέρει τα κ μεγαλύτερα στις κ πρώτες θέσεις. Αν βάλεις Για ι από 1 μέχρι 1 έχει κάνεις εύρεση (θέσεως) μεγίστου.
Ευχαριστώ! Πάλι καλά που έχουμε και εσάς (εκπαιδευτικούς ή όχι) και λύνουμε τις απορίες μας!

Γιαννούλης Γιώργος

Παράθεση από: Cloud_Strife στις 21 Απρ 2010, 09:41:19 ΠΜ
  ΓΙΑ  j ΑΠΟ  1 ΜΕΧΡΙ  10
    ΑΝ  max1<>Α[j] ΚΑΙ max2<Α[j] ΤΟΤΕ
      max2 <-- Α[j]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Πρώτη μέγιστή τιμή',max1,' και δεύτερη μέγιστή τιμή',max2
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Εύρεση_2_Μέγιστών_Τιμών
Απο ότι βλέπω ουσιαστικά εδώ κάνεις όλη την δουλειά που τον διαφοροποιείς από το να βρείς απλά το μεγαλύτερο. Στο μόνο που διαφωνώ λίγο είναι το εξής, ο αλγόριθμος αυτός δεν θα δουλέψει και για την περίπτωση που υπάρχουν 2 ίδιοι αριθμοί στον πίνακα

π.χ
100 5 3 7 100 8 89 45 12 34
ο πρώτος max που θα υπολογίσεις θα είναι το 100 και ο δεύτερος το 89 και όχι το σωστό 100 γιατι στο
ΑΝ  max1<>Α[j] ΚΑΙ  max2<Α[j] ΤΟΤΕ
συγκρίνεις την τιμή του max.
Ένας τρόπος να το λύσεις αυτό είναι να μην κρατάς μόνο την μεγιστη τιμή αλλα και την θέση και στο αν να συγκρίνεις αν η θέση είναι διαφορετική

Σε κώδικα έχεις το εξής:

Παράθεση από: Cloud_Strife στις 21 Απρ 2010, 09:41:19 ΠΜ
Εδώ είναι ένα πρόγραμμα που βρίσκει τις δύο μέγιστες τιμές max1 και max2 ενός μονοδιάστατου πίνακα (με την κατάλληλη αλλαγή του κώδικα, βρίσκει τρεις, τέσσερις ή περισσότερες) αποφεύγοντας την ταξινόμησή του. Για την θέση μπορουμε να βάλουμε και βοηθητικές μεταβλητές pos1 και pos2 αντίστοιχα.

ΥΓ: Ξέρω μπορεί να είναι πιο γρήγορο η φθίνουσα ταξινόμηση για την εύρεση των μέγιστων τιμών αλλά σας παρουσιάζω μια εναλλακτική λύση, διευρύνοντας τον προγραμματισμό.

ΙΣΧΥΕΙ ΓΙΑ ΑΡΙΘΜΟΥΣ ΜΕΓΑΛΥΤΕΡΟΥΣ Ή ΙΣΟΥΣ ΜΕ ΤΟ ΜΗΔΕΝ!
Το δουλεύω και για αρνητικούς, ίσως πετύχω και κάποια γενίκευση.
Οι αλλαγές θα επισημαίνονται με κόκκινο χρώμα.

ΠΡΟΓΡΑΜΜΑ Εύρεση_2_Μέγιστών_Τιμών
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:  Α[10], j, max1, max2,θ1
ΑΡΧΗ
  ΓΙΑ  j ΑΠΟ  1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ  Α[j]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!  Εύρεση πρώτης μέγιστης τιμή μονοδιάστατου πίνακα
  max1 <-- Α[1]
θ1<--1
  ΓΙΑ  j ΑΠΟ  2 ΜΕΧΡΙ  10
    ΑΝ  max1<Α[j] ΤΟΤΕ
      max1 <-- Α[j]
      θ1<--j
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!  Εύρεση δεύτερης μέγιστης τιμή μονοδιάστατου πίνακα
  Αν θ1=1 τότε! Αν βρήκες πρίν την μεγιστη τιμή στην 1η θεση τοτε αρχίζεις απο την 2 αλλιώς αρχισε απο την 1η και απλά μην συγκρίνεις με την θέση που βρήκες τον προηγούμενο μέγιστο...
    max2 <-- Α[2]
  Αλλιώς
    max2<--A[1]
  Τέλος_Αν

  ΓΙΑ  j ΑΠΟ  1 ΜΕΧΡΙ  10
    ΑΝ  θ1<>j ΚΑΙ max2<Α[j] ΤΟΤΕ
      max2 <-- Α[j]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Πρώτη μέγιστή τιμή',max1,' και δεύτερη μέγιστή τιμή',max2
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Εύρεση_2_Μέγιστών_Τιμών

zeus.zeusold

και μια διαφορετική απάντηση στο θέμα.

Αν Α[1]>Α[2] τότε
      ΜΑΧ1<-- Α[1]
      Θ1<--1
      ΜΑΧ2<--Α[2]
      Θ2<--2
Αλλιώς
      ΜΑΧ1<-- Α[2]
      Θ1<--2
      ΜΑΧ2<--Α[1]
     Θ2<--1
Τέλος_Αν
Για Ι από 2 μέχρι Ν
   Αν  Α[Ι]> ΜΑΧ1 τότε
      ΜΑΧ2<--ΜΑΧ1
      Θ2<--Θ1
      ΜΑΧ1<--Α[Ι]
      Θ1<--Ι
   Αλλιώς_Αν Α[Ι]>ΜΑΧ2 τότε
      ΜΑΧ2<--Α[Ι]
      Θ2<--Ι
   Τέλλος_Αν
Τέλος_Επανάληψης