Totem's Lair: Guida al Vb.Net, Comprendere e implementare un algoritmo

A49. Comprendere e implementare un algoritmo

Moltissime volte ricevo richieste di aiuto o consigli su come eseguire una certa azione, su come far in modo che il programma processi in una certa maniera dei dati. Tali domande hanno il più delle volte risposte molto semplici. La difficoltà insita in ogni problema di informatica, sia esso atto a calcolare la media aritmetica di un insieme di misure o finalizzato all'analisi di un file di dati, consiste nell'individuare un algoritmo efficace per risolverlo.
Non deve spaventare questa parola, che, al contrario di quel che si possa pensare, non differisce dalle tecniche usate per risolvere un problema di matematica. Per chi non ne conoscesse il significato, dò una semplice definizione, ripresa 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 sull'inizio della definizione, ossia "insieme di istruzioni elementari". Infatti, quando il cervello elabora un problema, più per abitudine che per istinto, è portato a considerare più operazioni simultaneamente, ad esempio: per calcolare la media aritmetica di più numeri è necessario dividere la somma per la numerosità dell'insieme dei dati. Si è implicitamente richiesto di calcolare una somma, quindi di eseguire prima un dato numero di addizioni e in seguito una divisione!
Altra caratteristica importante è data dall'ordine: istruzioni uguali, se eseguite in sequenze diverse possono portare a risultati anche assai diversi. Eccone un esempio. Nelle applicazioni Windows Form (che vedremo nella prossima lezione), si può ricorrere all'uso di un timer per eseguire istruzioni a intervalli di tempo prefissati. Si potrebbe voler visualizzare un messaggio quando viene soddisfatta una certa condizione e parallelamente fermare il timer. Il codice che più spesso si scrive è:

If [Condizione] Then
    '> Visualizza il messaggio
    '> Ferma il timer
End If

