Algoritmi e diagrammi di flusso

---

---

1) Che cos'è un algoritmo (e chi lo esegue)
2) Dati e variabili: l'assegnazione non è un uguale
3) Il diagramma di flusso: i quattro blocchi e le regole
4) Lo pseudocodice e la prima struttura: la sequenza
5) La selezione: nel rombo c'è un'espressione booleana
6) L'iterazione: i tre cicli, il contatore e l'accumulatore
7) La tabella di traccia: far girare l'algoritmo a mano
8) Caso di studio: le divisioni successive sono un algoritmo
9) Dieci esercizi svolti, con la traccia rifatta passo passo
10) Gli errori da non fare in verifica
11) Domande frequenti
12) Conclusioni: bastano tre strutture

---

Che cos'è un algoritmo (e chi lo esegue)

Prima di scrivere una riga di codice c'è una catena di quattro anelli, e saltarne uno si paga:

problema → analisi → algoritmo → programma

Il problema è la domanda in italiano ("calcola la media dei voti di una classe"). L'analisi è la fase in cui decidi che cosa entra, che cosa esce e che cosa serve per passare dall'uno all'altro; quando il problema è grosso, la si fa dall'alto verso il basso — è quella che i libri chiamano progettazione top-down, o per raffinamenti successivi: si spezza il problema in sottoproblemi più piccoli e si continua finché ogni pezzo non è abbastanza semplice da scriversi da solo. L'algoritmo è la sequenza finita di istruzioni che risolve il problema. Il programma è quell'algoritmo tradotto in un linguaggio che il calcolatore capisce.

L'algoritmo non è il programma. Un algoritmo si può scrivere in italiano, disegnare su un tovagliolo, spiegare a voce. Lo stesso algoritmo diventa dieci programmi diversi in dieci linguaggi diversi. È per questo che questo capitolo viene prima di imparare Python o C: se l'algoritmo è sbagliato, nessun linguaggio te lo aggiusta.

L'esecutore, e perché conta

Un algoritmo non esiste da solo: esiste sempre rispetto a un esecutore, cioè a chi lo dovrà eseguire. L'esecutore può essere una persona o un automa. Un'istruzione si dice elementare quando quell'esecutore la sa fare direttamente, senza doverla scomporre.

"Fai una carbonara" è elementare per un cuoco, non per un tredicenne. Ogni volta che scrivi un algoritmo devi sapere a chi lo stai scrivendo, altrimenti non puoi decidere quanto scendere nel dettaglio.

Da dove viene la parola

Muhammad ibn Musa al-Khwarizmi (circa 780 - circa 850) era un matematico legato alla regione di Khwarazm, in Asia centrale — da cui il suo nome — anche se sulla sua provenienza esatta gli storici non sono d'accordo. Quello che è certo è che intorno all'820 lavorava alla Casa della Sapienza di Baghdad, di cui diresse la biblioteca. Il suo trattato al-Kitab al-mukhtasar fi hisab al-jabr wa'l-muqabala ci ha dato la parola algebra, da al-jabr, il nome di una delle operazioni descritte nel libro.

La parola algoritmo viene invece dal suo nome. Al-Khwarizmi scrisse anche un'opera sull'aritmetica indiana, quella posizionale con lo zero: l'originale arabo è perduto, ma ne è sopravvissuta una traduzione latina intitolata Algoritmi de numero Indorum, dove Algoritmi è la latinizzazione di al-Khwarizmi (MacTutor History of Mathematics, University of St Andrews). Algebra e algoritmo vengono dallo stesso uomo per due strade diverse, e "algoritmo" in origine voleva dire letteralmente "il modo di far di conto di al-Khwarizmi": la procedura meccanica passo passo. Che è esattamente quello che stai per imparare a scrivere.

Le cinque proprietà (quelle che ti chiedono a voce)

Queste sono da sapere con questi nomi, ed è una delle domande di teoria che tornano più spesso all'orale.


Una precisazione onesta, così non litighi col tuo libro: alcuni testi mettono la generalità fra le proprietà desiderabili anziché fra quelle necessarie, e tengono come indispensabili solo le prime quattro. Se il tuo professore ne chiede cinque, dai queste cinque; se ne chiede quattro, togli la generalità e citala a parte.

Un ultimo esempio, che ti servirà davvero: l'algoritmo di Euclide per il massimo comune divisore, descritto negli Elementi di Euclide, libro VII, proposizioni 1 e 2, intorno al 300 a.C. Ha 2300 anni, sta in nove blocchi, e lo disegni per intero nel paragrafo 9.

---

Dati e variabili: l'assegnazione non è un uguale

Le tre categorie di dati di un algoritmo

Attenzione al nome, perché qui si perde un punto per niente: queste sono categorie (o ruoli) dei dati, non tipi di dato. I tipi di dato sono un'altra cosa — intero, reale, carattere, booleano, stringa — e se all'interrogazione ti chiedono "quali sono i tipi di dato?" la risposta non è questa.

Detto questo, ogni algoritmo lavora su tre categorie di dati, e distinguerle è il primo passo dell'analisi:

• dati di ingresso (input): quelli che arrivano da fuori, letti dall'utente o da un file;
• dati di uscita (output): i risultati, quelli che l'algoritmo comunica;
• dati di lavoro: le variabili d'appoggio, che nascono e muoiono dentro l'algoritmo e nessuno vede da fuori.

Da qui nasce la tabella che il professore ti fa compilare prima di disegnare. Esempio: "leggi due voti e stampane la media".


Sembra burocrazia. Non lo è: chi salta questa tabella disegna diagrammi che leggono dati che non servono e dimenticano di stampare il risultato.

La variabile è una scatola con un solo foglietto dentro

Una variabile è un contenitore con un nome. Ha un nome (somma), un contenuto, e il contenuto può cambiare. Ma contiene un valore solo alla volta: scriverci dentro un valore nuovo significa buttare via il vecchio, perso per sempre.

La freccia, e come si legge ad alta voce

In tutta questa guida l'assegnazione si scrive con la freccia:

x ← 5
contatore ← contatore + 1

E si legge "a x assegna 5", oppure "x diventa x più uno". Mai, mai "x uguale 5".

Molti linguaggi scrivono l'assegnazione con = o con :=, e proprio quel simbolo = è la causa dell'errore più antico e più diffuso della programmazione: leggere x = x + 1 come un'equazione. Come equazione sarebbe impossibile, perché nessun numero è uguale a sé stesso più uno. Come assegnazione è normalissima.


Quella riga sulla copia vale per i numeri, che sono l'unica cosa che maneggiamo qui. Quando più avanti incontrerai i vettori scoprirai che per i dati composti la faccenda cambia, e che in certi linguaggi b ← a non copia niente: dà un secondo nome alla stessa roba. Per ora tienilo solo come avviso.

La regola che risolve tutto: a destra si legge, a sinistra si scrive. Prima si calcola tutta l'espressione a destra usando i valori attuali, poi il risultato viene scritto nella variabile a sinistra, sovrascrivendo quello che c'era.

Traccia obbligatoria, tre righe:

Inizializzare non è dichiarare

