Dal problema all’algoritmo

Riepilogo

Questa lezione non contiene codice, e non per distrazione: l’algoritmo precede il programma, e chi non sa descrivere con precisione che cosa si deve fare non saprà dirlo neppure in C++. Prima si insegna a specificare un problema, cioè a dichiarare quali dati riceve, quale risultato deve restituire e quale relazione li lega, e si mostra che uno stesso enunciato ammette specifiche diverse. Poi si definisce l’algoritmo come procedimento finito, preciso e generale, e si scrive in passi numerati quello della divisione per sottrazioni successive. Si insegna a seguire a mano un algoritmo con una tabella di traccia, che sarà per tutto il corso il primo strumento per capire e per fare il debug. Si presentano i tre modi di combinare i passi (sequenza, decisione e ripetizione), con i quali si scrive ogni algoritmo, e si impara a giustificare che una ripetizione termina mediante una quantità che decresce a ogni iterazione e non può scendere indefinitamente.

Obiettivi di apprendimento

Specificare un problema semplice indicandone gli input, gli output e le condizioni che devono soddisfare.
Descrivere un algoritmo in passi numerati, senza ambiguità, con decisioni e ripetizioni esplicite.
Seguire a mano un algoritmo con una tabella di traccia e determinarne il risultato per un input dato.
Distinguere, in un procedimento dato, la sequenza, la decisione e la ripetizione, e giustificare che una ripetizione termina.

Che cos’è un problema computazionale

Un problema computazionale è una relazione fra due categorie di dati: quelli che si ricevono, chiamati input, e quelli che si devono restituire, chiamati output. Risolverlo non consiste nell’ottenere una risposta per un caso, ma nel disporre di un metodo che, per ogni input ammissibile, produca un output che soddisfi la relazione. «Quanto fa 17 diviso 5?» è una domanda; «dati due interi, ottenerne il quoziente e il resto» è un problema, perché parla di tutte le coppie di interi allo stesso tempo.

Ora, il linguaggio comune è impreciso, e lo stesso enunciato può essere inteso in vari modi. Per questo, prima di risolvere, si specifica: si scrive che cosa entra, che cosa esce e quali condizioni deve soddisfare ciascuna cosa. La specifica ha tre parti. L’input elenca i dati con la loro categoria (interi, decimali, parole) e le condizioni che si richiedono loro, che si chiamano precondizione: chi usa la soluzione si impegna a rispettarle. L’output elenca i risultati. La relazione, o postcondizione, dice che cosa deve soddisfare l’output rispetto all’input: chi scrive la soluzione si impegna a garantirla ogni volta che la precondizione sia stata rispettata. Ne segue che la specifica è un contratto fra chi pone il problema e chi lo risolve, e che fuori dalla precondizione la soluzione non promette nulla.

EsempioIl massimo di tre numeri

Enunciato comune: «trovare il maggiore di tre numeri». Specifica:

Input: tre numeri $x$ , $y$ , $z$ (interi o decimali, senza altra condizione).
Output: un numero $m$ .
Relazione: $m$ è uno dei tre dati, e nessuno di essi è maggiore di $m$ ; cioè $m \geq x$ , $m \geq y$ e $m \geq z$ .

La relazione non dice «il maggiore dei tre», che è proprio ciò che si voleva precisare, ma due condizioni verificabili. La prima esige che $m$ sia uno dei dati (senza di essa, il numero 1000 soddisferebbe la seconda per quasi ogni input); la seconda, che nessuno lo superi. E la specifica risolve di passaggio un dubbio che l’enunciato lasciava aperto: se due dati sono a pari merito per il massimo, come in $(4, 9, 9)$ , l’output è $9$ , e non c’è alcun errore in questo.

Uno stesso enunciato ammette specifiche diverse, e scegliere fra di esse è una decisione, non una svista. Il caso più istruttivo è quello della divisione intera. Per interi $a \geq 0$ e $b > 0$ , tutti sono d’accordo: il quoziente $q$ e il resto $r$ sono gli unici interi che soddisfano

a = b \cdot q + r, \quad 0 \leq r < b

Così, per $a = 17$ e $b = 5$ sono $q = 3$ e $r = 2$ , perché $17 = 5 \cdot 3 + 2$ . Ma l’enunciato «dividere due interi» non dice che cosa fare se $a$ è negativo, e la domanda non è oziosa: per $a = -7$ e $b = 2$ ci sono due risposte ragionevoli.

EsempioDue specifiche della divisione con dividendo negativo

