Cicli for e do-while

Argomento di Programmazione 1. Fatto a lezione fra settembre e ottobre, deck 3.3: slide 3-15 (for e do-while), slide 32-34 (break e continue), slide 35-37 (Böhm-Jacopini). Prima: Ciclo while ed esempi. In mezzo al deck, slide 16-31: Switch.

Il filo del deck:

while            già visto: valuta, poi esegue
   |
for              stesso ciclo, inizializzazione + condizione + aggiornamento in una riga
   |             utile quando il numero di giri è noto
do-while         esegue, poi valuta: almeno un giro
   |
switch           selezione multipla (nota a parte)
   |
break/continue   uscire dal ciclo, saltare al giro dopo
   |
Böhm-Jacopini    sequenza, if-else e while bastano per ogni algoritmo

1Definizioni

Ciclo for (slide 3-5). Il prof lo presenta come la forma compatta dello schema tipico del while con contatore, utile quando il numero di iterazioni è noto a priori:

contatore = valIniz;                    for (contatore = valIniz;
while (contatore <= valFin) {                contatore <= valFin;
    ... istruzioni da ripetere ...           contatore++) {
    contatore++;                            ... istruzioni da ripetere ...
}                                       }

Le tre parti dell’intestazione, separate da ;:

• espr1, l’inizializzazione: eseguita una sola volta, prima di tutto;
• espr2, la condizione: valutata all’inizio e a ogni iterazione, prima del corpo;
• espr3, l’aggiornamento: eseguito a ogni iterazione, dopo il corpo.

Come nel while, se la condizione è falsa subito il corpo si esegue zero volte.

Equivalenza for-while (slide 9). L’intestazione può contenere espressioni qualunque, e

for (espr1; espr2; espr3) {          espr1;
    istruzioni                       while (espr2) {
}                                        istruzioni
                                         espr3;
                                     }

fanno la stessa cosa. Unica eccezione: un continue nel corpo (vedi sotto). Il consiglio della slide: nel for usare espr1 solo per inizializzare la variabile di ciclo, espr2 solo per la condizione di uscita, espr3 solo per incrementarla o decrementarla. Il C permette di più, ma poi il ciclo non si legge.

Si può anche lasciare vuota una parte: for (; i < n; ) è un while; for (;;) senza condizione è un ciclo infinito (la condizione mancante vale vero), da cui si esce solo con break o return.

Ciclo do-while (slide 13).

do {
    blocco istruzioni
} while (espressione);

Prima si esegue il corpo, poi si valuta la condizione: se è vera si ripete, se è falsa si esce. Quindi il corpo si esegue almeno una volta, anche se la condizione è falsa dall’inizio. Il ; dopo la parentesi è obbligatorio, a differenza di while e for.

break (slide 32). Dentro un while, for, do-while o switch provoca l’uscita immediata da quell’istruzione. L’esecuzione continua con l’istruzione che la segue. Con due cicli annidati, break esce solo da quello più interno che lo contiene.

continue (slide 33). Dentro un while, for o do-while salta le istruzioni rimanenti del corpo e passa all’iterazione successiva. Non si applica allo switch. Dove va il salto:

• nel while e nel do-while, alla valutazione della condizione;
• nel for, all’aggiornamento espr3, e poi alla condizione.

Teorema di Böhm-Jacopini (slide 35-37). Il prof parte da tre domande: esistono algoritmi che non si possono scrivere con sequenze, if-else e while? Esistono strutture capaci di codificare qualsiasi algoritmo? Ne esistono di più potenti? La risposta, in teoria: sequenza, selezione (if-else) e ciclo (while) sono complete, cioè bastano a codificare qualsiasi algoritmo espresso con un diagramma di flusso.

Con le parole della slide 37: le strutture if-else e while sono equivalenti a quelle del linguaggio assemblatore, che modifica direttamente o sotto condizione il registro contatore di programma (PC, i salti visti in Architettura hardware e software di un calcolatore). Quello che si scrive con una si scrive con l’altra. E sono equivalenti alle strutture di controllo di qualsiasi altro linguaggio.

Conseguenza pratica: for, do-while e switch non aggiungono potenza, solo comodità. Ognuno si riscrive con while e if-else.

2Concetti

2.1Quante volte gira un for

Per il caso tipico for (i = a; i < b; i++), con la variabile non toccata nel corpo:

• il corpo gira $b - a$ volte (zero se $a \geq b$);
• si esce con i uguale a $b$, il primo valore che rende falsa la condizione.

Con i <= b i giri diventano $b - a + 1$ e si esce con $b + 1$. Con passo diverso da 1, per esempio i += 3, conviene elencare i valori: for (i = 10; i > 0; i -= 3) vede 10, 7, 4, 1 ed esce con $-2$.

