ΓΛΩΣΣΑ: εντολές επανάληψης
Κεφ. 8 §8.2 · ΟΣΟ, ΜΕΧΡΙΣ_ΟΤΟΥ, ΓΙΑ, έλεγχος εγκυρότητας, εμφωλευμένοι βρόχοι
Το Θέμα Γ των Πανελλαδικών είναι σχεδόν πάντα ένα πλήρες πρόγραμμα με επανάληψη: διάβασε δεδομένα μέχρι να δοθεί μια τιμή τερματισμού, έλεγξε ότι είναι έγκυρα, μέτρησε, άθροισε, βρες το μέγιστο.
Τις δομές τις γνώρισες ήδη στη δομή επανάληψης. Εδώ τις δένουμε σε ολοκληρωμένα προγράμματα ΓΛΩΣΣΑΣ και μαθαίνεις τις λεπτομέρειες που κρίνουν τις μονάδες.
Οι τρεις εντολές στη ΓΛΩΣΣΑ
ΟΣΟ συνθήκη ΕΠΑΝΑΛΑΒΕ εντολές ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ εντολές ΜΕΧΡΙΣ_ΟΤΟΥ συνθήκη
ΓΙΑ μεταβλητή ΑΠΟ τιμή1 ΜΕΧΡΙ τιμή2 ΜΕ_ΒΗΜΑ β εντολές ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
- Το ΟΣΟ είναι η γενική εντολή: κάθε επανάληψη μπορεί να γραφτεί με αυτό.
- Το ΜΕΧΡΙΣ_ΟΤΟΥ εκτελεί το σώμα τουλάχιστον μία φορά — ιδανικό για έλεγχο εγκυρότητας δεδομένων.
- Στο ΓΙΑ το βήμα μπορεί να είναι αρνητικό (μέτρηση προς τα κάτω). Αν με θετικό βήμα η αρχική τιμή είναι μεγαλύτερη από την τελική, το σώμα δεν εκτελείται. Η μεταβλητή του ΓΙΑ δεν πρέπει να αλλάζει μέσα στο σώμα.
Ισοδυναμία ΓΙΑ και ΟΣΟ
Το ΓΙΑ i ΑΠΟ α ΜΕΧΡΙ τ ΜΕ_ΒΗΜΑ β (με β > 0) είναι ισοδύναμο με:
i ← α ΟΣΟ i <= τ ΕΠΑΝΑΛΑΒΕ εντολές i ← i + β ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Με αρνητικό βήμα η συνθήκη γίνεται i >= τ. Από την ισοδυναμία προκύπτει ότι μετά το τέλος του ΓΙΑ η μεταβλητή έχει την πρώτη τιμή που ξεπέρασε το όριο: μετά το ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5, το i είναι 6.
Ποια είναι η τιμή του κ μετά την εκτέλεση του ΓΙΑ κ ΑΠΟ 2 ΜΕΧΡΙ 11 ΜΕ_ΒΗΜΑ 3;
Μέθοδος: το «καλούπι» του Θέματος Γ
- Αρχικοποιήσεις πριν από την επανάληψη: μετρητές και αθροιστές στο 0, γινόμενα στο 1.
- Πρώτο ΔΙΑΒΑΣΕ πριν από το ΟΣΟ (αν υπάρχει τιμή τερματισμού).
- Μέσα στο ΟΣΟ: έλεγχος εγκυρότητας των υπόλοιπων δεδομένων με ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ … ΜΕΧΡΙΣ_ΟΤΟΥ.
- Επεξεργασία: μετρητές, αθροιστές, μέγιστο/ελάχιστο (με αρχική τιμή την πρώτη τιμή).
- Τελευταία εντολή του σώματος: το επόμενο ΔΙΑΒΑΣΕ της τιμής τερματισμού.
- Μετά την επανάληψη: μέσος όρος και εκτυπώσεις, με έλεγχο ότι δόθηκε τουλάχιστον μία τιμή (αποφυγή διαίρεσης με το 0).
Θέμα τύπου Πανελλαδικών: Να γραφεί πρόγραμμα που διαβάζει ονόματα μαθητών και τους βαθμούς τους (0–20, με έλεγχο εγκυρότητας) μέχρι να δοθεί όνομα 'ΤΕΛΟΣ'. Να εμφανίζει τον μέσο όρο, πόσοι έχουν βαθμό τουλάχιστον 18 και το όνομα του μαθητή με τον μεγαλύτερο βαθμό (θεωρούμε ότι είναι μοναδικός).
ΠΡΟΓΡΑΜΜΑ Βαθμοι ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: πλ, αρ ΠΡΑΓΜΑΤΙΚΕΣ: β, Σ, μεγ ΧΑΡΑΚΤΗΡΕΣ: ον, ονμεγ ΑΡΧΗ πλ ← 0 αρ ← 0 Σ ← 0 ΔΙΑΒΑΣΕ ον ΟΣΟ ον <> 'ΤΕΛΟΣ' ΕΠΑΝΑΛΑΒΕ ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ ΔΙΑΒΑΣΕ β ΜΕΧΡΙΣ_ΟΤΟΥ β >= 0 ΚΑΙ β <= 20 πλ ← πλ + 1 Σ ← Σ + β ΑΝ πλ = 1 ΤΟΤΕ μεγ ← β ονμεγ ← ον ΑΛΛΙΩΣ_ΑΝ β > μεγ ΤΟΤΕ μεγ ← β ονμεγ ← ον ΤΕΛΟΣ_ΑΝ ΑΝ β >= 18 ΤΟΤΕ αρ ← αρ + 1 ΤΕΛΟΣ_ΑΝ ΔΙΑΒΑΣΕ ον ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ πλ > 0 ΤΟΤΕ ΓΡΑΨΕ 'Μέσος όρος: ', Σ / πλ ΓΡΑΨΕ 'Με 18 και πάνω: ', αρ ΓΡΑΨΕ 'Καλύτερος: ', ονμεγ ΑΛΛΙΩΣ ΓΡΑΨΕ 'Δεν δόθηκαν μαθητές' ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
Για τα δεδομένα Νίκος 15, Μαρία 19, Άννα 18, ΤΕΛΟΣ: μέσος όρος , με 18 και πάνω 2, καλύτερη η Μαρία.
Πόσες φορές εκτελείται η εντολή ΓΡΑΨΕ;
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 4 ΓΙΑ j ΑΠΟ i ΜΕΧΡΙ 4 ΓΡΑΨΕ i, j ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Παράδειγμα 1: Ο αλγόριθμος του Ευκλείδη για τον ΜΚΔ δύο θετικών ακεραίων.
ΔΙΑΒΑΣΕ α, β ΟΣΟ β <> 0 ΕΠΑΝΑΛΑΒΕ υ ← α MOD β α ← β β ← υ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ α
Ίχνος για α = 48, β = 18:
- υ = 48 MOD 18 = 12 → α = 18, β = 12
- υ = 18 MOD 12 = 6 → α = 12, β = 6
- υ = 12 MOD 6 = 0 → α = 6, β = 0
- β = 0: τέλος, εμφανίζεται 6
Εδώ δεν ξέρουμε από πριν πόσες επαναλήψεις θα γίνουν, άρα ΓΙΑ δεν μπορεί να χρησιμοποιηθεί.
Παράδειγμα 2: Πλήθος ψηφίων ενός θετικού ακεραίου x.
πλ ← 0 ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ x ← x DIV 10 πλ ← πλ + 1 ΜΕΧΡΙΣ_ΟΤΟΥ x = 0 ΓΡΑΨΕ πλ
Για x = 4096: 409, 40, 4, 0 → 4 ψηφία. Το ΜΕΧΡΙΣ_ΟΤΟΥ ταιριάζει γιατί κάθε αριθμός έχει τουλάχιστον ένα ψηφίο. Με ΟΣΟ x > 0 το αποτέλεσμα για x = 0 θα ήταν 0 ψηφία — λάθος για το 0.
Τι εμφανίζεται;
Σ ← 0 κ ← 10 ΟΣΟ κ < 10 ΕΠΑΝΑΛΑΒΕ Σ ← Σ + κ κ ← κ + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ
Ο αλγόριθμος του Ευκλείδη είναι εντυπωσιακά γρήγορος: το 1844 ο Gabriel Lamé απέδειξε ότι το πλήθος των βημάτων του δεν ξεπερνά το πενταπλάσιο του πλήθους των ψηφίων του μικρότερου αριθμού. Ήταν ένα από τα πρώτα αποτελέσματα της ανάλυσης αλγορίθμων — και η απόδειξη χρησιμοποιεί τους αριθμούς Fibonacci.
Στο «καλούπι» του τερματισμού θυμήσου το σάντουιτς του ΔΙΑΒΑΣΕ: ένα ΔΙΑΒΑΣΕ πριν από το ΟΣΟ και ένα ως τελευταία εντολή μέσα του. Το «ψωμί» προστατεύει το «γέμισμα» από την τιμή τερματισμού.
Να γραφεί τμήμα που εμφανίζει όλους τους τέλειους αριθμούς από 2 έως 10000. Τέλειος είναι ο αριθμός που ισούται με το άθροισμα των γνήσιων διαιρετών του (π.χ. ).
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Για κάθε ν αθροίζουμε τους διαιρέτες του από 1 έως ν DIV 2 (κανένας γνήσιος διαιρέτης δεν ξεπερνά το μισό του αριθμού).
ΓΙΑ ν ΑΠΟ 2 ΜΕΧΡΙ 10000 Σ ← 0 ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ ν DIV 2 ΑΝ ν MOD δ = 0 ΤΟΤΕ Σ ← Σ + δ ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ Σ = ν ΤΟΤΕ ΓΡΑΨΕ ν ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Εμφανίζονται οι 6, 28, 496, 8128. Το Σ ← 0 πρέπει να είναι μέσα στο εξωτερικό ΓΙΑ (μηδενίζεται για κάθε νέο ν) — αν το βάλεις έξω, το άθροισμα «κουβαλάει» τους διαιρέτες όλων των προηγούμενων αριθμών.
- Αρχικοποίηση αθροιστή έξω από το εξωτερικό βρόχο, ενώ πρέπει να μηδενίζεται για κάθε επανάληψη του (π.χ. άθροισμα ανά μαθητή).
- Αλλαγή της μεταβλητής του ΓΙΑ μέσα στο σώμα.
- ΟΣΟ χωρίς εντολή που αλλάζει τη συνθήκη: ατέρμονη επανάληψη.
- Έλεγχος εγκυρότητας με ΑΝ (δίνει μόνο μία ευκαιρία): χρειάζεται επανάληψη, ώστε να ξαναζητείται η τιμή όσες φορές χρειαστεί.
- ΟΣΟ: γενική εντολή, 0+ εκτελέσεις · ΜΕΧΡΙΣ_ΟΤΟΥ: 1+ εκτελέσεις, ιδανικό για έλεγχο εγκυρότητας · ΓΙΑ: γνωστό πλήθος.
- ΓΙΑ ≡ αρχικοποίηση + ΟΣΟ + αύξηση κατά το βήμα· μετά το τέλος η μεταβλητή έχει ξεπεράσει το όριο.
- Καλούπι: αρχικοποιήσεις → ΔΙΑΒΑΣΕ → ΟΣΟ (έλεγχος εγκυρότητας, επεξεργασία, ΔΙΑΒΑΣΕ) → αποτελέσματα.
- Εμφωλευμένα ΓΙΑ: το εσωτερικό τρέχει ολόκληρο για κάθε τιμή του εξωτερικού.
- Πρόσεξε πού μηδενίζεις κάθε αθροιστή.