Ciclo while ed esempi

Argomento di Programmazione 1. Fatto a lezione a settembre, deck 3.2: slide 40-57 e slide 69-97. Prima: Istruzioni condizionali. Dopo: Cicli for e do-while. In mezzo al deck, slide 58-68: Input e output di caratteri.

Il filo:

while                  sintassi, flowchart, semantica
   |
somma 1..5             contatore, accumulatore, inizializzazione
   |
sentinella             leggi prima del ciclo, rileggi in fondo al corpo
   |
MCD                    Euclide (sottrazioni) contro definizione (divisioni, %)
   |                   e quale è più efficiente
moltiplicazione        solo ×2, /2 e somme
   |
scala                  S(n) = S(n-1) + S(n-2) + S(n-3), tre variabili che scorrono

1Definizioni

Istruzione iterativa, o ciclo (slide 40). Ripete l’esecuzione di un blocco di istruzioni finché vale una condizione. Parola chiave while. La condizione si valuta prima di eseguire il blocco.

while (espressione) istruzione

L’istruzione, detta corpo del ciclo, è quasi sempre un blocco fra graffe.

Semantica (slide 41).

1. Si valuta la condizione.
2. Se è VERA si esegue il corpo, poi si torna al punto 1.
3. Se è FALSA il corpo non si esegue e si prosegue con l’istruzione dopo il ciclo.

Due conseguenze:

• se la condizione è falsa subito, il corpo si esegue zero volte;
• il ciclo termina solo se il corpo cambia qualcosa che prima o poi rende falsa la condizione. Altrimenti è un ciclo infinito.

Istruzioni composte (slide 42). if e while non esistono nella macchina di Von Neumann, che conosce solo salti. Sono una caratteristica dei linguaggi di alto livello, e si compongono fra loro: un if dentro un while, un while dentro un altro.

Contatore e accumulatore. Due ruoli che una variabile ha in quasi ogni ciclo:

• contatore: conta i giri, i++ a ogni passaggio;
• accumulatore: raccoglie un risultato, Somma += i.

Entrambi vanno inizializzati prima del ciclo: il primo Somma += i legge il valore di Somma.

Sentinella (slide 45). Un valore speciale che segnala la fine dei dati e che non fa parte dei dati. Nell’esercizio del prof è lo 0: si sommano numeri finché non arriva 0.

Massimo comune divisore (slide 47-48). Dati due interi positivi $m$ e $n$, $MCD(m, n)$ è il più grande intero che li divide entrambi. L’algoritmo di Euclide si basa su:

Perché vale: un numero che divide $n$ e $m$ divide anche $n - m$, e uno che divide $n - m$ e $m$ divide anche $n = (n - m) + m$. Le due coppie hanno gli stessi divisori comuni, quindi lo stesso massimo. Si sottrae il minore dal maggiore finché i due numeri diventano uguali, e quel valore è l’MCD.

2Concetti

2.1Tracciare un ciclo

Si fa una tabella con una colonna per variabile e una riga per giro, più una riga iniziale. In ogni riga si scrive il valore della condizione e poi i valori alla fine del corpo. Ci si ferma alla riga in cui la condizione è falsa: quella riga dà i valori con cui si esce.

Tre domande a cui la tabella risponde sempre, e che all’esame vengono chieste: quante volte si esegue il corpo, con che valori si esce, cosa si stampa.

2.2Il pattern di lettura

Con la sentinella il dato va letto prima del ciclo, perché la condizione lo deve controllare, e poi riletto in fondo al corpo, così il controllo successivo guarda il dato nuovo:

leggi dato
while (dato non è la sentinella) {
    usa dato
    leggi dato
}

Se si leggesse all’inizio del corpo, la sentinella verrebbe usata come un dato normale prima del controllo. Lo stesso schema torna con getchar in Input e output di caratteri.

2.3Efficienza: contare i giri

(slide 56-57) Due algoritmi corretti per lo stesso problema si confrontano contando quante volte si esegue il corpo del while. Il conto dipende dai dati: un algoritmo può vincere su una coppia e perdere su un’altra. Verificati con un contatore aggiunto nei due programmi:

