Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

Βρόχοι

Περίληψη

Το μάθημα Από το πρόβλημα στον αλγόριθμο αναγνώρισε τρεις τρόπους σύνθεσης βημάτων: την ακολουθία, την απόφαση και την επανάληψη. Οι δύο πρώτοι έχουν ήδη τη γραφή τους στη C++· αυτό το μάθημα δίνει στον τρίτο τη δική του. Μελετά τις τρεις μορφές του βρόχου: το while, που αποτιμά τη συνθήκη του πριν από κάθε γύρο και μπορεί να μην εκτελέσει ποτέ το σώμα του· το do, που την αποτιμά μετά και το εκτελεί τουλάχιστον μία φορά· και το for, που συγκεντρώνει σε μία γραμμή την αρχικοποίηση, τη συνθήκη και το βήμα της μεταβλητής που διέπει την επανάληψη. Δείχνει ότι οι τρεις εκφράζουν τον ίδιο μηχανισμό, ώστε καθεμία μετασχηματίζεται στις άλλες, και διδάσκει πώς επιλέγουμε τη σαφέστερη· παρουσιάζει τα break και continue, που αλλάζουν την πορεία ενός γύρου· και κλείνει με τους εμφωλευμένους βρόχους, των οποίων το εσωτερικό σώμα εκτελείται τόσες φορές όσες δίνει ένα άθροισμα. Το εργαλείο που συνοδεύει όλο το μάθημα είναι ο πίνακας ίχνους: η εκτέλεση ενός βρόχου με το χέρι, γύρο προς γύρο, είναι ο τρόπος να προβλέψουμε πόσες φορές εκτελείται το σώμα του και τι αφήνει όταν βγαίνει.

Μαθησιακοί στόχοι

  1. Να γράφετε έναν βρόχο while, do ή for για μια δεδομένη επανάληψη, επιλέγοντας τη σαφέστερη μορφή.
  2. Να εκτελείτε με το χέρι έναν βρόχο με τον πίνακα ίχνους του και να προβλέπετε πόσες φορές εκτελείται το σώμα.
  3. Να μετασχηματίζετε έναν βρόχο από τη μία μορφή στην άλλη διατηρώντας τη σημασία του.
  4. Να γράφετε εμφωλευμένους βρόχους και να υπολογίζετε πόσες φορές εκτελείται το εσωτερικό σώμα.

while

Η μορφή ενός while

Ένα while γράφεται έτσι:

Κώδικας C++
while (συνθήκη) {    σώμα}

Η σημασία του διατυπώνεται σε τρία βήματα: αποτιμάται η συνθήκη· αν είναι ψευδής, ο βρόχος τερματίζει και η εκτέλεση συνεχίζει μετά το άγκιστρο που τον κλείνει· αν είναι αληθής, εκτελείται το σώμα και επιστρέφουμε στο πρώτο βήμα. Κάθε εκτέλεση του σώματος λέγεται γύρος (ή επανάληψη). Η συνθήκη είναι μια λογική έκφραση σαν εκείνες του μαθήματος Σχέσεις και λογική, και το σώμα είναι ένα μπλοκ· ο κανόνας των αγκίστρων που καθόρισε το μάθημα Αποφάσεις ισχύει και εδώ: το σώμα ενός βρόχου έχει πάντα άγκιστρα, ακόμη κι αν περιέχει μία μόνο εντολή.

Από τον ορισμό προκύπτουν δύο συνέπειες. Η πρώτη: η συνθήκη αποτιμάται πριν από κάθε γύρο, ώστε, αν είναι ψευδής από την αρχή, το σώμα δεν εκτελείται ούτε μία φορά. Η δεύτερη: για να τερματίσει ο βρόχος, το σώμα πρέπει να αλλάζει κάτι από όσα διαβάζει η συνθήκη· αν τίποτε δεν αλλάζει, η συνθήκη που ήταν αληθής μία φορά θα είναι πάντα αληθής. Ωστόσο, η αλλαγή δεν αρκεί: το μάθημα Από το πρόβλημα στον αλγόριθμο έδειξε ότι χρειάζεται μια φυσική ποσότητα που μειώνεται σε κάθε γύρο, η φθίνουσα ποσότητα, και το μάθημα Σχεδίαση σωστών βρόχων θα την κάνει μέθοδο.