Attenzione (slide 11-12): se il corpo modifica la variabile di ciclo, l’intestazione da sola non dice più niente. La regola della slide è non farlo mai.

2.2Quale ciclo scegliere

numero di giri noto prima di partire         for       (contare, scorrere 1..N)
si ripete finché vale una condizione,        while     (sentinella, lettura fino a EOF,
  e può non servire nemmeno un giro                     Euclide)
il corpo va eseguito almeno una volta,       do-while  (chiedere un input finché
  e la condizione dipende da quel giro                  non è valido, menu)

Sono tutti equivalenti, quindi la scelta è di leggibilità. Il do-while è giusto quando il dato da controllare nasce dentro il corpo: con un while si dovrebbe leggere una volta prima del ciclo e una volta dentro, o inventare un valore iniziale finto.

2.3do-while come while

do {                          corpo
    corpo                     while (cond) {
} while (cond);                   corpo
                              }

Il corpo scritto una volta prima del while fa il “giro garantito”. Al contrario, un while si scrive come do-while solo con un if davanti che controlla la condizione, altrimenti il primo giro avviene anche quando non dovrebbe.

3Metodo

Tracciare un for.

1. Esegui espr1 una volta e scrivi la riga iniziale della tabella.
2. Valuta espr2. Se è falsa ti fermi: quella riga dà i valori di uscita.
3. Esegui il corpo, poi espr3, e scrivi una riga con i valori dopo l’aggiornamento.
4. Torna al passo 2.

Con break ti fermi subito e non esegui espr3; con continue salti il resto del corpo ma espr3 sì.

Due for annidati. Il ciclo interno riparte da capo a ogni giro di quello esterno. Il totale dei giri del corpo interno è la somma, su ogni giro esterno, dei giri interni: con estremi fissi è il prodotto ($N \cdot M$), con j che parte da i è $N + (N - 1) + \ldots + 1 = N (N + 1) / 2$.

Tradurre for in while.

1. espr1 diventa un’istruzione prima del while.
2. espr2 diventa la condizione del while.
3. espr3 diventa l’ultima istruzione del corpo.
4. Se nel corpo c’è un continue, prima di ogni continue va ripetuta espr3, altrimenti il while non aggiorna più la variabile e può non finire.

Tradurre while in for. L’inizializzazione prima del ciclo va in espr1, l’aggiornamento in fondo al corpo va in espr3. Se non c’è un aggiornamento “pulito” in fondo (sentinella, lettura con getchar) il while è già la scelta giusta.

Input con controllo del range.

do {
    stampa la richiesta
    leggi n (e controlla che scanf abbia letto)
} while (n fuori dal range);

4Esempi svolti a lezione

4.1Somma di n numeri in input, da while a for

(slide 6 e slide 8) La slide trasforma il ciclo con contatore in un for. Il codice della slide legge con scanf(x);, che è sbagliato: scanf vuole la stringa di formato e l’indirizzo della variabile, cioè scanf("%d", &x) (gcc rifiuta scanf(x): passa un int dove serve una stringa). Versione corretta con il controllo dell’input:

#include <stdio.h>

int main(void)
{
    int x;
    int n = 5;
    int somma = 0;
    int contatore;

    for (contatore = 1; contatore <= n; contatore++) {
        if (scanf("%d", &x) != 1) {
            printf("input non valido\n");
            return 1;
        }
        somma = somma + x;
    }
    printf("somma=%d\n", somma);
    return 0;
}

Con input 4 7 -2 10 1 stampa somma=20 (verificato). Nel while della slide c’erano int contatore = 1; prima del ciclo e contatore=contatore+1; in fondo al corpo: nel for finiscono rispettivamente in espr1 ed espr3, e la dichiarazione resta senza valore iniziale.

4.2Somma dei primi 5 interi con il for

(slide 7) La slide riprende il programma while di Ciclo while ed esempi e chiede di riscriverlo con il for:

#include <stdio.h>

int main(void)
{
    int Somma = 0;
    int n = 5;
    int i;

    for (i = 1; i <= n; i++) {
        Somma += i;
    }
    printf("Somma= %d\n", Somma);
    return 0;
}

Output Somma= 15, come prima. i=1; prima del while diventa espr1, i <= n resta la condizione, i++; in fondo al corpo diventa espr3. L’inizializzazione Somma=0 resta fuori: non è la variabile di ciclo.

4.3Quante volte gira

(slide 10-12) Tre domande in fila.

Slide 10. for (i=0; i<10; i++) printf("Hello World!\n"); stampa la riga 10 volte: i vale 0, 1, …, 9, ed esce con i a 10. La slide scrive le virgolette tipografiche (“Hello World!\n”): in C le stringhe vogliono le virgolette dritte ", con quelle curve il programma non compila.

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 0; i < 10; i++) {
        printf("Hello World!\n");
    }
    printf("i=%d\n", i);
    return 0;
}

