Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Δομή επανάληψης => Μήνυμα ξεκίνησε από: nikolasmer στις 19 Οκτ 2013, 08:40:26 ΜΜ

Τίτλος: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 19 Οκτ 2013, 08:40:26 ΜΜ
Να βρεθούν οι τρεις πρώτοι αριθμοί(βαθμοί , επιδόσεις κλπ) από μια πλειάδα τιμών γνωστού ή άγνωστου πλήθους.(Γενικά να βρεθούν οι περισσότεροι από ένας μεγαλύτεροι ή μικρότεροι). Το έκανα πάντα με πίνακες και δεν με απασχόλησε ιδιαίτερα παρά μόνο το 2010 αν θυμάμαι καλά στην άσκηση με τα σκάφη και το δείκτη GPH. Προσπάθησα λίγο και τελικά παρέδωσα τα όπλα και πάλι την είχα λύσει με πίνακες. Καμία ιδέα για τον αλγόριθμο και τη μεθοδολογία του έχει κανείς(Με δομές επανάληψης);
Ευχαριστώ.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: petrosp13 στις 19 Οκτ 2013, 08:51:06 ΜΜ
Θα πρότεινα να έχεις 3 μεταβλητές max και να ελέγχεις κάθε νέο αριθμό σε σχέση με αυτούς, ξεκινώντας από τον μεγαλύτερο
Αν ο αριθμός είναι μεγαλύτερος από το max1, τότε μπαίνει max1 και το max1 μπαίνει στο max2, αφού αυτό μπει στο max3
Αντίστοιχα, για τα max2 και max3
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 19 Οκτ 2013, 09:18:03 ΜΜ
Παράθεση από: petrosp13 στις 19 Οκτ 2013, 08:51:06 ΜΜ
Θα πρότεινα να έχεις 3 μεταβλητές max και να ελέγχεις κάθε νέο αριθμό σε σχέση με αυτούς, ξεκινώντας από τον μεγαλύτερο
Αν ο αριθμός είναι μεγαλύτερος από το max1, τότε μπαίνει max1 και το max1 μπαίνει στο max2, αφού αυτό μπει στο max3
Αντίστοιχα, για τα max2 και max3

Πέτρο ευχαριστώ. Θα το προσπαθήσω! ;)
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: gpapargi στις 20 Οκτ 2013, 09:37:49 ΠΜ
Μια εύκολη υλοποίηση η οποία όμως κάνει πιο πολλές σαρώσεις του πίνακα από μια, είναι η τροποποίηση της φυσσαλίδας στον εξωτερικό βρόχο. Αφού ξέρεις ότι η φυσσαλίδα ανεβάζει στην πρώτη σάρωση τον μεγαλύυερο στην πρώτη θέση, στη δεύτερη σάρωση τον δεύτερο στη δεύτερη θέση κλπ, μπορείς να κάνει 3 εξωτερικές σάρώσεις. Πχ Για ι από 2 μέχρι 4... Στη γενική περίπτωση κ εξωτερικές σαρώσεις
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 20 Οκτ 2013, 10:15:39 ΠΜ
Το παρακάτω το τέσταρα και νομίζω οτι παίζει.
Κώδικας [Επιλογή]

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


Με την προϋπόθεση οτι η επανάληψη θα γίνεται τουλαχιστον 3 φορές.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 20 Οκτ 2013, 10:56:01 ΠΜ
Αν είχαμε πίνακες και θέλαμε τα εμφανίσουμε τους τρείς πρώτους ή γενικότερα έναν αριθμό από πρώτους, τότε στον αλγόριθμο ταξινόμησης φυσαλλίδας θα βάζαμε η εξωτερική επανάληψη να γίνεται τόσες φορές όσα είναι και τα στοιχεία που θέλουμε. Επίσης με μια είσοδο σε μια διαδικασία του αριθμού των μεγαλύτερων στοιχείων που θέλουμε , μπορούσαμε να σχηματίσουμε και ενα αντίστοιχο υποπρόγραμμα. Αναρωτιέμαι, ο παραπάνω αλγόριθμος με δομή επανάληψης, γίνεται υποπρόγραμμα με επιπλέον είσοδο το πλήθος των μέγιστων που ψάχνουμε;
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: petrosp13 στις 20 Οκτ 2013, 11:13:22 ΠΜ
Παράθεση από: nikolasmer στις 20 Οκτ 2013, 10:56:01 ΠΜ
γίνεται υποπρόγραμμα με επιπλέον είσοδο το πλήθος των μέγιστων που ψάχνουμε;

Μόνο με πίνακα για τα μέγιστα
Δεν γίνεται με μεταβλητές
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: gkatsion στις 20 Οκτ 2013, 06:29:43 ΜΜ
Είναι πολύ βασικό αυτό που αναφέρεις συνάδελφε στην αρχή.

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

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

Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: gpapargi στις 21 Οκτ 2013, 08:53:45 ΠΜ
Η αλήθεια είναι ότι δεν πρόσεξα ότι μπορεί το πλήθος των στοιχείων μπορεί να είναι και άγνωστο γι αυτό έγραψα για μερική ταξινόμηση (πχ 3 εξωτερικές επαναλήψεις).

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

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

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

