Δομή Επανάληψης Ασκήσεις και Θεωρία για το ΑΕΠΠ
Τι είναι η Δομή Επανάληψης στην ΑΕΠΠ
Η δομή επανάληψης επιτρέπει στο πρόγραμμα να εκτελεί μία ή περισσότερες εντολές πολλές φορές, όσο αυτό απαιτείται από το πρόβλημα. Είναι μία από τις βασικές δομές του δομημένου προγραμματισμού και εμφανίζεται πολύ συχνά σε θεωρία, ασκήσεις και θέματα εξετάσεων στο ΑΕΠΠ.
Στη ΓΛΩΣΣΑ η δομή επανάληψης χρησιμοποιείται είτε όταν γνωρίζουμε από πριν πόσες φορές θα εκτελεστεί μία διαδικασία είτε όταν η επανάληψη εξαρτάται από μία συνθήκη. Οι βασικές μορφές της είναι η Για, η Όσο και η Μέχρις_ότου.
Μορφές της Δομής Επανάληψης
1. Δομή Για — χρησιμοποιείται όταν το πλήθος των επαναλήψεων είναι γνωστό από πριν.
ΓΙΑ μεταβλητή ΑΠΟ αρχική_τιμή ΜΕΧΡΙ τελική_τιμή
εντολές
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
2. Δομή Όσο — η συνθήκη ελέγχεται στην αρχή, άρα μπορεί να μην εκτελεστεί καμία φορά.
ΟΣΟ συνθήκη ΕΠΑΝΑΛΑΒΕ
εντολές
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
3. Δομή Μέχρις_ότου — η συνθήκη ελέγχεται στο τέλος, άρα η επανάληψη εκτελείται τουλάχιστον μία φορά.
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
εντολές
ΜΕΧΡΙΣ_ΟΤΟΥ συνθήκη
Οι τελεστές στη ΓΛΩΣΣΑ
Στη ΓΛΩΣΣΑ χρησιμοποιούμε αριθμητικούς, συγκριτικούς και λογικούς τελεστές. Η σωστή χρήση τους είναι απαραίτητη στις ασκήσεις επανάληψης, γιατί μέσα στις δομές Όσο και Μέχρις_ότου οι συνθήκες καθορίζουν πότε θα συνεχιστεί ή θα τερματιστεί ο βρόχος.
Αριθμητικοί Τελεστές στη ΓΛΩΣΣΑ
Οι αριθμητικοί τελεστές είναι οι: ^, *, /, mod, div, +, -. Η προτεραιότητά τους είναι όπως και στα μαθηματικά: πρώτα οι δυνάμεις, μετά οι πολλαπλασιασμοί και οι διαιρέσεις και στο τέλος οι προσθέσεις και οι αφαιρέσεις.
Προσοχή: οι πράξεις div και mod εφαρμόζονται σε ακεραίους, ενώ η πράξη / δίνει πραγματικό αποτέλεσμα.
Συγκριτικοί τελεστές στη ΓΛΩΣΣΑ
Οι συγκριτικοί τελεστές είναι οι =, <>, >, <, >=, <=. Το αποτέλεσμα κάθε συγκριτικής πράξης είναι μία λογική τιμή, δηλαδή Αληθής ή Ψευδής.
Λογικοί τελεστές στη ΓΛΩΣΣΑ
Οι λογικοί τελεστές είναι οι ΚΑΙ, Η και ΟΧΙ. Χρησιμοποιούνται για να συνδυάζουμε δύο ή περισσότερες συνθήκες στις δομές επανάληψης και επιλογής.
Τυπολόγιο Δομής Επανάληψης
Στη ΓΛΩΣΣΑ πολλές φορές θα χρειαστεί να λύσουμε ασκήσεις που βασίζονται στο πλήθος, στο άθροισμα, στο μέσο όρο, στο ποσοστό, στο μέγιστο και στο ελάχιστο. Παρακάτω μπορείτε να δείτε ένα βασικό τυπολόγιο της δομής επανάληψης.
| Κατηγορία | Συνθήκη / Τύπος |
|---|---|
| Γνωστό πλήθος επαναλήψεων | ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν |
| Άγνωστο πλήθος με έλεγχο στην αρχή | ΟΣΟ συνθήκη ΕΠΑΝΑΛΑΒΕ |
| Άγνωστο πλήθος με έλεγχο στο τέλος | ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ ... ΜΕΧΡΙΣ_ΟΤΟΥ συνθήκη |
| Πλήθος | plithos ← plithos + 1 |
| Άθροισμα | S ← S + x |
| Μέσος όρος | MO ← S / plithos |
| Ποσοστό | (μερικό πλήθος / συνολικό πλήθος) * 100 |
| Μέγιστο | Αρχικοποίηση max και διαδοχικές συγκρίσεις |
| Ελάχιστο | Αρχικοποίηση min και διαδοχικές συγκρίσεις |
Μεθοδολογίες Δομής Επανάληψης στη ΓΛΩΣΣΑ
Οι πιο συχνές μεθοδολογίες στις ασκήσεις επανάληψης είναι η μεθοδολογία πλήθους, αθροίσματος, μέσου όρου, ποσοστού, μεγίστου και ελαχίστου.
Μεθοδολογία Πλήθους, Αθροίσματος και Μέσου Όρου
Στις ασκήσεις πλήθους χρησιμοποιούμε έναν μετρητή που αρχικοποιείται με 0 και αυξάνεται κάθε φορά που μία συνθήκη είναι αληθής. Στις ασκήσεις αθροίσματος χρησιμοποιούμε έναν αθροιστή που αρχικοποιείται επίσης με 0. Για τον μέσο όρο χρειαζόμαστε πάντα και άθροισμα και πλήθος.
Μεθοδολογία Ποσοστού
Η μεθοδολογία ποσοστού είναι πολύ συχνή στις ασκήσεις επανάληψης και βασίζεται στον τύπο (μερικό πλήθος / συνολικό πλήθος) * 100. Πριν από τον υπολογισμό του ποσοστού ελέγχουμε ότι το συνολικό πλήθος δεν είναι 0.
Μεθοδολογία Μεγίστου και Ελαχίστου
Στη μεθοδολογία μεγίστου και ελαχίστου θέτουμε αρχικά ως max ή min την πρώτη τιμή που διαβάζουμε και στη συνέχεια συγκρίνουμε κάθε νέα τιμή μέσα στην επανάληψη.
Παραδείγματα και Λυμένες Ασκήσεις Δομής Επανάληψης
Παράδειγμα 1: Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ που διαβάζει 10 αριθμούς και υπολογίζει το άθροισμά τους.
ΠΡΟΓΡΑΜΜΑ Α1
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: i, x, S
ΑΡΧΗ
S ← 0
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
ΔΙΑΒΑΣΕ x
S ← S + x
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ S
ΤΕΛΟΣ Α1
Επεξήγηση Λύσης
Πρόκειται για κλασική άσκηση αθροίσματος με γνωστό πλήθος επαναλήψεων, άρα χρησιμοποιούμε τη δομή Για. Ο αθροιστής S αρχικοποιείται με 0 και σε κάθε βήμα προστίθεται η νέα τιμή.
Παράδειγμα 2: Να διαβάζονται αριθμοί μέχρι να δοθεί το 0 και να υπολογίζεται πόσοι από αυτούς είναι θετικοί.
ΠΡΟΓΡΑΜΜΑ Α2
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: x, plithos
ΑΡΧΗ
plithos ← 0
ΔΙΑΒΑΣΕ x
ΟΣΟ x <> 0 ΕΠΑΝΑΛΑΒΕ
ΑΝ x > 0 ΤΟΤΕ
plithos ← plithos + 1
ΤΕΛΟΣ_ΑΝ
ΔΙΑΒΑΣΕ x
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ plithos
ΤΕΛΟΣ Α2
Παράδειγμα 3: Να ζητείται συνεχώς ένας αριθμός μέχρι να δοθεί άρτιος.
ΠΡΟΓΡΑΜΜΑ Α3
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: x
ΑΡΧΗ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ x
ΜΕΧΡΙΣ_ΟΤΟΥ x MOD 2 = 0
ΓΡΑΨΕ x
ΤΕΛΟΣ Α3
Συχνά λάθη μαθητών στη Δομή Επανάληψης
Τα πιο συνηθισμένα λάθη που κάνουν οι μαθητές στη δομή επανάληψης έχουν να κάνουν με τη λάθος επιλογή ανάμεσα στις δομές Για, Όσο και Μέχρις_ότου, με την κακή αρχικοποίηση μεταβλητών και με τη λανθασμένη χρήση μετρητών, αθροιστών και συνθηκών τερματισμού.
Ιδιαίτερη προσοχή χρειάζεται και στον υπολογισμό του ποσοστού και του μέσου όρου, γιατί αυτοί συνήθως γίνονται μετά το τέλος της επανάληψης. Επίσης, οι μαθητές μπερδεύουν συχνά τη δομή Όσο με τη Μέχρις_ότου, επειδή η πρώτη ελέγχει τη συνθήκη στην αρχή ενώ η δεύτερη στο τέλος.
Ερωτήσεις Σωστό-Λάθος στη Δομή Επανάληψης ΑΕΠΠ
1. Η δομή Για χρησιμοποιείται όταν γνωρίζουμε από πριν το πλήθος των επαναλήψεων.
ΣΩΣΤΟ — Η δομή Για είναι κατάλληλη όταν ξέρουμε από την αρχή πόσες φορές θα εκτελεστεί ο βρόχος.
2. Η δομή Όσο εκτελείται πάντοτε τουλάχιστον μία φορά.
ΛΑΘΟΣ — Αν η συνθήκη είναι ψευδής από την αρχή, η δομή Όσο μπορεί να μην εκτελεστεί καμία φορά.
3. Η δομή Μέχρις_ότου ελέγχει τη συνθήκη στο τέλος.
ΣΩΣΤΟ — Για αυτόν τον λόγο εκτελείται τουλάχιστον μία φορά.
4. Ο μέσος όρος υπολογίζεται μόνο με μετρητή.
ΛΑΘΟΣ — Για τον μέσο όρο χρειαζόμαστε άθροισμα και πλήθος.
5. Το ποσοστό συνήθως υπολογίζεται με τον τύπο (μερικό πλήθος / συνολικό πλήθος) * 100.
ΣΩΣΤΟ — Αυτός είναι ο βασικός τύπος της μεθοδολογίας ποσοστού.
Ασκήσεις Πολλαπλής Επιλογής στη Δομή Επανάληψης ΑΕΠΠ
Ερώτηση 1: Ποια από τις παρακάτω περιπτώσεις είναι καταλληλότερη για τη δομή Για;
α. Διαβάζω αριθμούς μέχρι να δοθεί 0
β. Επαναλαμβάνω ακριβώς 20 φορές
γ. Ελέγχω μέχρι να βρεθεί άρτιος αριθμός
δ. Επαναλαμβάνω μέχρι ο χρήστης να δώσει σωστό κωδικό
Απάντηση: β — Η δομή Για χρησιμοποιείται όταν το πλήθος είναι γνωστό από πριν.
Ερώτηση 2: Πότε χρησιμοποιούμε τη δομή Όσο;
α. Όταν γνωρίζουμε ακριβώς 15 επαναλήψεις
β. Όταν η συνθήκη ελέγχεται στην αρχή και το πλήθος είναι άγνωστο
γ. Όταν θέλουμε υποχρεωτικά μία εκτέλεση
δ. Όταν δεν υπάρχει συνθήκη
Απάντηση: β — Στη δομή Όσο ο έλεγχος γίνεται στην αρχή.
Ερώτηση 3: Ποιο είναι βασικό χαρακτηριστικό της δομής Μέχρις_ότου;
α. Δεν εκτελείται ποτέ
β. Εκτελείται μόνο αν η συνθήκη είναι αληθής στην αρχή
γ. Ελέγχει τη συνθήκη στο τέλος
δ. Έχει πάντα γνωστό πλήθος επαναλήψεων
Απάντηση: γ — Η συνθήκη τερματισμού ελέγχεται στο τέλος της επανάληψης.
Άσκηση Αντιστοίχισης στη Δομή Επανάληψης ΑΕΠΠ
| Στήλη Α — Δομή / Μεθοδολογία | Στήλη Β — Λειτουργία |
|---|---|
| 1. ΓΙΑ | α. Γνωστό πλήθος επαναλήψεων |
| 2. ΟΣΟ | β. Έλεγχος συνθήκης στην αρχή |
| 3. ΜΕΧΡΙΣ_ΟΤΟΥ | γ. Έλεγχος συνθήκης στο τέλος |
| 4. ΠΛΗΘΟΣ | δ. Αύξηση μετρητή κατά 1 |
| 5. ΠΟΣΟΣΤΟ | ε. (μερικό/συνολικό) * 100 |
Απαντήσεις: 1→α, 2→β, 3→γ, 4→δ, 5→ε
Συχνές Ερωτήσεις για τη Δομή Επανάληψης ΑΕΠΠ
Η δομή επανάληψης είναι η βασική δομή προγραμματισμού που χρησιμοποιούμε όταν θέλουμε να εκτελέσουμε τις ίδιες εντολές πολλές φορές. Στην ΑΕΠΠ και στη ΓΛΩΣΣΑ η επανάληψη ελέγχεται πάντα από κάποια συνθήκη ή από έναν μετρητή, ώστε το πρόγραμμα να ξέρει πότε θα συνεχίσει και πότε θα σταματήσει.
Με απλά λόγια, αν μια διαδικασία δεν γίνεται μία μόνο φορά αλλά ξανά και ξανά, τότε συνήθως χρειαζόμαστε μια δομή επανάληψης.
Χρησιμοποιούμε τη Για όταν ξέρουμε από πριν πόσες επαναλήψεις πρέπει να γίνουν, για παράδειγμα όταν θέλουμε να διαβάσουμε 10 τιμές ή όταν θα κάνουμε πράξεις για όλους τους αθλητές μίας ομάδας.
Χρησιμοποιούμε την Όσο όταν το πλήθος των επαναλήψεων δεν είναι γνωστό από την αρχή και η συνθήκη ελέγχεται πριν εκτελεστούν οι εντολές, ενώ χρησιμοποιούμε τη Μέχρις_ότου όταν η συνθήκη ελέγχεται στο τέλος και θέλουμε να γίνει οπωσδήποτε τουλάχιστον μία εκτέλεση.
Η βασική διαφορά είναι το πότε ελέγχεται η συνθήκη της δομής επανάληψης.
Στη δομή Όσο η συνθήκη ελέγχεται στην αρχή, άρα υπάρχει περίπτωση η επανάληψη να μην εκτελεστεί καμία φορά αν η συνθήκη δεν ισχύει στην αρχή.
Στη δομή Μέχρις_ότου ο έλεγχος γίνεται στο τέλος, οπότε οι εντολές εκτελούνται τουλάχιστον μία φορά και μετά εξετάζεται αν πρέπει να σταματήσει η επανάληψη.
Στις ασκήσεις δομής επανάληψης, για να βρούμε ποσοστό, πρώτα μετράμε πόσες περιπτώσεις ικανοποιούν αυτό που ζητά η άσκηση και μετά βρίσκουμε το συνολικό πλήθος των περιπτώσεων. Στο τέλος εφαρμόζουμε τον τύπο ( 𝜇 𝜀 𝜌 𝜄 𝜅 ό 𝜋 𝜆 ή𝜃 𝜊 𝜍 / 𝜎 𝜐 𝜈 𝜊 𝜆 𝜄 𝜅 ό 𝜋 𝜆 ή 𝜃 𝜊 𝜍 ) × 100.
Αν το σκεφτείς πρακτικά, πρώτα βρίσκεις “πόσοι πέτυχαν το κριτήριο” και μετά “πόσοι ήταν συνολικά”. Μόνο πρόσεχε να μην κάνεις τη διαίρεση πριν βεβαιωθείς ότι το συνολικό πλήθος δεν είναι μηδέν.
Για τον μέσο όρο, αυτό που μας ενδιαφέρει είναι να βρούμε το άθροισμα όλων των τιμών και το πλήθος τους, γιατί ο μέσος όρος βγαίνει στο τέλος από τη διαίρεση άθροισμα προς πλήθος.
Για το μέγιστο και το ελάχιστο, η κλασική τεχνική είναι να διαβάζεις πρώτα την πρώτη τιμή, να την αποθηκεύεις ως αρχικό μέγιστο ή ελάχιστο και μετά να συγκρίνεις μία-μία τις επόμενες τιμές μέσα στην επανάληψη. Με απλά λόγια, πρώτα κάνεις σωστή αρχικοποίηση και μετά ενημερώνεις τις μεταβλητές μόνο όταν βρίσκεις μεγαλύτερη ή μικρότερη τιμή.
Το πιο συχνό λάθος είναι ότι οι μαθητές διαλέγουν λάθος είδος επανάληψης, δηλαδή χρησιμοποιούν Για ενώ το πλήθος δεν είναι γνωστό ή χρησιμοποιούν Όσο και Μέχρις_ότου χωρίς να προσέχουν πότε ελέγχεται η συνθήκη.
Εξίσου συχνά είναι τα λάθη στην αρχικοποίηση και στην ενημέρωση μεταβλητών, όπως αθροιστές, μετρητές, μέγιστα και ελάχιστα. Πολλές φορές επίσης μπερδεύονται στον υπολογισμό ποσοστού ή μέσου όρου, επειδή δεν έχουν εντοπίσει σωστά ποια μεγέθη πρέπει πρώτα να βρουν μέσα στην επανάληψη.
Πίνακας είναι μια στατική δομή δεδομένων που αποθηκεύει ένα σύνολο στοιχείων ίδιου τύπου, προσβάσιμων μέσω δεικτών. Όλα τα στοιχεία του πίνακα καταλαμβάνουν συνεχόμενες θέσεις μνήμης και το μέγεθός του δεν μπορεί να αλλάξει κατά την εκτέλεση του προγράμματος.
Η σειριακή αναζήτηση χρησιμοποιείται σε μικρούς ή μη ταξινομημένους πίνακες, καθώς ελέγχει διαδοχικά όλα τα στοιχεία. Η δυαδική αναζήτηση εφαρμόζεται μόνο σε ταξινομημένους πίνακες και είναι πολύ πιο αποδοτική (O(log N) vs O(N)), καθώς χωρίζει επαναληπτικά τον πίνακα στο μισό.
Η ταξινόμηση φυσαλίδας συγκρίνει και ανταλλάσσει γειτονικά στοιχεία μέχρι να ταξινομηθεί ολόκληρος ο πίνακας. Η ταξινόμηση κατ’ επιλογή βρίσκει σε κάθε βήμα το μικρότερο στοιχείο του μη ταξινομημένου τμήματος και το τοποθετεί στη σωστή θέση. Και οι δύο έχουν πολυπλοκότητα O(N²), αλλά η φυσαλίδα είναι συνήθως πιο αργή στην πράξη.
Η συγχώνευση ενώνει δύο ταξινομημένους μονοδιάστατους πίνακες σε έναν τρίτο ταξινομημένο πίνακα. Χρησιμοποιεί τρεις δείκτες (έναν για κάθε πίνακα) και σε κάθε βήμα συγκρίνει τα τρέχοντα στοιχεία των δύο πινάκων, αντιγράφοντας το μικρότερο στον τελικό πίνακα. Ο προκύπτων πίνακας είναι πάντα ταξινομημένος.
Όχι, όλα τα στοιχεία ενός πίνακα πρέπει να είναι ίδιου τύπου (π.χ. όλοι ακέραιοι, όλοι πραγματικοί, όλοι χαρακτήρες). Αν χρειάζεται να αποθηκεύσουμε δεδομένα διαφορετικού τύπου, χρησιμοποιούμε δισδιάστατο πίνακα όπου κάθε στήλη αντιπροσωπεύει ένα διαφορετικό πεδίο (π.χ. όνομα, βαθμός, μάθημα).
Για να υπολογίσουμε το συνολικό άθροισμα ενός δισδιάστατου πίνακα, χρησιμοποιούμε δύο εμφωλευμένες επαναλήψεις: η εξωτερική διατρέχει τις γραμμές και η εσωτερική τις στήλες. Σε κάθε βήμα προσθέτουμε το τρέχον στοιχείο σε μια μεταβλητή sum. Αν θέλουμε άθροισμα ανά γραμμή ή στήλη, μηδενίζουμε το άθροισμα σε κάθε νέα γραμμή/στήλη.
