Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
set, giorno?
in corso

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 del deck:

while                  sintassi, flowchart, semantica          slide 40-42
   |
somma 1..5             contatore, accumulatore, inizializzazione  slide 43-44
   |
sentinella             leggi prima del ciclo, rileggi in fondo   slide 45-46
   |
MCD                    Euclide (sottrazioni) contro definizione  slide 47-55
   |                   (divisioni, poi %)
efficienza             quante volte gira il corpo?              slide 56-57
   |
   |   (slide 58-68: getchar e putchar, nota a parte)
   |
moltiplicazione        solo ×2, /2 e somme, invariante          slide 69-73
   |
scala                  S(n) = S(n-1) + S(n-2) + S(n-3)          slide 74-97
                       tre variabili che scorrono, crescita esponenziale

1Definizioni

Istruzione iterativa, o ciclo (slide 40). Con le parole della slide: “ripetizione esecuzione blocco di istruzioni al verificarsi di una condizione”. Parola chiave while. La condizione è valutata prima dell’esecuzione del blocco.

while (espressione) istruzione

L’istruzione, detta corpo del ciclo, è quasi sempre un blocco fra graffe. Come nell’if, la condizione è vera se vale un numero diverso da zero (Istruzioni condizionali).

A parole: il while è un if che, finito il suo ramo, torna su a ricontrollare la condizione. L’if decide se eseguire una volta; il while decide ogni volta se eseguire ancora.

Nel flowchart della slide la freccia del ramo TRUE dopo il blocco risale sopra il rombo: dopo il corpo si torna sempre a valutare la condizione, e l’unica uscita è il ramo FALSE.

Semantica (slide 41).

  1. Si valuta la condizione.
  2. Se è VERA si esegue il corpo, e infine si valuta di nuovo la condizione (si riparte da 1).
  3. Se è FALSA il corpo non viene eseguito e si prosegue con l’istruzione dopo il ciclo.

Due conseguenze:

Esempio 1, un conto alla rovescia (il corpo gira, poi la condizione diventa falsa):

#include <stdio.h>

int main(void)
{
    int n = 3;

    while (n > 0) {
        printf("%d ", n);
        n--;
    }
    printf("via! n=%d\n", n);
    return 0;
}
giron > 0stampan alla fine del corpo
inizio3
13 > 0 vero3 2
22 > 0 vero2 1
31 > 0 vero1 0
0 > 0 falso, si esce

Output (verificato): 3 2 1 via! n=0. Tre giri, e si esce con n a 0: il primo valore che rende falsa la condizione.

Esempio 2, zero giri (la condizione è falsa al primo controllo):

#include <stdio.h>

