2.4. Divisibilità Come trovare il massimo comune divisore e scoprire se un numero è perfetto. Prerequisiti operatori: % e ==. funzioni ricorsive, struttura di selezione: if ..else, struttura di iterazione: while e for, dati: numeri e liste.
Argomenti trattati massimo comune divisore, divisori di un numero, numeri perfetti.
Problema Scrivere una libreria funzione che ricerchi i numeri perfetti, i numeri cioè che sono uguali alla somma dei loro divisori tranne il numero stesso.
Soluzione Gli elaboratori elettronici permettono di affrontare e risolvere alcuni problemi legati alla divisibilità. Python mette a disposizione alcuni comandi per questo. Il primo di questi è l’operatore: “%”. Lo stesso operatore ha significati completamente diversi a seconda del contesto in cui si trova. Serve per formattare stringhe: “somma=%s” % somma, ma tra due numeri % non viene utilizzato per qualcosa che riguarda le percentuali, ma serve per calcolare il resto di una divisione. Fin dalle elementari ci hanno insegnato che 13 diviso 3 fa 4 con il resto di 1. In Python il resto di questa divisione lo si trova con l’espressione: 13 % 3:
13 % 3 -> 1 15 % 4 -> 3 55 % 10 -> 5 457 % 40 ->17 ... Ma cosa centra il resto della divisione con la divisibilità? In matematica si dice che un numero è divisibile per un altro quando il resto della divisione è uguale a zero. Perciò si dice che 15 è divisibile per 5 perché il resto di 15 diviso 5 è 0. Tutti i numeri pari sono divisibili per 2 perché il resto della divisione tra un numero pari e 2 è proprio 0. L’operatore % che dà il resto di una divisione permette di determinare se un numero divide esattamente un altro. Possiamo scrivere una funzione che trova se un numero è divisibile per 3: def div3(num):
return num % 3 == 0
E così via, ad esempio per controllare se un numero è divisibile per 7 si può costruire la funzione: def div7(num):
return num % 7 == 0
Una generica funzione che controlla se il numero n è divisibile per il numero d, può essere: def divisibile(num, div):
return num % div == 0
- In vari casi nei calcoli aritmetici è necessario trovare il minimo comune multiplo e il massimo comune divisore. Partiamo da quest’ultimo. L’algoritmo di Euclide dice che:
- è a se a=b
- il mcd di a e b | altrimenti è il mcd tra
- la differenza tra a e b eil più piccolo tra a e b
Tradotto in Python con una funzione ricorsiva: def mcd1(a, b):
if a==b: return a elif a>b: return mcd1(a-b, b) else: return mcd1(b-a, a)
Vari altri algoritmi sono possibili, tra tutti spicca per semplicità ed eleganza il seguente, composto da tre righe di codice: def mcd(a, b):
‘’‘Massimo Comune Divisore tra a e b’‘’ while b:
a, b = b, a%breturn a
Possiamo scrivere ora una funzione che restituisca la lista dei divisori di un numero. Ci sono molti modi per farlo, un’idea può essere: predisporre una lista vuota, per d che va da 1 a n: se d divide n aggiungi d alla lista restituisci la lista così ottenuta Tradotto in Python: def divisori0(num):
‘’‘Restituisce la lista dei divisori di num. Usa un ciclo for e append per popolare la lista.’‘’ result=[] for div in range(1, num+1):
if (num % div)==0: result.append(div)return result
La funzione precedente è formata da tre blocchi: l’inizializzazione della variabile che conterrà la lista dei divisori, il ciclo che popola questa lista, l’istruzione che termina la funzione restituendo come risultato la lista dei divisori. Python mette a disposizione una sintassi più compatta per popolare una lista. Lo stesso risultato della funzione precedente può essere ottenuto la una sola riga di istruzioni: def divisori1(num):
‘’‘Restituisce la lista dei divisori di n. Usa la costruzione di liste, list comprehension.’‘’ return [div for div in range(1, num+1) if (num % div)==0]
Che può essere tradotto con: restituisci la lista formata dagli elementi d tali che d appartengono all’intervallo [1, num] e div è divisore di num. Le funzioni precedenti sono poco efficienti, è possibile migliorare la ricerca dei divisori di un numero in diversi modi: 1. Python permette di scrivere funzioni che restituiscono più oggetti, in particolare ha una funzione primitiva che restituisce quoziente intero e resto di una divisione tra interi. Nella shell di IDLE facciamo qualche prova: >>> print divmod(17, 5) 3, 2 2. Ogni volta che troviamo un divisore, possiamo conoscerne anche un’altro: se div è divisore anche num/div lo è. 3. Tra la metà di num e num stesso non ci sono divisori, quindi possiamo dimezzare l’intervallo di ricerca. 4. Anzi, se ogni volta che incontriamo un divisore div, inseriamo anche num/div, possiamo fermarci nella ricerca quando div supera num/div. Tenendo conto di queste osservazioni possiamo scrivere una funzione più complicata, ma moto più efficiente: def divisori(n):
result=[] d=1 q=n r=0 while d<=q:
- if r==0:
- if d==q: result+=[d] else: result+=[d, q]
d+=1 q, r = divmod(n, d)
- # print d, q, r
- result.sort() return result
Stampare i valori di alcune variabili all’interno di un ciclo, può aiutare a capirne il suo funzionamento o a scoprire degli errori. Quando non serve, la riga che produce la stampa può essere trasformata in un commento semplicemente anteponendo il carattere “#” al comando. Una volta che abbiamo i divisori di un numero possiamo sommarli tutti tranne il numero stesso. Ad esempio: I divisori di 3 sono: [1, 3], la somma dei divisori di 3 tranne 3 stesso è: 1. I divisori di 4 sono: [1, 2, 4], la somma dei divisori di 4 tranne 4 stesso è: 3. I divisori di 5 sono: [1, 5], la somma dei divisori di 5 tranne 5 stesso è: 1. I divisori di 6 sono: [1, 2, 3, 6], la somma dei divisori di 6 tranne 6 stesso è: 6. ... Ora i numeri che sono ugualia alla somma dei loro divisori, tranne il numero stesso, sono detti numeri perfetti. Python ha una funzione che restituisce la somma di tutti i numeri contenuti in una lista; possiamo usarla per calcolare la somma dei divisori. Usiamo IDLE per fare un po’ di provacce. Ad esempio se voglio trovare la somma dei divisori di 4 o di 12 posso scrivere >>> print sum([1, 2, 4]) 7 >>> print sum([1, 2, 3, 4, 6, 12]) 28 O più semplicemente posso far calcolare a Python la lista dei divisori: >>> print sum(divisori(4)) 7 >>> print sum(divisori(12)) 28 Peccato che la somma che ci interessa sia quella di tutti i divisori tranne l’ultimo. Python mette a disposizione un metodo per estrarre una sottolista di una lista, per estrarre una “fetta” di una lista. Per maggiori informazioni si può (ri)guardare il capitolo sulle Liste e Tuple. Spezzettiamo tutte le operazioni logiche che chiediamo a Python di compiere in modo da renderci conto di quello che succede: >>> # mettiamo in d4 la lista dei divisori di 4 >>> d4=divisori(4) >>> # per sicurezza stampiamo il contenuto di d4 >>> print d4 [1, 2, 4] >>> # bene, ora mettiamo in d4mu il contenuto di d4 meno l’ultimo elemento >>> d4mu=d4[:-1] >>> # ora stampiamo la somma degli elementi di d4mu >>> print sum(d4mu) 3 Ora possiamo mettere tutto assieme: stampiamo la somma della fetta dei divisori di 4: >>> print sum(divisori(4)[:-1]) 3 Bene possiamo ora creare una funzione che restituisca la “somma” dei divisori di un numero passato come argomento: def sommadiv(n):
return sum(divisori(n)[:-1])
E, infine, possiamo scrivere una funzione che restituisce “vero” o “falso” a seconda che un numero sia “perfetto” oppure no: def perfetto(n):
return n==sommadiv(n)
Possiamo usare la funzione precedente per stampare tutti i numeri perfetti minori di 100: def perfetti100():
- for n in range(2, 101):
- if perfetto(n): print n, “è perfetto”, divisori(n)
Oppure creare una procedura che vada avanti finché non viene premuto il tasto <Ctrl-c> e che continua a cercare numeri perfetti: def perfetti0():
n=2 while True:
if perfetto(n): print n, “è perfetto”, divisori(n) n+=1
Un perfezionamento di questa procedura permette di partire da un numero a propria scelta, se non viene indicato è 2, e di andare avanti finché l’utente non decide di interrompere il ciclo. Quando il ciclo viene interrotto, premendo il tasto <Ctrl-c>, la procedura, prima di terminare, stampa il valore attuale di n. def perfetti(n=2):
- while True:
- try:
- if perfetto(n): print n, “è perfetto”, divisori(n) n+=1
- except:
- print “sono arrivato al numero”, n return
Riassumendo L’operatore “%” restituisce il resto della divisione tra due interi. la funzione divmod(n, d) restituisce il quoziente e il reato della duivisione tra due numeri. Si possono scrivere funzioni che sfruttando, la selezione, l’iterazione o la ricorsione, esplorano proprietà legate alla divisibilità dei numeri naturali.