Dichiarare una variabile significa dire che la scatola esiste. Inizializzarla significa metterci dentro un valore noto. Una variabile letta prima di essere assegnata contiene un valore indefinito: certi linguaggi si rifiutano proprio di far partire il programma, altri lo eseguono e stampano un numero imprevedibile, quella che si chiama "spazzatura". Cambia il sintomo, non la sostanza: su quel valore non ci si può contare, mai.

Variabile e costante

Accanto alle variabili ci sono le costanti: hanno un nome e un valore che non cambia mai per tutta l'esecuzione. Il cambio euro-dollaro di un esempio più avanti, il numero 2 con cui si divide per sapere se un numero è pari, il −1 che segnala la fine dei dati: sono tutte costanti. Si scrivono con un nome parlante proprio per non ritrovarsi numeri misteriosi sparsi nell'algoritmo, e la domanda "che differenza c'è fra una variabile e una costante" è di quelle che arrivano puntuali.

Lo scambio di due variabili: prima la versione sbagliata

Devi scambiare il contenuto di a e b. Quasi tutti scrivono così:

a ← b
b ← a

Tracciamolo con a = 3 e b = 7:


Il 3 è sparito alla prima riga: nel momento in cui scrivi 7 dentro a, il 3 non è più recuperabile da nessuna parte, e la seconda riga può solo ricopiare il 7.

Pensa a due bicchieri pieni: per scambiarne il contenuto ti serve un terzo bicchiere vuoto. Non è un trucco da informatici, è fisica.

temp ← a
a ← b
b ← temp

Tre righe, tre ruoli: temp ← a mette al sicuro, a ← b sovrascrive senza rimpianti, b ← temp recupera. E nota che l'ordine delle istruzioni conta: le stesse tre righe in ordine diverso non scambiano niente.

---

Il diagramma di flusso: i quattro blocchi e le regole

Il diagramma di flusso è la rappresentazione grafica di un algoritmo. Occhio ai nomi, perché cambiano da libro a libro e la traccia del compito può usarne uno qualsiasi: diagramma a blocchi, diagramma di flusso e flow chart sono la stessa identica cosa. Esiste una norma internazionale che ne fissa i simboli: ISO 5807:1985, recepita in Italia come UNI ISO 5807:1988. Se il professore te lo chiede, il numero è quello.

Detto questo, va detta anche la verità: a scuola non si applica la norma per intero. Se ne usa un sottoinsieme piccolissimo: quattro blocchi veri e propri — ovale, parallelogramma, rettangolo, rombo — più la linea di flusso, che è una freccia e non un blocco, e il connettore, che serve solo a spezzare il disegno. Quello che ti valutano è la coerenza e il rispetto della forma geometrica, non l'aderenza integrale alla norma.

I simboli che servono

La check-list del disegno (qui si perdono punti per niente)

1) Un solo blocco INIZIO e un solo blocco FINE.
2) Si legge dall'alto verso il basso e da sinistra a destra.
3) Dal rombo escono sempre due frecce e sono sempre etichettate V e F (oppure SI e NO). Una freccia senza etichetta è un errore secco.
4) Ogni blocco dev'essere raggiungibile e ogni percorso deve arrivare al FINE: niente rami morti.
5) Le frecce non si incrociano se si può evitare: per andare lontano si usa il connettore.
6) Dentro il rettangolo ci va un'assegnazione; dentro il rombo ci va un confronto. Mai il contrario.

Esistono altri due simboli che ogni tanto compaiono, e vale la pena non confonderli: il rettangolo con le doppie barre laterali è il processo predefinito, cioè la chiamata a un sottoprogramma; l'esagono è invece il blocco di preparazione, ed è quello che alcuni libri usano per l'intestazione del ciclo enumerativo. In questa guida non ci servono: il ciclo PER lo disegniamo sempre con un rombo e un contatore, e funziona uguale.

Come disegniamo i diagrammi in questa guida

Qui non usiamo immagini: un diagramma fatto di testo lo puoi copiare, cercare e leggere sul telefono la sera prima della verifica. Usiamo due formati, e li dichiariamo.

Formato semigrafico, per i diagrammi corti. Le forme sono rese così:

• ( ... ) è l'ovale, cioè il blocco terminale
• / ... / è il parallelogramma, cioè input o output
• [ ... ] è il rettangolo, cioè l'elaborazione
• < ... ? > è il rombo, cioè il controllo
• la barra verticale e i trattini sono le linee di flusso
• (A) è il connettore, il cerchietto con la lettera dentro

Una semplificazione tipografica, dichiarata: quando un ramo deve scendere accanto a un altro, la sua linea di flusso viene disegnata con i due punti : invece che con la barra. È sempre una freccia normalissima, cambia solo il carattere.

Formato tabellare, per i diagrammi lunghi. Ogni blocco ha un numero e la tabella dice dove si va dopo. Le colonne sono N°, Forma, Contenuto, Se VERO vai a, Se FALSO vai a; per i blocchi che non sono rombi la colonna "Se VERO" contiene semplicemente il blocco successivo e l'altra un trattino. È lo stesso disegno, scritto in righe.

Nei laboratori italiani si usano AlgoBuild, pensato apposta per la scuola secondaria italiana e che durante l'esecuzione mostra le variabili e la traccia delle istruzioni eseguite, e Flowgorithm: se puoi, disegna lì e premi "esegui".

Infine la tesi di tutta la guida: il diagramma di flusso non descrive quello che vuoi ottenere, descrive quello che succede, nell'ordine in cui succede. Non è un disegno decorativo da fare dopo per la consegna: è una cosa che si esegue, mettendo il dito su un blocco e seguendo le frecce. Il calcolatore non capisce le tue intenzioni: fa solo quello che c'è scritto, una riga alla volta, in quell'ordine.

---

Lo pseudocodice e la prima struttura: la sequenza

Il dialetto che usiamo qui

Ogni libro inventa il proprio pseudocodice e quasi nessuno lo dichiara. Noi lo dichiariamo. Questo è il nostro:

INIZIO
   LEGGI n
   somma ← 0
   contatore ← 0
   MENTRE contatore < n ESEGUI
      LEGGI x
      somma ← somma + x
      contatore ← contatore + 1
   FINE MENTRE
   SE contatore ≠ 0 ALLORA
      SCRIVI somma / contatore
   ALTRIMENTI
      SCRIVI "nessun dato"
   FINE SE
FINE

Se il tuo libro usa parole diverse non sei tu a sbagliare: lo pseudocodice non ha una sintassi rigida, è italiano più qualche parola chiave. L'unica cosa che deve essere vera è che sia traducibile riga per riga in un linguaggio vero. Ecco la corrispondenza con la convenzione anglicizzata, quella che molti libri italiani usano al posto delle parole in italiano. Una precisazione onesta: queste parole vengono da Pascal e dal BASIC, non da C o Python — in C si usano le graffe e in Python l'indentazione, e parole come endif o next lì non esistono. La traduzione vera verso quei due linguaggi la trovi nella tabella in fondo alla guida.