La definizione fa sempre $\min(m, n)$ giri. Euclide per sottrazioni è velocissimo con numeri vicini o multipli, lento quando uno è molto più piccolo dell’altro: con (1000, 2) toglie 2 per 499 volte.

3Metodo

Scrivere un ciclo.

1. Cosa si ripete? Diventa il corpo.
2. Quando ci si ferma? Scrivi la condizione di uscita, poi negala (De Morgan, Algebra di Boole): quella è la condizione del while.
3. Quali variabili servono dal primo giro? Inizializzale prima del ciclo.
4. Cosa, nel corpo, fa avanzare verso l’uscita? Se niente cambia, il ciclo è infinito.
5. Prova a mano il caso zero giri e il caso un giro.

Ciclo che conta da 1 a n.

i = 1;
while (i <= n) {
    ...
    i++;
}

Esegue il corpo $n$ volte, ed esce con $i = n + 1$.

4Esempi svolti a lezione

4.1Esempio della slide 41

while (z != y) {y = z - x; x = x*3;} serve solo a mostrare la sintassi, ma tracciarlo dice molto. Con $x = 0$, $y = 1$, $z = 4$:

Un giro, si esce con x=0 y=4 z=4 (verificato). Ma se $x$ non è zero il ciclo non finisce mai: y = z - x è uguale a z solo quando $x = 0$, e x = x*3 non porta mai a zero un numero diverso da zero. Un ciclo che termina solo per certi dati iniziali è un classico da tracing.

4.2Somma dei primi 5 interi

(slide 43-44)

#include <stdio.h>

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

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

Output: Somma= 15. Il corpo gira 5 volte e si esce con i a 6.

La slide chiede cosa succede con int Somma;, cioè senza inizializzare a 0. Una variabile locale non inizializzata ha un valore indeterminato, e leggerla (lo fa il primo Somma += i) è comportamento indefinito: in pratica di solito parte da quello che c’era in memoria e la somma esce sbagliata, a volte giusta per caso, il che è peggio. La slide si chiede anche se n=5, i; debba essere inizializzato: n sì, perché serve alla condizione; i riceve il valore da i=1; prima del ciclo, quindi va bene così.

4.3Somma con sentinella 0

(slide 45-46) Il programma della slide legge con scanf prima del ciclo e in fondo al corpo, e il commento “Manca qualcosa?” punta all’inizializzazione di Somma. Qui c’è in più il controllo del valore di ritorno di scanf:

#include <stdio.h>

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

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

Con input 4 7 -2 10 0 99:

Output: Somma= 19. Il 99 dopo la sentinella non viene mai letto. Con input 0 subito il corpo non gira e stampa Somma= 0.

Perché il controllo di letti: scanf restituisce quanti valori ha letto. Se l’input finisce senza lo 0 restituisce EOF e non tocca dato. Il programma della slide, senza controllo, a quel punto somma all’infinito l’ultimo numero letto: provato con input 5 3 e un limite di sicurezza a 1000 giri, la somma arriva a 3002.

4.4MCD con Euclide (soluzione 1)

(slide 49-50) Esempi della slide:

MCD ≠ 1:  MCD(15,3) = MCD(12,3) = MCD(9,3) = MCD(6,3) = MCD(3,3) = 3
MCD = 1:  MCD(7,5)  = MCD(2,5)  = MCD(2,3) = MCD(2,1) = MCD(1,1) = 1

La slide scrive il secondo come MCD(3,2) = MCD(1,2), scambiando l’ordine: l’MCD non dipende dall’ordine, il risultato non cambia.

Codice della slide 50, con controllo dell’input:

#include <stdio.h>

int main(void)
{
    int m;
    int n;
    int MCD;

    printf("Inserisci m=");
    if (scanf("%d", &m) != 1) {
        return 1;
    }
    printf("Inserisci n=");
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    if (m <= 0 || n <= 0) {
        printf("servono due interi positivi\n");
        return 1;
    }

    while (m != n) {
        if (m > n) m = m - n;
        else n = n - m;
    }
    MCD = n;
    printf("MCD=%d\n", MCD);
    return 0;
}