int main(void)
{
    int x = 10;
    int giri = 0;

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

10 < 5 è falso subito: il corpo non si esegue mai. Output (verificato): x=10 giri=0. È la differenza con il do-while di Cicli for e do-while, che il corpo lo esegue sempre almeno una volta.

Controesempio, il ciclo che non finisce:

i = 1;
while (i <= 5)
    printf("%d ", i);
    i++;

Senza graffe il corpo è solo il printf (come per l’if, fino al primo ;). i++ è fuori dal ciclo, i resta 1, e il programma stampa 1 1 1 1 ... per sempre. Lo stesso succede con while (i <= 5);: il ; è un corpo vuoto, la condizione non cambia mai e il programma si blocca senza stampare niente.

Istruzioni composte (slide 42). Riassumendo con la slide: if e while sono istruzioni complesse che non esistono nella macchina di Von Neumann, che conosce solo salti; sono componibili anch’esse con altre istruzioni composte (un if dentro un while, un while dentro un altro); sono una caratteristica del linguaggio di alto livello. Il compilatore le traduce in salti condizionati.

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

Entrambi vanno inizializzati prima del ciclo, perché il primo Somma += i legge il valore di Somma. Il valore iniziale è l’elemento neutro dell’operazione: 0 per le somme e i conteggi, 1 per i prodotti.

Esempio 1, accumulatore di prodotto: 5!=1⋅2⋅3⋅4⋅55! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5.

#include <stdio.h>

int main(void)
{
    int i = 1;
    int prodotto = 1;

    while (i <= 5) {
        prodotto *= i;
        i++;
    }
    printf("5! = %d\n", prodotto);
    return 0;
}
giroi <= 5prodottoi
inizio11
11 <= 51·1 = 12
22 <= 51·2 = 23
33 <= 52·3 = 64
44 <= 56·4 = 245
55 <= 524·5 = 1206
6 <= 5 falso

Output (verificato): 5! = 120. Con prodotto = 0 il risultato sarebbe 0 qualunque cosa succeda dopo: lo zero assorbe ogni moltiplicazione.

Esempio 2, contatore e accumulatore insieme, con un if nel corpo: quanti sono i pari fra 1 e 10, e quanto fa la loro somma.

#include <stdio.h>

int main(void)
{
    int i = 1;
    int pari = 0;
    int somma_pari = 0;

    while (i <= 10) {
        if (i % 2 == 0) {
            pari++;
            somma_pari += i;
        }
        i++;
    }
    printf("pari=%d somma=%d\n", pari, somma_pari);
    return 0;
}

Il corpo gira 10 volte, ma pari e somma_pari cambiano solo nei giri con i pari: 2, 4, 6, 8, 10. Output (verificato): pari=5 somma=30, perché 2+4+6+8+10=302 + 4 + 6 + 8 + 10 = 30. i è il contatore dei giri, pari un contatore condizionato.

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. Serve quando non si sa in anticipo quanti dati arriveranno. La sentinella va scelta fuori dai dati validi: per sommare numeri qualsiasi lo 0 va bene (sommarlo non cambierebbe niente), per una lista di voti si può usare 0 o -1.

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

n−m>0  ⇒  MCD(n,m)=MCD(n−m,m)m−n>0  ⇒  MCD(n,m)=MCD(m−n,n)n - m > 0 \;\Rightarrow\; MCD(n, m) = MCD(n - m, m) \qquad m - n > 0 \;\Rightarrow\; MCD(n, m) = MCD(m - n, n)

Perché vale: un numero che divide nn e mm divide anche n−mn - m, e uno che divide n−mn - m e mm divide anche n=(n−m)+mn = (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 (perché MCD(d,d)=dMCD(d, d) = d).

L’idea in un disegno: un rettangolo m×nm \times n da cui si taglia via a ogni giro un quadrato di lato pari al lato corto. Quando resta un quadrato, il suo lato è l’MCD: è il quadrato più grande che piastrella il rettangolo di partenza senza avanzi.

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.

Esempio 1, un ciclo che non conta di uno in uno. Quante volte gira, e con che i esce?

#include <stdio.h>

int main(void)
{
    int i = 1;
    int giri = 0;

    while (i < 20) {
        i = i * 3;
        giri++;
    }
    printf("i=%d giri=%d\n", i, giri);
    return 0;
}
giroi < 20igiri
inizio10
11 < 2031
23 < 2092
39 < 20273
27 < 20 falso

Output (verificato): i=27 giri=3. Si esce con i oltre il limite, non uguale a 20: il ciclo controlla solo prima di ogni giro.

Esempio 2, due variabili che si aggiornano a vicenda (la successione di Fibonacci, che torna nella scala):

#include <stdio.h>

int main(void)
{
    int a = 1;
    int b = 1;

    while (b < 30) {
        int t = a + b;
        a = b;
        b = t;
    }
    printf("a=%d b=%d\n", a, b);
    return 0;
}
girob < 30tab
inizio11
11 < 30212
22 < 30323
33 < 30535
45 < 30858
58 < 3013813
613 < 30211321
721 < 30342134
34 < 30 falso

Output (verificato): a=21 b=34. t serve a non perdere il vecchio b: se si scrivesse a = b; b = a + b;, a sarebbe già sovrascritto e b raddoppierebbe soltanto.

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.

Esempio 1, il massimo di una sequenza terminata da 0. Il massimo si inizializza con il primo dato, non con 0: con soli numeri negativi uno 0 iniziale vincerebbe sempre.

#include <stdio.h>

int main(void)
{
    int dato = 0;
    int max;
    int quanti = 0;
    int letti;

    letti = scanf("%d", &dato);
    max = dato;
    while (letti == 1 && dato != 0) {
        quanti++;
        if (dato > max) {
            max = dato;
        }
        letti = scanf("%d", &dato);
    }
    if (quanti == 0) {
        printf("nessun dato\n");
    } else {
        printf("letti=%d max=%d\n", quanti, max);
    }
    return 0;
}

Con input 4 -2 9 3 0 8:

girocondizionedato usatoquantimaxletto dopo
inizio044
14 != 0414-2
2-2 != 0-2249
39 != 09393
43 != 03490
0 != 0 falso

Output (verificato): letti=4 max=9. Con -5 -3 -8 0 stampa letti=3 max=-3; con 0 subito stampa nessun dato.

Esempio 2, lettura e controllo nella stessa condizione: contare i positivi fino alla sentinella -1.

#include <stdio.h>

int main(void)
{
    int dato;
    int positivi = 0;

    while (scanf("%d", &dato) == 1 && dato != -1) {
        if (dato > 0) {
            positivi++;
        }
    }
    printf("positivi=%d\n", positivi);
    return 0;
}

La condizione legge e poi controlla: && valuta dato != -1 solo se scanf ha letto davvero (cortocircuito). Con input 3 -5 0 7 -1 4 conta 3 e 7: output positivi=2 (verificato). Qui lo 0 è un dato normale, perché la sentinella è -1. È la stessa forma compatta di while ((c = getchar()) != EOF).

2.3Cicli annidati

Il corpo di un while può contenere un altro while. Il ciclo interno riparte da capo a ogni giro di quello esterno, quindi la sua variabile va rimessa al valore iniziale dentro il corpo esterno. Per le figure: il ciclo esterno scorre le righe r, quello interno le colonne c, e dopo il ciclo interno si va a capo. Nelle slide di questo deck non ci sono; servono per i quadrati N×NN \times N della teorica, e si ritrovano con il for in Cicli for e do-while.

Esempio 1, un rettangolo pieno di 3 righe e 4 colonne:

#include <stdio.h>

int main(void)
{
    int r = 0;

    while (r < 3) {
        int c = 0;
        while (c < 4) {
            printf("*");
            c++;
        }
        printf("\n");
        r++;
    }
    return 0;
}

Output (verificato): tre righe di ****. Il printf("*") si esegue 3⋅4=123 \cdot 4 = 12 volte.

Controesempio: se c si dichiara e si azzera fuori dal ciclo esterno (int c = 0; prima del primo while), al secondo giro esterno c vale già 4, il ciclo interno non parte e si stampano solo gli a capo. Output (verificato): **** e poi due righe vuote.

Esempio 2, un quadrato 4×44 \times 4 a pattern. Si decide il carattere di ogni casella dal confronto fra r e c: sulla diagonale r == c, sopra c > r, sotto c < r.

#include <stdio.h>

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

    while (r < N) {
        int c = 0;
        while (c < N) {
            if (c == r)
                printf("\\");
            else if (c > r)
                printf("+");
            else
                printf("-");
            c++;
        }
        printf("\n");
        r++;
    }
    return 0;
}

Output (verificato):

\+++
-\++
--\+
---\

"\\" è la sequenza di escape del carattere \. Come si ragiona su un pattern: si disegna la griglia con gli indici, si cerca la condizione su r e c che separa i caratteri, si controlla su una riga e una colonna di bordo.

2.4Efficienza: contare i giri

(slide 56-57) Due algoritmi corretti per lo stesso problema si confrontano, dice la slide, “in termini di istruzioni eseguite”: 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:

(m,n)(m, n)MCDgiri Euclide (sottrazioni)giri definizione
(1000, 500)5001500
(1000, 2)24992
(15, 3)343
(7, 5)145
(12, 18)6212

La definizione fa sempre min⁡(m,n)\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.

Due esempi per allenarsi a contare senza eseguire:

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. Esempio: “esci quando arriva 0 o l’input finisce” diventa letti == 1 && dato != 0.
  3. Quali variabili servono dal primo giro? Inizializzale prima del ciclo (0 per somme e conteggi, 1 per prodotti, il primo dato per massimo e minimo).
  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 nn volte, ed esce con i=n+1i = n + 1. Con i = 0; while (i < n) sono ancora nn giri, ed esce con i=ni = n.

Tracciare un ciclo all’esame.

  1. Una colonna per variabile, più una per la condizione e una per l’output.
  2. Riga iniziale con i valori prima del ciclo.
  3. Per ogni giro: calcola la condizione con i valori correnti, poi esegui il corpo istruzione per istruzione e scrivi i valori finali.
  4. Con k-- o i++ dentro la condizione: si confronta il valore vecchio, poi la variabile cambia, anche nel test che fa uscire.
  5. All’uscita rileggi le tre risposte: giri, valori finali, output esatto (spazi e a capo compresi).

Algoritmo di Euclide per sottrazioni a mano. Scrivi la coppia, sottrai il minore dal maggiore, riscrivi la coppia; fermati quando sono uguali. Controllo: il risultato divide i due numeri di partenza.

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=0x = 0, y=1y = 1, z=4z = 4:

giroz != yyx
inizio10
14 != 1 vero4 - 0 = 40·3 = 0
4 != 4 falso

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

4.2Somma dei primi 5 interi

(slide 43-44) Si riconosce un problema di accumulatore: un contatore i da 1 a 5 e una somma che raccoglie.

#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;
}
giroi <= nSommai
inizio01
11 <= 50 + 1 = 12
22 <= 51 + 2 = 33
33 <= 53 + 3 = 64
44 <= 56 + 4 = 105
55 <= 510 + 5 = 156
6 <= 5 falso