Prima specifica: il resto non è mai negativo, $0 \leq r < b$ . Allora $-7 = 2 \cdot (-4) + 1$ , e l’output è $q = -4$ , $r = 1$ . È quella che si studia in matematica, nella lezione «Divisibilità e divisione con resto» del corso Algebra e Geometria I.

Seconda specifica: il quoziente è il risultato della divisione con i decimali, privato della parte decimale, cioè arrotondato verso lo zero; il resto è ciò che manca, e ha il segno del dividendo. Allora $-7 / 2 = -3{,}5$ si tronca a $-3$ , e $-7 = 2 \cdot (-3) + (-1)$ : l’output è $q = -3$ , $r = -1$ .

Entrambe soddisfano $a = b \cdot q + r$ ; differiscono nella condizione che si impone al resto. Nessuna delle due è un errore, ma un programma che ne usi una credendo di usare l’altra darà risultati sbagliati con i negativi. Anticipiamo un dato: C++ adotta la seconda, come si vedrà nella lezione Aritmetica; chi si aspetta la prima avrà una sorpresa.

C’è una terza opzione, che è la più frequente nella pratica: escludere il caso con la precondizione. Se la specifica esige $a \geq 0$ , il problema dei negativi scompare, non perché sia stato risolto, ma perché chi usa la soluzione si è impegnato a non porlo. Ciò che non si può fare è lasciare la questione indecisa. E per la stessa ragione la specifica esige $b > 0$ : con $b = 0$ non esistono $q$ e $r$ che soddisfino la relazione, e il contratto deve dirlo.

Un errore frequente consiste nello specificare con un esempio: «l’output di 17 e 5 è 3 e 2». Un esempio illustra, ma non specifica, perché non dice che cosa accade con gli altri input; infinite relazioni diverse coincidono su un caso. La specifica si scrive come condizione generale, e gli esempi servono poi a verificarla.

Algoritmi

Una volta specificato il problema, si cerca un metodo per risolverlo. Un algoritmo è una sequenza di istruzioni che, applicata a qualunque input che soddisfi la precondizione, produce in un numero finito di passi un output che soddisfa la postcondizione. La definizione contiene tre requisiti.

Finitezza. L’algoritmo si scrive con un numero finito di istruzioni e, per ogni input ammissibile, termina dopo averne eseguito un numero finito. Un procedimento che per qualche input continua per sempre non è un algoritmo per quell’input.
Precisione. Ogni istruzione ha un unico significato, e chi la esegue sa in ogni momento che cosa fare e qual è l’istruzione successiva. Nessuna decisione è lasciata al giudizio di chi esegue.
Generalità. L’algoritmo risolve il problema per tutti gli input ammissibili, non solo per un caso.

Con una certa libertà, si chiama algoritmo anche un procedimento preciso e che termina, ma che per qualche input ammissibile non soddisfa la postcondizione: a rigore è un algoritmo per un altro problema, e si dirà che è scorretto per il problema specificato. Così si parlerà nei problemi di questa lezione, che confutano algoritmi scorretti con un controesempio.

Una ricetta di cucina somiglia a un algoritmo, ed è per questo il paragone abituale; ma quasi nessuna lo è. «Aggiungere un pizzico di sale» non è preciso, perché un pizzico non è una quantità; «cuocere in forno finché non è dorato» dipende da un giudizio che due persone darebbero in modo diverso; «sbattere varie volte» non dice quante. Un cuoco colma queste lacune con la sua esperienza; un computer non ne ha nessuna. Ne segue il requisito che governa tutto il corso: un algoritmo deve poter essere seguito da chi non capisce il problema, senza indovinare nulla. Se per eseguire un passo bisogna sapere a che cosa serve, il passo è scritto male.

Gli algoritmi di questo corso si scrivono prima in passi numerati, in italiano, con alcune convenzioni. I dati che cambiano durante l’algoritmo si indicano con lettere o parole, come $q$ o $r$ , e si chiamano variabili. Si scrive « $r$ assume il valore $r - b$ » per dire che si calcola $r - b$ con il valore attuale di $r$ e il risultato diventa il nuovo valore di $r$ ; il valore precedente si perde. Nella forma abbreviata, che si usa quando si prendono appunti, la stessa istruzione si scrive con una freccia verso sinistra, che sulla tastiera è r <- r - b. Le istruzioni si eseguono nell’ordine del loro numero, salvo che una di esse dica altrimenti.

EsempioLa divisione per sottrazioni successive

Il problema è quello specificato nella sezione precedente: input, due interi $a \geq 0$ e $b > 0$ ; output, due interi $q$ e $r$ con $a = b \cdot q + r$ e $0 \leq r < b$ . L’idea è quella di ripartire: si tolgono da $a$ gruppi di $b$ finché è possibile, si contano i gruppi tolti, e ciò che avanza è il resto.