La slide dichiara anche min e contatore, che qui non servono (gcc -Wall le segnala come inutilizzate).

“Perché n e non m?” chiede la slide su MCD=n;. Si esce dal ciclo solo quando m != n è falso, cioè quando $m = n$: MCD=m; darebbe lo stesso risultato.

Tracing su (1000, 2), la coppia della slide 57:

A ogni giro m cala di 2: da 1000 a 2 servono $(1000 - 2) / 2 = 499$ giri. Stampa MCD=2. Su (1000, 500) basta un giro: 1000 - 500 = 500, e i due sono uguali.

Errore del programma della slide. Se uno dei due input è 0 il ciclo non termina: con $m = 0$, $n = 5$ il ramo else fa n = 5 - 0 all’infinito. L’algoritmo vale per interi positivi, come dice il testo del problema, e il programma deve controllarlo (è il m <= 0 || n <= 0 aggiunto sopra).

4.5MCD per definizione (soluzione 2)

(slide 51-54) Si provano tutti i candidati da 1 al minore dei due, e si tiene l’ultimo che li divide entrambi. Il minore basta perché un divisore di un numero positivo non può superarlo.

Come si controlla “contatore divide m” senza %? Con la divisione intera: (m/contatore)*contatore è uguale a m solo se la divisione non ha resto. Con $m = 15$: (15/4)*4 è 12, diverso da 15; (15/5)*5 è 15.

La slide 52 contiene due errori, corretti nella 53: le parentesi dell’if sono sbilanciate (if ((m/mcd)*mcd == m) && (...) ), non compila) e divide per mcd invece che per contatore. Versione 2a corretta:

#include <stdio.h>

int main(void)
{
    int m;
    int n;
    int mcd;
    int min;
    int contatore;

    if (scanf("%d %d", &n, &m) != 2 || n <= 0 || m <= 0) {
        printf("servono due interi positivi\n");
        return 1;
    }
    mcd = 1;
    if (n <= m) min = n; else min = m;
    contatore = 1;
    while (contatore <= min) {
        if ((m / contatore) * contatore == m && (n / contatore) * contatore == n)
            mcd = contatore;
        contatore = contatore + 1;
    }
    printf("%d\n", mcd);
    return 0;
}

La nota della slide 53: la divisione fra interi è approssimata, meglio evitarla se si può. Qui funziona proprio perché tronca.

Versione 2b (slide 54): stesso programma, con l’operatore % (resto della divisione intera) al posto del trucco. Cambia solo la riga dell’if:

#include <stdio.h>

int main(void)
{
    int m;
    int n;
    int mcd;
    int min;
    int contatore;

    if (scanf("%d %d", &n, &m) != 2 || n <= 0 || m <= 0) {
        printf("servono due interi positivi\n");
        return 1;
    }
    mcd = 1;
    if (n <= m) min = n; else min = m;
    contatore = 1;
    while (contatore <= min) {
        if (!(m % contatore) && !(n % contatore))
            mcd = contatore;
        contatore = contatore + 1;
    }
    printf("%d\n", mcd);
    return 0;
}

!(m % contatore) è vero quando il resto è 0, cioè quando contatore divide m. Tutte e tre le versioni danno 3 su (15, 3), 1 su (7, 5), 2 su (1000, 2), 6 su (12, 18) (verificato).

Errori di etichetta nelle slide. La slide 54 dice “Soluzione 1b” nel testo e “2b” nel titolo. La 55 chiama Soluzione 1 la definizione e Soluzione 2 Euclide, al contrario delle slide 47 e 51. Le 56 e 57 parlano di “minimo comune divisore”: è il massimo (il minimo comune divisore di due interi è sempre 1).

4.6Moltiplicazione con ×2, /2 e somme