Stampa 10 volte Hello World! e poi i=10 (verificato).

Slide 11. Stesso ciclo, corpo qualunque: 10 volte, se il corpo non tocca i.

Slide 12. Con i++; anche dentro il corpo, ogni giro aumenta i di 2:

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 0; i < 10; i++) {
        printf("%d ", i);
        i++;
    }
    printf("\nfine: i=%d\n", i);
    return 0;
}

Output (verificato):

0 2 4 6 8 
fine: i=10

Il corpo gira 5 volte, non 10. È il punto della slide: guardando solo l’intestazione non si può rispondere, quindi la variabile di ciclo non si modifica nel corpo.

4.4Somma con sentinella 0, con il do-while

(slide 14) La slide mostra il programma con il while (lo stesso di Ciclo while ed esempi) e chiede di riscriverlo con il do-while. Con il do-while la lettura sta una volta sola, dentro il corpo:

#include <stdio.h>

int main(void)
{
    int Somma = 0;
    int dato = 0;
    int letti;

    do {
        letti = scanf("%d", &dato);
        if (letti == 1) {
            Somma += dato;
        }
    } while (letti == 1 && dato != 0);
    printf("Somma= %d\n", Somma);
    return 0;
}

Con input 4 7 -2 10 0 99 stampa Somma= 19; con input 0 stampa Somma= 0; con input vuoto anche Somma= 0 (verificati). La sentinella viene sommata, ma sommare 0 non cambia niente: per questo qui il do-while funziona senza un if in più. Con una sentinella diversa, per esempio $-1$, andrebbe esclusa con un if (dato != -1).

La slide 14 dichiara int Somma,dato; senza inizializzare Somma (il commento “inizializzazione?” e “Manca qualcosa?” puntano proprio lì) e non controlla scanf: a fine input senza lo 0 il ciclo non finirebbe più.

4.5Conteggio dei caratteri, con il do-while

(slide 15) Il programma della slide conta i caratteri in input con while ((c = getchar()) != EOF) ++nc;, come in Input e output di caratteri. Riscritto con il do-while, il carattere si legge nel corpo e il controllo di EOF va fatto due volte:

#include <stdio.h>

int main(void)
{
    int c;
    int nc = 0;

    do {
        c = getchar();
        if (c != EOF) {
            ++nc;
        }
    } while (c != EOF);
    printf("\nNumero Caratteri=%d\n", nc);
    return 0;
}

Con input ciao più invio stampa Numero Caratteri=5 (l’a capo è un carattere); con input vuoto Numero Caratteri=0. Senza l’if, cioè con ++nc; e basta, conterebbe anche l’EOF: 6 e 1 (verificati entrambi).

Il conteggio dei caratteri è l’esempio in cui il do-while non conviene: l’input può essere vuoto, quindi il giro garantito non serve, e la versione while è più corta e più chiara. È la risposta da dare se all’esame chiedono quale dei due è meglio.

4.6break e continue nel for

(slide 34) Il programma della slide ha if (i == 3) break; e, commentata, la variante con continue.

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 1; i <= 10; i++) {
        if (i == 3) break;
        printf("i=%d\n", i);
    }
    printf("Fine: i=%d\n", i);
    return 0;
}

Output con break (verificato):

i=1
i=2
Fine: i=3

Con i == 3 si esce subito dal for: niente printf, niente i++. Per questo i vale 3 e non 4.

Con continue al posto di break:

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 1; i <= 10; i++) {
        if (i == 3) continue;
        printf("i=%d\n", i);
    }
    printf("Fine: i=%d\n", i);
    return 0;
}

stampa i=1, i=2, poi salta il 3 e prosegue da i=4 fino a i=10, e alla fine Fine: i=11 (verificato). Il continue salta il printf ma non l’i++ di espr3, quindi il ciclo arriva in fondo normalmente. La slide stampa "Fine: i=%d" senza \n finale.

5Esercizi tipo esame

Esercizio 1. Scrivi l’output esatto e quante volte si esegue il corpo.

#include <stdio.h>

int main(void)
{
    int i;
    int s = 0;

    for (i = 10; i > 0; i -= 3) {
        s += i;
    }
    printf("i=%d s=%d\n", i, s);
    return 0;
}

Esercizio 2. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int x = 5;
    int giri_while = 0;
    int giri_do = 0;

    while (x < 5) {
        x++;
        giri_while++;
    }
    printf("while: x=%d giri=%d\n", x, giri_while);

    do {
        x++;
        giri_do++;
    } while (x < 5);
    printf("do-while: x=%d giri=%d\n", x, giri_do);
    return 0;
}

while: x=5 giri=0
do-while: x=6 giri=1

