Εύρεση Ν μεγαλύτερων από άγνωστο πλήθος δεδομένων

[nikolasmer]

Χαιρετώ.
Σε μια ανάγνωση του Δ θέματος του ΟΕΦΕ του 2015 προσπάθησα να απομονώσω το ερώτημα της "Εύρεσης των 10 μεγαλύτερων στοιχείων από άγνωστο πλήθος δεδομένων. Δεν υπάρχει πίνακας για όλα, συνεπώς ταξινόμηση όλων και εμφάνιση των 10 μεγαλύτερων αποκλείεται. Δυο τρόπους λύσης σκέφτηκα αλλά είναι και οι δύο σκουπίδια θεωρώ. Τιμή φρουρός το 0 και υποθέτουμε πως θα εισαχθούν τουλάχιστον 10 στοιχεία.
1ος τρόπος: Βάζω τα 10 και από εκεί και έπειτα ταξινομώ, συγκρίνω το τελευταίο με το καινούριο στοιχείο και έπειτα ξανά ταξινόμηση κλπ.

ΠΡΟΓΡΑΜΜΑ ΤΡΟΠΟΣ1
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ι, J, Χ, ΤΕΜΠ, Π[10] 
ΑΡΧΗ
  Ι <- 1
  ΔΙΑΒΑΣΕ Χ
  ΟΣΟ Χ <> 0 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Ι <= 10 ΤΟΤΕ
      Π[Ι] <- Χ
    ΑΛΛΙΩΣ
      ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ 10
        ΓΙΑ J ΑΠΟ 10 ΜΕΧΡΙ Ι ΜΕ_ΒΗΜΑ -1
          ΑΝ Π[J - 1] < Π[J] ΤΟΤΕ
            ΤΕΜΠ <- Π[J - 1] 
            Π[J - 1] <- Π[J] 
            Π[J] <- ΤΕΜΠ
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΑΝ Π[10] < Χ ΤΟΤΕ
        Π[10] <- Χ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    Ι <- Ι + 1
    ΔΙΑΒΑΣΕ Χ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ 10
    ΓΙΑ J ΑΠΟ 10 ΜΕΧΡΙ Ι ΜΕ_ΒΗΜΑ -1
      ΑΝ Π[J - 1] < Π[J] ΤΟΤΕ
        ΤΕΜΠ <- Π[J - 1] 
        Π[J - 1] <- Π[J] 
        Π[J] <- ΤΕΜΠ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ Π[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

2ος τρόπος: Interpolation. Σκουπίδι τρόπος καθώς αν δεν ήταν ο διερμηνευτής δε θα μπορούσα να καταλάβω αν τρέχει ή όχι.

ΠΡΟΓΡΑΜΜΑ ΤΡΟΠΟΣ2
ΜΕΤΑΒΛΗΤΕΣ
  ΛΟΓΙΚΕΣ: FLAG
  ΑΚΕΡΑΙΕΣ: Ι, Π[10], J, Χ, Θ
ΑΡΧΗ
  Ι <- 1
  ΔΙΑΒΑΣΕ Χ
  ΟΣΟ Χ <> 0 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Ι = 1 ΤΟΤΕ
      Π[Ι] <- Χ
    ΑΛΛΙΩΣ
      ΑΝ Ι > 10 ΤΟΤΕ
        Ι <- 10
      ΤΕΛΟΣ_ΑΝ
      J <- 1
      FLAG <- ΨΕΥΔΗΣ
      ΟΣΟ J <= Ι - 1 ΚΑΙ FLAG = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
        ΑΝ Χ >= Π[J] ΤΟΤΕ
          Θ <- J
          FLAG <- ΑΛΗΘΗΣ
        ΑΛΛΙΩΣ
          J <- J + 1
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΑΝ FLAG = ΑΛΗΘΗΣ ΤΟΤΕ
        ΓΙΑ J ΑΠΟ Ι ΜΕΧΡΙ Θ + 1 ΜΕ_ΒΗΜΑ -1
          Π[J] <- Π[J - 1] 
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
        Π[Θ] <- Χ
      ΑΛΛΙΩΣ
        Π[Ι] <- Χ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    Ι <- Ι + 1
    ΔΙΑΒΑΣΕ Χ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ Π[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Υπάρχει κάτι πιό ευέλικτο και πιο παιδαγωγικά ορθό; Καθώς δεν έχω ιδέα πως να το μεταφέρω στα παιδιά.
Επίσης...σιχαίνομαι την ταξινόμηση με εισαγωγή του βιβλίου!... και το θέμα Δ του ΟΕΔΕ 2015!

[ssimaiof]

Νομίζω το "παιδαγωγικά ορθό" είναι μια γενίκευση του προβλήματος των δύο μεγαλύτερων. Δηλαδή αν ο αριθμός είναι μεγαλύτερος από τον 1ο μεγαλύτερο κάνω τον 1ο μεγαλύτερο 2ο μεγαλύτερο και σαν 1ο μεγαλύτερο βάζω τον αριθμό, αν όχι ελέγχω για το 2ο μεγαλύτερο κτλ.
Το παραπάνω σκεπτικό το γενικεύω για 3, 4 και τελικά Κ μεγαλύτερα:
Κρατώ έναν πίνακα Κ θέσεων (καλύτερα Κ+1 θέσεων για να αποφύγω την υπέρβαση του ορίου του πίνακα! αλλά αυτό είναι άλλη συζήτηση) και τον αρχικοποιώ (είτε με πολύ μικρές τιμές ή με τον 1ο αριθμό) και εφαρμόζω τον αλγόριθμο ταξινόμησης Ευθείας Εισαγωγής (Straight Insertion Sort) (παρότι τον σιχαίνεσαι είναι πολύ πρακτικός και πολύ πιο κομψός ! και είναι και η γενίκευση του προηγούμενου) :
Για κάθε αριθμό που διαβάζω ξεκινάω από πάνω (1ο μεγαλύτερο, 2ο μεγαλύτερο) και ψάχνω να βρω τη θέση του πίνακα που όντως έχω ένα μεγαλύτερο στοιχείο. Όλα τα κάτω στοιχεία τα πάω μια θέση παρακάτω και στην θέση που ελευθέρωσα βάζω τον αριθμό.
Μια πρόχειρη λύση:

! Να διαβάζονται αριθμοί μέχρι να δοθεί ο αριθμός 0.
! Να εμφανιστούν οι κ μεγαλύτεροι αριθμοί.
! Περιορισμοί:   0 <= κ <= 10
ΠΡΟΓΡΑΜΜΑ Κ_Μέγιστα
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: k, i, j, α, Max[11] 
ΑΡΧΗ
  ΓΡΑΨΕ 'Δώστε πλήθος μεγαλύτερων αριθμών κ :  '
  ΔΙΑΒΑΣΕ k
  ΟΣΟ k < 0 Η k > 10 ΕΠΑΝΑΛΑΒΕ
    ΓΡΑΨΕ 'ΛΑΘΟΣ !!   Πρέπει 0 <= κ <= 10'
    ΓΡΑΨΕ 'Ξαναδώστε πλήθος αριθμών προς εξαίρεση κ :  '
    ΔΙΑΒΑΣΕ k
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k + 1
    Max[i] <- -999999
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Δώστε αριθμό :  '
  ΔΙΑΒΑΣΕ α
  ΟΣΟ α <> 0 ΕΠΑΝΑΛΑΒΕ
    ! Βρες τη θέση που πρέπει να μπει ο αριθμός αν είναι μεγαλύτερος
    i <- 1
    ΟΣΟ i <= k ΚΑΙ α <= Max[i] ΕΠΑΝΑΛΑΒΕ  ! Το α<=Max[i] δεν κάνει υπέρβαση επειδή έχουμε πίνακα Κ+1 θέσεων
      i <- i + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ! Μετακίνηση τους από κάτω μεγαλύτερους μία θέση παρακάτω
    ΓΙΑ j ΑΠΟ k ΜΕΧΡΙ i + 1 ΜΕ_ΒΗΜΑ -1
      Max[j] <- Max[j - 1] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ! Πρόσθεσε το νέο μεγαλύτερο
    Max[i] <- α

    ΓΡΑΨΕ 'Δώστε αριθμό :  '
    ΔΙΑΒΑΣΕ α
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Τα ', k, ' μεγαλύτερα:  '
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k
    ΓΡΑΨΕ Max[i], '  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[nikolasmer]

Νομίζω το "παιδαγωγικά ορθό" είναι μια γενίκευση του προβλήματος των δύο μεγαλύτερων. Δηλαδή αν ο αριθμός είναι μεγαλύτερος από τον 1ο μεγαλύτερο κάνω τον 1ο μεγαλύτερο 2ο μεγαλύτερο και σαν 1ο μεγαλύτερο βάζω τον αριθμό, αν όχι ελέγχω για το 2ο μεγαλύτερο κτλ.
Το παραπάνω σκεπτικό το γενικεύω για 3, 4 και τελικά Κ μεγαλύτερα:
Κρατώ έναν πίνακα Κ θέσεων (καλύτερα Κ+1 θέσεων για να αποφύγω την υπέρβαση του ορίου του πίνακα! αλλά αυτό είναι άλλη συζήτηση) και τον αρχικοποιώ (είτε με πολύ μικρές τιμές ή με τον 1ο αριθμό) και εφαρμόζω τον αλγόριθμο ταξινόμησης Ευθείας Εισαγωγής (Straight Insertion Sort) (παρότι τον σιχαίνεσαι είναι πολύ πρακτικός και πολύ πιο κομψός ! και είναι και η γενίκευση του προηγούμενου) :
Για κάθε αριθμό που διαβάζω ξεκινάω από πάνω (1ο μεγαλύτερο, 2ο μεγαλύτερο) και ψάχνω να βρω τη θέση του πίνακα που όντως έχω ένα μεγαλύτερο στοιχείο. Όλα τα κάτω στοιχεία τα πάω μια θέση παρακάτω και στην θέση που ελευθέρωσα βάζω τον αριθμό.
Μια πρόχειρη λύση:

! Να διαβάζονται αριθμοί μέχρι να δοθεί ο αριθμός 0.
! Να εμφανιστούν οι κ μεγαλύτεροι αριθμοί.
! Περιορισμοί:   0 <= κ <= 10
ΠΡΟΓΡΑΜΜΑ Κ_Μέγιστα
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: k, i, j, α, Max[11] 
ΑΡΧΗ
  ΓΡΑΨΕ 'Δώστε πλήθος μεγαλύτερων αριθμών κ :  '
  ΔΙΑΒΑΣΕ k
  ΟΣΟ k < 0 Η k > 10 ΕΠΑΝΑΛΑΒΕ
    ΓΡΑΨΕ 'ΛΑΘΟΣ !!   Πρέπει 0 <= κ <= 10'
    ΓΡΑΨΕ 'Ξαναδώστε πλήθος αριθμών προς εξαίρεση κ :  '
    ΔΙΑΒΑΣΕ k
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k + 1
    Max[i] <- -999999
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Δώστε αριθμό :  '
  ΔΙΑΒΑΣΕ α
  ΟΣΟ α <> 0 ΕΠΑΝΑΛΑΒΕ
    ! Βρες τη θέση που πρέπει να μπει ο αριθμός αν είναι μεγαλύτερος
    i <- 1
    ΟΣΟ i <= k ΚΑΙ α <= Max[i] ΕΠΑΝΑΛΑΒΕ  ! Το α<=Max[i] δεν κάνει υπέρβαση επειδή έχουμε πίνακα Κ+1 θέσεων
      i <- i + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ! Μετακίνηση τους από κάτω μεγαλύτερους μία θέση παρακάτω
    ΓΙΑ j ΑΠΟ k ΜΕΧΡΙ i + 1 ΜΕ_ΒΗΜΑ -1
      Max[j] <- Max[j - 1] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ! Πρόσθεσε το νέο μεγαλύτερο
    Max[i] <- α

    ΓΡΑΨΕ 'Δώστε αριθμό :  '
    ΔΙΑΒΑΣΕ α
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Τα ', k, ' μεγαλύτερα:  '
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k
    ΓΡΑΨΕ Max[i], '  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Καταπληκτικός τρόπος. Νομίζω πως ο παραπάνω τρόπος μπορεί να γίνει και χωρίς χρήση κ+1 θέσεων πίνακα. Αρκεί να βάλουμε κάποια λογική μεταβλητή. Σωστά σκέφτομαι; 

'Α , γιατί λέγεται "straight" insertion sort;;  

[ssimaiof]

Καταπληκτικός τρόπος. Νομίζω πως ο παραπάνω τρόπος μπορεί να γίνει και χωρίς χρήση κ+1 θέσεων πίνακα. Αρκεί να βάλουμε κάποια λογική μεταβλητή. Σωστά σκέφτομαι;

Υπάρχουν αρκετοί τρόποι και σχετίζεται και με την αποτίμηση των λογικών εκφράσεων. Αν δεν γίνεται πλήρης αποτίμηση μπορεί να δουλέψει και έτσι όπως είναι (χωρίς την επιπρόσθετη θέση του πίνακα). Αλλά αυτό είναι άλλη συζήτηση που νομίζω έχει γίνει και εδώ στο στέκι.

'Α , γιατί λέγεται "straight" insertion sort;;  

Και εγώ δεν είμαι καλός με τις ονομασίες. Τη συγκεκριμένη τη βρήκα στο βιβλίο του εκπαιδευτικού σελίδα 90 στην λύση της ΔΣ3 οπότε και στην ανέφερα.

[epsilonXi]

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

διάβασε χ
όσο χ <> 0 επανάλαβε
   Π[11] ← χ
   για χ από 11 μέχρι 2 με βήμα -1
      αν Π[χ] > Π[χ-1] τότε
         τεμπ ← Π[χ]
         Π[χ] ← Π[χ-1]
         Π[χ-1] ← τεμπ
      τέλος_αν
   τέλος_επανάληψης
   διάβασε χ
τέλος_επανάληψης

[Anastasis13]

Είναι πολύ πιο απλό:

Βάλε το στοιχείο στον πίνακα όταν:
    • ο πίνακας έχει λιγότερα από 10 στοιχεία
    • ο πίνακας έχει 10 η περισσότερα και το στοιχείο προς εισαγωγή είναι μεγαλύτερο από το μικρότερο στοιχείο του πίνακα.