(slide 69-73) Il problema: moltiplicare $m$ per $n$ usando solo moltiplicazioni e divisioni per 2 e somme. L’idea della slide: si scrive $n = 2 k_1 + r_1$ (quoziente e resto della divisione per 2), poi $k_1 = 2 k_2 + r_2$, e così via:

In pratica si dimezza un fattore e si raddoppia l’altro. Quando il fattore da dimezzare è dispari, la divisione intera perde un’unità, e quella parte si recupera sommando l’altro fattore a parte. mult accumula i raddoppi, sum le somme dovute ai resti.

#include <stdio.h>

int main(void)
{
    int m;
    int n;
    int mult;
    int max;
    int min;
    int sum;

    if (scanf("%d", &m) != 1 || scanf("%d", &n) != 1) {
        return 1;
    }
    if (n > m) {
        max = n;
        min = m;
    }
    else {
        max = m;
        min = n;
    }
    mult = max;
    sum = 0;
    while (min > 1) {
        if (min % 2) {
            sum += mult;
        }
        mult = mult * 2;
        min = min / 2;
    }
    printf("n=%d\n", n);
    printf("m=%d\n", m);
    printf("mult=%d\n", mult + sum);
    return 0;
}

Tracing con $m = 6$, $n = 13$ (quindi max = 13, min = 6):

Stampa n=13, m=6, mult=78. L’ultima colonna è sempre $78 = 6 \cdot 13$: è l’invariante del ciclo, la quantità che il corpo non cambia. Quando min arriva a 1 resta mult * 1 + sum, che è quello che il programma stampa. Si usa il minore come fattore da dimezzare perché così i giri sono meno.

Errori del programma della slide (verificati): funziona solo con fattori positivi.

• Se un fattore è 0, min vale 0, il ciclo non parte e stampa max: $5 \cdot 0$ dà 5.
• Se un fattore è negativo, min è negativo, il ciclo non parte: $-3 \cdot 4$ dà 4.

Il testo dice “due numeri interi”, quindi il programma andrebbe completato con i casi 0 e negativi, o il testo ristretto ai positivi.

4.7La scala a passi da 1, 2 o 3

(slide 74-97) Una scala di $N$ gradini si sale con passi da 1, 2 o 3 gradini. In quanti modi diversi si arriva in cima? Era già stato lasciato aperto in Introduzione al corso e algoritmi.

Casi piccoli (slide 77-80):

• $N = 1$: solo 1. $S(1) = 1$.
• $N = 2$: 1+1, 2. $S(2) = 2$.
• $N = 3$: 1+1+1, 1+2, 2+1, 3. $S(3) = 4$.
• $N = 4$: il primo passo è da 1, da 2 o da 3. Dopo un passo da 1 restano 3 gradini, che si salgono in $S(3)$ modi; dopo uno da 2 ne restano 2; dopo uno da 3 ne resta 1. Quindi $S(4) = S(3) + S(2) + S(1) = 4 + 2 + 1 = 7$.

Il ragionamento di $N = 4$ vale per ogni $N > 3$ (slide 92):

N    1  2  3  4   5   6   7   8    9    10
S    1  2  4  7  13  24  44  81  149   274

Pseudocodice (slide 81-84). Non serve ricordare tutta la successione, bastano gli ultimi tre valori:

1. leggi $N$;
2. inizializza le soluzioni note, per $N$ = 0, 1, 2;
3. tienile in tre variabili, che contengono le soluzioni per $K-3$, $K-2$ e $K-1$;
4. in un ciclo fai crescere $K$ da 3 fino a $N$: la soluzione per $K$ è la somma delle tre variabili, poi le tre variabili scorrono di un posto.

Codice (slide 85-90), con una dichiarazione per riga e il controllo di scanf:

#include <stdio.h>