Due regole di stile non negoziabili: l'indentazione (il rientro) è obbligatoria, perché è il modo in cui si vede che cosa sta dentro che cosa; e ogni struttura si chiude esplicitamente: FINE SE, FINE MENTRE, FINE PER. L'unica che fa eccezione è il RIPETI, che si chiude con la riga FINCHÉ condizione — non cercare un "FINE RIPETI", non esiste. Non chiudere è la causa dei diagrammi impossibili da disegnare, perché non si capisce più dove finisce il corpo. I commenti si scrivono fra graffe.

La sequenza

La sequenza è la struttura più semplice: le istruzioni vengono eseguite una dopo l'altra, nell'ordine in cui sono scritte. Ha un solo ingresso e una sola uscita, e tieni d'occhio questa frase: torna in tutte le strutture e alla fine diventa un teorema.

Primo esempio: leggi due numeri e stampane la somma. In verifica te lo chiedono nei due modi insieme, quindi eccoli affiancati.

   ( INIZIO )
       |
   / leggi a /
       |
   / leggi b /
       |
   [ s ← a + b ]
       |
   / scrivi s /
       |
    ( FINE )

INIZIO
   LEGGI a
   LEGGI b
   s ← a + b
   SCRIVI s
FINE

Secondo esempio: converti una somma in euro in dollari, con un cambio fisso di 1,08.

INIZIO
   LEGGI euro
   dollari ← euro * 1.08
   SCRIVI dollari
FINE

Nota il punto al posto della virgola. Nel testo italiano si scrive 1,08; dentro un algoritmo si usa il punto, perché in tutti i linguaggi di programmazione il separatore decimale è quello e la virgola serve a separare le cose in un elenco. Scrivere 1,08 in Python non dà un errore: dà due numeri, l'1 e l'8, ed è un guaio che non te ne accorgi subito.

Nota una cosa che sembra ovvia e non lo è: se sposti la riga SCRIVI dollari sopra il calcolo, il programma stampa spazzatura, perché dollari non è ancora stata assegnata. Nella sequenza l'ordine è il significato, esattamente come nello scambio sbagliato del paragrafo 2.

---

La selezione: nel rombo c'è un'espressione booleana

La selezione (chiamata anche struttura alternativa o condizionale) è la struttura che permette all'algoritmo di scegliere fra due strade.

• Selezione unaria, o a una via: SE condizione ALLORA azioni FINE SE. Se la condizione è falsa non si fa niente e si prosegue.
• Selezione binaria, o a due vie: SE ... ALLORA ... ALTRIMENTI ... FINE SE. Una delle due strade si percorre sempre.
• Selezioni annidate: dentro un ramo ce n'è un'altra. Si annidano come scatole cinesi proprio perché ogni struttura ha un solo ingresso e una sola uscita.
• Selezione multipla (caso, in inglese switch): quando le strade sono più di due e dipendono dal valore di una sola variabile. Qui basta sapere che esiste.

Primo aggancio: il rombo contiene un'espressione booleana

Ed è il punto in cui devi cambiare idea su una cosa.

Il rombo non pone una domanda all'utente. Quello è il parallelogramma, che legge un dato. Il rombo valuta un'espressione, e quell'espressione vale Vero oppure Falso: nient'altro, mai una terza possibilità.

Vero e Falso sono i due valori dell'algebra di Boole. Le due uscite del rombo, quella etichettata V e quella etichettata F, sono le due righe di una tavola di verità. Se AND, OR, NOT e le tavole di verità non ti sono chiari, leggi prima la guida Algebra di Boole e porte logiche: il rombo è esattamente il punto in cui l'algebra di Boole entra nel diagramma di flusso, e senza quella non stai capendo il rombo, lo stai indovinando.

Gli operatori relazionali sono le fabbriche di booleani: prendono numeri e restituiscono Vero o Falso. Sono sei: = (uguale), ≠ (diverso), < (minore), > (maggiore), ≤ (minore o uguale), ≥ (maggiore o uguale). 5 ≤ 5 è vero, 6 ≤ 5 è falso, e l'attenzione va tutta sui casi in cui i due valori sono uguali.

Attenzione anche al doppio uso del simbolo =. Nel rettangolo x ← 0 è un'assegnazione: mette zero dentro x. Nel rombo x = 0 è un confronto: chiede se x vale zero, e la risposta è Vero o Falso. Sono due operazioni diverse che in molti linguaggi si scrivono con lo stesso segno, ed è per questo che qui usiamo la freccia.

Ecco la selezione binaria disegnata: il massimo fra due numeri.

   ( INIZIO )
       |
   / leggi a /
       |
   / leggi b /
       |
   < a > b ? >---- F ----> [ max ← b ]
       | V                      :
   [ max ← a ]                  :
       |                        :
       +<-----------------------+
       |
   / scrivi max /
       |
    ( FINE )

INIZIO
   LEGGI a
   LEGGI b
   SE a > b ALLORA
      max ← a
   ALTRIMENTI
      max ← b
   FINE SE
   SCRIVI max
FINE

Nota la forma del disegno: i due rami si riuniscono prima di proseguire. Nessuna freccia risale. Tienilo a mente, perché è l'unica differenza fra questo disegno e un ciclo.

Secondo aggancio: le condizioni composte, AND, OR, NOT e De Morgan

Le condizioni vere non sono quasi mai singole. Si scrivono unendo più confronti con AND, OR e NOT:

(voto ≥ 6) AND (assenze < 50)
(giorno = "sabato") OR (giorno = "domenica")

E si valutano esattamente con le tavole di verità che hai già studiato. Chiamiamo A la condizione voto ≥ 6 e B la condizione assenze < 50:


Quattro righe, una sola porta al ramo Vero: è la tavola di verità della porta AND, tale e quale a quella della guida Algebra di Boole e porte logiche. Il rombo non è una cosa nuova: è una porta logica disegnata in un altro modo.

Adesso il pezzo che vale la verifica. Considera questo ciclo:

MENTRE (tentativi < 3) AND (password errata) ESEGUI

Domanda tipica: quando si esce dal ciclo? Si esce quando la condizione diventa falsa, cioè quando vale la sua negazione:

NOT( (tentativi < 3) AND (password errata) )

E per De Morgan questa diventa:

(tentativi ≥ 3) OR (password corretta)

Negando, l'AND è diventato OR. Chi risponde "si esce quando i tentativi sono almeno 3 e la password è corretta" sbaglia, e sbaglia in un modo cattivo: il programma sembra funzionare finché non lo provi sul caso giusto.

La regola sta in due mosse, e chi ne fa una sola sbaglia sempre: si nega ciascun pezzo, E si scambia AND con OR. In italiano corrente lo senti a orecchio: negare "piove e ho l'ombrello" non dà "non piove e non ho l'ombrello", dà "non piove oppure non ho l'ombrello". Basta che una delle due cose non sia vera.

Ecco la tabella delle negazioni, compreso il corollario sui confronti che quasi nessuno spiega:


E due condizioni scritte male che ricorrono in ogni compito:

• x = 3 OR 4 è una traduzione letterale dall'italiano e non significa niente. Si scrive (x = 3) OR (x = 4). Ogni operatore di confronto vuole due operandi, e AND e OR uniscono due condizioni complete, non due pezzi. Se dopo AND non c'è una condizione che sta in piedi da sola, è sbagliata.
• (x > 5) AND (x < 0) è sempre falsa: nessun numero è insieme maggiore di 5 e minore di 0. Per dire "fuori dall'intervallo da 0 a 5" serve OR: (x < 0) OR (x > 5).

Ultima nota: AND lega più forte di OR, quindi a OR b AND c significa a OR (b AND c). Nel dubbio metti le parentesi, che non costano niente.

Selezioni annidate: il massimo fra tre numeri

INIZIO
   LEGGI a
   LEGGI b
   LEGGI c
   SE a > b ALLORA
      max ← a
   ALTRIMENTI
      max ← b
   FINE SE
   SE c > max ALLORA
      max ← c
   FINE SE
   SCRIVI max
FINE

Un bonus che chiarisce le idee: SE (A AND B) ALLORA azione è equivalente a due selezioni unarie annidate, SE A ALLORA SE B ALLORA azione. L'AND non è una regola di scrittura, è una struttura.

Pari o dispari

L'operatore MOD dà il resto della divisione intera. Un numero è pari se il resto della divisione per 2 è zero.

INIZIO
   LEGGI n
   SE n MOD 2 = 0 ALLORA
      SCRIVI "pari"
   ALTRIMENTI
      SCRIVI "dispari"
   FINE SE
FINE

Tieni d'occhio n MOD 2: torna nel paragrafo 8, e lì scoprirai che è la stessa identica cosa dell'ultima cifra binaria.

---

L'iterazione: i tre cicli, il contatore e l'accumulatore

L'iterazione (o ciclo, o struttura ripetitiva) serve a ripetere un gruppo di istruzioni. In italiano se ne studiano tre forme, e i nomi contano perché sono nomi da interrogazione.


La regola di scelta sta in tre righe, ed è la risposta alla domanda "quale ciclo useresti e perché?":

1) numero di ripetizioni noto in partenza → PER;
2) non noto, e può capitare di non entrare mai → MENTRE;
3) non noto, ma il corpo va eseguito almeno una volta → RIPETI.

La trappola numero uno

Nel MENTRE la condizione è quella di permanenza: si continua finché è vera. Nel RIPETI ... FINCHÉ la condizione è quella di uscita: si esce quando diventa vera.

Le due condizioni sono l'una la negazione dell'altra. Se converti un ciclo dall'una all'altra forma devi negare la condizione — e negarla bene, con De Morgan a due mosse come nel paragrafo 5. Continuare MENTRE (a > 0) AND (b > 0) significa uscire quando (a ≤ 0) OR (b ≤ 0).

Piccola nota per chi guarda già il C, e va letta con attenzione perché è una fonte di pasticci. Il do ... while del C è un ciclo a condizione finale: strutturalmente è il nostro RIPETI, non il nostro MENTRE. Quello che cambia è la polarità della condizione: il do ... while continua finché la condizione è vera, mentre il RIPETI ... FINCHÉ si ferma quando diventa vera. Quindi la traduzione giusta è RIPETI corpo FINCHÉ cond che diventa do { corpo } while ( NOT cond );. La condizione va negata, non ricopiata.

La regola dei tre punti

Ogni ciclo ha tre luoghi in cui compare la stessa variabile di controllo:

1) dove nasce: l'inizializzazione, fuori dal ciclo;
2) dove viene interrogata: il rombo della condizione;
3) dove cambia: l'aggiornamento, dentro il corpo.

Se ne manca uno, il ciclo è rotto. Nel PER i tre punti sono impacchettati automaticamente nella riga di intestazione, ed è per questo che è molto più difficile dimenticarsi l'aggiornamento — ma attenzione a non dire che un PER non può andare in ciclo infinito: se il corpo tocca la variabile di controllo o l'estremo finale, può succedere anche lì. Nel MENTRE invece i tre punti sono tutti a carico tuo, e il terzo è quello che si dimentica.

Domanda di controllo da farti sempre: che cosa fa diventare falsa questa condizione? Se non sai indicare un'istruzione precisa dentro il corpo, e nel ciclo ci si entra, il ciclo è infinito.

Il ciclo è la freccia che torna indietro

Questo è l'unico modo onesto di distinguere una selezione da un'iterazione nel disegno, perché il simbolo è lo stesso rombo. Guarda i due schemi: stessa condizione, stessa istruzione dentro.

Selezione:

       |
   < c ≤ 5 ? >---- F ---->
       | V
   / scrivi c /
       |
   ... si prosegue verso il basso

Iterazione:

   (A)
       |
   < c ≤ 5 ? >---- F ---->
       | V
   / scrivi c /
       |
   [ c ← c + 1 ]
       |
       +--> risale ad (A)

Nella forma cambia una cosa sola: nell'iterazione una freccia risale verso il rombo. Nella selezione nessuna freccia risale. Il ciclo è quella freccia.

E nota il rettangolo in più, che non è un dettaglio: nel momento in cui una freccia risale, diventa obbligatorio che qualcosa faccia cambiare c. Togli quel rettangolo e il disegno resta bello uguale, ma il ciclo non finisce più. È la regola dei tre punti qui sopra, vista da fuori.

Da qui due frasi che ti tolgono metà dei dubbi:

• la selezione esegue il corpo 0 o 1 volta; l'iterazione 0, 1 o molte volte. E sì, il MENTRE può eseguire il corpo zero volte: se la condizione è falsa già alla prima valutazione, si salta tutto.
• il rombo viene attraversato solo quando la freccia ci arriva. Mentre il corpo è in esecuzione nessuno sta controllando la condizione: il corpo si conclude sempre per intero, poi si torna al rombo. Un ciclo non "si accorge" a metà corpo che la condizione è cambiata.

Un ciclo che non termina viola la finitezza del paragrafo 1: nel diagramma lo riconosci perché c'è una freccia che risale e, lungo quel percorso, nessun blocco tocca la variabile della condizione. Con un'avvertenza, che è anche una domanda da trabocchetto: se la condizione è falsa già alla prima valutazione non si entra proprio, e allora il ciclo termina subito anche senza aggiornamento. c ← 10 seguito da MENTRE c < 5 non stampa niente e finisce lì.

Contatore e accumulatore

Due schemi da riconoscere a colpo d'occhio. Hanno la stessa forma, v ← v + qualcosa, ma rispondono a due domande diverse.


C'è un terzo schema che si chiede sempre insieme a questi due, e che è il più semplice di tutti: la variabile flag, in italiano interruttore. È una variabile booleana che parte da un valore — di solito Falso — e viene ribaltata la prima volta che succede una certa cosa, per poterlo controllare dopo il ciclo. "Ho trovato almeno un numero negativo?" si risolve con trovato ← Falso prima del ciclo, trovato ← Vero dentro il SE, e una domanda sola alla fine. Contatore, accumulatore e flag rispondono a tre domande diverse: quanti, quanto, e se è successo.

La regola per inizializzare si ricorda meglio come regola dell'elemento neutro: si parte dal valore che non altera l'operazione. Per la somma è 0, per il prodotto è 1. Un accumulatore di prodotto inizializzato a 0 resta 0 per sempre, ed è il motivo per cui il fattoriale di mezza classe dà zero.