Output: Somma= 15 (verificato). Il corpo gira 5 volte e si esce con i a 6. Controllo: 1+2+…+n=n(n+1)/2=5⋅6/2=151 + 2 + \ldots + n = n(n+1)/2 = 5 \cdot 6 / 2 = 15.

La slide chiede “Cosa succede se scrivete 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 (“Inizializzazione necessaria?”): 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 46 legge con scanf prima del ciclo (“leggo dato prima ciclo, possibile sentinella”) e in fondo al corpo; il commento “Manca qualcosa?” e il fumetto “Inizializzazione variabile Somma” puntano a int Somma=0. 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:

girocondizionedato usatoSommaletto dopo
inizio04
14 != 0447
27 != 0711-2
3-2 != 0-2910
410 != 010190
0 != 0 falso

Output: Somma= 19 (verificato). 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.

Sulla slide la stringa di formato è "Somma= %d\n ", con uno spazio dopo \n: stampa uno spazio in più all’inizio della riga successiva. Innocuo, ma è il genere di dettaglio che conta quando si chiede l’output esatto.

4.4MCD con Euclide (soluzione 1)

(slide 49-50) Esempi della slide, tracciati per intero:

giro(m,n)(m, n) per MCD(15,3)MCD(15, 3)(m,n)(m, n) per MCD(7,5)MCD(7, 5)
inizio(15, 3)(7, 5)
115 - 3: (12, 3)7 - 5: (2, 5)
212 - 3: (9, 3)5 - 2: (2, 3)
39 - 3: (6, 3)3 - 2: (2, 1)
46 - 3: (3, 3)2 - 1: (1, 1)
fineuguali: MCD = 3uguali: MCD = 1

