Esercizi di programmazione

Vogli presentarvi un piccolo esercizio di programmazione, un semplice programmino che macina numeri.

L'ispirazione mi è venuta scoprendo il sito ProjectEuler in una maillinglist.

ProjectEuler è una collezione di problemi matematici e informatici a cui dare una soluzione. ProjectEuler dice di sé

"La motivazione che ha spinto l'avvio del Progetto Euler, e la sua prosecuzione, è di fornire una piattaforma per la mente indagatrice, per approfondire zone sconosciute e imparare nuovi concetti in un contesto divertente e ricreativo."

ProjectEuler chiede di non divulgare le soluzioni per non togliere il gusto di indagare e scoprire a chi volesse cimentarvisi. Ma noi facciamo un'eccezione per far vedere come Python sia flessibile, potente e anche conciso (se si vuole).

Il problema numero uno chiede di trovare la somma degli interi minori di 1000 e divisibili per 3 o per 5. Semplice. Volevo proporre due soluzioni, una "classica" nel senso di ampia e verbosa e una estremamente conisa.

Prima soluzione:

somma = 0                # (0)
for x in xrange(3,1000): # (1)
    if x % 3 == 0:       # (2)
        somma += x       # (2.1)
    elif x % 5 == 0:     # (3)
        somma += x       # (3.1)
print somma

Vediamo nel dettaglio. (1) cicliamo tra i numeri da 3 a 1000 (escluso), ovviamente i numeri minori di tre non sono divisibili né per tre né per cinque quindi li saltiamo. (2) vediamo se x è divisibile per tre, (3) altrimenti proviamo se x è divisibile per cinque. Nei punti (2.1) e (3.1) sommiamo alla nostra varibile accumulatore somma (definita la passo (0)) il valore di x.

Potevamo risparmiaci un paio di passi raggruppando le condizioni:

somma = 0
for x in xrange(3,1000):
    if (x % 3 == 0) or (x % 5 == 0):
        somma += x
print somma

Per leggibilità ho messo le parentesi intorno alle due condizioni, ma grazie alla priorità degli operatori non sarebbe stato necessario.

Se volessimo cercare di scrive il programma più compatto possibile, potremmo usare la finzione sum() che somma gli elementi di una lista o di un oggetto iterabile. Per creare la lista possiamo usare due simpatiche contrazioni di if e for. Per esempio per creare una lista di valori di interi da 3 a 1000 potremmo scrivere così:

(x for x in xrange(3,1000))

e la somma è quindi:

sum(x for x in xrange(3,1000))

Ma così facendo avremmo la somma ti tutti i valori nell'intervallo. Dobbiamo discernere quali valori entrano nella lista e quali no, la condizione è sempre la stessa x % 3 == 0 or x % 5 == 0, adesso usiamo una forma contratta dell'istruzione <expr> if <cond> else <expr>:

sum((x if x % 3 == 0 or x % 5 == 0 else 0) for x in xrange(3,1000))

Finito! Abbiamo ottenuto lo stesso risultato! Da notare che stiamo usando python con un paradigma di programmazione funzionale.

Nelle versioni più vecchie di python [1] non esisteva il costrutto <expr> if <cond> else <expr>, ma si poteva utilizzare un po' di programmazione logica [2] sfruttando gli operatori and e or oltre al fatto di tenere presente come python valuta le espressioni. Quindi avremmo potuto avere il medesimo risultato con il codice seguente:

sum(((x % 3 == 0 or x % 5 == 0) and x or 0) for x in xrange(3,1000))

Il giochetto sta tutto nell'ordine e nelle proprietà degli operatori logici. Schematizziamo il nostro codice nel modo seguente:

<expr 1> and <expr 2> or <expr 3>

Ricordiamo che l'interprete valuta l'intera espressione da sinistra verso destra. Ricordiamo anche che l'operatore logico AND è vero solo (e soltanto) se entrambi gli operandi sono veri, falso se anche uno solo è falso. Mentre l'operator OR è vero se anche solo uno degli operandi è vero e falso se entrambi lo sono contemporaneamente. Quindi il nostro interprete python deve valutare se la nostra espressione e restituire un valore. Facciamolo noi al suo posto: partiamo da sinistra e valutiamo <expr 1> questa potrà avere valore vero o falso. Se <expr 1> è vera [3] per decidere che valore avrà l'intera espressione saremmo costretti a valutare anche <expr 2>. Se <expr 2> è vera allora abbiamo finito, l'intera espressione varrà il valore di <expr 2>. Se è falsa allora l'espressione varrà il valore che avrà <expr 3>. Finito.

Ovviamente queste non sono gli unici modi per risolvere il problema, nel forum di ogni problema ce ne sono per tutti i gusti e per tutti i linguaggi, ci sono soluzioni squisitamente matematiche e altre più computazionali. Una interessante utilizza i set di python che si riproduce le proprietà degli insiemi e dice semplicemente che il risultato e la somma dei multipli di tre range(3,1000,3) e di cinque range(5,1000,5) ovviamente senza ripetizioni.

Spero di aver stimolato un po' di curriosità nei lettori e vi consiglio di dare un'occhiata ai vari problemi di ProjectEuler.

[1] precedenti alla versione 2.5 [PEP308].
[2] chi ha detto Prolog?
[3] un qualsiasi valore che non sia Null, 0, False.

Commenti

Comments powered by Disqus