2.7. Scomposizione in fattori primi Come scomporre un numero in fattori primi. Prerequisiti operatori: >, e ==. funzioni con parametri, funzione divmod() struttura di selezione: if ..else, struttura di iterazione: while e istruzione break, liste e tuple.
Argomenti trattati scomposizione di un numero in fattori primi, programmazione guidata dai test,
Problema Scrivere una funzione che produca la scomposizione in fattori primi di un numero.
Soluzione Il teorema fondamentale dell’aritmetica dice che la scomposizione in fattori primi di un numero è unica. Ciò vuol dire che posso seguire diverse strade, ma il risultato dipende solo dal numero e non dal percorso seguito:
72 = 23 32 72 = 23 32 72 = 23 32
/ \ / \ / \
2 36 4 18 8 9
/ \ / \ / \ / \ / \
6 6 2 2 2 9 2 4 3 3
/ \ / \ / \ / \
2 3 2 3 3 3 2 2
Il metodo che preferisco, per scomporre in fattori un numero, è quello dell’albero binario:
se il numero è primo, è già scomposto in fattori primi, altrimenti da questo numero derivo due rami sotto cui scrivo due numeri il cui prodotto dia il numero di partenza, ripeto i due passi precedenti per ogni nuovo numero.
Questo metodo, ricorsivo, permette ad ogni passo di scegliere i divisori più comodi e quindi in molti casi rende più semplice il calcolo rispetto al metodo che solitamente si trova nei libri delle medie:
3600 | 2 3600 = 243252
1800 | 2 / \
900 | 2 100 36
450 | 2 / \ / \
225 | 3 10 10 4 9
75 | 3 / \ / \ / \ / \
25 | 5 2 5 2 5 2 2 3 3
5 | 5
1 |
3600 = 243252
A me piace anche perché non devo riscrivere il numero di partenza quando ho terminato la scomposizione (la solita pigrizia). Il metodo ad albero binario diventa del tutto uguale al metodo proposto sui libri, se ogni volta scelgo il divisore più piccolo possibile:
3600 = 243252
/ \
2 1800
/ \
2 900
/ \
2 450
/ \
2 225
/ \
3 75
/ \
3 25
/ \
5 5
Il metodo ad albero prevede che siamo noi a scegliere tra tutti i possibili divisori di un numero quale utilizzare, il teorema fondamentale dell’aritmetica ci assicura che qualunque divisore va bene. Se la scelta la facciamo con un po’ di buon senso possiamo renderci più semplice il calcolo. Ora, se vogliamo realizzare una funzione automatica che scomponga in fattori un numero, dobbiamo tenere presente che, per le macchine (purtroppo spesso anche per i politici e gli amministratori in genere), il buon senso risulta molto difficile, mentre risulta facile il calcolo. Quindi l’algoritmo può diventare qualcosa di simile a questo: Dividi il num. per il più piccolo divisore (maggiore di 1!) dividi il quoziente ottenuto per il più piccolo divisore continua così finché non hai ottenuto come quoziente 1 Nel caso del numero 120 otteniamo:
120 | 2
60 | 2
30 | 2
15 | 3
5 | 5
1 |
Abbiamo visto che non è il metodo più pratico quando dobbiamo fare a mano la scomposizione, ma è molto meccanico e quindi è più facilmente trasformabile in un algoritmo. Otteniamo quindi . Prima di procedere dobbiamo pensare ad una struttura di dati che permetta di rappresentare tutti i possibili risultati delle scomposizioni in fattori: ma anchee anchee ... Perché scrivere potenze separate da un puntino è comodo per un essere umano, ma non lo è molto per un computer. Ricordando che ,..., ogni fattore può essere visto come una potenza, possiamo osservare che la scomposizione in fattori primi è formata da una sequenza di potenze in numero variabile. In Python la struttura di dati che viene utilizzata per contenere sequenze di lunghezza variabile è la lista, quindi la funzione che scomporrà in fattori un numero dovrà restituire come risultato una lista di potenze: [ potenza1, potenza2, potenza3, ...]. Una potenza può essere vista come una coppia di numeri: la base e l’esponente. Una coppia in Python può essere rappresentata da una tupla: 23 = (2, 3), 51 = (5, 1), ... La scomposizione in fattori di un numero può essere vista come una sequenza di potenze ed essere rappresentata in Python come una lista di tuple: la rappresentazione interna di può essere la lista di coppie: [(2, 3), (3, 1), (5, 1)] che va interpretata come due elevato alla terza per tre elevato alla prima per cinque elevato alla prima. Ora abbiamo tutti gli elementi per affrontare il problema: incominciamo a scrive il codice! Il metodo seguito di solito è quello di:
- scrivere una prima funzione
- provarla in vari casi
- correggerla
- tornare al punto 2 finché non risulta sufficientemente corretta.
Questo metodo funziona, ma dal punto di vista informatico è molto meglio, prima scrivere i test del nostro programma e poi il codice che risolve il problema: prima definiamo gli “esercizi” e i risultati che ci aspettiamo di ottenere e poi scriviamo la funzione che dovrà risolvere gli “esercizi”. Questo modo di procedere, che può sembrare strano, è così importante da meritare un nome: “programmazione guidata dai test”, “test driven”. Bene, mano all’editor e iniziamo a scrivere il nostro programma: def fattorizza(numero):
“”“Scomposizione in fattori primi di numero.”“” risultato = [] return risultato
- def prova(funzione, risultato_atteso):
- “”“Esegue la funzione e confronta il risultato
- con risultato_atteso.”“”
risultato=eval(funzione) if risultato==risultato_atteso:
print “%s -> %s corretto” % (funzione, risultato)- else:
- print “%s -> %s, risultato atteso: %s”
- % (funzione, risultato, risultato_atteso)
- def test():
prova(“fattorizza(7)”, [(7, 1)]) prova(“fattorizza(8)”, [(2, 3)]) prova(“fattorizza(23)”, [(23, 1)]) prova(“fattorizza(28)”, [(2, 2), (7, 1)]) prova(“fattorizza(30)”, [(2, 1), (3, 1), (5, 1)]) prova(“fattorizza(120)”, [(2, 3), (3, 1), (5, 1)]) prova(“fattorizza(%s)” % (2*2*3*3*3*3*7*11*11),
[(2, 2), (3, 4), (7, 1), (11, 2)])
if __name__==”__main__”: test() Qualche commento alle 3 funzioni. La prima, fattorizza(), è quella che dobbiamo costruire. È definita in modo decisamente stupido: qualunque sia l’argomento passato alla funzione, e messo nel parametro numero, darà come risultato una lista vuota. Per ora va bene così perché ci concentriamo sulle funzioni che servono per il test. La funzione prova() è la più complessa: Ha 2 parametri, nel primo viene messa la funzione da eseguire e nel secondo il risultato atteso. Esegue la funzione e memorizza il risultato. Confronta il risultato ottenuto con quello atteso e stampa un messaggio adeguato. L’ultima, test() è costituita da una sequenza di chiamate alla funzione prova() passandole via via diverse funzioni da verificare con i risultati attesi. Quando eseguiamo il programma l’ultima linea chiama la funzione test() e otteniamo il seguente output: fattorizza(7) -> [], risultato atteso: [(7, 1)] fattorizza(8) -> [], risultato atteso: [(2, 3)] fattorizza(23) -> [], risultato atteso: [(23, 1)] fattorizza(28) -> [], risultato atteso: [(2, 2), (7, 1)] fattorizza(30) -> [], risultato atteso: [(2, 1), (3, 1), (5, 1)] fattorizza(120) -> [], risultato atteso: [(2, 3), (3, 1), (5, 1)] fattorizza(274428) -> [], risultato atteso: [(2, 2), (3, 4), (7, 1), (11, 2)] A questo punto possiamo essere moderatamente soddisfatti: il programma non fa quello che vogliamo, ma funziona correttamente. Un piccolo cambiamento alla funzione fattorizza() le permette di trattare correttamente i numeri primi:
- def fattorizza(numero):
- “”“Scomposizione in fattori primi di numero.”“” risultato = [(numero, 1)] return risultato
L’output è: fattorizza(7) -> [(7, 1)] corretto fattorizza(8) -> [(8, 1)], risultato atteso: [(2, 3)] fattorizza(23) -> [(23, 1)] corretto fattorizza(28) -> [(28, 1)], risultato atteso: [(2, 2), (7, 1)] fattorizza(30) -> [(30, 1)], risultato atteso: [(2, 1), (3, 1), (5, 1)] fattorizza(120) -> [(120, 1)], risultato atteso: [(2, 3), (3, 1), (5, 1)] fattorizza(274428) -> [(274428, 1)], risultato atteso: [(2, 2), (3, 4), (7, 1), (11, 2)] I numeri 7 e 23 vengono scomposti correttamente e questo ci conforta sul buon funzionamento delle funzioni di test che, oltre a riconoscere i casi sbagliati, tutti nella prima versione di fattorizza(), riconoscono anche quelli corretti. A questo punto conviene riprendere gli esempi di scomposizione in fattori risolti con carta e penna. È chiaro che ci sono delle operazioni che vengono ripetute fin quando il numero da scomporre è maggiore di 1. In informatica ciò si traduce con un ciclo while: fin quando numero>1:
esegui qualcosa
Ma prima di iniziare il ciclo devo porre il divisore uguale al più basso valore, cioè porre il divisore uguale a 2. divisore=2 fin quando numero>1:
esegui qualcosa
All’interno del ciclo devo calcolare quoziente e resto della divisione di numero per divisore e controllare il resto. Se il resto è uguale a zero, aggiungo una coppia e aggiorno il numero, altrimenti incremento il divisore: divisore=2 fin quando numero>1:
calcolo quoziente e resto di numero / divisore se resto è uguale a 0:
aggiungo una coppia al risultato aggiorno il numero
- altrimenti
- incremento il divisore
Le idee, a questo punto sono abbastanza chiare per poter essere tradotte in Python: def fattorizza(numero):
“”“Scomposizione in fattori primi di numero.”“” risultato = [] divisore=2 while numero>1:
quoziente, resto = divmod(numero, divisore) if resto==0: # numero è multiplo di divisore
- risultato.append((divisore, 1)) # aggiungo una coppia
- a risultato
numero=quoziente # aggiorno numero
- else:
- divisore+=1 # incremento divisore
return risultato
L’esecuzione del programma produce: fattorizza(7) -> [(7, 1)] corretto fattorizza(8) -> [(2, 1), (2, 1), (2, 1)], risultato atteso: [(2, 3)] fattorizza(23) -> [(23, 1)] corretto fattorizza(28) -> [(2, 1), (2, 1), (7, 1)], risultato atteso: [(2, 2), (7, 1)] fattorizza(30) -> [(2, 1), (3, 1), (5, 1)] corretto fattorizza(120) -> [(2, 1), (2, 1), (2, 1), (3, 1), (5, 1)], risultato atteso: [(2, 3), (3, 1), (5, 1)] fattorizza(274428) -> [(2, 1), (2, 1), (3, 1), (3, 1), (3, 1), (3, 1), (7, 1), (11, 1), (11, 1)], risultato atteso: [(2, 2), (3, 4), (7, 1), (11, 2)] Ora anche 30 è fattorizzato correttamente, non solo, anche le altre soluzioni sarebbero giuste se noi avessimo deciso di accettare al posto di . Rimbocchiamoci le maniche e cerchiamo di aggiustare le cose. Nel precedente algoritmo effettivamente non c’è traccia di esponenti. Prima di iniziare il ciclo oltre a porre divisore uguale a 2 dobbiamo porre l’esponente uguale a 0 e aumentare l’esponente ogni volta che divisore divide numero. Quando divisore divide numero, invece di aggiungere una coppia, incrementiamo l’esponente. La coppia viene invece aggiunta quando divisore non divide numero solo se l’esponente è maggiore di zero: def fattorizza(numero):
“”“Scomposizione in fattori primi di numero.”“” risultato = [] divisore=2 esponente=0 while numero>1:
quoziente, resto = divmod(numero, divisore) if resto==0: # numero è multiplo di divisore
esponente+=1 # incremento esponente numero=quoziente # aggiorno numero
- else:
- if esponente>0: # se esponente è cambiato
- risultato.append((divisore, esponente)) # agg. una
- # coppia a ris.
divisore+=1 # incremento divisore
return risultato
Operate le modifiche basta eseguire il programma: fattorizza(7) -> [], risultato atteso: [(7, 1)] fattorizza(8) -> [], risultato atteso: [(2, 3)] fattorizza(23) -> [], risultato atteso: [(23, 1)] fattorizza(28) -> [(2, 2), (3, 2), (4, 2), (5, 2), (6, 2)],
risultato atteso: [(2, 2), (7, 1)]
fattorizza(30) -> [(2, 1), (3, 2), (4, 2)], risultato atteso: [(2, 1), (3, 1), (5, 1)] fattorizza(120) -> [(2, 3), (3, 4), (4, 4)], risultato atteso: [(2, 3), (3, 1), (5, 1)] fattorizza(274428) -> [(2, 2), (3, 6), (4, 6), (5, 6), (6, 6), (7, 7), (8, 7), (9, 7), (10, 7)], risultato atteso:
[(2, 2), (3, 4), (7, 1), (11, 2)]
Disastro! Anche quello che prima funzionava ora non va più! Cosa è successo? Possiamo fare una prima osservazione: nei numeri primi il risultato è una lista vuota, perché finito il ciclo ci è rimasta in mano una coppia che dobbiamo aggiungere alla lista. Quindi, prima di restituire il risultato dobbiamo aggiungere l’ultima coppia: def fattorizza(numero):
“”“Scomposizione in fattori primi di numero.”“” risultato = [] divisore=2 esponente=0 while numero>1:
quoziente, resto = divmod(numero, divisore)
- # print numero, divisore, quoziente, resto
- if resto==0: # numero è multiplo di divisore
- esponente+=1 # incremento esponente numero=quoziente # aggiorno numero
- else:
- if esponente>0: # se esponente è cambiato
- risultato.append((divisore, esponente)) # agg. una
- # coppia a ris.
divisore+=1 # incremento divisore
- risultato.append((divisore, esponente)) # agg. una coppia
- # a risultato
return risultato
Ora il programma produce: fattorizza(7) -> [(7, 1)] corretto fattorizza(8) -> [(2, 3)] corretto fattorizza(23) -> [(23, 1)] corretto fattorizza(28) -> [(2, 2), (3, 2), (4, 2), (5, 2), (6, 2), (7, 3)], risultato atteso: [(2, 2), (7, 1)] fattorizza(30) -> [(2, 1), (3, 2), (4, 2), (5, 3)], risultato atteso: [(2, 1), (3, 1), (5, 1)] fattorizza(120) -> [(2, 3), (3, 4), (4, 4), (5, 5)], risultato atteso: [(2, 3), (3, 1), (5, 1)] fattorizza(274428) -> [(2, 2), (3, 6), (4, 6), (5, 6), (6, 6), (7, 7), (8, 7), (9, 7), (10, 7), (11, 9)], risultato atteso: [(2, 2), (3, 4), (7, 1), (11, 2)] Qualcosa è migliorato: i numeri con un solo fattore primo, non importa con quale esponente, sono fattorizzati in modo corretto, gli altri sono strampalati. Il problema deriva dal fatto che, all’interno del ciclo, quando viene aggiunta una coppia al risultato, l’esponente deve essere rimesso a zero. def fattorizza(numero):
“”“Scomposizione in fattori primi di numero.”“” risultato = [] divisore=2 esponente=0 while numero>1:
quoziente, resto = divmod(numero, divisore) if resto==0: # numero è multiplo di divisore
esponente+=1 # incremento esponente numero=quoziente # aggiorno numero
- else:
- if esponente>0: # se esponente è cambiato
- risultato.append((divisore, esponente)) # agg. una
- # coppia a ris.
esponente=0 # rimette a zero esponente
divisore+=1 # incremento divisore
- risultato.append((divisore, esponente)) # agg. una coppia
- # a risultato
return risultato
Il programma ora produce: fattorizza(8) -> [(2, 3)] corretto fattorizza(23) -> [(23, 1)] corretto fattorizza(28) -> [(2, 2), (7, 1)] corretto fattorizza(30) -> [(2, 1), (3, 1), (5, 1)] corretto fattorizza(120) -> [(2, 3), (3, 1), (5, 1)] corretto fattorizza(274428) -> [(2, 2), (3, 4), (7, 1), (11, 2)] corretto Se la nostra base di test è abbastanza ampia possiamo ritenerci soddisfatti. Non solo, se qualche utente della nostra funzione, o noi stessi ci accorgiamo di un particolare caso che produce un errore, basta che lo aggiungiamo ai casi da verificare e poi modificare la fattorizza() in modo che funzioni correttamente in tutta la nostra base di prove. Questo meccanismo permette di evitare che la correzione di un errore produca un errore nei casi che prima funzionavano correttamente.
Riassumendo Un buon modo di scrivere un programma è quello di farsi guidare dai test. In particolare nei programmi complessi, perdere del tempo nella costruzione di una adeguata batteria di test fa guadagnare, complessivamente, molto tempo. Prima di mettersi a scrive del codice si deve arrivare a dare una buona descrizione a parole dell’algoritmo che si vuole realizzare. Se l’algoritmo è pensato bene, non è difficile correggere eventuali errori magari scovandoli con qualche istruzione print posizionata appropriatamente.