Nulla di sbagliato nella sintassi e, a prima vista neanche nella logica, ma... se il timer ha un intervallo impostato a valori minori di 2000 (e in genere è sempre sull'ordine delle centinaia), viene visualizzata una serie di decine se non centinaia di messaggi a schermo. Questo perchè, dato che l'istruzione usata per visualizzare i messaggi in questo tipo di applicazioni ferma l'esecuzione del codice fino alla pressione di uno dei pulsanti proposti, la condizione viene soddisfatta un gran numero di volte prima che il codice prosegua al passo successivo, ossia fermare il timer. Quindi il codice più corretto è:

If [Condizione] Then
    '> Ferma il timer
    '> Visualizza il messaggio
End If

Ecco come un errore apparentemente semplice ha compromesso irreversibilmente il programma!
Il computer, tuttavia, è un "asino veloce", e non è capace di eseguire operazioni complesse al di fuori di quelle basilari. Bisogna quindi scomporre il problema in più sottoproblemi facilmente risolvibili individualmente. In questo capitolo farò due esempi, uno semplice e un altro più complesso, che richiedono di pensare prima all'algoritmo da utilizzare.

Problema 1: La frequenza assoluta

Ecco un piccolo problema di programmazione che nella mia classe, a suo tempo, ha riscosso una totale incapacità di risoluzione:

La frequenza assoluta

Generare un array di x numeri casuali, con x inserito da testiera, compresi tra y e z, anch'essi inseriti da tastiera. Quindi clacolare la frequenza assoluta di ogni numero presente.

Non si sono riscontrati problemi fino al punto in cui è stato necessario calcolare la frequenza. La difficoltà non esiste se si scompone il quesito in più operazioni semplici. Per far questo, risulta molto utile utilizzare i diagrammi di flusso, oppure uno schema disegnato a penna su un foglio di carta. Ad esempio, ecco uno schema del flusso del problema:

Creare una variabile x, quindi richiederne il valore da testiera
Creare due variabili y e z, quindi richiederne il valore da tastiera
Controllare che y sia minore o uguale a z. In caso contrario, invertire i valori
Creare un array di x elementi
Iterare x volte sull'array, inizializzando ogni cella ordinatamente

Creare un randomizzatore temporaneo (classe Random)
Assegnare alla cella il valore casuale estratto tra y e z

L'array è pieno. Ora creare una lista dictionary a tipizzazione forte di (Int32, Int32). La lista conterrà una chiave (il numero) e un valore (la frequenza di quel numero), che verrà incrementata ogni volta che si trova un valore uguale
Iterare x volte sull'array

Controllare che il valore della cella dell'array esista: in questo caso, aumentare di 1 la frequenza del valore nella lista che ha per chiave questo numero; in caso contrario, aggiungere tale numero alla lista e impostarne la frequenza ad 1

Scrivere in output tutte le frequenze

La difficoltà sta nel sapere usare le liste come contenitori: se un programmatore conosce bene tutte le risorse a propria disposizione, sa sempre dove immagazzinare un certo tipo di dati, e quali oggetti preferire rispetto ad altri e per quali motivi. Infatti, nessuno ha pensato alla possibilità di prendere una lista di valori binari chiave-valore. Ecco il codice:

Module Module1
    Sub Main()
        Dim ArraySize As Int32

        'Legge la dimensione
        Console.WriteLine("Inserire il numero di elementi: ")
        ArraySize = Console.ReadLine

        'Se è minore di 0, esce dal programma
        If ArraySize < 0 Then
            Console.WriteLine("Dimensione non valida!")
            Console.ReadKey()
            Exit Sub
        End If

        'Crea l'array di un dato numero di elementi
        Dim Values(ArraySize - 1) As Int32
        Dim Min, Max As Int32

        'Legge valore minimo e massimo
        Console.WriteLine("Inserire minimo e massimo:")
        Console.Write("Minimo: ")
        Min = Console.ReadLine
        Console.Write("Massimo: ")
        Max = Console.ReadLine

        'Se il minimo è maggiore del massimo, inverte i
        'valori, onde evitare errori in seguito
        If Min > Max Then
            Dim Temp As Int32 = Min
            Min = Max
            Max = Temp
        End If

        'Una nuova classe per generare numeri casuali
        Dim Rnd As New Random
        For I As Int32 = 0 To Values.Length - 1
            'Assegna a Values(I) un numero casuale intero tra Min
            'e Max, estremi inclusi. Il "+1" è stato messo perchè
            'il secondo parametro rappresenta il limite superiore
            'escluso.
            Values(I) = Rnd.Next(Min, Max + 1)
        Next

        'Nuovo dizionario di frequenze
        Dim Frequences As New Dictionary(Of Int32, Int32)
        For I As Int32 = 0 To Values.Length - 1
            'Se Values(I) è un numero già rilevato...
            If Frequences.ContainsKey(Values(I)) Then
                'Incrementa la sua frequenza di 1
                Frequences(Values(I)) += 1
            Else
                'Altrimenti lo aggiunge, impostandone la 
                'frequenza a 1
                Frequences.Add(Values(I), 1)
            End If
        Next

        'Scrive ogni valore e rispettiva frequenza a schermo
        For Each Key As Int32 In Frequences.Keys
            Console.WriteLine("Il valore {0} compare {1} volte.", _
            Key, Frequences(Key))
        Next

        Console.ReadKey()
    End Sub
End Module

Problema 2: Ordinamento

Il secondo problema tratta dell'ordinamento crescente di un insieme di elementi. Non sono molte le occasioni in cui si prospetta un quesito del genere, dato che il .Net Framework offre metodi di ordinamento automatico per quasi tutti i tipi di collezione. Tuttavia, talvolta è utile sapere come avviene l'ordinamento e come implementarne uno sotto forma di algoritmo. Ecco un esempio:

Module Module1
    'Notare il vincolo di interfaccia: se non è possibile comparare due
    'elementi, non è neanche possibile ordinarli
    Sub SortArray(Of T As IComparable)(ByVal Values() As T)
        'Il numero di sostituzioni effettuate
        Dim Occurrences As Int32 = 0

        Do
            Occurrences = 0
            'Itera su ogni elemento
            For I As Int32 = 0 To Values.Length - 1
                If I = Values.Length - 1 Then
                    'Se è l'ultimo elemento non si può comparare
                    'con l'elemento successivo in quanto non esiste,
                    'quindi continua fino alla fine
                    Continue For
                End If
                'Se l'elemento corrente è maggiore del successivo,
                'li scambia di posto, poichè l'ordine deve essere
                'crescente, e non decrescente
                If Values(I).CompareTo(Values(I + 1)) = 1 Then
                    'La funzione Swap è stata definita del capitolo
                    'suoi Generics: scambia due valori
                    Swap(Values(I), Values(I + 1))
                    'È stata effettuata una sostituzione:
                    'aumenta Occurrences di 1
                    Occurrences += 1
                End If
            Next
            'Se non sono state effettuate sostituzioni, significa
            'che l'array è ordinato, quindi termina
        Loop Until Occurrences = 0
    End Sub

    Sub Main()
        Dim A() As Int32 = {0, 90, 23, 89, 1098, 26, 478}

        SortArray(A)
        'Il metodo ForEach è un metodo statico della classe astratta
        'Array e permette di eseguire una data azione per ogni
        'elemento dell'array. Accetta come primo parametro l'array in
        'questione e come secondo un delegate di tipo Action generic
        'Esso rappresenta una procedura che accetta un solo parametro
        'di tipo T. In questo caso, scrive a schermo ogni numero
        A.ForEach(A, New Action(Of Int32)(AddressOf Console.WriteLine))

        Console.ReadKey()
    End Sub
End Module

Il ragionamento è semplice:

Si devono eseguire alcune operazioni sull'array. Partendo dal presupposto che ogni operazione cambi l'ordine di almeno due elementi, una volta che la routine non sostituirà più niente, la lista sarà ordinata
Sotto questa condizione, si itera sugli elementi dell'array

Dato che l'ordine è crescente, un elemento nella posizione N deve avere un valore per certo minore o tutt'al più uguale rispetto a ogni elemento successivo. Si esegue quindi un controllo tra l'elemento N-esimo e l'(N+1)-esimo: se il primo è maggiore del secondo, allora li si scambia di posto
Dopo aver eseguito un'operazione del genere, si incrementa il contatore delle sostituzioni di uno

Se il contatore delle sostituzioni è zero, ossia tutti gli elementi sono ordinati, esce automaticamente dal ciclo, altrimenti lo ripete un'altra volta

Questa costituisce un'implementazione con i generics dell'algoritmo di ordinamento Bubble Sort.

In conclusione

Per "trasformare" un qualsiasi problema in un algoritmo, occorre prima individuare i procedimenti logici che portano alla sua risoluzione e successivamente scomporli in singole e semplici operazioni eseguibili dal computer. Tutti i costrutti, gli operatori, le classi, e i metodi analizzati fino ad ora non sono altro che degli strumenti in grado di aiutarvi nella scrittura di un programma: quello che è necessario fare è saper scegliere quali usare e quando usarli per raggiungere la soluzione nel modo più efficace.

The Totem's Lair - Copyright (C) 2009
È vietata la riproduzione sia totale che parziale del sito.