Οι τρείς μεγαλύτεροι (ή μικρότεροι)

Ξεκίνησε από nikolasmer, 19 Οκτ 2013, 08:40:26 ΜΜ

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

nikolasmer

Να βρεθούν οι τρεις πρώτοι αριθμοί(βαθμοί , επιδόσεις κλπ) από μια πλειάδα τιμών γνωστού ή άγνωστου πλήθους.(Γενικά να βρεθούν οι περισσότεροι από ένας μεγαλύτεροι ή μικρότεροι). Το έκανα πάντα με πίνακες και δεν με απασχόλησε ιδιαίτερα παρά μόνο το 2010 αν θυμάμαι καλά στην άσκηση με τα σκάφη και το δείκτη GPH. Προσπάθησα λίγο και τελικά παρέδωσα τα όπλα και πάλι την είχα λύσει με πίνακες. Καμία ιδέα για τον αλγόριθμο και τη μεθοδολογία του έχει κανείς(Με δομές επανάληψης);
Ευχαριστώ.
Μερεντίτης Νικόλαος
Πληροφορικός

petrosp13

Θα πρότεινα να έχεις 3 μεταβλητές max και να ελέγχεις κάθε νέο αριθμό σε σχέση με αυτούς, ξεκινώντας από τον μεγαλύτερο
Αν ο αριθμός είναι μεγαλύτερος από το max1, τότε μπαίνει max1 και το max1 μπαίνει στο max2, αφού αυτό μπει στο max3
Αντίστοιχα, για τα max2 και max3
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

nikolasmer

Παράθεση από: petrosp13 στις 19 Οκτ 2013, 08:51:06 ΜΜ
Θα πρότεινα να έχεις 3 μεταβλητές max και να ελέγχεις κάθε νέο αριθμό σε σχέση με αυτούς, ξεκινώντας από τον μεγαλύτερο
Αν ο αριθμός είναι μεγαλύτερος από το max1, τότε μπαίνει max1 και το max1 μπαίνει στο max2, αφού αυτό μπει στο max3
Αντίστοιχα, για τα max2 και max3

Πέτρο ευχαριστώ. Θα το προσπαθήσω! ;)
Μερεντίτης Νικόλαος
Πληροφορικός

gpapargi

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

nikolasmer

Το παρακάτω το τέσταρα και νομίζω οτι παίζει.
Αλγόριθμος μαχ_για_τρεις
Για ι από 1 μέχρι 10
  Διάβασε χ
  Αν ι = 1 τότε
    μαχ1 ← χ
    μαχ2 ← χ
    μαχ3 ← χ
  Τέλος_αν
  Αν χ > μαχ1 τότε
    μαχ3 ← μαχ2
    μαχ2 ← μαχ1
    μαχ1 ← χ
  αλλιώς_αν χ > μαχ2 τότε
    μαχ3 ← μαχ2
    μαχ2 ← χ
  αλλιώς_αν χ > μαχ3 τότε
    μαχ3 ← χ
  Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε μαχ1, μαχ2, μαχ3
Τέλος μαχ_για_τρεις


Με την προϋπόθεση οτι η επανάληψη θα γίνεται τουλαχιστον 3 φορές.
Μερεντίτης Νικόλαος
Πληροφορικός

nikolasmer

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

petrosp13

Παράθεση από: nikolasmer στις 20 Οκτ 2013, 10:56:01 ΠΜ
γίνεται υποπρόγραμμα με επιπλέον είσοδο το πλήθος των μέγιστων που ψάχνουμε;

Μόνο με πίνακα για τα μέγιστα
Δεν γίνεται με μεταβλητές
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

gkatsion

Είναι πολύ βασικό αυτό που αναφέρεις συνάδελφε στην αρχή.

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

Αλλά αν η πλειάδα των αριθμών είναι άγνωστη τότε σίγουρα δεν χρησιμοποιείς πίνακα
γιατί δεν μπορείς να ορίσεις το μέγεθος του και χρησιμοποιείς σίγουρα 3 μεταβλητές!

ΈΞΟΔΟΣ_ΑΠΟ_ΛΥΚΕΙΟ <-- ΑΕΙ + PHD + ΑΣΕΠ

gpapargi

Η αλήθεια είναι ότι δεν πρόσεξα ότι μπορεί το πλήθος των στοιχείων μπορεί να είναι και άγνωστο γι αυτό έγραψα για μερική ταξινόμηση (πχ 3 εξωτερικές επαναλήψεις).

Ωστόσο μια που τέθηκε το θέμα, έχει ενδιαφέρον να δούμε πόσο μπορεί να γενικευτεί. Δηλαδή αν θέλεις τους 100 μεγαλύτερους και δεν ξέρεις το συνολικό πλήθος (απλά ξέρεις ότι είναι πάνω από 100) τότε πως μπορείς να βρεις τους 100 πρώτους; Δηλαδή αν θέλεις τους κ μεγαλύτερους (κ γνωστό) και δεν έχεις το συνολικό πλήθος (ξέρεις απλά ότι είναι μεγαλύτερο του κ) πως μπορείς να το λύσεις;