Quattro giri in entrambi i casi (verificato). 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. Il caso MCD = 1 vuol dire che 7 e 5 sono primi fra loro.

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). Nel corpo del while c’è un if-else: è l’istruzione composta dentro un’altra della slide 42.

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

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

giromnramo
inizio10002
19982m > n
29962m > n
……2
49922m > n
2 != 2 falso

A ogni giro m cala di 2: da 1000 a 2 servono (1000−2)/2=499(1000 - 2) / 2 = 499 giri. Stampa MCD=2 (verificato). 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=0m = 0, n=5n = 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, verificato con input 0 5).

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. Siccome i candidati crescono, l’ultimo trovato è il più grande.

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=15m = 15: (15/4)*4 è 3*4, cioè 12, diverso da 15; (15/5)*5 è 3*5, cioè 15, uguale.

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. Lo scheletro delle slide 51-54 è in pseudo-C (main() senza tipo, scanf(n), printf(mcd)). 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: “divisione tra numeri interi sarà approssimata in generale, evitare usare divisioni se possibile”. 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. Le versioni danno 3 su (15, 3), 1 su (7, 5), 2 su (1000, 2), 6 su (12, 18), come Euclide (verificato).

Tracing della 2b su n=8n = 8, m=12m = 12 (input 8 12): min vale 8.

