Lezione 08 · Programmi, algoritmi ed esecutori; diagrammi di flusso¶

Prima di scrivere un programma bisogna sapere come si risolve il problema. Questo "come" è l'algoritmo. In questa lezione impari a descriverlo in modo preciso, anche con un disegno: il diagramma di flusso. È lo stesso lavoro che fai all'esame quando, prima di scrivere il codice, ragioni sui passi da fare.

Problemi e istanze¶

Uno degli scopi principali dell'informatica è risolvere problemi con i calcolatori.

Un problema è una classe di domande dello stesso tipo, a cui si risponde con lo stesso metodo. Ogni domanda specifica della classe è un'istanza del problema.

• Problema: "qual è la somma Z di due numeri X e Y?"
• Istanza: "qual è la somma di 4 e 7?"

X e Y sono le variabili di ingresso (dati di input): ogni combinazione dei loro valori genera un'istanza diversa. Z è la variabile di uscita (dato di output): il suo valore dipende dall'istanza.

Non tutti i problemi sono uguali¶

Quindi la descrizione di un problema di solito non dice come risolverlo, a volte è imprecisa o ambigua, e per alcuni problemi una soluzione non esiste: si chiamano problemi non calcolabili. La teoria della calcolabilità studia quali problemi si possono risolvere con un procedimento automatico.

Calcolabile ma non trattabile: la Torre di Hanoi¶

Ci sono tre paletti e n dischi di grandezza decrescente. Bisogna spostare tutti i dischi da un paletto a un altro, un disco alla volta, senza mai mettere un disco sopra uno più piccolo.

Il problema ha una soluzione, ma richiede almeno 2ⁿ − 1 mosse. Con n = 64 dischi e una mossa al secondo servono 2⁶⁴ − 1 secondi: circa 585 miliardi di anni. Il problema è calcolabile ma non trattabile: la soluzione esiste, ma richiede un tempo inaccettabile.

n = int(input('Numero di dischi: '))
mosse = 2 ** n - 1
anni = mosse / (365.25 * 24 * 3600)   # una mossa al secondo
print('Mosse necessarie:', mosse)
print(f'Tempo con una mossa al secondo: {anni:.1f} anni')

Prova con 10, 30 e 64.

Algoritmo, esecutore, programma¶

Un algoritmo è una sequenza finita di passi che porta alla realizzazione di un compito: un insieme finito di istruzioni che, eseguite in un ordine stabilito, portano alla soluzione di un problema. Gli aspetti importanti sono:

• i passi sono in numero finito;
• vanno eseguiti in sequenza, in un ordine preciso;
• elaborano i dati di input;
• producono i dati di output, cioè la soluzione.

L'esecutore è chi esegue l'algoritmo. Un algoritmo dipende sia dal compito sia dall'esecutore: l'esecutore riesce nel suo compito se e solo se comprende ed esegue tutti i passi.

flowchart LR
    I[/"Input"/] --> E["Esecutore + Algoritmo"]
    E --> O[/"Output"/]

Un programma è un algoritmo scritto in un linguaggio di programmazione, cioè un linguaggio comprensibile all'esecutore. Il linguaggio descrive, senza ambiguità, tutte e sole le operazioni che l'esecutore sa fare.

Un calcolatore è un esecutore particolare: non ha capacità decisionale, compie solo le azioni previste. Il suo processore è un automa, una macchina che esegue algoritmi: a partire dai dati iniziali produce in uscita i risultati.

Descrivere un algoritmo¶

Per risolvere un problema:

