.. title: Esercizi di programmazione
.. slug: esercizi-di-programmazione
.. date: 2015-03-07 17:30:09 UTC+01:00
.. tags: python, programmazione
.. category: 
.. link: 
.. description: 
.. type: text

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."

.. TEASER_END: Leggi di più...
    
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:

.. code:: python

    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:

.. code:: python

    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ì:

.. code:: python
    
    (x for x in xrange(3,1000))

e la somma è quindi:

.. code:: python
    
    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>``:

.. code:: python
    
    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 [#]_ non esisteva il costrutto 
``<expr> if <cond> else <expr>``, ma si poteva utilizzare un po' di 
programmazione logica [#]_ 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:

.. code:: python
    
    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:

.. code:: python

    <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 [#]_ 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_.



.. [#] precedenti alla versione 2.5 [PEP308_].
.. [#] chi ha detto Prolog_?
.. [#] un qualsiasi valore che non sia ``Null``, ``0``, ``False``.



.. _ProjectEuler: https://projecteuler.net/
.. _uno: https://projecteuler.net/problem=1
.. _Python: https://python.org
.. _Prolog: https://it.wikipedia.org/wiki/Prolog
.. _PEP308: https://www.python.org/dev/peps/pep-0308/