$q$ assume il valore $0$ , e $r$ assume il valore $a$ .
Finché vale $r \geq b$ , ripeti i passi 3 e 4; quando smette di valere, prosegui al passo 5.
$r$ assume il valore $r - b$ .
$q$ assume il valore $q + 1$ ; torna al passo 2.
Restituisci $q$ e $r$ , e termina.

Il passo 2 è una domanda che si pone ogni volta: prima della prima iterazione e dopo ciascuna. I passi 3 e 4 formano il corpo della ripetizione, ciò che si ripete. Nulla è lasciato al giudizio di chi esegue: in ogni momento c’è una sola istruzione successiva.

L’algoritmo è lento (per dividere un milione per tre compie più di trecentomila iterazioni), e il metodo scolastico della divisione è molto più rapido; ma è corretto, e la sua semplicità lo rende ideale per imparare a ragionare sugli algoritmi. Il corso tornerà sulla differenza fra un algoritmo corretto e uno efficiente nella lezione Il costo di un algoritmo.

Conviene, infine, separare l’algoritmo dalla sua scrittura. L’algoritmo della divisione per sottrazioni è lo stesso se lo si scrive in italiano, in un diagramma, in C++ o in qualunque altro linguaggio di programmazione: ciò che lo definisce è la sequenza delle operazioni, non le parole. Un programma è la scrittura di un algoritmo in un linguaggio che una macchina può eseguire, e la lezione Programmi, compilatori e C++ spiegherà come avviene questa esecuzione. Se è così, un programma può essere sbagliato in due modi molto diversi: perché l’algoritmo è scorretto, e allora nessun linguaggio lo salva, oppure perché l’algoritmo è corretto ma è stato scritto male. Distinguere i due casi è metà del lavoro di debugging, ed è per questo che il corso scrive sempre prima l’algoritmo.

Seguire un algoritmo a mano

Leggere un algoritmo non basta per sapere che cosa fa; bisogna eseguirlo. Seguirlo a mano, come farebbe la macchina, senza saltare passi né indovinare risultati, è l’abilità più utile di un programmatore: con essa si verifica un algoritmo prima di scriverlo, si prevede l’output di un programma prima di eseguirlo e si trova l’errore di uno che non funziona.

Lo strumento è la tabella di traccia: una colonna per il numero del passo che si esegue, una colonna per ogni variabile e, se conviene, una per le condizioni che si valutano; e una riga per ogni passo eseguito. In ogni riga si annota il nuovo valore della variabile che è cambiata in quel passo e si lascia in bianco ciò che non è cambiato, in modo che il valore attuale di una variabile sia l’ultimo scritto nella sua colonna. Le condizioni si annotano con il loro risultato.

EsempioLa traccia della divisione di 17 per 5

Seguiamo la divisione per sottrazioni successive con $a = 17$ e $b = 5$ . La freccia della figura indica il passo appena eseguito; la linea tratteggiata ricorda che il passo 4 torna al 2.

Dimostrazione

$(q, r) = (0, 17)$
Passo 1: si danno i valori iniziali. L’input soddisfa la precondizione, perché $17 \geq 0$ e $5 > 0$ .
$(q, r) = (1, 12)$
Prima iterazione. Nel passo 2 si verifica che $17 \geq 5$ , quindi si esegue il corpo: il passo 3 toglie un gruppo di cinque e il passo 4 lo conta.
$(q, r) = (2, 7)$
Seconda iterazione: $12 \geq 5$ , e il corpo si esegue di nuovo.
$(q, r) = (3, 2)$
Terza iterazione: $7 \geq 5$ , e il corpo si esegue di nuovo.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
Nel passo 2 la condizione non è soddisfatta, perché $2 < 5$ : l’algoritmo prosegue al passo 5 e restituisce $q = 3$ e $r = 2$ . L’output soddisfa la postcondizione.

La tabella completa ha dodici righe: il passo 1, tre iterazioni di tre righe ciascuna (passi 2, 3 e 4), la verifica che fallisce e la restituzione.

Due osservazioni sulla tabella. La prima: il numero di iterazioni è uguale al quoziente, $3$ , e il passo 2 è stato eseguito una volta più del corpo, $4$ volte; ciò accade sempre in una ripetizione di questa forma, perché l’ultima verifica è quella che fallisce. La seconda: la traccia insegna qualcosa che il testo dell’algoritmo non dice a prima vista; se $a < b$ , per esempio $a = 3$ e $b = 5$ , la condizione fallisce la prima volta, il corpo non si esegue nessuna volta, e l’output è $q = 0$ , $r = 3$ , che è corretto, perché $3 = 5 \cdot 0 + 3$ . Dimenticare il caso in cui la ripetizione non si esegue è uno degli errori più frequenti nel progettare algoritmi, e la traccia con input piccoli lo scopre.

