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).
- Si valuta la condizione.
- Se è VERA si esegue il corpo, e infine si valuta di nuovo la condizione (si riparte da 1).
- Se è FALSA il corpo non viene eseguito 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.
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;
}
| giro | n > 0 | stampa | n alla fine del corpo |
|---|---|---|---|
| inizio | 3 | ||
| 1 | 3 > 0 vero | 3 | 2 |
| 2 | 2 > 0 vero | 2 | 1 |
| 3 | 1 > 0 vero | 1 | 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:
- contatore: conta i giri o gli elementi che soddisfano una condizione,
i++opari++; - accumulatore: raccoglie un risultato giro dopo giro,
Somma += ioprodotto *= i.
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: .
#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;
}
| giro | i <= 5 | prodotto | i |
|---|---|---|---|
| inizio | 1 | 1 | |
| 1 | 1 <= 5 | 1·1 = 1 | 2 |
| 2 | 2 <= 5 | 1·2 = 2 | 3 |
| 3 | 3 <= 5 | 2·3 = 6 | 4 |
| 4 | 4 <= 5 | 6·4 = 24 | 5 |
| 5 | 5 <= 5 | 24·5 = 120 | 6 |
| 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é . 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 e , è il più grande intero che li divide entrambi. L’algoritmo di Euclide si basa sul fatto che (slide 48):
Perché vale: un numero che divide e divide anche , e uno che divide e divide anche . 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é ).
L’idea in un disegno: un rettangolo 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;
}
| giro | i < 20 | i | giri |
|---|---|---|---|
| inizio | 1 | 0 | |
| 1 | 1 < 20 | 3 | 1 |
| 2 | 3 < 20 | 9 | 2 |
| 3 | 9 < 20 | 27 | 3 |
| 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;
}
| giro | b < 30 | t | a | b |
|---|---|---|---|---|
| inizio | 1 | 1 | ||
| 1 | 1 < 30 | 2 | 1 | 2 |
| 2 | 2 < 30 | 3 | 2 | 3 |
| 3 | 3 < 30 | 5 | 3 | 5 |
| 4 | 5 < 30 | 8 | 5 | 8 |
| 5 | 8 < 30 | 13 | 8 | 13 |
| 6 | 13 < 30 | 21 | 13 | 21 |
| 7 | 21 < 30 | 34 | 21 | 34 |
| 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:
| giro | condizione | dato usato | quanti | max | letto dopo |
|---|---|---|---|---|---|
| inizio | 0 | 4 | 4 | ||
| 1 | 4 != 0 | 4 | 1 | 4 | -2 |
| 2 | -2 != 0 | -2 | 2 | 4 | 9 |
| 3 | 9 != 0 | 9 | 3 | 9 | 3 |
| 4 | 3 != 0 | 3 | 4 | 9 | 0 |
| 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 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 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 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:
| MCD | giri Euclide (sottrazioni) | giri definizione | |
|---|---|---|---|
| (1000, 500) | 500 | 1 | 500 |
| (1000, 2) | 2 | 499 | 2 |
| (15, 3) | 3 | 4 | 3 |
| (7, 5) | 1 | 4 | 5 |
| (12, 18) | 6 | 2 | 12 |
La definizione fa sempre 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:
i = 0; while (i < 10) i += 3;gira peri= 0, 3, 6, 9: 4 giri, si esce coni= 12.i = 1; while (i < 100) i *= 2;gira peri= 1, 2, 4, 8, 16, 32, 64: 7 giri, si esce coni= 128. Raddoppiare fa crescereiin fretta: i giri sono circa , contro i 99 di uni++.
3Metodo
Scrivere un ciclo.
- Cosa si ripete? Diventa il corpo.
- 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” diventaletti == 1 && dato != 0. - 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).
- Cosa, nel corpo, fa avanzare verso l’uscita? Se niente cambia, il ciclo è infinito.
- 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 volte, ed esce con . Con i = 0; while (i < n) sono ancora giri, ed esce con .
Tracciare un ciclo all’esame.
- Una colonna per variabile, più una per la condizione e una per l’output.
- Riga iniziale con i valori prima del ciclo.
- Per ogni giro: calcola la condizione con i valori correnti, poi esegui il corpo istruzione per istruzione e scrivi i valori finali.
- Con
k--oi++dentro la condizione: si confronta il valore vecchio, poi la variabile cambia, anche nel test che fa uscire. - 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 , , :
| giro | z != y | y | x |
|---|---|---|---|
| inizio | 1 | 0 | |
| 1 | 4 != 1 vero | 4 - 0 = 4 | 0·3 = 0 |
| 4 != 4 falso |
Un giro, si esce con x=0 y=4 z=4 (verificato). Ma se non è zero il ciclo non finisce mai: y = z - x è uguale a z solo quando , e x = x*3 non porta mai a zero un numero diverso da zero. Con : 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;
}
| giro | i <= n | Somma | i |
|---|---|---|---|
| inizio | 0 | 1 | |
| 1 | 1 <= 5 | 0 + 1 = 1 | 2 |
| 2 | 2 <= 5 | 1 + 2 = 3 | 3 |
| 3 | 3 <= 5 | 3 + 3 = 6 | 4 |
| 4 | 4 <= 5 | 6 + 4 = 10 | 5 |
| 5 | 5 <= 5 | 10 + 5 = 15 | 6 |
| 6 <= 5 falso |
Output: Somma= 15 (verificato). Il corpo gira 5 volte e si esce con i a 6. Controllo: .
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:
| giro | condizione | dato usato | Somma | letto dopo |
|---|---|---|---|---|
| inizio | 0 | 4 | ||
| 1 | 4 != 0 | 4 | 4 | 7 |
| 2 | 7 != 0 | 7 | 11 | -2 |
| 3 | -2 != 0 | -2 | 9 | 10 |
| 4 | 10 != 0 | 10 | 19 | 0 |
| 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 | per | per |
|---|---|---|
| inizio | (15, 3) | (7, 5) |
| 1 | 15 - 3: (12, 3) | 7 - 5: (2, 5) |
| 2 | 12 - 3: (9, 3) | 5 - 2: (2, 3) |
| 3 | 9 - 3: (6, 3) | 3 - 2: (2, 1) |
| 4 | 6 - 3: (3, 3) | 2 - 1: (1, 1) |
| fine | uguali: MCD = 3 | uguali: 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 : MCD=m; darebbe lo stesso risultato.
Tracing su (1000, 2), la coppia della slide 57:
| giro | m | n | ramo |
|---|---|---|---|
| inizio | 1000 | 2 | |
| 1 | 998 | 2 | m > n |
| 2 | 996 | 2 | m > n |
| … | … | 2 | |
| 499 | 2 | 2 | m > n |
| 2 != 2 falso |
A ogni giro m cala di 2: da 1000 a 2 servono 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 , 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 : (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 , (input 8 12): min vale 8.
| giro | contatore | m % contatore | n % contatore | divide entrambi? | mcd |
|---|---|---|---|---|---|
| inizio | 1 | 1 | |||
| 1 | 1 | 0 | 0 | sì | 1 |
| 2 | 2 | 0 | 0 | sì | 2 |
| 3 | 3 | 0 | 2 | no | 2 |
| 4 | 4 | 0 | 0 | sì | 4 |
| 5 | 5 | 2 | 3 | no | 4 |
| 6 | 6 | 0 | 2 | no | 4 |
| 7 | 7 | 5 | 1 | no | 4 |
| 8 | 8 | 4 | 0 | no | 4 |
| 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 per usando solo moltiplicazioni e divisioni per 2 e somme; (b) scriverlo in C. L’idea della slide: si scrive (quoziente e resto della divisione per 2), poi , e così via:
In pratica si dimezza un fattore e si raddoppia l’altro. Un esempio a mano, :
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 , (quindi max = 13, min = 6):
| giro | min > 1 | min % 2 | sum | mult | min | mult * min + sum |
|---|---|---|---|---|---|---|
| inizio | 0 | 13 | 6 | 78 | ||
| 1 | 6 > 1 | 0 | 0 | 26 | 3 | 78 |
| 2 | 3 > 1 | 1 | 0 + 26 = 26 | 52 | 1 | 78 |
| 1 > 1 falso |
Stampa n=13, m=6, mult=78 (verificato). L’ultima colonna è sempre : è 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 del minore).
Perché l’invariante regge in un giro con min dispari, : prima vale ; dopo il corpo sum vale , mult vale , min vale , e . Con min pari il resto non c’è e sum non cambia.
Errori del programma della slide (verificati): funziona solo con fattori positivi.
- Se un fattore è 0,
minvale 0, il ciclo non parte e stampamax: dà 5. - Se un fattore è negativo,
minè negativo, il ciclo non parte: 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 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 con i salti da uno, da uno o due, da uno due o tre gradini.
Casi piccoli (slide 77-80):
- : solo
1. . - :
1+1,2. . - :
1+1+1,1+2,2+1,3. . - : il primo passo è da 1, da 2 o da 3. Dopo un passo da 1 restano 3 gradini, che si salgono in modi; dopo uno da 2 ne restano 2; dopo uno da 3 ne resta 1. Quindi .
Controllo di 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 vale per ogni (slide 91-92, dove la slide prima mostra la successione con “S(n) = ???” e poi la risposta):
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: .
Pseudocodice (slide 81-84). Non serve ricordare tutta la successione, bastano gli ultimi tre valori:
- leggi ;
- inizializza le soluzioni note, per = 0, 1, 2;
- tienile in tre variabili, che contengono le soluzioni per , e ;
- in un ciclo fai crescere da 3 fino a : la soluzione per è 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 , i modi se il primo passo è da 1; PassiTipo2 contiene ; PassiTipo3 contiene . 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 :
| giro | i | i < N+1 | TotaleModi | PassiTipo3 | PassiTipo2 | PassiTipo1 |
|---|---|---|---|---|---|---|
| inizio | 3 | 0 | 1 | 1 | 2 | |
| 1 | 3 → 4 | 3 < 6 | 1+1+2 = 4 | 1 | 2 | 4 |
| 2 | 4 → 5 | 4 < 6 | 1+2+4 = 7 | 2 | 4 | 7 |
| 3 | 5 → 6 | 5 < 6 | 2+4+7 = 13 | 4 | 7 | 13 |
| 6 | 6 < 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 . L’inizializzazione PassiTipo3 = 1 vuol dire : per il caso “primo passo da 3” arriva in cima, e conta un modo. Ma per il programma stampa , quindi per 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. cresce in fretta: sta ancora in un int a 32 bit (massimo 2 147 483 647), no. Il programma con 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 fra Fibonacci () e , e aggiungono e . Con :
| 900 | 832 040 | 53 798 080 | 1 073 741 824 | circa |
è polinomiale, le tre successioni in mezzo sono esponenziali (ogni passo moltiplica per circa 1,62, 1,84 e 2), cresce ancora più in fretta. In scala logaritmica un’esponenziale è una retta, e una curva che si appiattisce: è quello che si vede nel grafico. È il primo assaggio di complessità: un algoritmo che fa operazioni è inutilizzabile già per piccoli.
Le due soluzioni di ChatGPT (slide 96-97), in Python:
- Ricorsiva: una funzione che per restituisce
countWays(n-1) + countWays(n-2) + countWays(n-3), con i casi base → 0, → 1, → 1, → 2. È la ricorrenza scritta pari pari, ma ricalcola gli stessi valori moltissime volte: per fa 289 chiamate, per circa 57 milioni (contate con uno script: 56 843 233). - Programmazione dinamica: un array
dpdi posti riempito da 3 in su, condp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Ogni valore si calcola una volta: tempo e memoria .
La soluzione del prof è la dinamica senza array: tiene solo gli ultimi tre valori, quindi tempo 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
- Dimenticare di inizializzare accumulatori e contatori (
int Somma;). - Inizializzare un prodotto a 0 (il risultato resta 0) o un massimo a 0 (sbaglia con soli negativi).
- Dimenticare l’aggiornamento nel corpo (
i++): ciclo infinito. - Corpo di più istruzioni senza graffe: solo la prima è nel ciclo, e spesso è proprio l’aggiornamento a restare fuori.
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
scanfin 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 < nei <= nfanno un numero di giri diverso. Controlla sempre il primo e l’ultimo giro. - Credere che si esca con la variabile uguale al limite: con
i < 20ei *= 3si esce con 27. - Con
k--nella condizione, dimenticare che anche il test che fa uscire decrementa. - 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 faSomma += 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
nom? -
Cosa succede all’algoritmo di Euclide per sottrazioni se un input è 0?
-
Come si controlla se
cdividemsenza 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 girawhile (k--)e quanto valekall’uscita? -
Quante volte si esegue il corpo di
i = 0; while (i < 10) i += 3;e quanto valeialla fine? -
A che valore si inizializzano un accumulatore di somma, uno di prodotto e la variabile del massimo, e perché?
-
In due
whileannidati, perché la variabile del ciclo interno va azzerata dentro il corpo di quello esterno? -
Perché
while (scanf("%d", &dato) == 1 && dato != -1)non usa mai undatonon letto?