E la regola d'oro, in grassetto perché vale un voto: contatori e accumulatori si inizializzano prima del ciclo in cui vengono aggiornati, mai dentro. Inizializzarli dentro li riazzera a ogni giro. La formulazione precisa — "prima del ciclo in cui vengono aggiornati" — serve per quando incontrerai i cicli annidati: lì l'accumulatore che somma una riga per volta va azzerato dentro il ciclo esterno, perché ogni riga ricomincia da capo. Ma è dentro il ciclo esterno e fuori da quello interno, che è quello che lo aggiorna: la regola tiene. Nel codice è un errore invisibile; nel diagramma di flusso è evidentissimo, perché vedi il rettangolo dentro l'anello.

I quattro schemi che coprono quasi tutti i compiti

Somma dei primi N interi, con il PER:

somma ← 0
PER i DA 1 A n ESEGUI
   somma ← somma + i
FINE PER
SCRIVI somma

Lettura con sentinella, con il MENTRE. La sentinella è un valore convenzionale che segnala la fine dei dati, per esempio −1 su una serie di voti. Qui il MENTRE è la scelta giusta: se l'utente scrive subito −1, non si deve elaborare niente, mentre il RIPETI elaborerebbe la sentinella prima di accorgersene.

somma ← 0
conta ← 0
LEGGI x
MENTRE x ≠ -1 ESEGUI
   somma ← somma + x
   conta ← conta + 1
   LEGGI x
FINE MENTRE

Media, cioè accumulatore diviso contatore, con la protezione dalla divisione per zero:

SE conta ≠ 0 ALLORA
   SCRIVI somma / conta
ALTRIMENTI
   SCRIVI "nessun dato inserito"
FINE SE

Ricerca del massimo, che è il terzo schema accanto al contatore e all'accumulatore, e ha una regola tutta sua: max si inizializza con il primo valore letto, non con 0. Se lo inizializzi a 0 e i dati sono tutti negativi, il tuo massimo risulta 0, che non è nemmeno uno dei dati.

LEGGI n
LEGGI x
max ← x
letti ← 1
MENTRE letti < n ESEGUI
   LEGGI x
   SE x > max ALLORA
      max ← x
   FINE SE
   letti ← letti + 1
FINE MENTRE
SCRIVI max

Guarda l'ordine: il primo valore viene letto fuori dal ciclo e serve a inizializzare max, e per questo letti parte da 1 e non da 0. Il ciclo si occupa solo dal secondo in poi. La precondizione è n ≥ 1, e non è pignoleria: il massimo di zero numeri non esiste, quindi va escluso invece che lasciato succedere.

---

La tabella di traccia: far girare l'algoritmo a mano

La tabella di traccia è il foglio su cui esegui l'algoritmo con la matita, al posto del calcolatore. È lo strumento più sottovalutato del capitolo e l'unico che risponde alla domanda più frequente di tutte le verifiche: "che cosa stampa questo diagramma se in ingresso metto 7?". Si costruisce così, ed è una procedura, non un'ispirazione:

1) una colonna per ogni variabile, più una colonna output e una colonna con il passo o il numero di giro;
2) una riga per ogni istruzione eseguita, o per ogni giro di ciclo se il corpo è breve;
3) metti il dito su un blocco alla volta: in ogni istante il dito è su un blocco solo. Non esistono due istruzioni attive insieme. Da ogni blocco esce una freccia sola — tranne il FINE, da cui non esce niente, e il rombo, da cui ne escono due ma ne imbocchi una;
4) quando arrivi a un rombo, scrivi anche l'esito: V o F. È lì che si vede l'errore.

Traccia della somma dei primi 5 interi

Algoritmo: somma ← 0, poi PER i DA 1 A 5 ESEGUI somma ← somma + i.


Output: 15. E il controllo veloce: 1+2+3+4+5 vale davvero 15.

Traccia di un ciclo infinito

Adesso lo stesso ciclo con l'aggiornamento dimenticato:

c ← 1
MENTRE c ≤ 5 ESEGUI
   SCRIVI c
FINE MENTRE

Quattro righe identiche e i puntini convincono più di qualsiasi frase: c non cambia mai, quindi la condizione non diventerà mai falsa. Manca il terzo dei tre punti del paragrafo 6. Questo algoritmo viola la finitezza.

La traccia serve a contare, non a "vedere"

Il secondo uso della tabella è scovare gli errori di conteggio, quelli che si chiamano off-by-one, cioè "sbagliato di uno". Non si vedono a occhio: si contano le righe della tabella e si confrontano con il numero atteso.


Se ti serve un ciclo che gira N volte e la tabella ne conta N−1, non riscrivere tutto: hai scritto < nel punto in cui serviva ≤.

---

Caso di studio: le divisioni successive sono un algoritmo

Adesso la parte più utile della guida, e la prendiamo da una cosa che sai già fare.

Nella guida Sistemi di numerazione: binario, decimale ed esadecimale hai imparato a convertire un numero decimale in binario con il metodo delle divisioni successive: dividi per 2, segna il resto, ripeti sul quoziente, e alla fine leggi i resti dal basso verso l'alto. Lì c'è il perché funziona. Qui c'è il come si scrive come algoritmo.

Perché proprio questo esempio: siccome conosci già il risultato, tutta la tua attenzione può andare sulla struttura. E si vede una cosa importante: una procedura che sai eseguire a mano è già un algoritmo. Il diagramma di flusso non lo inventa, lo scrive.

Analisi del problema

Servono due operazioni che d'ora in poi consideriamo elementari:

• n DIV 2 è il quoziente intero della divisione: 13 DIV 2 fa 6, si butta via la parte decimale;
• n MOD 2 è il resto: 13 MOD 2 fa 1.

Lo pseudocodice

INIZIO
   LEGGI n
   RIPETI
      r ← n MOD 2
      SCRIVI r          { le cifre escono dalla meno significativa }
      n ← n DIV 2
   FINCHÉ n = 0
FINE

Il diagramma, blocco per blocco

Sette blocchi. Le colonne "Se VERO" e "Se FALSO" hanno il significato dichiarato nel paragrafo 3: per i blocchi che non sono rombi la prima indica semplicemente il blocco successivo.


Guarda il blocco 6: sull'uscita F la freccia risale al blocco 3. È il ciclo, ed è la freccia che torna indietro del paragrafo 6.

La tabella di traccia per n = 13

Le cifre sono uscite nell'ordine 1, 0, 1, 1, cioè dalla meno significativa alla più significativa. Lette al contrario danno 1101. Verifica: 8 + 4 + 0 + 1 fa 13. Torna.

Perché RIPETI e non MENTRE

Questa è la ragione per cui questo algoritmo è didatticamente perfetto: la differenza fra i due cicli qui non è teorica, si tocca con mano.

Prova con n = 0. Con RIPETI, il corpo viene eseguito almeno una volta: si calcola 0 MOD 2 che fa 0, si stampa 0, si calcola 0 DIV 2 che fa 0, la condizione n = 0 è vera e si esce. Output: 0. Corretto, perché zero in binario si scrive 0.