Μπορείς να πάρεις ένα πίνακα κ θέσεων (αφού το κ είναι γνωστό), να το ταξινομήσεις (αφού διαβάσεις τους κ πρώτους που θα εισαχθούν) και μετά για κάθε ένα καινούργιο αριθμό που διαβάζεις να σαρώνεις τον πίνακα για να δεις ποια είναι η θέση που πρέπει να μπει. Αν υπάρχει τέτοια θέση, τον κάνεις insert (δηλαδή τον βάζεις και σπρώχνεις τα άλλα μια θέση κάτω). Ο ένας πέφτει έξω από τον πίνακα. Αν όμως είναι μικρότερος από αυτόν στην θέση κ τότε δεν μπαίνει καθόλου. Έχει ενδιαφέρον σαν άσκηση. Μοιάζει πολύ με την insert sort ως προς τις ιδέες που περικλείει.

nikolasmer

Παράθεση από: gpapargi στις 21 Οκτ 2013, 08:53:45 ΠΜ
Ωστόσο μια που τέθηκε το θέμα, έχει ενδιαφέρον να δούμε πόσο μπορεί να γενικευτεί. Δηλαδή αν θέλεις τους 100 μεγαλύτερους και δεν ξέρεις το συνολικό πλήθος (απλά ξέρεις ότι είναι πάνω από 100) τότε πως μπορείς να βρεις τους 100 πρώτους; Δηλαδή αν θέλεις τους κ μεγαλύτερους (κ γνωστό) και δεν έχεις το συνολικό πλήθος (ξέρεις απλά ότι είναι μεγαλύτερο του κ) πως μπορείς να το λύσεις;

Μπορείς να πάρεις ένα πίνακα κ θέσεων (αφού το κ είναι γνωστό), να το ταξινομήσεις (αφού διαβάσεις τους κ πρώτους που θα εισαχθούν) και μετά για κάθε ένα καινούργιο αριθμό που διαβάζεις να σαρώνεις τον πίνακα για να δεις ποια είναι η θέση που πρέπει να μπει. Αν υπάρχει τέτοια θέση, τον κάνεις insert (δηλαδή τον βάζεις και σπρώχνεις τα άλλα μια θέση κάτω). Ο ένας πέφτει έξω από τον πίνακα. Αν όμως είναι μικρότερος από αυτόν στην θέση κ τότε δεν μπαίνει καθόλου. Έχει ενδιαφέρον σαν άσκηση. Μοιάζει πολύ με την insert sort ως προς τις ιδέες που περικλείει.

Φοβερό. Πολύ ωραίο!
Άρα τότε γίνεται υποπρόγραμμα απλά όπως είπε και ο Πέτρος παραπάνω δεν μπορούμε να το λύσουμε μόνο με δομές επανάληψης παρά μόνο με πίνακες.
Μερεντίτης Νικόλαος
Πληροφορικός

petrosp13

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

elepap

Αλγόριθμος διαβάζει 20 βαθμούς, να βρίσκει τους 3 μεγαλύτερους.
Υπάρχει λύση χωρίς την χρήση πινάκων;

nikolasmer

Διάβασε όλο το παραπάνω τοπικ και ίσως οδηγηθείς στη λύση σε αυτό που ψάχνεις.
Μερεντίτης Νικόλαος
Πληροφορικός

elepap

Ευχαριστώ για την άμεση απάντηση nikolasmer.
Τώρα έριξα μια ματιά στον κώδικα που έγραψες. Έχει όμως ένα πρόβλημα. Σε περίπτωση που κάποιος εισάγει από την πρώτη επανάληψη τον μεγαλύτερο βαθμό τότε θα εμφανίσει και τους 3 ίδιους.
Για παράδειγμα αν εισάγεις 20,16,12,10,9,18,7,13,15,8
θα έπρεπε να εμφανίσει μαχ1=20, μαχ2=18, μαχ3=16
εμφανίζει όμως μαχ1=20, μαχ2=20, μαχ3=20

Αποστολάτος Άκης

μπορεις να κάνεις το εξής: κατατάσεις τους 3 πρωτους ξέχωρα...


διαβασε χ1,χ2,χ3
αν χ1 >=χ2 και χ2 >=χ3 τοτε
  μαχ1 <-- χ1
  μαχ2 <-- χ2
  μαχ3 <-- χ3
αλλιως_αν χ1 >=χ2 και χ3 >=χ2 τοτε
   μαχ1 <-- χ1
  μαχ2 <-- χ2
  μαχ3 <-- χ3
αλλιως_αν χ2 >=χ1 και χ1 >=χ3 τοτε
  μαχ1 <-- χ2
  μαχ2<-- χ1
  μαχ3 <-- χ3
αλλιως_αν χ2>=χ1 και χ3>=χ1 τοτε
  μαχ1 <-- χ2
  μαχ2 <-- χ3
  μαχ2 <-- χ1
αλλιως_αν χ3>=χ1 και χ1>=χ2 τοτε
  μαχ1<-- χ3
  μαχ2<-- χ1
  μαχ3<-- χ2
αλλιως
  μαχ1 <-- χ3
  μαχ2 <-- χ2
  μαχ3 <-- χ1
τελος_αν

και ύστερα τους υπόλοιπους
για k από 4 μέχρι 20
  Διάβασε x
  Αν x >  μαχ1 Τότε
     μαχ3 <-- μαχ2
     μαχ2 <--  μαχ1
     μαχ1<-- x
  αλλιώς_αν x > μαχ2 Τότε
     μαχ3 <-- μαχ2
     μαχ2 <-- x
  αλλιώς_αν x > μαχ3 τότε
     μαχ3 <-- x
  τέλος_αν
τέλος_επανάληψης
   
αλλά δε βρίσκω λόγο να το κάνεις χωρίς πίνακες.....
Καλό βράδυ & καλή συνέχεια.....