La traccia di un caso non dimostra che l’algoritmo sia corretto: verifica un caso. Ma una traccia ben scelta (un caso comune, un caso limite, il caso in cui la ripetizione non si esegue) scopre la maggior parte degli errori, e quella che fallisce dice dove sono. La lezione Progettare cicli corretti insegnerà a passare dai casi a una dimostrazione.

Sequenza, decisione e ripetizione

Visti da vicino, gli algoritmi si costruiscono con pochissimi pezzi. Ci sono istruzioni elementari (dare un valore a una variabile, restituire un risultato) e tre modi di combinarle.

Sequenza: un’istruzione dopo l’altra, in ordine. I passi 3 e 4 della divisione sono una sequenza: prima si sottrae, poi si conta.
Decisione: a seconda che una condizione sia soddisfatta o no, si esegue una parte o un’altra (oppure una parte o niente). «Se $y > m$ , $m$ assume il valore $y$ » è una decisione.
Ripetizione: finché una condizione è soddisfatta, si esegue una parte ancora e ancora. Il passo 2 della divisione, con il suo corpo, è una ripetizione.

Ogni forma ha un solo ingresso e una sola uscita, e il suo interno può essere a sua volta una qualunque delle tre: il corpo di una ripetizione può contenere decisioni, un ramo di una decisione può contenere una ripetizione, e così via. Se è così, con le tre forme si costruiscono algoritmi di qualunque complessità, come con pochi pezzi che si incastrano fra loro si costruisce qualunque edificio. Che bastino a esprimere ogni algoritmo è un risultato noto della teoria della programmazione (lo dimostrarono Corrado Böhm e Giuseppe Jacopini nel 1966); qui non lo si dimostra, ma tutto il corso lo conferma: i programmi che vi si scriveranno, per quanto lunghi siano, non useranno altro che queste tre forme, scritte in C++ come if per la decisione e while o for per la ripetizione, nelle lezioni Decisioni e Cicli.

Una notazione utile per vedere la forma di un algoritmo è il diagramma di flusso: ogni istruzione è un rettangolo, ogni condizione un rombo con due uscite (soddisfatta, che la figura etichetta $1$ , e non soddisfatta, $0$ ), e le frecce dicono qual è il passo successivo. È una notazione, non un fine: serve a cogliere con un colpo d’occhio un algoritmo piccolo, ma non scala, e nessuno scrive un programma grande disegnandolo.

EsempioTre forme e la loro composizione

La figura disegna le tre forme con istruzioni generiche $A$ e $B$ e una condizione $c$ , e poi le compone nel diagramma della divisione per sottrazioni successive.

Dimostrazione

$A ; B$
Sequenza: si esegue $A$ e poi $B$ ; c’è un solo ingresso e una sola uscita.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Decisione: se $c$ è soddisfatta, si esegue $A$ ; altrimenti, $B$ . Entrambi i rami si riuniscono in una sola uscita.
$c, A, c, A, \ldots, c$
Ripetizione: si valuta $c$ ; se è soddisfatta, si esegue $A$ e si torna a valutare $c$ ; altrimenti, si esce. La condizione si valuta una volta più del corpo.
$a = b \cdot q + r, \quad 0 \leq r < b$
Composizione: la divisione per sottrazioni successive è una sequenza (i valori iniziali, la ripetizione, la restituzione) la cui ripetizione ha per corpo un’altra sequenza (sottrarre, contare).

Distinguere le tre forme in un procedimento scritto in linguaggio comune è il primo passo per tradurlo. Il segnale di una decisione è un «se», un «nel caso in cui» o un «a seconda di»; quello di una ripetizione, un «finché», un «fino a quando», un «per ogni» o un «tante volte quante». Un procedimento senza nessuna di queste parole è una sequenza, e se deve trattare input di dimensione variabile (una lista di numeri, un testo), gli manca una ripetizione.

Termina?

La finitezza fa parte della definizione di algoritmo, e una ripetizione è l’unico luogo in cui può perdersi: una sequenza di cinque passi esegue cinque passi, e una decisione esegue uno dei suoi rami; ma una ripetizione esegue il suo corpo tante volte quante la condizione è soddisfatta, e nulla garantisce in anticipo che smetta di esserlo.