Con MENTRE n > 0, la condizione è falsa già alla prima valutazione: il corpo non viene eseguito nemmeno una volta e il programma non stampa niente. Sbagliato.

Ricordi la regola di scelta? "Non so quante volte, ma almeno una" → RIPETI. Eccola applicata a un caso vero.

Verifica della finitezza

Questo algoritmo termina sempre? Con una precondizione dichiarata — n ≥ 0, e ha senso, perché stiamo convertendo un numero naturale — sì, e si dimostra in una riga: a ogni giro n viene sostituito da n DIV 2, cioè si dimezza, e una successione di interi non negativi che si dimezza raggiunge 0 in un numero finito di passi. Con un n negativo il discorso salta, ed è il motivo per cui le precondizioni si scrivono invece di darle per scontate. Per n = 13 ci sono voluti 4 giri; per un numero di un miliardo ne servirebbero 30. La proprietà del paragrafo 1 non è una definizione da imparare a memoria: è una cosa che si verifica.

Due bonus a costo zero

Contare i bit. Aggiungi un contatore e ottieni gratis "quanti bit servono per rappresentare n":

INIZIO
   LEGGI n
   bit ← 0
   RIPETI
      r ← n MOD 2
      SCRIVI r
      n ← n DIV 2
      bit ← bit + 1
   FINCHÉ n = 0
   SCRIVI bit
FINE

Per n = 13 il contatore arriva a 4, e infatti 1101 ha quattro cifre. È di nuovo materia della guida sui sistemi di numerazione, ottenuta qui con una riga di codice.

Il test di parità. La condizione n MOD 2 = 0 del paragrafo 5, quella che distingue i pari dai dispari, è la stessa cosa che chiedere se l'ultimo bit vale 0. Il bit meno significativo di un numero binario dice esattamente se il numero è pari. Due guide, un solo fatto.

---

Dieci esercizi svolti, con la traccia rifatta passo passo

Otto esercizi classici più due di tipo inverso, tutti nello stesso formato: algoritmo, dati d'ingresso dichiarati, e la tabella di traccia rifatta riga per riga. I primi due sono di sola sequenza e la traccia non serve, per gli altri c'è. Impara il metodo, non i singoli esercizi.

Esercizio 1 — Somma di due numeri

Solo sequenza, ed è quello del paragrafo 4. Ingresso a e b, uscita s, elaborazione s ← a + b. Con a = 12 e b = 5 l'output è 17. Qui la traccia non serve: senza rombi e senza cicli, l'ordine di esecuzione è l'ordine di scrittura.

Esercizio 2 — Scambio di due variabili

Già svolto nel paragrafo 2, ma è così frequente che vale ripeterne il risultato: con a = 3 e b = 7, la sequenza temp ← a, a ← b, b ← temp porta a a = 7 e b = 3, mentre la versione senza temp porta a a = 7 e b = 7.

Esercizio 3 — Massimo fra tre numeri

Selezioni annidate, pseudocodice nel paragrafo 5. Traccia con a = 4, b = 9, c = 7:


Output: 9. Prova a rifarla con a = 4, b = 9, c = 11: il secondo rombo dà V e max diventa 11.

Esercizio 4 — Equazione di primo grado ax + b = 0

Il classico con i casi degeneri, cioè quelli in cui la formula x = -b / a non si può usare.

INIZIO
   LEGGI a
   LEGGI b
   SE a ≠ 0 ALLORA
      x ← -b / a
      SCRIVI x
   ALTRIMENTI
      SE b = 0 ALLORA
         SCRIVI "equazione indeterminata"
      ALTRIMENTI
         SCRIVI "equazione impossibile"
      FINE SE
   FINE SE
FINE

Verifica del primo caso: x = -(-12) / 3 = 12 / 3 = 4, e infatti 3 per 4 meno 12 fa 0.

Esercizio 5 — Media di N voti con controllo di validità

Qui lavorano insieme iterazione, selezione, contatore, accumulatore e una condizione composta con AND.

INIZIO
   LEGGI n
   somma ← 0
   validi ← 0
   letti ← 0
   MENTRE letti < n ESEGUI
      LEGGI v
      letti ← letti + 1
      SE (v ≥ 1) AND (v ≤ 10) ALLORA
         somma ← somma + v
         validi ← validi + 1
      ALTRIMENTI
         SCRIVI "voto non valido, scartato"
      FINE SE
   FINE MENTRE
   SE validi ≠ 0 ALLORA
      SCRIVI somma / validi
   ALTRIMENTI
      SCRIVI "nessun voto valido"
   FINE SE
FINE

Traccia con n = 4 e i voti 7, 15, 6, 8:


Uscita dal ciclo perché letti < n diventa 4 < 4, cioè falsa. Poi validi ≠ 0 è vera, quindi si stampa 21 / 3 che fa 7. Nota il ruolo dei due contatori: letti conta quanti dati sono arrivati, validi conta quanti sono stati accettati. Confonderli è l'errore che fa dividere per il numero sbagliato.

Esercizio 6 — Lettura con sentinella −1

INIZIO
   somma ← 0
   conta ← 0
   LEGGI x
   MENTRE x ≠ -1 ESEGUI
      somma ← somma + x
      conta ← conta + 1
      LEGGI x
   FINE MENTRE
   SE conta ≠ 0 ALLORA
      SCRIVI somma / conta
   ALTRIMENTI
      SCRIVI "nessun dato"
   FINE SE
FINE

Traccia con i dati 7, 8, 6, −1:


Output: 21 / 3 uguale 7. Osserva la struttura: c'è una lettura prima del ciclo e una lettura in fondo al corpo. Serve perché la condizione deve poter essere valutata già al primo giro. E se l'utente scrive −1 come primo dato, il ciclo non parte affatto, conta resta 0 e la protezione dalla divisione per zero fa il suo lavoro. Con un RIPETI la sentinella verrebbe sommata, a meno di infilare dentro il corpo un controllo in più che complica il disegno senza guadagnarci niente: ecco perché qui il MENTRE è la scelta naturale.

Esercizio 7 — Potenza per moltiplicazioni ripetute

Calcolare b elevato a e senza usare l'operatore di potenza, con e ≥ 0. Accumulatore di prodotto, quindi inizializzato a 1. Nota che la precondizione fa lavorare l'algoritmo anche su e = 0: il ciclo non gira nemmeno una volta e resta p = 1, che è la risposta giusta.

INIZIO
   LEGGI b
   LEGGI e
   p ← 1
   PER i DA 1 A e ESEGUI
      p ← p * b
   FINE PER
   SCRIVI p
FINE

Traccia con b = 2 ed e = 5:


Output: 32, e infatti 2 elevato a 5 fa 32. Ora prova a inizializzare p ← 0: la prima moltiplicazione dà 0, la seconda anche, e il risultato è 0 per sempre. È l'errore dell'elemento neutro.

Esercizio 8 — Massimo comune divisore con l'algoritmo di Euclide