int main(void)
{
    int N;
    int i;
    int TotaleModi = 0;
    int PassiTipo3;
    int PassiTipo2;
    int PassiTipo1;

    printf("inserire numero di gradini della scala: ");
    if (scanf("%d", &N) != 1) {
        return 1;
    }

    if (N < 0) {
        printf("errore numero di gradini\n");
    }
    else if (N <= 2) {
        printf("Combinazioni per salire scala di %d gradini: %d\n", N, N);
    }
    else {
        i = 3;
        PassiTipo3 = 1;
        PassiTipo2 = 1;
        PassiTipo1 = 2;
        while (i < N + 1) {
            TotaleModi = PassiTipo3 + PassiTipo2 + PassiTipo1;
            PassiTipo3 = PassiTipo2;
            PassiTipo2 = PassiTipo1;
            PassiTipo1 = TotaleModi;
            i++;
        }
        printf("Combinazioni per salire scala di %d gradini: %d\n", N, TotaleModi);
    }
    return 0;
}

PassiTipo1 contiene $S(i-1)$, i modi se il primo passo è da 1; PassiTipo2 contiene $S(i-2)$; PassiTipo3 contiene $S(i-3)$. Il commento alterfor(i=3; i<N+1; i++) della slide anticipa che lo stesso ciclo si scriverà con un for (Cicli for e do-while).

Tracing con $N = 5$:

Stampa Combinazioni per salire scala di 5 gradini: 13. L’ordine dello scorrimento conta: se si scrivesse prima PassiTipo1 = TotaleModi e poi PassiTipo2 = PassiTipo1, il vecchio PassiTipo1 andrebbe perso.

Incoerenza su $N = 0$. L’inizializzazione PassiTipo3 = 1 vuol dire $S(0) = 1$: per $N = 3$ il caso “primo passo da 3” arriva in cima, e conta un modo. Ma per $N \leq 2$ il programma stampa $N$, quindi per $N = 0$ stampa 0. Quale dei due sia giusto per una scala di zero gradini è una convenzione (un modo: non muoversi; oppure nessuno), ma il programma dovrebbe sceglierne una. La prima soluzione di ChatGPT sotto usa 1.

Overflow. $S(n)$ cresce in fretta: $S(36) = 2\,082\,876\,103$ sta ancora in un int a 32 bit (massimo 2 147 483 647), $S(37)$ no. Il programma con $N = 37$ stampa un numero negativo (provato: -463960867). Il superamento del massimo di un int con segno è comportamento indefinito.

Successioni a confronto (slide 93-94). I grafici della slide, in scala logaritmica, mettono $S(n)$ fra Fibonacci ($F(n) = F(n-1) + F(n-2)$) e $2^n$, e aggiungono $n^2$ e $n!$. Con $n = 30$:

$n^2$ è polinomiale, le tre successioni in mezzo sono esponenziali (ogni passo moltiplica per circa 1,62, 1,84 e 2), $n!$ cresce ancora più in fretta. È il primo assaggio di complessità: un algoritmo che fa $S(n)$ operazioni è inutilizzabile già per $n$ piccoli.

Le due soluzioni di ChatGPT (slide 96-97), in Python:

1. Ricorsiva: una funzione che per $n > 2$ restituisce countWays(n-1) + countWays(n-2) + countWays(n-3), con i casi base $n < 0$ → 0, $n = 0$ → 1, $n = 1$ → 1, $n = 2$ → 2. È la ricorrenza scritta pari pari, ma ricalcola gli stessi valori moltissime volte: per $n = 30$ fa circa 57 milioni di chiamate (contate con uno script).
2. Programmazione dinamica: un array dp di $n + 1$ posti riempito da 3 in su, con dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Ogni valore si calcola una volta: tempo $O(N)$ e memoria $O(N)$.

La soluzione del prof è la dinamica senza array: tiene solo gli ultimi tre valori, quindi tempo $O(N)$ e memoria costante. Funzioni, ricorsione e array in C arrivano più avanti nel corso.

5Esercizi tipo esame

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

#include <stdio.h>

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

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

Esercizio 2. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int n = 3725;
    int somma = 0;
    int cifre = 0;

    while (n > 0) {
        somma += n % 10;
        n /= 10;
        cifre++;
    }
    printf("%d %d %d\n", n, somma, cifre);
    return 0;
}

