2.3. Criteri di divisibilità Dove si insegna a Python a utilizzare i criteri di divisibilità. Prerequisiti funzioni con parametri, struttura di selezione: if ..else, struttura di iterazione: while, dati: numeri, stringhe e liste.

Argomenti trattati i criteri di divisibilità, conversioni da numero a stringa e viceversa, costruzione di liste, ricorsione.

Problema Scrivere una libreria di funzioni che implementi i criteri di divisibilità dei numeri naturali. La funzione div2(n) deve verificare che il numero n sia divisibile per 2 e restituire True se n è pari e False se non lo è. Devo poter dare i seguenti comandi ottenendo le risposte corrette: >>> print div2(5) False >>> print div2(613264) True >>> print div5(64343) False ...

Soluzione Ovviamente per prima cosa bisogna conoscere i criteri di divisibilità, ne riporto, di seguito una possibile definizione, i libri li spiegano molto meglio... Divisibilità per 2: i seguenti numeri sono divisibili per 2: 0, 2, 4, 6, 8, un numero è divisibile per 2 se la sua ultima cifra è un numero divisibile per 2. Divisibilità per 4: i seguenti numeri sono divisibili per 4: 0, 4, 8, 12, 16, un numero è divisibile per 4 se lo è anche il numero che si ottiene togliendo 20 un numero è divisibile per 4 se le sue ultime 2 cifre formano un numero divisibile per 4. Divisibilità per 8: i seguenti numeri sono divisibili per 8: 0, 8, 16, 24, 32 un numero è divisibile per 8 se lo è anche il numero che si ottiene togliendo 40 un numero è divisibile per 8 se le sue ultime 3 cifre formano un numero divisibile per 8. Divisibilità per 5: i seguenti numeri sono divisibili per 5: 0, 5, un numero è divisibile per 5 se la sua ultima cifra è un numero divisibile per 5. Divisibilità per 25: i seguenti numeri sono divisibili per 25: 0, 25, 50, 75, un numero è divisibile per 25 se le sue ultime 2 cifre formano un numero divisibile per 25. Divisibilità per 10: un numero è divisibile per 10 se la sua ultima cifra è 0. Divisibilità per 100: un numero è divisibile per 100 se le sue ultime 2 cifre formano il numero 0. Divisibilità per 3: i seguenti numeri sono divisibili per 3: 0, 3, 6, 9, un numero è divisibile per 3 se la somma delle sue cifre è un numero divisibile per 3. Divisibilità per 9: i seguenti numeri sono divisibili per 9: 0, 9, un numero è divisibile per 9 se la somma delle sue cifre è un numero divisibile per 9. Divisibilità per 11: i seguenti numeri sono divisibili per 11: 0, 11, un numero è divisibile per 11 se la differenza della somma delle sue cifre di posto pari e la somma delle sue cifre di posto dispari è un numero divisibile per 11. Divisibilità per 7: i seguenti numeri sono divisibili per 7: 0, 7, un numero è divisibile per 7 se la differenza tra doppio dell’ultima cifra e il numero formato dalle altre cifre è un numero divisibile per 7. Tutte le definizioni date sopra sono ricorsive, ma le funzioni che faremo non utilizzeranno questa tecnica. Il criterio più semplice è quello della divisibilità per 2, è semplice, ma richiede di poter estrarre da un numero, il numero formato dalla sua ultima cifra. Quindi, prima di affrontare il criterio, dobbiamo scrivere una funzione che dato un numero restituisca il numero formato dalla sua ultima cifra, cioè che funzioni così: >>> print destra1(743843) 3 Un metodo, può essere questo: trasformo un numero in stringa con il comando str(<numero>) prendo il carattere più a destra <stringa>[-1] lo trasformo in numero con il comando int(<stringa>) restituisco questo numero con il comando return <valore> La funzione potrebbe essere: def destra1(numero):

“”“destra1(numero) -> ultima cifra del numero.”“” numero_in_stringa=str(numero) ultimo_carattere=numero_in_stringa[-1] risultato=int(ultimo_carattere) return risultato

Alcune osservazioni: 1. la funzione destra1 ha un parametro che si chiama numero e che conterrà il numero da cui trarre l’ultima cifra. 2. La prima riga dopo l’intestazione della funzione è un commento che dovrebbe ricordare a noi, o spiegare a chi usa la funzione, qual è l’effetto di questo pezzo di codice. 3. Ho usato parecchie variabili cercando di dare loro dei nomi abbastanza espliciti. 4. Ogni funzione usata modifica il valore assegnato all’ultima variabile.