1. si capisce se il problema ammette soluzioni;
2. se sì, si trova un metodo risolutivo (l'algoritmo);
3. si esprime il metodo in un linguaggio comprensibile all'esecutore.

In un algoritmo ci sono due tipi di frasi:

• le istruzioni, che descrivono le operazioni da fare;
• le strutture di controllo, che dicono in quale ordine eseguirle.

Istruzioni elementari e non elementari¶

• Elementari: l'esecutore le capisce e le sa eseguire direttamente (es. somma = a + b).
• Non elementari: l'esecutore non le conosce, quindi bisogna fornirgli anche la loro specifica, che le scompone in istruzioni elementari. Permettono di scrivere l'algoritmo in modo più compatto (es. "calcola m = max(a, b)", che poi va spiegata con un confronto).

Le tre strutture di controllo¶

Caratteristiche delle operazioni¶

Ogni operazione di un algoritmo deve avere quattro caratteristiche:

• finitezza: termina in un tempo finito;
• descrivibilità: produce effetti descrivibili, ad esempio confrontando lo stato degli oggetti prima e dopo;
• riproducibilità: nelle stesse condizioni iniziali produce sempre lo stesso effetto;
• comprensibilità: è espressa in una forma che l'esecutore capisce.

Sequenza statica e sequenze dinamiche¶

Quando l'esecutore lavora, compie una serie di azioni una dopo l'altra: un processo sequenziale. L'elenco delle istruzioni effettivamente eseguite, nell'ordine di esecuzione, si chiama sequenza di esecuzione (o sequenza dinamica).

La sequenza statica è invece l'ordine in cui le istruzioni sono scritte nell'algoritmo.

• Una sola sequenza statica può dare origine a molte sequenze dinamiche, a seconda dei dati.
• Esempio: nelle equazioni di 2° grado, se il discriminante è negativo il programma segue una strada (nessuna radice reale), altrimenti un'altra (calcolo delle radici).
• Se l'algoritmo contiene un ciclo, il numero di sequenze dinamiche può essere infinito. Nel solitario del carcerato si possono eliminare le carte al primo tentativo, al secondo, dopo n tentativi… oppure mai: il processo non termina.

Studiare quante e quali sequenze dinamiche ci sono serve a confrontare soluzioni diverse (quale è più veloce?) e a capire se un algoritmo termina.

I diagrammi di flusso¶

Un diagramma di flusso (flow chart) rappresenta un algoritmo con un disegno. Ogni azione è un blocco; le frecce indicano l'ordine di esecuzione. Ogni blocco ha un ramo in ingresso e uno o più rami in uscita.

Esempio: somma di due numeri¶

flowchart TD
    S(["Inizio"]) --> L[/"Leggi a, b"/]
    L --> C["somma = a + b"]
    C --> P[/"Stampa somma"/]
    P --> F(["Fine"])

• Il parallelogramma Leggi a, b legge due numeri e li salva nelle variabili di ingresso a e b.
• Il rettangolo fa il calcolo e assegna il risultato alla variabile di uscita somma.
• Il parallelogramma Stampa somma mostra il risultato.

a = float(input('a = '))
b = float(input('b = '))
somma = a + b
print('somma =', somma)

Esempio: massimo tra due numeri¶

Prima versione, con un'istruzione non elementare: "calcola m = max(a, b)". Se l'esecutore non sa cos'è il massimo, bisogna scomporla con un rombo:

flowchart TD
    S(["Inizio"]) --> L[/"Leggi a, b"/]
    L --> D{"a > b ?"}
    D -- SI --> A["m = a"]
    D -- NO --> B["m = b"]
    A --> P[/"Stampa m"/]
    B --> P
    P --> F(["Fine"])

a = float(input('a = '))
b = float(input('b = '))
if a > b:
    m = a
else:
    m = b
print('Il massimo è', m)

Esempio: massimo tra tre numeri¶

flowchart TD
    S(["Inizio"]) --> L[/"Leggi a, b, c"/]
    L --> D1{"a > b ?"}
    D1 -- SI --> D2{"a > c ?"}
    D1 -- NO --> D3{"b > c ?"}
    D2 -- SI --> PA[/"Stampa a"/]
    D2 -- NO --> PC1[/"Stampa c"/]
    D3 -- SI --> PB[/"Stampa b"/]
    D3 -- NO --> PC2[/"Stampa c"/]
    PA --> F(["Fine"])
    PC1 --> F
    PB --> F
    PC2 --> F

Ci sono 4 sequenze dinamiche diverse (una per ogni blocco "Stampa"), ma la sequenza statica è una sola. In Python i rombi diventano if annidati:

a = float(input('a = '))
b = float(input('b = '))
c = float(input('c = '))
if a > b:
    if a > c:
        print('Il massimo è', a)
    else:
        print('Il massimo è', c)
else:
    if b > c:
        print('Il massimo è', b)
    else:
        print('Il massimo è', c)

I cicli nei diagrammi di flusso¶

Spesso alcune istruzioni vanno ripetute. Nel diagramma un ciclo è una freccia che torna indietro.

Ciclo while¶

Gli elementi del ciclo while sono:

• l'inizializzazione delle variabili usate nella condizione: la prima volta che si controlla la condizione, deve avere un valore sensato;
• la condizione del ciclo, un test che decide se entrare (o restare) nel ciclo;
• il corpo del ciclo, le istruzioni da ripetere. Nel corpo ci deve essere un'istruzione di modifica che, prima o poi, rende falsa la condizione. Altrimenti il ciclo è infinito.

Il test si fa prima del corpo: se la condizione è subito falsa, il corpo non viene mai eseguito.

Ciclo do-while¶

Nel ciclo do-while (o repeat-until) il test si fa dopo il corpo: il corpo viene eseguito almeno una volta.

Esempio: stampa dei numeri da 1 a 10¶

Si usa una variabile contatore i che parte da 1, si stampa e si incrementa dopo ogni stampa, e ci si ferma quando supera 10.

Soluzione con while: il test è in alto, prima della stampa.

flowchart TD
    S(["Inizio"]) --> I["n = 10<br>i = 1"]
    I --> D{"i ≤ n ?"}
    D -- SI --> P[/"Stampa i"/]
    P --> INC["i = i + 1"]
    INC --> D
    D -- NO --> F(["Fine"])

Soluzione con do-while: il test è in basso, dopo la stampa.

flowchart TD
    S(["Inizio"]) --> I["n = 10<br>i = 1"]
    I --> P[/"Stampa i"/]
    P --> INC["i = i + 1"]
    INC --> D{"i ≤ n ?"}
    D -- SI --> P
    D -- NO --> F(["Fine"])

n = 10

# Versione while: il test è prima del corpo
i = 1
while i <= n:
    print(i, end=' ')
    i = i + 1
print()

# Versione do-while: il test è dopo il corpo
i = 1
while True:
    print(i, end=' ')
    i = i + 1
    if not (i <= n):
        break
print()

Esempio: stampa dei numeri pari fino a −1¶

Leggere un numero; se è −1 terminare; se è pari stamparlo; poi (pari o dispari) tornare a leggere.

flowchart TD
    S(["Inizio"]) --> L[/"Leggi N"/]
    L --> D1{"N = -1 ?"}
    D1 -- SI --> F(["Fine"])
    D1 -- NO --> D2{"N è pari ?"}
    D2 -- SI --> P[/"Stampa N"/]
    D2 -- NO --> L
    P --> L

N = int(input('Numero (-1 per finire): '))
while N != -1:
    if N % 2 == 0:
        print(N, 'è pari')
    N = int(input('Numero (-1 per finire): '))
print('Fine')

Esempio: massimo tra n numeri¶

Si parte con max = −∞ (un valore più piccolo di qualunque numero) e un indice i = 1. Si confronta ogni aᵢ con max e, se è più grande, si aggiorna max.

flowchart TD
    S(["Inizio"]) --> L[/"Leggi a1, ..., an"/]
    L --> I["max = -∞<br>i = 1"]
    I --> D1{"ai > max ?"}
    D1 -- SI --> A["max = ai"]
    D1 -- NO --> INC["i = i + 1"]
    A --> INC
    INC --> D2{"i > n ?"}
    D2 -- NO --> D1
    D2 -- SI --> P[/"Stampa max"/]
    P --> F(["Fine"])

numeri = [12, 45, 7, 45, 30, 2]   # i valori a1, ..., an
n = len(numeri)

massimo = float('-inf')   # meno infinito
i = 0                     # in Python le posizioni partono da 0
while i < n:
    if numeri[i] > massimo:
        massimo = numeri[i]
    i = i + 1
print('Il massimo è', massimo)

Esempio: sconto sul prezzo¶

Dati i prezzi di 3 prodotti, se il totale è minore di 500 € si applica uno sconto del 15%, altrimenti del 20%. Si stampa il prezzo finale.

flowchart TD
    S(["Inizio"]) --> I["sconto = 0.15"]
    I --> L[/"Leggi p1, p2, p3"/]
    L --> T["totale = p1 + p2 + p3"]
    T --> D{"totale ≥ 500 ?"}
    D -- SI --> S2["sconto = 0.2"]
    D -- NO --> C["totale = totale * (1 - sconto)"]
    S2 --> C
    C --> P[/"Stampa totale"/]
    P --> F(["Fine"])

Il trucco: si parte dallo sconto "normale" (15%) e lo si cambia solo se serve.

sconto = 0.15
p1 = float(input('Prezzo 1: '))
p2 = float(input('Prezzo 2: '))
p3 = float(input('Prezzo 3: '))
totale = p1 + p2 + p3
if totale >= 500:
    sconto = 0.2
totale = totale * (1 - sconto)
print(f'Prezzo finale: {totale:.2f} euro')

Esempio: calcolo della media¶

Leggere valori non negativi finché l'utente inserisce 0; poi calcolare e stampare la media. Servono un contatore n e un accumulatore tot.

flowchart TD
    S(["Inizio"]) --> I["n = 0<br>tot = 0"]
    I --> L[/"Leggi x"/]
    L --> D{"x = 0 ?"}
    D -- NO --> A["tot = tot + x<br>n = n + 1"]
    A --> L
    D -- SI --> M["m = tot / n"]
    M --> P[/"Stampa m"/]
    P --> F(["Fine"])

n = 0
tot = 0
x = float(input('Valore (0 per finire): '))
while x != 0:
    tot = tot + x
    n = n + 1
    x = float(input('Valore (0 per finire): '))
if n > 0:
    m = tot / n
    print('Media:', m)
else:
    print('Nessun valore inserito')

Nota che la lettura compare due volte in Python: una prima del ciclo (inizializzazione) e una alla fine del corpo (modifica). Nel diagramma invece la freccia torna sullo stesso blocco "Leggi x".

Esempio: prodotto tramite somme¶

Calcolare x · y (con x ≥ 0 e y ≥ 0) usando solo somme: si somma x a sé stesso y volte.

flowchart TD
    S(["Inizio"]) --> L[/"Leggi x, y"/]
    L --> I["p = 0"]
    I --> D1{"x = 0 ?"}
    D1 -- SI --> P[/"Stampa p"/]
    D1 -- NO --> D2{"y = 0 ?"}
    D2 -- SI --> P
    D2 -- NO --> A["p = p + x<br>y = y - 1"]
    A --> D2
    P --> F(["Fine"])

x = int(input('x (>= 0): '))
y = int(input('y (>= 0): '))
p = 0
if x != 0:
    while y != 0:
        p = p + x
        y = y - 1
print('Prodotto:', p)

Errori frequenti negli esercizi¶

Esercizi¶

Esercizio 1 · Tipo di triangolo. Date le lunghezze a, b, c dei lati di un triangolo, stampa se è equilatero (tre lati uguali), isoscele (due lati uguali) o scaleno (tutti diversi). Disegna prima il diagramma di flusso, poi traducilo in Python.

# Scrivi qui la tua soluzione

flowchart TD
    S(["Inizio"]) --> L[/"Leggi a, b, c"/]
    L --> D1{"a = b ?"}
    D1 -- SI --> D2{"b = c ?"}
    D2 -- SI --> E[/"Stampa equilatero"/]
    D2 -- NO --> I1[/"Stampa isoscele"/]
    D1 -- NO --> D3{"a = c ?"}
    D3 -- SI --> I2[/"Stampa isoscele"/]
    D3 -- NO --> D4{"b = c ?"}
    D4 -- SI --> I3[/"Stampa isoscele"/]
    D4 -- NO --> SC[/"Stampa scaleno"/]
    E --> F(["Fine"])
    I1 --> F
    I2 --> F
    I3 --> F
    SC --> F

a = float(input('a = '))
b = float(input('b = '))
c = float(input('c = '))
if a == b:
    if b == c:
        print('equilatero')
    else:
        print('isoscele')
elif a == c:
    print('isoscele')
elif b == c:
    print('isoscele')
else:
    print('scaleno')

Esercizio 2 · Massimo tra dieci numeri. Leggi 10 numeri, uno alla volta, e stampa il più grande. Suggerimento: usa un contatore i da 1 a 10. Al primo numero (i = 1) il massimo è proprio quel numero; poi aggiorni il massimo solo se il nuovo numero è più grande.

# Scrivi qui la tua soluzione (per provarla puoi mettere n = 3)

flowchart TD
    S(["Inizio"]) --> I["n = 10<br>i = 1"]
    I --> D1{"i ≤ n ?"}
    D1 -- SI --> L[/"Leggi x"/]
    L --> D2{"i = 1 OR x > max ?"}
    D2 -- SI --> A["max = x"]
    D2 -- NO --> INC["i = i + 1"]
    A --> INC
    INC --> D1
    D1 -- NO --> P[/"Stampa max"/]
    P --> F(["Fine"])

n = 10
i = 1
while i <= n:
    x = float(input('Numero: '))
    if i == 1 or x > massimo:
        massimo = x
    i = i + 1
print('Il massimo è', massimo)

Esercizio 3 · Somma dei pari con sentinella. Leggi numeri interi finché l'utente inserisce −1. Alla fine stampa quanti numeri pari sono stati inseriti e la loro somma. Disegna il diagramma e traducilo in Python. Con l'input 4, 7, 10, 3, −1 il programma deve stampare 2 pari, somma 14.

# Scrivi qui la tua soluzione

flowchart TD
    S(["Inizio"]) --> I["conta = 0<br>somma = 0"]
    I --> L[/"Leggi N"/]
    L --> D1{"N = -1 ?"}
    D1 -- NO --> D2{"N è pari ?"}
    D2 -- SI --> A["conta = conta + 1<br>somma = somma + N"]
    D2 -- NO --> L
    A --> L
    D1 -- SI --> P[/"Stampa conta, somma"/]
    P --> F(["Fine"])

conta = 0
somma = 0
N = int(input('Numero (-1 per finire): '))
while N != -1:
    if N % 2 == 0:
        conta = conta + 1
        somma = somma + N
    N = int(input('Numero (-1 per finire): '))
print('Numeri pari:', conta)
print('Somma dei pari:', somma)

Verifica¶