Per giustificare che una ripetizione termina si cerca una quantità, calcolata con le variabili, che soddisfi due condizioni: è un numero naturale (intero e non negativo) finché la ripetizione continua, e decresce strettamente a ogni iterazione. Se è così, la ripetizione termina: una successione di naturali strettamente decrescente non può essere infinita, perché ogni iterazione la abbassa almeno di uno e da un naturale $n$ non ci sono più di $n$ gradini fino allo zero. Tale quantità si chiama variante o funzione limitante, e la lezione Progettare cicli corretti la userà in modo sistematico.

EsempioLa variante della divisione per sottrazioni

Nella divisione per sottrazioni successive, la variante è $r$ . Finché la ripetizione continua, $r \geq b > 0$ , quindi $r$ è un naturale. A ogni iterazione, $r$ assume il valore $r - b$ , e poiché $b > 0$ (precondizione), il nuovo valore è strettamente minore. Pertanto la ripetizione termina, e lo fa al più dopo $a$ iterazioni (di fatto, esattamente dopo $q$ iterazioni, il quoziente).

Si osservi dove si è usata la precondizione $b > 0$ . Se si esegue l’algoritmo con $b = 0$ , il passo 3 lascia $r$ invariato, la condizione $r \geq 0$ è sempre soddisfatta e la ripetizione non termina mai: l’algoritmo non è sbagliato, ma ha ricevuto un input che il contratto escludeva. E se $b$ fosse negativo, $r$ crescerebbe a ogni iterazione. La precondizione non è un ornamento: è esattamente ciò che serve perché il ragionamento funzioni.

Le due condizioni della variante sono necessarie, ed è facile sbagliare su una qualunque delle due. Si consideri questo procedimento, che pretende di decidere se un naturale $n$ è pari: «finché $n \neq 0$ , $n$ assume il valore $n - 2$ ; se si arriva allo zero, $n$ era pari». La quantità $n$ decresce a ogni iterazione, eppure il procedimento non termina se $n$ è dispari: con $n = 5$ passa per $3$ , $1$ , $-1$ , $-3$ , e la condizione $n \neq 0$ non fallisce mai. Ciò che non è soddisfatto è l’altra condizione: $n$ smette di essere naturale, perché la condizione della ripetizione non gli impedisce di scendere sotto lo zero. La correzione consiste nel ripetere finché $n \geq 2$ e nel decidere alla fine secondo il valore che rimane, $0$ o $1$ ; ora $n$ è naturale a ogni iterazione, perché si sottrae solo quando $n \geq 2$ , e decresce: il procedimento termina.

Decidere se una ripetizione termina non è sempre facile. Un esempio celebre: partendo da un naturale $n \geq 1$ , finché $n \neq 1$ , se $n$ è pari lo si divide per due, e se è dispari lo si sostituisce con $3n + 1$ . Con $n = 6$ la successione è $6, 3, 10, 5, 16, 8, 4, 2, 1$ , e termina. Nessuno ha trovato un $n$ per cui non termini, e lo si è verificato con i computer per quantità enormi di valori; ma nessuno è riuscito a dimostrare che termini sempre: è la congettura di Collatz, un problema aperto della matematica. Nessuna quantità nota decresce a ogni iterazione. La morale per chi programma è modesta e ferma: un algoritmo di cui non si sa giustificare la terminazione non è finito.

Errori frequenti

Passi ambigui. «Ripetere varie volte», «finché va bene», «prendere un numero adeguato». Ogni passo deve poter essere eseguito senza capire il problema; altrimenti, è scritto male.
Dimenticare il caso in cui la ripetizione non si esegue. Ogni ripetizione con la condizione all’inizio può eseguire il suo corpo zero volte. Bisogna chiedersi sempre che cosa restituisce l’algoritmo in quel caso, e la traccia con un input minimo lo dice.
Specificare con un esempio. «Per 17 e 5 dà 3 e 2» non è una specifica; la relazione si scrive come condizione generale, e l’esempio la illustra.
Confondere l’algoritmo con il suo programma. Un programma che non funziona può avere sbagliato l’algoritmo o la sua scrittura. Chi non ha scritto prima l’algoritmo non sa quale delle due cose cercare.
Dare per scontata la terminazione. Che una quantità decresca non basta: deve essere inoltre naturale finché si ripete.

Problemi risolti

Problema risolto 1Il maggiore di tre numeri, con pari merito

Scrivere un algoritmo che soddisfi la specifica del massimo di tre numeri della prima sezione, e seguirlo a mano per gli input $(7, 2, 5)$ e $(4, 9, 9)$ .