Esercizio 3. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 0; i < 10; i++) {
        if (i % 3 == 0) continue;
        if (i > 7) break;
        printf("%d ", i);
    }
    printf("\ni=%d\n", i);
    return 0;
}

1 2 4 5 7 
i=8

Esercizio 4. Quanto vale conta alla fine? E i e j?

#include <stdio.h>

int main(void)
{
    int i;
    int j;
    int conta = 0;

    for (i = 0; i < 4; i++) {
        for (j = i; j < 4; j++) {
            conta++;
        }
    }
    printf("conta=%d i=%d j=%d\n", conta, i, j);
    return 0;
}

Esercizio 5. Il for e il while qui sotto sono equivalenti? Se no, correggi il while.

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 0; i < 5; i++) {
        if (i == 2) continue;
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

i = 0;
while (i < 5) {
    if (i == 2) continue;
    printf("%d ", i);
    i++;
}

i = 0;
while (i < 5) {
    if (i == 2) {
        i++;
        continue;
    }
    printf("%d ", i);
    i++;
}

Esercizio 6. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int k = 0;

    do {
        printf("%d ", k);
        k += 4;
    } while (k < 10);
    printf("| k=%d\n", k);

    k = 20;
    do {
        printf("%d ", k);
        k += 4;
    } while (k < 10);
    printf("| k=%d\n", k);
    return 0;
}

0 4 8 | k=12
20 | k=24

Esercizio 7. Scrivi un programma che chiede un intero $n$ fra 1 e 10, ripetendo la domanda finché il valore è fuori range, e poi stampa $n!$ con un for.

#include <stdio.h>

int main(void)
{
    int n;
    int letti;
    int i;
    int fatt = 1;

    do {
        printf("n (1-10): ");
        letti = scanf("%d", &n);
        if (letti != 1) {
            return 1;
        }
    } while (n < 1 || n > 10);

    for (i = 2; i <= n; i++) {
        fatt *= i;
    }
    printf("%d! = %d\n", n, fatt);
    return 0;
}

Esercizio 8. Scrivi l’output esatto per $N = 4$.

#include <stdio.h>

int main(void)
{
    int N = 4;
    int r;
    int c;

    for (r = 0; r < N; r++) {
        for (c = 0; c < N; c++) {
            if (c <= r) printf("*");
            else printf(".");
        }
        printf("\n");
    }
    return 0;
}

*...
**..
***.
****

Esercizio 9. Riscrivi con un for e poi con un do-while, mantenendo lo stesso comportamento per ogni $n$:

i = n;
while (i > 0) {
    printf("%d ", i);
    i -= 2;
}

i = n;
if (i > 0) {
    do {
        printf("%d ", i);
        i -= 2;
    } while (i > 0);
}

6Errori tipici

• Modificare la variabile di ciclo dentro il corpo del for: il numero di giri non si legge più dall’intestazione (slide 12).
• for (i = 0; i < 10; i++); con il punto e virgola: il corpo è l’istruzione vuota, il blocco dopo si esegue una volta sola con i a 10.
• Separare le parti del for con la virgola invece del ;.
• Dimenticare il ; dopo while (cond) nel do-while.
• Usare il do-while quando il caso “zero giri” è possibile (input vuoto, $n = 0$): il primo giro avviene comunque.
• Tradurre un for con continue in un while senza ripetere l’aggiornamento: ciclo infinito.
• Credere che break esca da tutti i cicli annidati: esce solo da quello che lo contiene direttamente.
• Pensare che continue funzioni nello switch: vale solo per i cicli. Un continue dentro uno switch dentro un ciclo agisce sul ciclo.
• Sbagliare il valore di uscita: dopo for (i = 0; i < n; i++) la variabile vale $n$, non $n - 1$. Dopo un break vale quello che aveva quando è scattato.
• scanf(x) come sulla slide 6: serve scanf("%d", &x).

7Domande

• Quali sono le tre parti dell’intestazione di un for, e quando viene eseguita ciascuna?

• Come si riscrive for (espr1; espr2; espr3) corpo con un while?

• In quale caso la traduzione di un for in while non è equivalente?

• Quante volte viene eseguito, al minimo, il corpo di un do-while? E quello di un while o di un for?

• Quando conviene il for, quando il while, quando il do-while?

• Perché non si dovrebbe modificare la variabile di ciclo dentro il corpo di un for?

• Cosa fa break dentro un ciclo? E dentro due cicli annidati?

• Cosa fa continue in un for? Dove salta in un while?

• Con quale valore esce i da for (i = 1; i <= 10; i++) if (i == 3) break;? E con continue al posto di break?

• Cosa dice il teorema di Böhm-Jacopini?

• Quante volte gira il corpo interno di for (i = 0; i < N; i++) for (j = i; j < N; j++)?