L’ultima osservazione permette di riscrivere il pezzo di codice precedente usando il paradigma funzionale, qualcosa del genere: Restituisci - la trasformazione in intero - dell’ultimo carattere - della stringa ottenuta dal numero. return int(str(numero)[-1]) La funzione diventa quindi: def destra1(numero):

“”“destra1(numero) -> ultima cifra del numero.”“” return int(str(numero)[-1])

Dopo aver eseguito il file che contiene la funzione (tasto <F5>), nell’ambiente IDLE si può provarla con diversi valori: >>> print destra1(65326432) 2 >>> print destra1(8676) 6 ... Ora abbiamo lo strumento per risolvere il criterio di divisibilità per 2 (e quali altri?). La funzione dovrà implementare questa logica: se l’ultima cifra del numero è 0 o 2 o 4 o 6 o 8 restituisci True altrimenti restituisci False La funzione potrebbe quindi essere: def div2(n):

“”“n e’ divisibile per 2.”“” if (destra1(n)==0 or destra1(n)==2 or

destra1(n)==4 or destra1(n)==6 or destra1(n)==8):

return True

else:

return False

Alcune osservazioni: 1. La funzione rispecchia letteralmente quanto progettato. 2. La funzione destra1(n) viene chiamata 5 volte per dare sempre lo stesso risultato, questo non è efficiente! 3. Si può fare a meno dell’istruzione if.

Per ovviare al problema del punto 2 si potrebbe usare una variabile e chiamare la funzione destra1(n) una sola volta, migliorerebbe l’efficienza. Ma Python ci mette a disposizione un altro strumento che rende il codice ancora più leggibile: destra1(n) in (0, 2, 4, 6, 8) Che verifica se l’ultima cifra di n è contenuta nella “tupla” (0, 2, 4, 6, 8). E dato che questa espressione dà come risultato un valore vero o falso, non abbiamo bisogno di usare l’istruzione if ma basta che la funzione restituisca esattamente questo valore. La funzione diventa quindi: def div2(n):

“”“n e’ divisibile per 2.”“” return destra1(n) in (0, 2, 4, 6, 8)

Nota: la concisione e la leggibilità sono caratteristiche importanti nella programmazione! Per completare l’opera possiamo costruire una funzione “test” che metta alla prova div2. La possiamo fare in molti modi diversi. Io ho pensato di provare con 5 casi di numeri divisibili per 2 e 5 di numeri non divisibili per due: def test():

print “ndivisibilita’ per 2” numeri=[0, 2, 8, 9456546, 10546454674670,

1, 7, 3163, 5*11*7*13, 7*15*19*33]

for a in numeri: print “a=%s; div2: %s” % (a, div2(a))

Alcune osservazioni: 1. I simboli ”n” all’interno di una stringa significano: “va a capo”. 2. Qui viene utilizzato un ciclo for, la sintassi è: for <variabile> in <sequenza>:

<blocco di istruzioni>

e significa all’incirca: per ogni elemento della sequenza esegui il blocco di codice. Nel nostro caso, per ogni numero contenuto in numeri stampa la stringa formattata. 3. Il comando print è seguito da tre oggetti: 1. una stringa che contiene i simboli: “%s” che sono dei segnaposti, 2. l’operatore di formattazione “%”, 3. una tupla che contiene tanti oggetti quanti sono i segnaposti. Prima di stampare la stringa, vengono calcolati gli oggetti presenti nella tupla e inseriti in ordine nella stringa dove ci sono i segnaposti.

Conviene aggiungere in fondo al file l’istruzione: if __name__ == “__main__”: test () In questo modo quando viene eseguito il programma vene eseguita automaticamente la funzione test(). Mentre se usiamo il programma come libreria di funzioni test() non viene eseguito.

Il criterio di divisibilità per 4 assomiglia molto a quello per 2, ma richiede che si estragga il numero composto dalle ultime due cifre, partiamo da qui. Visto come era semplice la funzione per estrarre una cifra possiamo modificarla per estrarne 2: def destra2(numero):

“”“destra2(numero) -> ultime due cifre del numero.”“” return int(str(numero)[-2:])

Funziona, se il numero ha più di 2 cifre ma se ne ha solo una? Qualche prova ci fa vedere che Python è abbastanza furbo e se gli si chiede di restituire più cifre di quelle contenute in una stringa restituisce l’intera stringa. Possiamo ora affrontare la divisibilità per 4. prima chiariamo il concetto: estraggo le ultime 2 cifre del numero, continuo a togliere 20 finché diventa più piccolo di 20, controllo che quello che ho ottenuto sia un multiplo di 4. In Python: def div4(n):

“”“n e’ divisibile per 4.”“” n2=destra2(n) while n2>=20: n2-=20 return n2 in [0, 4, 8, 12, 16]

