[VB.NET] Project Euler .net – Problema n. 1

Molto spesso, per imparare un nuovo linguaggio di programmazione, si esaminano alcuni problemi matematici. Questo avviene per due motivi: il primo è motivo deriva dal fatto che molti piccoli problemi matematici sono molto semplici e quindi non aggiungono livelli di complessità all’attuale nostro problema di imparare un particolare linguaggio di programmazione. Il secondo motivo è dato dal fatto che questo approccio consente di imparare in modo più efficace i costrutti di base della programmazione nel linguaggio scelto: cicli, istruzioni condizionali, assegnazione di valori, visualizzazione del risultato e così via.

Un sito interessante che raccoglie molti di questi problemi matematici, in ordine di difficoltà crescente, è “Project Euler .net” (http://projecteuler.net). Potete registrarvi al sito per provare a dare le vostre soluzioni. Quando fornirete una soluzione corretta, vedrete nel vostro “pannello” dei problemi le soluzioni trovate e potrete anche visualizzare un file PDF contenente una spiegazione dettagliata della soluzione proposta.

Utilizzerò pertanto qualcuno di questi problemi per costruire il nostro “vocabolario” di algoritmi in VB.NET. Il fatto che il sito abbia il suffisso “.net” è solamente un caso: non ha alcuna attinenza con il Framework .NET 😉

Il primo problema consiste nell’esaminare e sommare tra loro tutti i multipli di 3 e di 5 in un intervallo di numeri naturali che va da 1 a “x”. Per esempio, tra 1 e 9, la somma dei multipli di 3 e 5 è pari a 23 (= 3+5+6+9).

Trovare la somma di tutti i numeri multipli di 3 e di 5, tra 1 e 999.

Possiamo risolvere questo problema in almeno due modi (ma probabilmente anche in molti altri). In entrambi i casi otteniamo il numero 233168.

La prima soluzione è la seguente:

  Private Sub Button1_Click(ByVal sender As System.Object,
        ByVal e As System.EventArgs) Handles Button1.Click
    Dim risultato As Integer
    Dim max As Integer = 999
    For i As Integer = 1 To max
      If i Mod 3 = 0 Or i Mod 5 = 0 Then
        risultato += i
      End If
    Next
    MessageBox.Show(risultato.ToString)
  End Sub 

Esaminiamo come funziona questa prima soluzione.

Il codice è inserito nel gestore dell’evento Click di un pulsante.

Prima di tutto definiamo le variabili risultato e max: la prima per accogliere il valore del risultato finale, la seconda per fissare il numero massimo dell’intervallo di numeri naturali da valutare.

Subito dopo abbiamo definito un ciclo, con un indice “i” che varia da 1 al numero contenuto nella variabile “max”. In tale ciclo analizziamo ciascun numero naturale, verificando se sia divisibile per 3 o per 5 (senza resto). Se è divisibile, il numero viene sommato al risultato, altrimenti viene ignorato.

Infine, visualizziamo il valore risultante.

La seconda soluzione invece è maggiormente ottimizzata:

  Private Sub Button2_Click(ByVal sender As System.Object,
         ByVal e As System.EventArgs) Handles Button2.Click
    Dim risultato As Integer
    Dim max As Integer = 999
    risultato = calcola(max, 3) + calcola(max, 5) - calcola(max, 15)
    MessageBox.Show(risultato.ToString)
  End Sub

  Private Function calcola(ByVal max As Integer,
         ByVal passo As Integer) As Integer
    Dim n = max \ passo
    Return passo * n * (n + 1) \ 2
  End Function 

Partendo dal presupposto che stiamo sommando tutti i multipli di 3 e di 5, possiamo anche effettuare una semplice operazione per trovare tutti i multipli dell’uno e dell’altro valore, invece di provare tutti i valori nell’intervallo considerato (da 1 a 999). In tal caso dobbiamo anche sottrarre tutti i multipli di 15, perché 15 è divisibile sia per 3 sia per 5, e quindi dobbiamo evitare di contare tali valori per due volte.

Ricordando che la somma dei primi n numeri interi è uguale a n*(n+1)/2, possiamo utilizzare questa semplice formula per eseguire l’operazione desiderata, prima con il numero 3, poi con il numero 5 e infine con il numero 15.

La differenza, rispetto al programma precedente, sta tutta nell’istruzione seguente

risultato = calcola(max, 3) + calcola(max, 5) - calcola(max, 15) 

e nell’aggiunta della funzione di calcolo denominata “calcola”.

Tale funzione accetta gli argomenti “max” e “passo” che rappresentano rispettivamente il valore massimo dell’intervallo di numeri naturali (in questo caso 999) e il divisore da considerare (3, 5 o 15). La funzione “calcola” realizza semplicemente il calcolo secondo la formula sopra indicata.

Confrontando la complessità computazionale dei due programmi (chiamata “O grande”), troviamo che nel primo caso abbiamo una complessità O(n), mentre nel secondo caso abbiamo O(1). Nel secondo caso, quindi, la complessità (e la durata di esecuzione) è indipendente dal numero di valori da esaminare (in questo caso 999).

N.B. lo spunto per questo post e l’informazione sul sito Project Euler .net è stato gentilmente concesso da Claudio Cherubino (http://www.fsharp.it e http://www.claudiocherubino.it/). Grazie!

Pubblicato il 24 luglio 2010 su Novità. Aggiungi ai preferiti il collegamento . 4 commenti.

  1. Grazie Mario, sono mesi che cerco un sito del genere. Ho chiesto in giro,ma tu- finalmente- hai trovato ciò che cercavo.

    Mi piace

  2. p.s.:dimenticavo….Se venissi a conoscenza di siti simili, ma che riguardano altri argomenti (es.: OOP, database, ecc.), potresti segnalarli sul blog, di tanto in tanto?

    Mi piace

  3. Ciao Matteo,
    si certamente, qualsiasi cosa che possa essere utile dal punto di vista didattico è la benvenuta in questo blog! 🙂

    Mi piace

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: