Δομή επανάληψης
Κεφ. 2 §2.4.5 · Οι τρεις επαναλήψεις, αθροιστές, μετρητές, μέγιστο
Πώς μετράει το κινητό σου τα βήματα όλης της μέρας; Πώς βρίσκει το Spotify το πιο πολυακουσμένο τραγούδι σου; Κάνοντας το ίδιο πράγμα ξανά και ξανά: διάβασε τιμή, πρόσθεσε, σύγκρινε.
Η δομή επανάληψης είναι η καρδιά των ασκήσεων του Θέματος Γ και Δ. Εδώ μαθαίνεις τα τρία είδη της και τα «εργαλεία» που θα χρησιμοποιείς σε κάθε άσκηση: αθροιστή, μετρητή, μέγιστο και ελάχιστο.
Τα τρία σχήματα επανάληψης
Η δομή επανάληψης εκτελεί μια ομάδα εντολών πολλές φορές, όσο ισχύει ή μέχρι να ισχύσει μια συνθήκη.
1. ΟΣΟ … ΕΠΑΝΑΛΑΒΕ — ο έλεγχος γίνεται στην αρχή:
ΟΣΟ συνθήκη ΕΠΑΝΑΛΑΒΕ εντολές ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Οι εντολές εκτελούνται όσο η συνθήκη είναι αληθής. Αν είναι ψευδής από την αρχή, δεν εκτελούνται καμία φορά.
2. ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ … ΜΕΧΡΙΣ_ΟΤΟΥ — ο έλεγχος γίνεται στο τέλος:
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ εντολές ΜΕΧΡΙΣ_ΟΤΟΥ συνθήκη
Οι εντολές εκτελούνται τουλάχιστον μία φορά και η επανάληψη σταματά όταν η συνθήκη γίνει αληθής.
3. ΓΙΑ … ΑΠΟ … ΜΕΧΡΙ — όταν ο αριθμός των επαναλήψεων είναι γνωστός:
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10 ΜΕ_ΒΗΜΑ 1 εντολές ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Αν το βήμα είναι 1, το ΜΕ_ΒΗΜΑ μπορεί να παραλειφθεί.
Ποια επανάληψη εκτελεί το σώμα της οπωσδήποτε τουλάχιστον μία φορά;
Εργαλεία κάθε επανάληψης
- Μετρητής: μεταβλητή που αυξάνεται κατά 1 κάθε φορά που συμβαίνει κάτι: πλ ← πλ + 1. Αρχική τιμή 0.
- Αθροιστής: μεταβλητή που συγκεντρώνει άθροισμα: Σ ← Σ + x. Αρχική τιμή 0.
- Γινόμενο: Π ← Π * x. Αρχική τιμή 1 (όχι 0!).
- Μέγιστο / ελάχιστο: αρχική τιμή η πρώτη τιμή που διαβάζεται (ή μια τιμή σίγουρα μικρότερη/μεγαλύτερη από όλες)· σε κάθε νέα τιμή: ΑΝ x > max ΤΟΤΕ max ← x.
- Μέσος όρος: στο τέλος, ΜΟ ← Σ / πλ — με έλεγχο ότι πλ <> 0.
Οι αρχικοποιήσεις γίνονται πριν από την επανάληψη· τα τελικά αποτελέσματα εμφανίζονται μετά από αυτή.
Παράδειγμα 1: Να υπολογιστεί το άθροισμα .
Σ ← 0 ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 100 Σ ← Σ + i ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ
Εμφανίζεται 5050. Το ίδιο με ΟΣΟ:
Σ ← 0 i ← 1 ΟΣΟ i <= 100 ΕΠΑΝΑΛΑΒΕ Σ ← Σ + i i ← i + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ
Στο ΟΣΟ πρέπει εσύ να αρχικοποιήσεις και να αυξήσεις το i — το ΓΙΑ το κάνει αυτόματα.
Μέθοδος: ποια επανάληψη να διαλέξω
- Ξέρεις πόσες φορές θα επαναληφθεί (π.χ. «για 30 μαθητές»); → ΓΙΑ.
- Δεν ξέρεις πόσες φορές και η επανάληψη μπορεί να μην εκτελεστεί καθόλου (π.χ. «μέχρι να δοθεί αρνητικός», όπου ο πρώτος μπορεί να είναι αρνητικός); → ΟΣΟ με ένα ΔΙΑΒΑΣΕ πριν και ένα στο τέλος του σώματος.
- Το σώμα πρέπει να εκτελεστεί τουλάχιστον μία φορά (π.χ. έλεγχος εγκυρότητας: «διάβασε μέχρι να δοθεί τιμή από 1 έως 20»); → ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ … ΜΕΧΡΙΣ_ΟΤΟΥ.
- Κάθε ΓΙΑ μετατρέπεται σε ΟΣΟ. Το αντίστροφο δεν ισχύει πάντα: το ΟΣΟ μετατρέπεται σε ΓΙΑ μόνο όταν το πλήθος των επαναλήψεων είναι γνωστό.
Παράδειγμα 2: Διαβάζονται θερμοκρασίες μέχρι να δοθεί η τιμή 999 (τιμή τερματισμού). Να εμφανιστεί η μέγιστη θερμοκρασία και πόσες θερμοκρασίες ήταν αρνητικές.
ν ← 0 πλ ← 0 ΔΙΑΒΑΣΕ θ ΟΣΟ θ <> 999 ΕΠΑΝΑΛΑΒΕ ν ← ν + 1 ΑΝ ν = 1 ΤΟΤΕ max ← θ ΑΛΛΙΩΣ_ΑΝ θ > max ΤΟΤΕ max ← θ ΤΕΛΟΣ_ΑΝ ΑΝ θ < 0 ΤΟΤΕ πλ ← πλ + 1 ΤΕΛΟΣ_ΑΝ ΔΙΑΒΑΣΕ θ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ ν > 0 ΤΟΤΕ ΓΡΑΨΕ max, πλ ΑΛΛΙΩΣ ΓΡΑΨΕ 'Δεν δόθηκαν θερμοκρασίες' ΤΕΛΟΣ_ΑΝ
Ίχνος για είσοδο 4, -2, 7, -1, 999:
- θ = 4: ν = 1, max = 4, πλ = 0
- θ = -2: ν = 2, max = 4, πλ = 1
- θ = 7: ν = 3, max = 7, πλ = 1
- θ = -1: ν = 4, max = 7, πλ = 2
- θ = 999: η συνθήκη γίνεται ψευδής, τέλος
Εμφανίζεται 7 2. Το 999 δεν επεξεργάζεται, γιατί το δεύτερο ΔΙΑΒΑΣΕ είναι η τελευταία εντολή του σώματος. Ο μετρητής ν δίνει στο max ως αρχική τιμή την πρώτη θερμοκρασία και μας προστατεύει αν η πρώτη τιμή είναι ήδη 999.
Πόσες φορές εκτελείται η εντολή ΓΡΑΨΕ;
ΓΙΑ i ΑΠΟ 3 ΜΕΧΡΙ 20 ΜΕ_ΒΗΜΑ 4 ΓΡΑΨΕ i ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Θέμα τύπου Πανελλαδικών: Να μετατραπεί το παρακάτω τμήμα σε ισοδύναμο με χρήση της δομής ΟΣΟ … ΕΠΑΝΑΛΑΒΕ και να βρεθεί τι εμφανίζεται.
Σ ← 0 ΓΙΑ κ ΑΠΟ 10 ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -3 Σ ← Σ + κ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ, κ
Λύση: Με αρνητικό βήμα η συνθήκη συνέχισης είναι κ >= τελική τιμή:
Σ ← 0 κ ← 10 ΟΣΟ κ >= 1 ΕΠΑΝΑΛΑΒΕ Σ ← Σ + κ κ ← κ - 3 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ, κ
Ίχνος: κ = 10 (Σ = 10), κ = 7 (Σ = 17), κ = 4 (Σ = 21), κ = 1 (Σ = 22), κ = -2 → τέλος. Εμφανίζεται 22 -2. Η μεταβλητή του ΓΙΑ, μετά το τέλος, έχει την τιμή που έκανε τη συνθήκη ψευδή.
Τι εμφανίζεται;
x ← 1 ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ x ← x * 3 ΜΕΧΡΙΣ_ΟΤΟΥ x > 50 ΓΡΑΨΕ x
Ο «πολλαπλασιασμός αλά ρωσικά», που παρουσιάζει και το σχολικό βιβλίο, βασίζεται στο ότι κάθε ακέραιος γράφεται στο δυαδικό σύστημα: υποδιπλασιάζοντας τον έναν παράγοντα βρίσκεις τα δυαδικά του ψηφία, και προσθέτεις τον (διπλασιαζόμενο) άλλο παράγοντα όπου το ψηφίο είναι 1. Με την ίδια ιδέα πολλαπλασιάζουν και οι επεξεργαστές στο υλικό τους.
ΟΣΟ = «Οσο είναι αληθές, συνέχισε» — ΜΕΧΡΙΣ_ΟΤΟΥ = «Μόλις γίνει αληθές, σταμάτα». Γι' αυτό, όταν μετατρέπεις το ένα στο άλλο, η συνθήκη αντιστρέφεται (π.χ. ΟΣΟ x <= 10 ↔ ΜΕΧΡΙΣ_ΟΤΟΥ x > 10).
Πολλαπλασιασμός αλά ρωσικά. Να γραφεί αλγόριθμος που υπολογίζει το γινόμενο δύο θετικών ακεραίων Μ1 και Μ2 μόνο με διπλασιασμούς, υποδιπλασιασμούς και προσθέσεις, και να γίνει το ίχνος για 45 και 19.
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Όσο το Μ1 είναι θετικό: αν είναι περιττό, πρόσθεσε το Μ2 στο αποτέλεσμα· μετά υποδιπλασίασε το Μ1 (ακέραια) και διπλασίασε το Μ2.
ΔΙΑΒΑΣΕ Μ1, Μ2 Ρ ← 0 ΟΣΟ Μ1 > 0 ΕΠΑΝΑΛΑΒΕ ΑΝ Μ1 MOD 2 = 1 ΤΟΤΕ Ρ ← Ρ + Μ2 ΤΕΛΟΣ_ΑΝ Μ1 ← Μ1 DIV 2 Μ2 ← Μ2 * 2 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Ρ
Ίχνος:
- Μ1 = 45 (περιττό), Μ2 = 19: Ρ = 19
- Μ1 = 22 (άρτιο), Μ2 = 38: Ρ = 19
- Μ1 = 11 (περιττό), Μ2 = 76: Ρ = 95
- Μ1 = 5 (περιττό), Μ2 = 152: Ρ = 247
- Μ1 = 2 (άρτιο), Μ2 = 304: Ρ = 247
- Μ1 = 1 (περιττό), Μ2 = 608: Ρ = 855
- Μ1 = 0: τέλος
Εμφανίζεται 855, και πράγματι .
- Αρχικοποίηση γινομένου με 0: όλο το αποτέλεσμα γίνεται 0. Το γινόμενο ξεκινά από 1.
- Αρχικοποίηση μέγιστου με 0 όταν οι τιμές μπορεί να είναι αρνητικές. Ξεκίνα από την πρώτη τιμή.
- Επεξεργασία της τιμής τερματισμού (π.χ. το 999 μετράει στον μέσο όρο): το ΔΙΑΒΑΣΕ μέσα στο ΟΣΟ πρέπει να είναι η τελευταία εντολή.
- Μετατροπή ΟΣΟ ↔ ΜΕΧΡΙΣ_ΟΤΟΥ χωρίς αντιστροφή της συνθήκης.
- ΟΣΟ: έλεγχος στην αρχή, 0 ή περισσότερες εκτελέσεις, συνεχίζει όσο η συνθήκη είναι αληθής.
- ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ … ΜΕΧΡΙΣ_ΟΤΟΥ: έλεγχος στο τέλος, τουλάχιστον 1 εκτέλεση, σταματά όταν η συνθήκη γίνει αληθής.
- ΓΙΑ: γνωστό πλήθος, επαναλήψεις.
- Αθροιστής και μετρητής ξεκινούν από 0, γινόμενο από 1, μέγιστο/ελάχιστο από την πρώτη τιμή.
- Κάθε ΓΙΑ γράφεται ως ΟΣΟ· όχι όμως κάθε ΟΣΟ ως ΓΙΑ.