Φοβερό. Πολύ ωραίο!
Άρα τότε γίνεται υποπρόγραμμα απλά όπως είπε και ο Πέτρος παραπάνω δεν μπορούμε να το λύσουμε μόνο με δομές επανάληψης παρά μόνο με πίνακες.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: petrosp13 στις 21 Οκτ 2013, 11:12:09 ΠΜ
Και λύνεται μόνο με πίνακες γιατί δεν ξέρεις ακριβές πλήθος αποτελεσμάτων που θέλεις να βρεις, άρα δεν ξέρεις πόσες εντολές και πόσες μεταβλητές θα χρειαστείς
Αυτό παραμετροποιείται μόνο με θέσεις πίνακα Α
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: elepap στις 10 Ιαν 2014, 10:58:48 ΜΜ
Αλγόριθμος διαβάζει 20 βαθμούς, να βρίσκει τους 3 μεγαλύτερους.
Υπάρχει λύση χωρίς την χρήση πινάκων;
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 10 Ιαν 2014, 11:07:44 ΜΜ
Διάβασε όλο το παραπάνω τοπικ και ίσως οδηγηθείς στη λύση σε αυτό που ψάχνεις.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: elepap στις 10 Ιαν 2014, 11:34:05 ΜΜ
Ευχαριστώ για την άμεση απάντηση nikolasmer.
Τώρα έριξα μια ματιά στον κώδικα που έγραψες. Έχει όμως ένα πρόβλημα. Σε περίπτωση που κάποιος εισάγει από την πρώτη επανάληψη τον μεγαλύτερο βαθμό τότε θα εμφανίσει και τους 3 ίδιους.
Για παράδειγμα αν εισάγεις 20,16,12,10,9,18,7,13,15,8
θα έπρεπε να εμφανίσει μαχ1=20, μαχ2=18, μαχ3=16
εμφανίζει όμως μαχ1=20, μαχ2=20, μαχ3=20
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: Αποστολάτος Άκης στις 10 Ιαν 2014, 11:46:23 ΜΜ
μπορεις να κάνεις το εξής: κατατάσεις τους 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
  τέλος_αν
τέλος_επανάληψης
   
αλλά δε βρίσκω λόγο να το κάνεις χωρίς πίνακες.....
Καλό βράδυ & καλή συνέχεια.....
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: ikariofil στις 10 Ιαν 2014, 11:48:33 ΜΜ
Για θετικούς αριθμούς

Αλγόριθμος μαχ_για_τρεις
μαχ1 ← 0
μαχ2 ← 0
μαχ3 ← 0
Για ι από 1 μέχρι 10
  Διάβασε χ
  Αν χ > μαχ1 τότε
    μαχ3 ← μαχ2
    μαχ2 ← μαχ1
    μαχ1 ← χ
  αλλιώς_αν χ > μαχ2 τότε
    μαχ3 ← μαχ2
    μαχ2 ← χ
  αλλιώς_αν χ > μαχ3 τότε
    μαχ3 ← χ
  Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε μαχ1, μαχ2, μαχ3
Τέλος μαχ_για_τρεις
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 10 Ιαν 2014, 11:52:52 ΜΜ
Με πρόλαβαν οι συνάδελφοι. Και οι δυο λύσεις είναι τέλειες. Αυτή που είχα παραθέσει δεν δουλεύει και τόσο καλά.
Ευχαριστώ και γω όλους σας.
Καλό βράδυ.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: itt στις 10 Ιαν 2014, 11:54:10 ΜΜ
Αλλά γιατί αφού ξέρεις το μέγεθος του πίνακα, να τον αποφύγεις. Δεν δαγκώνουν.
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: nikolasmer στις 11 Ιαν 2014, 12:01:33 ΠΜ
Παράθεση από: itt στις 10 Ιαν 2014, 11:54:10 ΜΜ
Αλλά γιατί αφού ξέρεις το μέγεθος του πίνακα, να τον αποφύγεις. Δεν δαγκώνουν.
;D
+1
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: elepap στις 11 Ιαν 2014, 10:16:57 ΠΜ
Ναι το ξέρω ότι με πίνακες λύνεται τσακ μπαμ, αλλά υπήρχε απορία από ένα παιδί και ήθελα λίγο να το δω και με αυτό τον τρόπο.
Ευχαριστώ
Τίτλος: Απ: Οι τρείς μεγαλύτεροι (ή μικρότεροι)
Αποστολή από: danaos75 στις 13 Απρ 2014, 08:52:59 ΜΜ
Επειδή μας παίδεψε με έναν μαθητή μου μία άσκηση που του έδωσαν στο σχολείο
βρήκα αυτή την λύση που δουλεύει και για θετικούς και για αρνητικούς.
τα 2 τελευταία "αλλιώς_αν" είναι για να καλύψουν ακριβώς την περίπτωση
που αναφέρει ο/η συνάδελφος elepap "Σε περίπτωση που κάποιος εισάγει από την πρώτη
επανάληψη τον μεγαλύτερο βαθμό τότε θα εμφανίσει και τους 3 ίδιους"
Ενώ το "Αν Ν <> Μεγ1 και Ν <> Μεγ2 και Ν <> Μεγ3 τότε" είναι για να καλύψει
την περίπτωση να δωθει ξανα ένας αριθμός που είναι ήδη καταχωρημένος σαν π.χ. Μεγ1
και να αλλάξει την μετάβλητη Μεγ2 (π.χ. στην περίπτωση της εισαγωγής των 20,15,16,20)
στον αλγόριθμο των φίλων ikariofil και Αποστολάκη θα αλλάξει την μαχ2 σε 20 ενώ θα έπρεπε να παραμείνει 16.
Άρα αν μία τιμή έχει ήδη καταχωρηθεί σαν ενα απο τα μέγιστα τότε μην ασχοληθεις καθόλου.

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

Ελπίζω να βοήθησα έχετε ένα ΚΑΤΑΠΛΗΚΤΙΚΟ FORUM. Κρίμα για την ΑΕΠΠ.