girocontatorem % contatoren % contatoredivide entrambi?mcd
inizio11
1100sì1
2200sì2
3302no2
4400sì4
5523no4
6602no4
7751no4
8840no4
9 <= 8 falso

Stampa 4 (verificato), dopo 8 giri ed esce con contatore = 9. Euclide sulla stessa coppia fa 2 giri: (8, 12) → (8, 4) → (4, 4).

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: (a) descrivere un algoritmo per moltiplicare mm per nn usando solo moltiplicazioni e divisioni per 2 e somme; (b) scriverlo in C. L’idea della slide: si scrive n=2k1+r1n = 2 k_1 + r_1 (quoziente e resto della divisione per 2), poi k1=2k2+r2k_1 = 2 k_2 + r_2, e così via:

m⋅n=m(2k1+r1)=m(2(2k2+r2)+r1)=…m \cdot n = m (2 k_1 + r_1) = m (2 (2 k_2 + r_2) + r_1) = \ldots

In pratica si dimezza un fattore e si raddoppia l’altro. Un esempio a mano, 13⋅613 \cdot 6:

13 · 6  = 26 · 3          6 è pari: dimezzo 6, raddoppio 13
26 · 3  = 26 · (2·1 + 1)  3 è dispari: 3/2 dà 1 con resto 1
        = 52 · 1 + 26     il resto vale 26 · 1: lo metto da parte in sum
        = 52 + 26 = 78

Quando il fattore da dimezzare è dispari, la divisione intera perde un’unità, e quella parte si recupera sommando l’altro fattore a parte. La slide 73: “la variabile mult accumula le moltiplicazioni per 2, la variabile sum accumula le somme derivanti dai 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=6m = 6, n=13n = 13 (quindi max = 13, min = 6):

giromin > 1min % 2summultminmult * min + sum
inizio013678
16 > 10026378
23 > 110 + 26 = 2652178
1 > 1 falso

Stampa n=13, m=6, mult=78 (verificato). L’ultima colonna è sempre 78=6⋅1378 = 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 (circa log⁡2\log_2 del minore).

Perché l’invariante regge in un giro con min dispari, min=2k+1min = 2k + 1: prima vale mult⋅(2k+1)+summult \cdot (2k+1) + sum; dopo il corpo sum vale sum+multsum + mult, mult vale 2⋅mult2 \cdot mult, min vale kk, e 2⋅mult⋅k+sum+mult=mult(2k+1)+sum2 \cdot mult \cdot k + sum + mult = mult (2k + 1) + sum. Con min pari il resto non c’è e sum non cambia.

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

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 NN 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. Sulle slide 75-76 il prof disegna la scala da 1 a NN con i salti da uno, da uno o due, da uno due o tre gradini.

Casi piccoli (slide 77-80):

