Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Guida al Visual Basic .NET - Comprendere e implementare un algoritmo

Guida al Visual Basic .NET

Capitolo 50° - Comprendere e implementare un algoritmo

<< Precedente Prossimo >>


Forse sarebbe stato opportuno trattare questo argomento moooolto prima nella guida piuttosto che alla fine della sezione; non per niente, la comprensione degli algoritmi è la prima cosa che viene richiesta in un qualsiasi corso di informatica. Tuttavia, è pur vero che, per risolvere un problema, bisogna disporre degli strumenti giusti e, preferibilmente, conoscere tutti gli strumenti a propria disposizione. Ecco perchè, prima di giungere a questo punto, ho voluto spiegare tutti i concetti di base e la sintassi del linguaggio, poiché questi sono solo strumenti nelle mani del programmatore, la persona che deve occuparsi della stesura del codice.
Iniziamo col dare una classica definizione di algoritmo, mutuata da Wikipedia:

Insieme di istruzioni elementari univocamente interpretabili che, eseguite in un ordine stabilito, permettono la soluzione di un problema in un numero finito di passi.

Vorrei innanzitutto porre l'attenzione sulle prime parole: "insieme di istruzioni elementari" (io aggiungere "insieme finito", per essere rigorosi, ma mi sembra abbastanza difficile fornire un insieme infinito di istruzioni :P). Sottolineiamo elementari: anche se i linguaggi .NET si trovano ad un livello molto distante dal processore, che è in grado di eseguire un numero molto limitato di istruzioni - fra cui And, Or, Not, +, Shift, lettura e scrittura - la gamma di "comandi" disponibile è altrettanto esigua. Dopotutto, cosa possiamo scrivere che sia una vera e propria istruzione? Assegnamenti, operazioni matematiche e verifia di condizioni. Punto. I cicli? Non fanno altro che ripetere istruzioni. I metodi? Non fanno altro che richiamare altro codice in cui si cono istruzioni elementari. Dobbiamo imparare, quindi, a fare il meglio possibile con ciò ci cui disponiamo. Vi sarà utile, a questo proposito, disegnare dei diagrammi di flusso per i vostri algoritmi.
Inoltre, requsitio essenziale, è che ogni istruzione sia unvicamente interpretabile, ossia che non possa esserci ambiguità con qualsiasi altra istruzione. Dopotutto, questa condizione viene soddisfatta dall'elaboratore stesso, per come è costruito. Altro aspetto importante è l'ordine: eseguire prima A e poi B o viceversa è differente; molto spesso questa inversione può causare errori anche gravi. Infine, è necessario che l'algoritmo restituisca un risultato in un numero finito di passi: e questo è abbastanza ovvio, ma se ne perde di vista l'importanza, ad esempio, nelle funzioni ricorsive.
In genere, il problema più grande di un programmatore che deve scrivere un algoritmo è rendersi conto di come l'uomo pensa. Ad esempio: dovete scrivere un programma che controlla se due stringhe sono l'una l'anagramma dell'altra. A occhio è facile pensare a come fare: basta qualche tentativo per vedere se riusciamo a formare la prima con le lettere della seconda o viceversa, ma, domanda classica, "come si traduce in codice"? Ossia, dobbiamo domandarci come abbiamo fatto a giungere alla conclusione, scomponendo le istruzioni che il nostro cervello ha eseguito. Infatti, quasi sempre, per istinto o abitudine, siamo portati ad eseguire molti passi logici alla volta, senza rendercene conto: questo il computer non è in grado di farlo, e per istruirlo a dovere dobbiamo abbassarci al suo livello. Ecco una semplice lista di punti in cui espongo come passerei dal "linguaggio umano" al "linguaggio macchina":
  • Definizione di anagramma da Wikipedia: "Un anagramma è il risultato della permutazione delle lettere di una o più parole compiuta in modo tale da creare altre parole o eventualmente frasi di senso compiuto." ;
  • Bisogna controllare se, spostando le lettere, è possibile formare l'altra parola;
  • Ma questo è possibile solo se ogni lettera compare lo stesso numero di volte in entrambe le parole;
  • Per verificare quest'ultimo dato è necessario contare ogni lettera di entrambe le parole, e quindi controllare che tutte abbiano lo stesso numero di occorrenze;
  • Serve per prima cosa memorizzare i dati: due variabili String per le stringhe. Per gli altri dati, bisogna associare ad una lettera (Char) un numero (Int32), quindi una chiave ad un valore: il tipo di dato ideale è un Dictionary(Of Char, Int32). Si possono usare due dizionari o uno solo a seconda di cosa vi viene meglio (per semplicità ne userò due);
  • Ovviamente, a priori, se le stringhe hanno lunghezza diversa, sicuramente non sono anagrammi;
  • Ora è necessario analizzare le stringhe. Per scorrere una stringa, basta servirsi di un ciclo For e per ottenere un dato carattere a una data posizione, la proprietà (di default) Chars;
  • In questo ciclo, se il dizionario contiene il carattere, allora questo è già stato trovato almeno una volta, quindi se ne prende il valore e lo si incrementa di uno; in caso contrario, si aggiunge una nuova chiave con il valore 1;
  • Una volta ottenuti i due dizionari, per prima cosa, devono avere lo stesso numero di chiavi, altrimenti una stringa avrebbe dei caratteri che non compaiono nell'altra; poi bisogna vedere se ogni chiave del primo dizionario esiste anche nel secondo, ed infine se il valore ad essa associato è lo stesso. Se una sola di queste condizioni è falsa, allora le stringhe NON sono anagrammi.