L'idea è negli Elementi di Euclide, libro VII, intorno al 300 a.C., e si regge su un fatto solo: il MCD di due numeri è uguale al MCD fra il minore dei due e il resto della loro divisione. Quindi si sostituisce la coppia (a, b) con la coppia (b, a MOD b) e si ricomincia, finché il resto non è zero.

Una precisazione storica, visto che qui stiamo citando: Euclide non divideva. Negli Elementi il procedimento va per sottrazioni ripetute, che è la stessa idea eseguita in modo più lento. La versione con il resto che vedi qui sotto è la riscrittura moderna, ed è quella che si chiede a scuola.

INIZIO
   LEGGI a
   LEGGI b
   MENTRE b ≠ 0 ESEGUI
      r ← a MOD b
      a ← b
      b ← r
   FINE MENTRE
   SCRIVI a
FINE

Traccia con a = 1071 e b = 462:


Output: 21. I conti: 1071 diviso 462 fa 2 con resto 147; 462 diviso 147 fa 3 con resto 21; 147 diviso 21 fa 7 con resto 0. Tre divisioni.

Perché un MENTRE e non un PER: nessuno sa in anticipo quante divisioni serviranno. È il criterio di scelta del paragrafo 6 applicato a un caso reale. E quante ne servono al massimo? Nel 1844 Gabriel Lamé dimostrò che il numero di divisioni non supera mai cinque volte il numero di cifre, scritte in base dieci, del minore dei due numeri: qui 462 ha tre cifre, quindi al massimo 15 divisioni. Ne sono bastate tre. Il limite vale per questa versione, quella con il resto: la variante che invece di dividere sottrae ripetutamente può richiedere molti più passi.

Confrontalo con il metodo che ti hanno insegnato alle medie, cioè scomporre entrambi i numeri in fattori primi e moltiplicare quelli in comune. Su numeri piccoli è comodo; su due numeri da tredici cifre la scomposizione richiede decine di migliaia di divisioni di prova, mentre Euclide se la cava con una manciata. Se la scomposizione ti interessa per sé, la trovi nella guida Alla scoperta dei numeri primi. Qui il punto è un altro: stesso problema, stessa risposta, stesso calcolatore, e cambia solo il procedimento. Ecco perché questo capitolo viene prima di imparare un linguaggio.

Esercizio inverso A — che cosa stampa?

Questo tipo di esercizio è il più temuto e il meno allenato. Dato l'algoritmo, dire l'output con un ingresso preciso.

INIZIO
   LEGGI n
   s ← 0
   c ← 1
   MENTRE c ≤ n ESEGUI
      SE c MOD 2 ≠ 0 ALLORA
         s ← s + c
      FINE SE
      c ← c + 1
   FINE MENTRE
   SCRIVI s
FINE

Ingresso: n = 7. Non indovinare: traccia.


Output: 16. L'algoritmo somma i numeri dispari da 1 a n: 1 + 3 + 5 + 7 fa 16.

Esercizio inverso B — ripara il diagramma

Ti danno un algoritmo che dovrebbe contare quanti numeri positivi ci sono fra n letti. Ha tre difetti: due si vedono nel codice qui sotto, il terzo salta fuori solo se ti chiedi che cosa succede con certi dati in ingresso.

INIZIO
   LEGGI n
   letti ← 0
   MENTRE letti < n ESEGUI
      positivi ← 0
      LEGGI x
      SE x > 0 ALLORA
         positivi ← positivi + 1
      FINE SE
   FINE MENTRE
   SCRIVI positivi
FINE

Trovali prima di leggere.

1) positivi ← 0 sta dentro il ciclo. A ogni giro il contatore viene riazzerato, quindi alla fine vale 0 o 1, mai di più. Va spostato prima del MENTRE.
2) Manca l'aggiornamento di letti. Nessuna istruzione tocca la variabile della condizione: il ciclo è infinito. Serve letti ← letti + 1 dentro il corpo. È il terzo dei tre punti.
3) Il caso n ≤ 0 non è gestito. Se l'utente scrive 0, il ciclo non parte, positivi non viene mai assegnata e SCRIVI positivi stampa una variabile mai inizializzata — cioè esattamente la "spazzatura" del paragrafo 2. Non basta spostare positivi ← 0 fuori dal ciclo per bellezza: è quello spostamento che rende l'algoritmo corretto anche con zero dati, perché allora positivi vale 0 e la risposta 0 è giusta.

Sistemato così, l'algoritmo diventa:

INIZIO
   LEGGI n
   letti ← 0
   positivi ← 0
   MENTRE letti < n ESEGUI
      LEGGI x
      letti ← letti + 1
      SE x > 0 ALLORA
         positivi ← positivi + 1
      FINE SE
   FINE MENTRE
   SCRIVI positivi
FINE

Un'ultima cosa che in un compito vale un punto e che qui non si vede, perché non c'è il disegno: nel diagramma corrispondente le due uscite del rombo x > 0 vanno etichettate V e F. Senza etichette il disegno non si può eseguire, ed è errore anche se la logica è giusta.

---

Gli errori da non fare in verifica

La sezione da rileggere dieci minuti prima di entrare in classe. Non sono errori inventati: sono quelli che ricorrono nei compiti e che la ricerca didattica documenta da decenni. Roy Pea, in uno studio del 1986, li ha ricondotti tutti a un'unica illusione di fondo, che chiama il superbug: credere che dentro il linguaggio di programmazione ci sia una mente nascosta capace di interpretare quello che scrivi. Da lì nasce, fra gli altri, l'errore di attribuire al programma delle intenzioni — come se sapesse dove vuoi arrivare. Non le ha. C'è un esecutore che fa quello che c'è scritto, una riga alla volta, in quell'ordine.

Errori di disegno e di schema

Errori di condizione

Errori di struttura

Un'ultima misconcezione, la più insidiosa perché non produce errori di scrittura ma di ragionamento: credere che il ciclo si interrompa nell'istante in cui la condizione smette di essere vera, anche a metà corpo. Non succede. Il corpo si esegue sempre per intero e la condizione viene guardata solo quando la freccia torna al rombo.

---

Domande frequenti

Che differenza c'è fra un algoritmo e un programma?
L'algoritmo è la sequenza di passi che risolve il problema, e puoi scriverlo in italiano o disegnarlo con un diagramma di flusso. Il programma è quello stesso algoritmo tradotto in un linguaggio che il calcolatore capisce, come Python o C. Lo stesso algoritmo diventa programmi diversi in linguaggi diversi, ed è per questo che si progetta prima l'algoritmo e solo dopo si scrive il codice.

