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!