Vai al contenuto
Topos Uranos
Italiano

Cicli

Riepilogo

La lezione Dal problema all’algoritmo ha riconosciuto tre modi di comporre i passi: la sequenza, la decisione e la ripetizione. I primi due hanno già la loro scrittura in C++; questa lezione dà la sua al terzo. Studia le tre forme del ciclo: while, che valuta la sua condizione prima di ogni iterazione e può non eseguire mai il suo corpo; do, che la valuta dopo ed esegue il corpo almeno una volta; e for, che riunisce in una riga l’inizializzazione, la condizione e l’aggiornamento della variabile che governa la ripetizione. Mostra che le tre esprimono uno stesso meccanismo, di modo che ciascuna si trasforma nelle altre, e insegna a scegliere la più chiara; presenta break e continue, che alterano il corso di un’iterazione; e termina con i cicli annidati, il cui corpo interno si esegue un numero di volte che si calcola con una somma. Lo strumento che accompagna tutta la lezione è la tabella di traccia: seguire un ciclo a mano, iterazione per iterazione, è il modo di prevedere quante volte si esegue il suo corpo e che cosa lascia all’uscita.

Obiettivi di apprendimento

  1. Scrivere un ciclo while, do o for per una ripetizione data, scegliendo la forma più chiara.
  2. Seguire a mano un ciclo con la sua tabella di traccia e prevedere quante volte si esegue il corpo.
  3. Trasformare un ciclo da una forma a un’altra conservandone il significato.
  4. Scrivere cicli annidati e calcolare quante volte si esegue il corpo interno.

while

La forma di un while

Un while si scrive così:

Codice C++
while (condizione) {    corpo}

Il suo significato si enuncia in tre passi: si valuta la condizione; se è falsa, il ciclo termina e l’esecuzione prosegue dopo la graffa che lo chiude; se è vera, si esegue il corpo e si torna al primo passo. Ogni esecuzione del corpo si chiama iterazione (o giro). La condizione è un’espressione booleana come quelle della lezione Relazioni e logica, e il corpo è un blocco; la regola delle graffe che la lezione Decisioni ha fissato vale anche qui: il corpo di un ciclo porta sempre le graffe, anche se contiene una sola istruzione.

Dalla definizione seguono due conseguenze. La prima: la condizione si valuta prima di ogni iterazione, di modo che, se è falsa fin dall’inizio, il corpo non si esegue nemmeno una volta. La seconda: perché il ciclo termini, il corpo deve cambiare qualcosa di ciò che la condizione legge; se nulla cambia, la condizione che è stata vera una volta lo sarà sempre. Ora, cambiare non basta: la lezione Dal problema all’algoritmo ha mostrato che serve una quantità naturale che decresca a ogni iterazione, la variante, e la lezione Progettare cicli corretti ne farà un metodo.

La divisione per sottrazioni successive

Il primo algoritmo con ripetizione del corso è stato la divisione per sottrazioni successive: finché il resto è almeno il divisore, gli si sottrae il divisore e si aggiunge uno al quoziente. Scritto in C++, l’algoritmo si traspone quasi parola per parola.

EsempioIl quoziente e il resto per sottrazioni
Programma in 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);}
Input del programma
23 7
Output
23 = 7 · 3 + 2

Le righe 9 e 10 danno alle variabili il loro valore iniziale: non si è ancora sottratto nulla, di modo che il quoziente è 0 e il resto è tutto il dividendo. La riga 11 è la condizione del passo 2 dell’algoritmo; le righe 12 e 13, il corpo. Il programma suppone, come l’algoritmo, che a≥0a \geq 0 e b>0b > 0: con b=0b = 0, la riga 12 non cambierebbe r e il ciclo non terminerebbe.

La tabella di traccia

Seguire il ciclo a mano significa riempire una tabella: una riga per iterazione, una colonna per variabile e una per la condizione, valutata all’inizio dell’iterazione. La riga 0 registra lo stato prima della prima valutazione; l’ultima, la valutazione che risulta falsa e termina il ciclo.

EsempioLa traccia di 23 diviso 7

Dimostrazione

  1. Prima del ciclo si eseguono le righe 9 e 10: q=0q = 0 e r=23r = 23. È la riga 0 della tabella; la condizione non è ancora stata valutata.

  2. Prima iterazione. La condizione 23≥723 \geq 7 è vera, di modo che si esegue il corpo: rr passa a 16 e qq a 1. Poi l’esecuzione torna alla riga 11.

  3. Seconda iterazione. 16≥716 \geq 7 è vera: rr passa a 9 e qq a 2.

  4. Terza iterazione. 9≥79 \geq 7 è vera: rr passa a 2 e qq a 3.

  5. La quarta valutazione, 2≥72 \geq 7, è falsa: il corpo non si esegue, il ciclo termina e la riga 15 scrive 23=7⋅3+223 = 7 \cdot 3 + 2.

La traccia insegna a contare. Il corpo si è eseguito tre volte, tante quante il quoziente, e la condizione si è valutata quattro: una per iterazione e una in più, quella che fallisce. Questa relazione vale per ogni while che termina per la sua condizione: se il corpo si esegue kk volte, la condizione si valuta k+1k + 1 volte. E il caso estremo lo conferma: con l’input 5 7, la prima valutazione, 5≥75 \geq 7, è già falsa, il corpo si esegue zero volte, e il programma scrive 5=7⋅0+55 = 7 \cdot 0 + 5, che è corretto. Un while ben scritto tratta senza codice aggiuntivo il caso in cui non c’è nulla da ripetere.