Controllo di S(4)=7S(4) = 7 elencandoli: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Sono 7.

Il ragionamento di N=4N = 4 vale per ogni N>3N > 3 (slide 91-92, dove la slide prima mostra la successione con “S(n) = ???” e poi la risposta):

S(n)=S(n−1)+S(n−2)+S(n−3)S(n) = S(n-1) + S(n-2) + S(n-3)
N    1  2  3  4   5   6   7   8    9    10
S    1  2  4  7  13  24  44  81  149   274

Ogni valore è la somma dei tre prima: S(7)=24+13+7=44S(7) = 24 + 13 + 7 = 44.

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

  1. leggi NN;
  2. inizializza le soluzioni note, per NN = 0, 1, 2;
  3. tienile in tre variabili, che contengono le soluzioni per K−3K-3, K−2K-2 e K−1K-1;
  4. in un ciclo fai crescere KK da 3 fino a NN: la soluzione per KK è 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)S(i-1), i modi se il primo passo è da 1; PassiTipo2 contiene S(i−2)S(i-2); PassiTipo3 contiene S(i−3)S(i-3). Nei commenti della slide: “Soluzione se inizio con un passo da 3” e così via. Il fumetto della slide 89: “per calcolare la soluzione per N partiremo a calcolare le soluzioni da i=3, i=4, fino a i=N”. Il commento alterfor(i=3; i<N+1; i++) anticipa che lo stesso ciclo si scriverà con un for (Cicli for e do-while).

Tracing con N=5N = 5:

giroii < N+1TotaleModiPassiTipo3PassiTipo2PassiTipo1
inizio30112
13 → 43 < 61+1+2 = 4124
24 → 54 < 61+2+4 = 7247
35 → 65 < 62+4+7 = 134713
66 < 6 falso

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

Incoerenza su N=0N = 0. L’inizializzazione PassiTipo3 = 1 vuol dire S(0)=1S(0) = 1: per N=3N = 3 il caso “primo passo da 3” arriva in cima, e conta un modo. Ma per N≤2N \leq 2 il programma stampa NN, quindi per N=0N = 0 stampa 0 (verificato). 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 (“there’s 1 way to do it: not moving”).

Overflow. S(n)S(n) cresce in fretta: S(36)=2 082 876 103S(36) = 2\,082\,876\,103 sta ancora in un int a 32 bit (massimo 2 147 483 647), S(37)=3 831 006 429S(37) = 3\,831\,006\,429 no. Il programma con N=37N = 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)S(n) fra Fibonacci (F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)) e 2n2^n, e aggiungono n2n^2 e n!n!. Con n=30n = 30:

n2n^2F(30)F(30)S(30)S(30)2302^{30}30!30!
900832 04053 798 0801 073 741 824circa 2,65⋅10322{,}65 \cdot 10^{32}

n2n^2 è polinomiale, le tre successioni in mezzo sono esponenziali (ogni passo moltiplica per circa 1,62, 1,84 e 2), n!n! cresce ancora più in fretta. In scala logaritmica un’esponenziale è una retta, e n2n^2 una curva che si appiattisce: è quello che si vede nel grafico. È il primo assaggio di complessità: un algoritmo che fa S(n)S(n) operazioni è inutilizzabile già per nn piccoli.

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

  1. Ricorsiva: una funzione che per n>2n > 2 restituisce countWays(n-1) + countWays(n-2) + countWays(n-3), con i casi base n<0n < 0 → 0, n=0n = 0 → 1, n=1n = 1 → 1, n=2n = 2 → 2. È la ricorrenza scritta pari pari, ma ricalcola gli stessi valori moltissime volte: per n=10n = 10 fa 289 chiamate, per n=30n = 30 circa 57 milioni (contate con uno script: 56 843 233).
  2. Programmazione dinamica: un array dp di n+1n + 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)O(N) e memoria O(N)O(N).

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

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Ciclo while ed esempi (esercizi).

6Errori tipici

7Domande