Quali sono le proprietà di un algoritmo?
Cinque, e i nomi contano: finitezza (termina in un numero finito di passi), non ambiguità o univocità (ogni istruzione si interpreta in un solo modo), determinismo (a parità di dati in ingresso i risultati sono sempre gli stessi), eseguibilità (ogni azione è realizzabile in tempo finito da quell'esecutore) e generalità (risolve una classe di problemi, non un caso singolo). Alcuni libri considerano la generalità una proprietà desiderabile anziché necessaria e ne elencano solo quattro: dipende dal testo che usi.

Quale ciclo devo usare, MENTRE o RIPETI?
Se sai già quante volte devi ripetere, usa il PER. Se non lo sai e può capitare di non entrare mai nel ciclo, usa il MENTRE, che controlla la condizione prima e quindi può eseguire il corpo zero volte, al contrario del RIPETI che lo esegue sempre almeno una volta. Se non lo sai ma il corpo va eseguito almeno una volta, usa il RIPETI, che controlla la condizione alla fine. Attenzione alla trappola: nel MENTRE la condizione è di permanenza e si continua finché è vera, nel RIPETI è di uscita e si esce quando diventa vera, quindi le due condizioni sono l'una la negazione dell'altra.

Che cosa ci va dentro il rombo del diagramma di flusso?
Una condizione, cioè un'espressione booleana che vale Vero o Falso. Mai un'assegnazione: quella va nel rettangolo. E il rombo non pone una domanda all'utente, quello lo fa il parallelogramma di input: il rombo valuta un confronto già scritto. Dal rombo escono sempre due frecce e vanno sempre etichettate con V e F oppure con SI e NO, altrimenti il diagramma non si può eseguire ed è un errore secco anche se il resto è giusto.

Come si nega una condizione con AND?
Con le leggi di De Morgan, e sono due mosse da fare tutte e due: si nega ogni pezzo e si scambia AND con OR. La negazione di "(tentativi minore di 3) AND (password errata)" è "(tentativi maggiore o uguale a 3) OR (password corretta)". Chi fa una sola delle due mosse e lascia l'AND sbaglia, e sbaglia in un modo che sembra funzionare finché non provi il caso giusto. Ricorda anche che la negazione di "x maggiore di 5" è "x minore o uguale a 5", non "x minore di 5".

Perché il contatore va inizializzato fuori dal ciclo?
Perché tutto quello che sta dentro il corpo viene rieseguito a ogni giro. Se scrivi c uguale a 0 dentro il ciclo, il contatore si riazzera ogni volta e alla fine vale 0 o 1, mai il totale. Vale lo stesso per l'accumulatore, con una regola in più: si inizializza con l'elemento neutro dell'operazione, cioè 0 se accumuli somme e 1 se accumuli prodotti. Un accumulatore di prodotto inizializzato a 0 resta 0 per sempre, ed è il motivo per cui il fattoriale dà zero.

Che cos'è la tabella di traccia e a che serve?
È la tabella con cui esegui l'algoritmo a mano, con una colonna per ogni variabile, una colonna per l'output e una riga per ogni passo o per ogni giro di ciclo. Serve a rispondere alla domanda più frequente delle verifiche, cioè "che cosa stampa questo diagramma se in ingresso metto 7", e serve a contare le iterazioni per scovare gli errori di uno, detti anche off-by-one, quelli in cui il ciclo gira una volta di troppo o una di meno. Non si indovina l'output: si traccia.

Che cos'è il teorema di Böhm-Jacopini e devo saperlo?
Sì, viene chiesto spesso come domanda di teoria. Dice che qualunque algoritmo può essere realizzato usando solo tre strutture di controllo: sequenza, selezione e iterazione. Lo dimostrarono Corrado Böhm e Giuseppe Jacopini in un articolo pubblicato su Communications of the ACM nel maggio 1966, ed è un teorema italiano. La conseguenza pratica è che l'istruzione goto non serve, da cui nasce la programmazione strutturata. La dimostrazione non ti serve, l'enunciato sì.

---

Conclusioni: bastano tre strutture

Hai visto tre strutture: sequenza, selezione, iterazione. Adesso arriva il teorema che dice che non ti serve altro, e arriva alla fine apposta: prima si vedono le strutture all'opera, poi si scopre che sono tutto.

Teorema di Böhm-Jacopini. Qualunque algoritmo può essere realizzato utilizzando le sole tre strutture di controllo fondamentali: la sequenza, la selezione e l'iterazione.

L'articolo è Flow diagrams, Turing machines and languages with only two formation rules, pubblicato da Corrado Böhm e Giuseppe Jacopini su Communications of the ACM nel maggio 1966. Vale la pena dirlo: il teorema fondativo della programmazione strutturata, quello che sta nella prima pagina di ogni libro di informatica del mondo, porta due cognomi italiani. Böhm, milanese di nascita, nel 1966 era ricercatore del CNR a Roma, all'Istituto Nazionale per le Applicazioni del Calcolo; sarebbe diventato professore solo più tardi, a Torino nel 1970 e poi alla Sapienza nel 1974. Jacopini si era laureato in matematica a Roma proprio sotto la sua guida.

Non ti serve la dimostrazione. Ti serve la conseguenza pratica: se tre strutture bastano per qualunque algoritmo, allora l'istruzione goto, quella che fa saltare l'esecuzione in un punto qualsiasi, non serve a niente. Due anni dopo Edsger Dijkstra scrisse su Communications of the ACM (marzo 1968) la lettera che sconsigliava il goto in modo definitivo, e da lì nacque il rifiuto del "codice spaghetti", quello in cui le frecce vanno dove capita e nessuno riesce più a seguirle. Curiosità che vale un punto se la citi bene: il titolo con cui quella lettera è famosa, Go To Statement Considered Harmful, non è di Dijkstra ma del redattore della rivista. Lui l'aveva intitolata A Case against the GO TO Statement.

Da qui la definizione operativa di programma ben strutturato (nel lessico dei programmi ministeriali, "ben ordinato"): ogni struttura ha un solo ingresso e una sola uscita. È questa proprietà che permette di annidare le strutture come scatole cinesi e di sostituire un blocco con un altro senza rompere il resto. Ed è per questo che una freccia che entra dentro un ciclo dall'esterno è un errore grave e non una stranezza grafica.

Lo schema di una pagina

Glossario minimo

• Esecutore: chi esegue l'algoritmo, uomo o macchina. Le proprietà si definiscono rispetto a lui.
• Istruzione elementare: azione che l'esecutore sa fare senza scomporla.
• Condizione: espressione booleana che vale Vero o Falso, il contenuto del rombo.
• Corpo del ciclo: le istruzioni che vengono ripetute.
• Annidamento: una struttura contenuta dentro un'altra.
• Ben strutturato: programma fatto solo di strutture con un ingresso e un'uscita.
• Tabella di traccia: la tabella con cui esegui l'algoritmo a mano, una riga per passo.

Dove andrai a finire

Lo pseudocodice che hai usato qui si traduce riga per riga in un linguaggio vero:


Restano fuori da questa guida, di proposito: i sottoprogrammi (funzioni e procedure), quarto pilastro della programmazione strutturata e conseguenza pratica del teorema; la ricorsione; la complessità computazionale, cioè come si misura quale fra due algoritmi corretti è il migliore; e soprattutto i vettori, cioè come si lavora su tanti dati insieme invece che su valori singoli, e con essi gli algoritmi di ordinamento e ricerca. È la guida successiva naturale.

Nel frattempo, le due guide sorelle: Algebra di Boole e porte logiche, che spiega che cosa succede davvero dentro il rombo, e Sistemi di numerazione: binario, decimale ed esadecimale, da cui viene l'algoritmo che hai smontato nel paragrafo 8. Lette insieme, le tre valgono più della somma delle parti.