Soluzione

$m = x$
Idea: si percorre l’input conservando il maggiore visto finora in una variabile $m$ . Primo passo: $m$ assume il valore $x$ . Dopo di esso, $m$ è il massimo dei dati visti, che sono solo $x$ .
$m = \max(x, y, z)$
Secondo passo: se $y > m$ , $m$ assume il valore $y$ . Terzo passo: se $z > m$ , $m$ assume il valore $z$ . Quarto passo: restituire $m$ . Sono tre istruzioni in sequenza, due delle quali decisioni senza ramo alternativo.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Traccia per $(7, 2, 5)$ : dopo il primo passo $m = 7$ ; nel secondo, $2 > 7$ è falso e $m$ non cambia; nel terzo, $5 > 7$ è falso e $m$ non cambia. Si restituisce $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Traccia per $(4, 9, 9)$ : dopo il primo passo $m = 4$ ; nel secondo, $9 > 4$ e $m$ passa a valere $9$ ; nel terzo, $9 > 9$ è falso e $m$ non cambia. Si restituisce $9$ , che è corretto: il pari merito non richiede un trattamento a parte.
$m \geq x, \quad m \geq y, \quad m \geq z$
Giustificazione: dopo ogni passo, $m$ è uno dei dati visti e nessuno di essi lo supera. È vero dopo il primo, e ogni decisione lo conserva: se il dato nuovo è maggiore, diventa $m$ ; altrimenti, non supera $m$ . Alla fine sono stati visti tutti e tre, e $m$ soddisfa la postcondizione.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Se si fosse scritto $y \geq m$ al posto di $y > m$ , il risultato sarebbe lo stesso, perché in caso di pari merito si assegna un valore uguale. La scelta fra $>$ e $\geq$ avrebbe importanza se si chiedesse anche la posizione del massimo: con $>$ si restituisce la prima delle posizioni a pari merito, e con $\geq$ l’ultima; la formula chiama la posizione $p$ .

Problema risolto 2L’anno bisestile, corretto con un controesempio

Nel calendario gregoriano, un anno è bisestile se è divisibile per $4$ , salvo quelli divisibili per $100$ , che lo sono solo se sono anche divisibili per $400$ . Uno studente propone l’algoritmo «se l’anno è divisibile per $4$ , restituire sì; altrimenti, restituire no». Trovare un anno in cui fallisce e scrivere un algoritmo corretto, con la sua specifica.

Soluzione

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Specifica. Input: un intero $n \geq 1583$ (il calendario gregoriano è in vigore dall’ottobre 1582). Output: sì o no. Relazione: l’output è sì esattamente quando $n$ è divisibile per $4$ e non per $100$ , oppure è divisibile per $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
L’algoritmo proposto indovina nella maggior parte degli anni, e per questo sembra corretto. Per confutarlo basta un anno divisibile per $100$ e non per $400$ : $1900$ è divisibile per $4$ , e l’algoritmo dice sì; ma il $1900$ non fu bisestile.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Algoritmo corretto, in tre decisioni concatenate. Passo 1: se $n$ è divisibile per $400$ , restituire sì e terminare. Passo 2: se $n$ è divisibile per $100$ , restituire no e terminare. Passo 3: se $n$ è divisibile per $4$ , restituire sì; altrimenti, restituire no.
$2000, \quad 1900, \quad 2024, \quad 2023$
L’ordine delle domande è essenziale: vanno dalla regola più particolare alla più generale. Se si chiedesse prima della divisibilità per $4$ , l’anno $1900$ riceverebbe sì prima di arrivare all’eccezione. Traccia per quattro anni, uno per ciascun caso: $2000$ (passo 1: sì), $1900$ (passo 2: no), $2024$ (passo 3: sì), $2023$ (passo 3: no).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
L’insegnamento non riguarda solo i calendari: un algoritmo si confuta con un solo controesempio, e i controesempi si cercano ai bordi delle regole, non nei casi comuni. Provare con $2024$ , $2020$ e $2016$ non avrebbe scoperto nulla.

Problema risolto 3Quante iterazioni compie la divisione per sottrazioni

Seguire a mano la divisione per sottrazioni successive con $a = 20$ e $b = 5$ , e con $a = 0$ e $b = 7$ . Poi giustificare che per ogni input ammissibile l’algoritmo termina dopo esattamente $q$ iterazioni e che il suo output soddisfa la postcondizione.

Soluzione

$20 = 5 \cdot 4 + 0$
Traccia con $a = 20$ , $b = 5$ : $r$ passa per $20$ , $15$ , $10$ , $5$ , $0$ , e $q$ per $0$ , $1$ , $2$ , $3$ , $4$ . La quinta verifica, $0 \geq 5$ , fallisce. Output: $q = 4$ , $r = 0$ . Qui il caso limite è la divisione esatta: la quarta iterazione avviene perché $5 \geq 5$ , ed è per questo che la condizione deve essere $\geq$ e non $>$ .
$0 = 7 \cdot 0 + 0$
Traccia con $a = 0$ , $b = 7$ : la prima verifica, $0 \geq 7$ , fallisce; il corpo non si esegue nessuna volta. Output: $q = 0$ , $r = 0$ , che è corretto.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Una relazione che si conserva. Prima della prima iterazione, $b \cdot q + r = b \cdot 0 + a = a$ . A ogni iterazione $r$ diminuisce di $b$ e $q$ aumenta di $1$ , quindi $b \cdot q + r$ non cambia. Pertanto l’uguaglianza vale dopo ogni iterazione.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Terminazione. Finché si ripete, $r \geq b > 0$ , e $r$ è un naturale; a ogni iterazione diminuisce di $b \geq 1$ . Una successione strettamente decrescente di naturali è finita: la ripetizione termina.
$a = b \cdot q + r, \quad 0 \leq r < b$
Al termine, la condizione è fallita: $r < b$ . Inoltre $r \geq 0$ , perché si sottrae $b$ solo quando $r \geq b$ . Insieme alla relazione che si conserva, l’output soddisfa la postcondizione; e poiché $q$ conta le iterazioni, il numero di iterazioni è il quoziente.

Esercizi in linea

Esercizio 1Contare le iterazioni

Seguire a mano l’algoritmo seguente e scrivere nella casella il valore che restituisce, solo il numero.

$n$ assume il valore $29$ , e $k$ assume il valore $0$ .
Finché vale $n > 1$ , ripeti i passi 3 e 4; quando smette di valere, prosegui al passo 5.
Se $n$ è pari, $n$ assume il valore $n / 2$ ; se è dispari, $n$ assume il valore $n + 1$ .
$k$ assume il valore $k + 1$ ; torna al passo 2.
Restituisci $k$ .

Il browser controlla la tua risposta all’istante, senza valutarla.

Scrivi qui la tua risposta

Suggerimento

Fai la tabella: $n$ passa da $29$ a $30$ nella prima iterazione. Conta un’iterazione per ogni cambio di $n$ , finché $n$ non vale $1$ .

Esercizio 2La condizione che manca

L’algoritmo seguente, scritto nella forma abbreviata, deve calcolare il quoziente e il resto della divisione per sottrazioni successive, ma gli manca la condizione della ripetizione. Sostituire la riga di trattini bassi con la condizione corretta, senza cambiare il resto.

Il browser controlla la tua risposta all’istante, senza valutarla.

Scrivi qui la tua risposta

Suggerimento

Segui a mano l’algoritmo con $a = 10$ e $b = 5$ : la seconda iterazione deve avvenire anche se il resto vale esattamente $5$ .

Problemi proposti

Ogni problema ha un suggerimento, che conviene aprire solo dopo averlo tentato, e una risposta, che compare dopo aver aperto il suggerimento.

Problema proposto 1Specificare l’ordine di tre numeri

Scrivere la specifica del problema «ordinare tre numeri» (input, output e relazione) e indicare quali decisioni, non prese dall’enunciato, essa obbliga a prendere. Poi verificare che la specifica scarta questi due output per l’input $(5, 2, 5)$ : $(2, 5, 6)$ e $(2, 5, 5, 5)$ , e che ammette $(2, 5, 5)$ .

Suggerimento

Un output «ordinato» può non avere nulla a che fare con l’input. Quale condizione lega i numeri dell’output a quelli dell’input, compresi quelli ripetuti? Crescente o decrescente? Stretto o no?

Risposta

Input: tre numeri $x$ , $y$ , $z$ . Output: tre numeri $u$ , $v$ , $w$ . Relazione: $u \leq v \leq w$ , e $(u, v, w)$ è un riordinamento di $(x, y, z)$ , cioè contiene gli stessi valori con le stesse ripetizioni. Decisioni che l’enunciato non prendeva: il verso (qui, dal minore al maggiore); che l’ordine non è stretto ( $\leq$ e non $<$ , perché con valori ripetuti l’ordine stretto è impossibile); e che l’output deve essere un riordinamento. $(2, 5, 6)$ è ordinato ma contiene un $6$ che non c’era; $(2, 5, 5, 5)$ ha quattro valori; $(2, 5, 5)$ soddisfa entrambe le condizioni. Senza la condizione di riordinamento, $(0, 0, 0)$ sarebbe un output corretto per qualunque input.

