|
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
|
|
Feeds
Sondaggio
Condividi
Numeri
