Gli algoritmi

Introduzione agli algoritmi

Quando deleghiamo un compito a un esecutore (persona o macchina), abbiamo bisogno di una sequenza di istruzioni
chiara, realizzabile e finita. Nel quotidiano sembriamo non averne bisogno (diciamo: “vado al ristorante e mangio una pastasciutta”),
ma per un esecutore non umano, ogni passaggio va reso esplicito: dimensione della pentola, riempimento, ebollizione, sale, tempi, scolatura e condimento.

Partiremo da esempi fenomenologici semplici (media dei voti, area del cerchio, sconti e IVA) e poi introdurremo gradualmente
le strutture di controllo (sequenza, selezione, iterazione) con i relativi diagrammi di flusso.

Esempio guida: calcolare la media dei voti

Obiettivo: leggere una sequenza di voti e calcolarne la media. A ogni voto letto aggiorniamo il totale e il conteggio; quando
i voti sono finiti, eseguiamo la divisione finale.

Simboli del diagramma di flusso

• Rettangolo: istruzione/operazione.
• Parallelogramma: ingresso/uscita (lettura/stampa).
• Ovale: inizio/fine.
• Rombo: decisione (proposizione logica vera/falsa).

La Sequenza

La struttura più semplice: eseguire le istruzioni una dopo l’altra. Ad esempio, dati i raggio del cerchio, calcoliamo area
e circonferenza.

La Selezione a due vie

Dopo la sequenza, introduciamo la capacità di scegliere tra due percorsi in base a una condizione.

Esempio: nello stesso programma calcoliamo l’area di un rettangolo oppure di un triangolo rettangolo, in base all’input.

Le Iterazioni: Ripeti/Finché, Mentre/Fai e Per

Molti compiti richiedono di ripetere azioni finché non succede qualcosa (evento o soglia), oppure per un numero noto di volte.
Ecco tre control-flow classici, con agganci fenomenologici.

Ripeti … Finché (controllo in coda)

Prima esegui, poi verifichi la condizione: ripeti finché non è soddisfatta. Fenomeno: “Tiro il dado finché esce 6”.

Mentre … Fai (controllo in testa)

Verifichi la condizione all’inizio: se è falsa, il corpo può non eseguire neppure una volta.
Fenomeno: “Continuo a camminare mentre il semaforo è verde”.

Per (numero di iterazioni noto)

Usiamo per quando sappiamo a priori quante ripetizioni servono. Fenomeno: “Faccio 10 flessioni”.

Equivalenze: le strutture sono trasformabili l’una nell’altra (Teorema di Böhm–Jacopini).
Tuttavia è buona pratica usare la forma più naturale (leggibilità prima di tutto).

Selezione a più vie

Quando le alternative sono molte e dipendono dal valore di un’unica variabile, la forma “se … altrimenti” annidata diventa poco leggibile.
La selezione a più vie (switch/case) compatta e chiarisce.

Dalla tabella al codice: l’ascensore (automa di Mealy)

Colleghiamo ora le strutture viste con un esempio classico: l’ascensore, la cui logica è stata specificata da una tabella
(automa di Mealy). Possiamo implementarla con seleziona annidati.

Esercizi

1) Sequenze e selezioni

1. Scrivi un algoritmo che legge un intero e stampa: “pari” se è divisibile per 2, “dispari” altrimenti (diagramma + pseudocodice).
2. Amplia l’esempio “sconti e IVA” introducendo una seconda soglia con sconto del 15% oltre € 500.

2) Iterazioni

1. Media, massimo e minimo di una sequenza di voti terminata da un valore negativo (usa ripeti o mentre).
2. Numeri primi: per ciascuno dei 20 numeri letti, verifica se è primo usando il resto (Mod).
   primo = vero
   valore = 2
   ripeti
   se (n Mod valore) = 0 allora
   primo = falso
   altrimenti
   valore = valore + 1
   finché (valore > n/2) oppure (primo = falso)
3. Somma dei primi n numeri (usa mentre); poi riscrivilo con ripeti e con per.

3) Dalla grafica al codice

1. Traduci in pseudocodice il seguente diagramma di flusso e spiega cosa calcola:
   

   

4) Comprensione concettuale

1. Definisci “algoritmo”.
2. Qual è la differenza tra ciclo mentre e ciclo ripeti? E tra mentre e per?
3. Mostra come simulare un mentre con un ripeti e viceversa (usa piccoli esempi).
4. Simula un ciclo per con mentre e con ripeti.
5. Che differenza c’è tra selezione a due vie e a più vie? Quando preferire l’una o l’altra?

5) Quiz veloci

1. Un ciclo ripeti:
   • a) ha termine quando la condizione logica è vera ✅
   • b) è un’iterazione a due vie ❌
   • c) è un ciclo con controllo in testa ❌
   • d) è una selezione iterativa ❌
2. Il ciclo per:
   • a) serve per effettuare selezioni ❌
   • b) non può essere simulato con altri cicli ❌
   • c) può simulare un ciclo ripeti ✅ (con contatore e condizione opportuna)
   • d) teoricamente può non essere compreso in un linguaggio di programmazione ✅
3. Il ciclo mentre:
   • a) ha termine quando la condizione logica è vera ❌ (di solito si esce quando diventa falsa)
   • b) è un ciclo con controllo in testa ✅
   • c) si può simulare con un ciclo for ✅ (se noto il numero di iterazioni)
   • d) esegue il corpo un numero fisso di volte ❌
4. La struttura se:
   • a) è un ciclo ❌
   • b) è una selezione ✅
   • c) è un’iterazione ❌
   • d) è una sequenza ❌