Problema proposto 2Le cifre di un numero, da destra a sinistra

Scrivere un algoritmo in passi numerati che riceva un naturale $n$ e ne restituisca le cifre dall’ultima alla prima (per $4072$ , restituisce $2$ , $7$ , $0$ , $4$ ), usando solo il quoziente e il resto della divisione per $10$ . Seguirlo a mano per $4072$ e per $0$ , e giustificare che termina per ogni $n$ .

Suggerimento

Il resto della divisione per $10$ è l’ultima cifra, e il quoziente è il numero senza di essa. Decidi se la condizione si chiede prima o dopo aver restituito una cifra, e guarda che cosa accade con $n = 0$ , che ha una cifra.

Risposta

Un algoritmo corretto: (1) restituire il resto della divisione di $n$ per $10$ ; (2) $n$ assume il valore del quoziente della divisione di $n$ per $10$ ; (3) se $n > 0$ , tornare al passo 1; altrimenti, terminare. La domanda viene dopo il corpo, quindi il corpo si esegue almeno una volta: per $n = 0$ restituisce $0$ , che è la sua unica cifra. Se si chiedesse all’inizio («finché $n > 0$ »), per $n = 0$ non si restituirebbe nulla; è l’errore di dimenticare il caso in cui la ripetizione non si esegue. Traccia per $4072$ : si restituiscono $2$ , $7$ , $0$ , $4$ , e $n$ passa per $407$ , $40$ , $4$ , $0$ . Terminazione: la variante è $n$ , un naturale; se si torna al passo 1 è perché $n > 0$ , e per $n \geq 1$ il quoziente per $10$ è strettamente minore di $n$ , quindi $n$ decresce strettamente a ogni iterazione.

Problema proposto 3Il resto in monete

Si dispone di monete da $50$ , $10$ e $1$ unità, in quantità illimitata. Specifica: input, un naturale $m$ ; output, tre naturali $c_{50}$ , $c_{10}$ , $c_1$ con $50 c_{50} + 10 c_{10} + c_1 = m$ e la minor quantità possibile di monete, $c_{50} + c_{10} + c_1$ . Una persona propone l’algoritmo seguente. Trovare un input in cui fallisce, spiegare ogni difetto e correggerlo.

$c_{50}$ , $c_{10}$ e $c_1$ assumono il valore $0$ .
Se $m \geq 50$ , $c_{50}$ assume il valore $c_{50} + 1$ e $m$ assume il valore $m - 50$ .
Finché $m > 10$ : $c_{10}$ assume il valore $c_{10} + 1$ e $m$ assume il valore $m - 10$ .
Finché $m > 0$ : $c_1$ assume il valore $c_1 + 1$ e $m$ assume il valore $m - 1$ .
Restituisci $c_{50}$ , $c_{10}$ e $c_1$ .

Suggerimento

La somma delle monete è sempre $m$ ; ciò che può fallire è la quantità. Prova un multiplo esatto di $10$ e un importo superiore a $100$ , e chiediti quale modo di combinare i passi usa il passo 2 e quale dovrebbe usare.

Risposta

Ci sono due difetti. Primo, il passo 3 usa $m > 10$ : con $m = 10$ non restituisce nessuna moneta da $10$ e ne restituisce dieci da $1$ , invece di una. Secondo, il passo 2 è una decisione dove serve una ripetizione: con $m = 120$ , l’algoritmo così com’è scritto restituisce una moneta da $50$ , sei da $10$ e dieci da $1$ (diciassette monete), e anche con il passo 3 già corretto ne restituirebbe una da $50$ e sette da $10$ (otto), invece di due da $50$ e due da $10$ (quattro). L’input $m = 100$ mostra entrambi i difetti: l’algoritmo restituisce una moneta da $50$ , quattro da $10$ e dieci da $1$ , quindici monete, invece di due. Correzione: passo 2, «finché $m \geq 50$ , …»; passo 3, «finché $m \geq 10$ , …». Così corretto, l’algoritmo prende sempre la moneta più grande che ci sta, e con queste tre monete ciò dà la quantità minima: la cifra delle unità di $m$ si può pagare solo con monete da $1$ , e di ciò che resta conviene pagare con monete da $50$ tutto il possibile, perché cinque da $10$ valgono quanto una da $50$ . Con altre monete, per esempio da $1$ , $3$ e $4$ per $m = 6$ , prendere sempre la più grande non dà più il minimo ( $4 + 1 + 1$ contro $3 + 3$ ).