2. Numeri In questa sezione sono presentati dei problemi significativi da risolvere con Python puro o con l’aggiunta della libreria math. Per affrontare i problemi seguenti bisogna conoscere alcuni argomenti presentati nella sezione precedente.

2.1. Operazioni Cosa può fare un calcolatore che sa solo aggiungere o togliere uno

Prerequisiti funzioni con parametri, funzioni che restituiscono un valore, struttura di iterazione: while, Argomenti trattati concetti primitivi dell’aritmetica, algoritmi, grafi e linguaggio cicli. Problema Secondo il lavoro di Peano tutta l’aritmetica può essere derivata da 3 idee primitive: 1. zero 2. numero (naturale) 3. successore e da 5 proposizioni primitive: 1. Zero è un numero. 2. Il successore di ogni numero è un numero. 3. Due numeri non possono avere lo stesso successore. 4. Zero non è il successore di alcun numero. 5. Se lo zero ha una proprietà e per ogni numero che abbia quella proprietà anche il suo successore la ha allora tutti i numeri hanno quella proprietà. Tutta l’aritmetica può quindi essere derivata da questi tre concetti primitivi e da queste poche proposizioni. In particolare la quinta proposizione è detta anche principio di induzione e sta alla base delle definizioni ricorsive. Ispirati da Peano, ci poniamo il problema di stabilire quali siano le operazioni minime che un calcolatore deve saper fare per implementare l’aritmetica dei numeri naturali. Soluzione La soluzione non è unica, possiamo partire da un esecutore che sappia: 1. leggere dati, 2. confrontare un numero con 0, 3. aggiungere 1 a un numero, 4. togliere 1 a un numero, 5. ripetere delle istruzioni fin quando è vera una certa condizione, 6. restituire un risultato, 7. (per la divisione) eseguire porzioni diverse di codice a seconda del risultato di una condizione. Usando il linguaggio Python: 1. Per leggere i dati possiamo usare il meccanismo del passaggio di argomenti ad una funzione dotata di parametri. 2. Per confrontare il numero n con 0 possiamo usare le espressioni: n>0, n>=0 o n==0. 3. Per aggiungere 1 a un numero contenuto nella variabile n possiamo usare a piacere l’istruzione: n=n+1 oppure la più sintetica n+=1, del tutto equivalenti. 4. In modo analogo per togliere 1 possiamo scrivere n=n-1 o n-=1. 5. Per ripetere dei comandi possiamo usare l’istruzione while <condizione>:

<blocco di istruzioni>.

6. Per restituire un risultato usiamo l’istruzione return.

7. Per eseguire diverse porzioni di codice: if <condizione>:

<blocco di istruzioni>

else:

<blocco di istruzioni>

Scriviamo delle funzioni che realizzino le quattro operazioni e il confronto di numeri. Iniziamo dall’addizione. Per addizionare due numeri contenuti in n1 e n2 posso trovare il successore di n1 tante volte quanto è contenuto in n2. Possiamo descrivere così l’algoritmo: definisci la somma di n1 e n2 così:

finquando n2 è maggiore di 0:

aumenta di 1 n1 e diminuisci di 1 n2

alla fine, il risultato è contenuto in n1

La traduzione in Python non dovrebbe presentare grandi difficoltà. Aggiungiamo in fondo al file di programma una procedura test e un comando che viene eseguito quando viene eseguito il file come programma: def test():

t=[(4, 5), (5, 4), (367, 1), (1, 754), (0, 25), (36, 34),

(56, 0), (20, 4), (4, 20), (243, 243), (0, 0), (1, 1)]

for a, b in t:

print “%s+%s=%s” % (a, b, somma(a, b))

if __name__==”__main__”: test()

Per realizzare la funzione prodotto, usando il metodo delle addizioni ripetute, avremo bisogno di una variabile locale che contenga le somme parziali. La descrizione dell’algoritmo potrebbe essere: definisci il prodotto di n1 e n2 così:

in s metti zero fin quando n2 è maggiore di 0:

in s metti la somma di s e n1 diminuisci di 1 n2

alla fine, il risultato è contenuto in s

Per implementare correttamente la funzione quoziente, dobbiamo usare un’altra istruzione Python: l’istruzione if. Infatti non sempre è possibile eseguire le divisioni tra numeri naturali, non è definita una divisione con il divisore uguale a zero. Quindi la funzione quoziente, prima di procedere deve controllare il valore del secondo numero e terminare con un messaggio di errore se è uguale a zero.

Altra caratteristica importante dei numeri è il fatto che possono tutti essere confrontati tra di loro. Usando le solite istruzioni possiamo realizzare le tre funzioni di confronto: maggiore, minore, uguale. Ci sono diversi modi per realizzarle, uno è questo: definisci maggiore n1 di n2 così:

fin quando n2 è maggiore di 0:

diminuisco sia n1 sia n2 di 1

alla fine, il risultato è equivalente a in n1>0

Proviamo ad affrontare il problema con un approccio diverso, chiudiamo questo file e apriamone uno nuovo. Se il nostro esecutore è in grado di gestire funzioni con parametri che restituiscono valori, possiamo fare a meno dell’istruzione while e usare la ricorsione. Abbiamo già osservato come il principio di induzione sia vicino al meccanismo della ricorsione, ora vedremo come scrivere delle definizioni ricorsive e tradurle in funzioni. Una definizione ricorsiva definisce qualcosa nei termini della cosa stessa. Non sempre le definizioni ricorsive funzionano, perché siano accettabili bisogna che trasformino un caso in un caso più semplice e abbiano una condizione di terminazione. Ad esempio: addizionare i due numeri 6 e 3 è equivalente ad addizionare 7 e 2 questo è equivalente ad addizionare 8 a 1 e questo è equivalente ad addizionare 9 a 0. Si può osservare che il secondo addendo diventa sempre più piccolo, il problema diventa più semplice. La condizione di terminazione in questo caso è: la somma di un numero con 0 è il numero stesso. nel caso generale possiamo descrivere la definizione in questo modo:

è n1 se n2=0

somma di n1 e n2 |

altrimenti è somma di (n1+1) con (n2-1)

La traduzione in Python è pressoché letterale: def somma(n1, n2):

“”“somma(n1, n2) -> restituisce la somma n1+n2.”“” if n2==0: return n1 return somma(n1+1, n2-1)

Possiamo osservare che le due righe della definizione si sono tradotte in due righe della funzione. La prima riga della funzione è un commento utile come documentazione. Scrivi anche la procedura di test e controlla il funzionamento corretto della funzione. Se provi questa funzione con numeri molto grandi, Python termina con un errore perché non è in grado di gestire troppe funzioni ricorsive annidate una all’interno dell’altra.

Riassumendo Un Calcolatore può implementare tutta l’aritmetica partendo da poche semplici operazioni. I concetti di successore, predecessore, confronto con zero e iterazione permettono di realizzare l’addizione, la sottrazione, la moltiplicazione e la potenza. Per realizzare la divisione dobbiamo anche controllare che il divisore sia diverso da zero. Le stesse semplici operazioni permettono di realizzare anche il confronto tra numeri. Le operazioni e il confronto possono anche essere definiti in modo ricorsivo. Le definizioni ricorsive risultano molto sintetiche, ed espressive. È facile tradurre definizioni ricorsive in funzioni equivalenti. Il linguaggio Python non tratta le funzioni ricorsive in modo molto efficiente, altri linguaggi lo fanno molto meglio.