Alcune osservazioni: 1. La sintassi del ciclo while è: while <condizione>:

<blocco istruzioni>

2. Se il ciclo while deve ripetere una sola istruzione allora è possibile scriverla sulla stessa riga dell’intestazione dopo il duepunti.
3. L’istruzione n2-=20 significa: togli 20 dal numero collegato alla parola n2 e collega il risultato ancora alla stessa parola. È equivalente a n2=n2-20, ma è un po’ più sintetico.

Il criterio di divisibilità per 3 è di tipo diverso, non coinvolge solo la parte finale del numero, ma tutto il numero: richiede che si faccia la somma di tutte le cifre. Python mette a disposizione una funzione che somma gli elementi di una lista, solo se questi sono numeri. Abbiamo quindi bisogno di una funzione che trasformi un numero in una lista di cifre. Lo si può fare in diversi modi, ma usiamo un metodo tipico di Python: la costruzione di liste. Non è facilissimo da capire, ma è sintetico ed elegante. def cifre(numero):

“”“cifre(numero) -> lista delle cifre del numero.”“” return list(str(numero))

Si potrebbe tradurre con: restituisci la lista che contiene la trasformazione in intero di ogni carattere della stringa equivalente al numero. Oppure: Prendi il numero, lo trasformi in stringa, per ogni carattere della stringa, lo trasformi in intero e lo aggiungi alla lista. A questo punto scrivere la funzione che implementa il criterio di divisibilità per 3 diventa una passeggiata: def div3(n):

“”“n e’ divisibile per 3.”“” n=sum(cifre(n)) return n in [0, 3, 6, 9]

Modifichiamo la funzione test in modo che verifichi anche la nuova funzione: def test():

print “ndivisibilita’ per 2” numeri=[0, 2, 8, 9456546, 10546454674670,

1, 7, 3163, 5*11*7*13, 7*15*19*33]

for a in numeri: print “a=%s; div2: %s” % (a, div2(a)) ... print “ndivisibilita’ per 3” numeri=[0, 3, 9, 24, 36576798,

1, 7, 3163, 25466737, 5*11*7*13,]

for a in numeri: print “a=%s; div3: %s” % (a, div3(a))

Proviamolo... peccato che non funzioni: il numero 36576798 non viene riconosciuto come un multiplo di 3! Come mai? La somma delle cifre dà un numero di due cifre, quindi bisogna sommarne ancora le cifre e ripeterlo finquando la somma ottenuta rimane maggiore di 9. Qui ci viene in soccorso il ciclo while: def div3(n):

“”“n e’ divisibile per 3.”“” while n>9: n=sum(cifre(n)) return n in [0, 3, 6, 9]

Il criterio di divisibilità per 11 richiede che sommiamo le cifre di posto pari e le cifre di posto dispari. Abbiamo già una funzione che, dato un numero restituisce la lista delle sue cifre, dobbiamo costruire una funzione che data una lista restituisce due liste contenenti gli elementi di posto pari e di posto dispari. Possiamo utilizzare un ciclo for con una particolare istruzione Python che restituisce non solo l’elemento, ma anche la sua posizione: enumerate(<sequenza>). La funzione deve: predisporre due liste vuote, p e d, scorrere la lista data e: se la posizione è pari: aggiungerla alla lista p, altrimenti: aggiungerla alla lista d, restituire le due liste. def separa(lista):

“”“Separa in due liste gli elementi di posto pari e di

posto dispari.”“”

pari=[] dispari=[] for ind, cifra in enumerate(lista):

if div2(ind): p.append(cifra) else: d.append(cifra)

return pari, dispari

Alcune osservazioni: 1. Il metodo append aggiunge un elemento in coda ad una lista la sintassi è: <lista>.append(elemento). Può essere usato per costruire liste partendo da una lista vuota e aggiungendo man mano gli elementi. 2. A differenza di altri linguaggi, l’istruzione return può restituire anche più elementi. In questo caso, restituisce 2 liste. Chi chiama questa funzione deve caricare due variabili con il suo risultato, ad es.: postopari, postodispari = separa(c) Riassumendo Abbiamo visto come scrivere alcune funzioni non solo funzionanti, a anche efficienti, sintetiche e facilmente comprensibili. Abbiamo costruito assieme le seguenti funzioni di utilità: destra1(numero), destra2(numero), cifre(numero), separa(lista) e i seguenti criteri di divisibilità: div2(n), div4(n), div3(n). Hai costruito le seguenti funzioni che traducono le definizioni dei criteri di divisibilità: div5(n), div10(n), div25(n), div100(n), div1000(n), destran(numero, cifre), div8(n), div1000(n), div9(n).