Η διαίρεση με διαδοχικές αφαιρέσεις

Ο πρώτος αλγόριθμος με επανάληψη του κύκλου μαθημάτων ήταν η διαίρεση με διαδοχικές αφαιρέσεις: όσο το υπόλοιπο είναι τουλάχιστον ίσο με τον διαιρέτη, αφαιρούμε από αυτό τον διαιρέτη και προσθέτουμε ένα στο πηλίκο. Γραμμένος σε C++, ο αλγόριθμος μεταφέρεται σχεδόν λέξη προς λέξη.

ΠαράδειγμαΤο πηλίκο και το υπόλοιπο με αφαιρέσεις
Πρόγραμμα σε C++
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
Είσοδος του προγράμματος
23 7
Έξοδος
23 = 7 · 3 + 2

Οι γραμμές 9 και 10 δίνουν στις μεταβλητές την αρχική τους τιμή: δεν έχει αφαιρεθεί ακόμη τίποτε, οπότε το πηλίκο είναι 0 και το υπόλοιπο είναι ολόκληρος ο διαιρετέος. Η γραμμή 11 είναι η συνθήκη του βήματος 2 του αλγορίθμου· οι γραμμές 12 και 13, το σώμα. Το πρόγραμμα υποθέτει, όπως ο αλγόριθμος, ότι a≥0a \geq 0 και b>0b > 0: με b=0b = 0, η γραμμή 12 δεν θα άλλαζε το r και ο βρόχος δεν θα τερμάτιζε.

Ο πίνακας ίχνους

Η εκτέλεση του βρόχου με το χέρι σημαίνει να συμπληρώσουμε έναν πίνακα: μία γραμμή ανά γύρο, μία στήλη ανά μεταβλητή και μία για τη συνθήκη, αποτιμημένη στην αρχή του γύρου. Η γραμμή 0 καταγράφει την κατάσταση πριν από την πρώτη αποτίμηση· η τελευταία, την αποτίμηση που βγαίνει ψευδής και τερματίζει τον βρόχο.

ΠαράδειγμαΤο ίχνος του 23 διά 7

Απόδειξη

  1. Πριν από τον βρόχο εκτελούνται οι γραμμές 9 και 10: q=0q = 0 και r=23r = 23. Είναι η γραμμή 0· η συνθήκη δεν έχει αποτιμηθεί ακόμη.

  2. Πρώτος γύρος. Η συνθήκη 23≥723 \geq 7 είναι αληθής, οπότε εκτελείται το σώμα: το rr γίνεται 16 και το qq γίνεται 1. Έπειτα η εκτέλεση επιστρέφει στη γραμμή 11.

  3. Δεύτερος γύρος. Η 16≥716 \geq 7 είναι αληθής: το rr γίνεται 9 και το qq γίνεται 2.

  4. Τρίτος γύρος. Η 9≥79 \geq 7 είναι αληθής: το rr γίνεται 2 και το qq γίνεται 3.

  5. Η τέταρτη αποτίμηση, 2≥72 \geq 7, είναι ψευδής: το σώμα δεν εκτελείται, ο βρόχος τερματίζει και η γραμμή 15 γράφει 23=7⋅3+223 = 7 \cdot 3 + 2.

Το ίχνος μάς μαθαίνει να μετράμε. Το σώμα εκτελέστηκε τρεις φορές, όσες και το πηλίκο, και η συνθήκη αποτιμήθηκε τέσσερις: μία ανά γύρο και μία ακόμη, εκείνη που αποτυγχάνει. Η σχέση αυτή ισχύει για κάθε while που τερματίζει λόγω της συνθήκης του: αν το σώμα εκτελείται kk φορές, η συνθήκη αποτιμάται k+1k + 1 φορές. Και η ακραία περίπτωση το επιβεβαιώνει: με την είσοδο 5 7, η πρώτη αποτίμηση, 5≥75 \geq 7, είναι ήδη ψευδής, το σώμα εκτελείται μηδέν φορές, και το πρόγραμμα γράφει 5=7⋅0+55 = 7 \cdot 0 + 5, που είναι σωστό. Ένα καλογραμμένο while χειρίζεται χωρίς επιπλέον κώδικα την περίπτωση όπου δεν υπάρχει τίποτε να επαναληφθεί.