Esercizio 3. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int k = 4;
    int x = 1;

    while (k--)
        x = x * 2 + k;
    printf("k=%d x=%d\n", k, x);
    return 0;
}

Esercizio 4. Traccia Euclide per sottrazioni su $(m, n) = (21, 6)$: quanti giri, che MCD?

Esercizio 5. Scrivi un programma che legge $N$ e stampa un quadrato $N \times N$ con * sul bordo e . all’interno. Per $N = 5$:

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

#include <stdio.h>

int main(void)
{
    int N;
    int r;

    if (scanf("%d", &N) != 1 || N <= 0) {
        printf("N non valido\n");
        return 1;
    }
    r = 0;
    while (r < N) {
        int c = 0;
        while (c < N) {
            if (r == 0 || r == N - 1 || c == 0 || c == N - 1)
                printf("*");
            else
                printf(".");
            c++;
        }
        printf("\n");
        r++;
    }
    return 0;
}

Esercizio 6. Scrivi l’output esatto.

#include <stdio.h>

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

    while (r <= N) {
        int c = 1;
        while (c <= r) {
            printf("%d", c);
            c++;
        }
        printf("\n");
        r++;
    }
    return 0;
}

1
12
123
1234

Esercizio 7. Scrivi un programma che legge un intero non negativo e ne stampa le cifre al contrario come numero (1234 diventa 4321).

#include <stdio.h>

int main(void)
{
    int n;
    int rovescio = 0;

    if (scanf("%d", &n) != 1 || n < 0) {
        return 1;
    }
    while (n > 0) {
        rovescio = rovescio * 10 + n % 10;
        n = n / 10;
    }
    printf("%d\n", rovescio);
    return 0;
}

Esercizio 8. Traccia il programma della moltiplicazione con $m = 5$, $n = 11$.

6Errori tipici

• Dimenticare di inizializzare accumulatori e contatori (int Somma;).
• Dimenticare l’aggiornamento nel corpo (i++): ciclo infinito.
• while (i <= n); con il punto e virgola: il corpo è l’istruzione vuota, e se la condizione è vera il ciclo non finisce mai.
• Leggere la sentinella solo all’inizio del corpo: la sentinella viene elaborata come un dato.
• Non controllare il ritorno di scanf in un ciclo di lettura: a fine input il valore resta quello vecchio e il ciclo può non finire.
• Sbagliare di uno (off-by-one): i < n e i <= n fanno un numero di giri diverso. Controlla sempre il primo e l’ultimo giro.
• Nel doppio ciclo, non rimettere a zero la variabile del ciclo interno.
• Nello scorrimento delle tre variabili della scala, aggiornarle nell’ordine sbagliato.
• Euclide per sottrazioni con un input 0: ciclo infinito.

7Domande

• Qual è la semantica del while? Quante volte può essere eseguito il corpo, come minimo?

• Cosa succede se in un programma si dichiara int Somma; senza inizializzarla e poi si fa Somma += i?

• Cos’è una sentinella? Perché il dato si legge prima del ciclo e di nuovo in fondo al corpo?

• Su quale proprietà si basa l’algoritmo di Euclide per sottrazioni, e perché vale?

• Nell’algoritmo di Euclide, perché alla fine si può stampare indifferentemente n o m?

• Cosa succede all’algoritmo di Euclide per sottrazioni se un input è 0?

• Come si controlla se c divide m senza usare %?

• Quanti giri fanno Euclide e la definizione su (1000, 500) e su (1000, 2)?

• Qual è l’invariante del programma della moltiplicazione con ×2, /2 e somme?

• Per quali input il programma della moltiplicazione della slide sbaglia?

• Qual è la ricorrenza del problema della scala e come la si ricava?

• Perché il programma della scala tiene solo tre variabili e non tutta la successione?

• Perché la soluzione ricorsiva della scala è molto più lenta di quella con il ciclo?

• Con k = 3, quante volte gira while (k--) e quanto vale k all’uscita?

• Quante volte si esegue il corpo di i = 0; while (i < 10) i += 3; e quanto vale i alla fine?