Prima di vedere il codice, notate che è più semplice verificare quando NON succede qualcosa, poiché basta un solo (contro)esempio per confutare una teoria, ma ne occorrono infiniti per dimostrarla:
Module Module1

    Sub Main()
        Dim S1, S2 As String
        Dim C1, C2 As Dictionary(Of Char, Int32)
        Dim Result As Boolean = True

        Console.Write("Stringa 1: ")
        S1 = Console.ReadLine
        Console.Write("Stringa 2: ")
        S2 = Console.ReadLine

        If S1.Length = S2.Length Then
            C1 = New Dictionary(Of Char, Int32)
            For I As Int16 = 0 To S1.Length - 1
                If C1.ContainsKey(S1.Chars(I)) Then
                    C1(S1.Chars(I)) += 1
                Else
                    C1.Add(S1.Chars(I), 1)
                End If
            Next

            C2 = New Dictionary(Of Char, Int32)
            For I As Int16 = 0 To S2.Length - 1
                If C2.ContainsKey(S2.Chars(I)) Then
                    C2(S2.Chars(I)) += 1
                Else
                    C2.Add(S2.Chars(I), 1)
                End If
            Next

            If C1.Keys.Count = C2.Keys.Count Then
                For Each C As Char In C1.Keys
                    If Not C2.ContainsKey(C) Then
                        Result = False
                    ElseIf C1(C) <> C2(C) Then
                        Result = False
                    End If
                    If Not Result Then
                        Exit For
                    End If
                Next
            Else
                Result = False
            End If
        Else
            Result = False
        End If

        If Result Then
            Console.WriteLine("Sono anagrammi!")
        Else
            Console.WriteLine("Non sono anagrammi!")
        End If

        Console.ReadKey()
    End Sub
End Module


<< Precedente Prossimo >>
A proposito dell'autore

Programmatore e analista .NET 2005/2008/2010 (in particolare C# e VB.NET), anche nell'implementazione Mono per Linux. Conoscenze approfondite di Pascal, PHP, XML, HTML 4.01/5, CSS 2.1/3, Javascript (e jQuery). Conoscenze buone di C, LUA, GML, Ruby, XNA, AJAX e Assembly 68000. Competenze basilari di C++, SQL, Hlsl, Java.