Le strutture dati

I vettori
Fino ad ora abbiamo considerato sempre algoritmi adatti a risolvere problemi in cui comparivano variabili semplici. A volte può essere necessario raggruppare insieme valori sotto un unico nome. Abbiamo considerato in precedenza algoritmi per calcolare medie, massimi e minimi. Si basavano sull’acquisizione ripetuta di valori ed opportuni calcoli. La sequenza di dati letti in ingresso era scandita dai valori di una variabile che di volta in volta ne assumeva uno nuovo perdendo gli altri.

In questo modo non è possibile, ad esempio, calcolare gli scarti tra i vari valori e la media. Si potrebbe pensare di memorizzare i dati in variabili diverse. Tutto ciò funziona solo se il numero di informazioni da elaborare è piccolo. Pensate ad un algoritmo che contiene 100 istruzioni del tipo:

leggi a1
leggi a2

.
.
.
leggi a100

Per situazioni di questo tipo si introduce il concetto di vettore o array unidimensionale. Si tratta di una variabile composta che racchiude in un unico nome più valori distinti. L’acquisizione dei dati avverrebbe nel seguente modo:

per i=1 fino a 100
leggi a(i)

fine per

Le diverse informazioni sono accessibili usando il nome del vettore a, seguito da un numero tra parentesi, l’indice, che può variare da 1 fino al massimo numero dei dati. Si pensi ad un vettore come una struttura graficamente rappresentabile come in figura.

 Possiamo ora strutturare un algoritmo che risolva il problema accennato poc’anzi:

inizio
totale=0

per i=1 fino a 100
leggi a(i)
totale=totale + a(i)
fine per
media=totale/100
per i=1 fino a 100
scarti(i)=a(i)-media
stampa scarti(i)
fine per
fine

Si pone a 0 il valore del totale e poi si acquisiscono i valori dei dati con il ciclo per seguente:

per i=1 fino a 100
leggi a(i)
totale=totale + a(i)
fine per

Nel ciclo si aggiorna anche il valore del totale. Calcolata la media, un nuovo ciclo per ci permette di determinare gli scarti tra i valori in ingresso e la media.

per i=1 fino a 100
scarti(i)=a(i)-media
stampa scarti(i)
fine per

I dati così calcolati vengono anche stampati.

Consideriamo un altro esempio. Si tratta dell’algoritmo di Eratostene per determinare i vari numeri primi compresi tra 1 ed un dato valore. Si basa su un ragionamento di questo tipo: si costruisce un vettore contenente i numeri interi tra 1 ed un determinato valore come si può vedere in figura.

In questo caso abbiamo generato un vettore fino al 18 con un ciclo per di questo tipo:

per i=1 fino a 18
primi(i)=i
fine per

Il prossimo passo consiste nello scorrere il vettore andando a cancellare i multipli di 2, ottenendo un risultato di questo tipo:

Quindi si eliminano i multipli del 3.

Si passa ad esaminare la prossima casella. Dovrebbe essere quella del 4, ma essendo multiplo del 2 è già stato eliminato, così come tutti i suoi multipli. Dunque eliminiamo i multipli del 5, poi del 7 e così via. Alla fine del processo le caselle non vuote conterranno numeri primi. L’algoritmo si arresta quando si arriva alla metà del vettore. Infatti dopo la metà non ci possono essere più multipli di alcun numero considerabile.
Le successive scansioni avvengono con un algoritmo di questo genere:

per i=2 fino a 9
se primi(i)<>0 allora
per j=i fino a 18

se primi(j) Mod primi(i)=0 allora
primi(j)=0
fine per
fine se

fine per
per i=1 fino a 18
se primi(i)<>0 allora
stampa primi(i)
fine se
fine per

Il per esterno gestisce la ricerca dei multipli dal 2 al 9. Entro di esso troviamo l’istruzione:

se primi(i)<>0 allora

Il simbolo < > significa diverso da. Se troviamo un numero che non è stato ancora eliminato procediamo alla rimozione dei suoi multipli entro il ciclo per controllato dalla variabile j.

per j=i fino a 18
se primi(j) Mod primi(i)=0 allora
primi(j)=0
fine per

La variabile j parte dal valore attuale di i e scandisce tutto il vettore. L’ultimo ciclo per stampa l’elenco dei numeri primi.

per i=1 fino a 18
se primi(i)<>0 allora
stampa primi(i)
fine se
fine per

Ordinamento ingenuo
Una categoria di problemi tipicamente affrontata utilizzando i vettori è l’ordinamento. Consideriamo un elenco di valori, ad esempio dei nomi, che forniamo uno dopo l’altro ad un dato algoritmo. Partendo dall’assunto che è meglio far fare il lavoro agli altri, i nomi non verranno inseriti in ordine alfabetico, ma sarà l’algoritmo stesso ad ordinarli. Rappresentiamo graficamente l’elenco:

Elenco è il nome simbolico per indicare l’insieme dei nomi. È un vettore a 6 posizioni ciascuna corrispondente ad una singola variabile. Ricordiamo che per accedere a un valore bisogna specificare la casella a cui si fa riferimento con una notazione del tipo elenco(5). Per memorizzare Nadia abbiamo dovuto eseguire l’assegnamento elenco(5) = Nadia. Di fronte ad un caso così semplice l’operazione di ordinamento sembra immediata. Se supponiamo che l’elenco sia di 10.000 nomi non è più così semplice. Si rende necessaria una strategia sistematica. Il primo metodo che consideriamo, detto a ordinamento ingenuo, determina, dopo una lettura di tutti gli elementi del vettore da sinistra verso destra, quale sia il primo in ordine alfabetico. A questo punto tale valore viene portato in prima posizione. Concretamente pensate che i valori corrispondano a tessere del domino affian­cate. Per scambiare di posizione la tessera Alessandro con la tessera Mario, bisogna spostare il tassello Mario da qualche parte, in modo da lasciare libero il posto, spostare Alessandro nel buco che si è creato, ed infine posizionare Mario nel vuoto lasciato da Alessandro. Un’altra analogia che spesso viene fatta per descrivere situazioni di questo tipo è lo scambio del contenuto di due bicchieri. Provate a farlo senza usarne un terzo. A questo proposito usiamo entro l’algoritmo una variabile ausiliaria, chiamiamola Temp, per poter veicolare lo scambio.

Resta da dettagliare come sia possibile determinare quale debba essere l’elemento da portare in prima posizione. Nel nostro esempio lo si vede subito; si provi a trovarlo in un elenco che si estende per 100 pagine. Scorrendo la lista ci si annota da qualche parte quello che fino a un dato momento risulta essere il primo in ordine alfabetico. Quando se ne trova uno che lo precede si cancella ciò che si era annotato e lo si scrive al suo posto.
Bisogna ricordarsi la posizione in cui questo potenziale primo elemento si trova, di modo da potere poi fare lo scambio senza perdita di alcun dato. Vediamo anche qui graficamente come avviene lo scorrimento del vettore. Si usa la variabile pos per memorizzare la posizione attuale del primo in ordine alfabetico trovato fino ad un dato momento. La freccia indica in quale momento della scansione ci si trova.

Siamo arrivati alla fine della scansione e sapendo che è il quarto elemento quello da portare in prima posizione possiamo effettuare lo scambio. Si tratta ora di ripetere il tutto.

La nuova scansione partirà dal secondo elemento, il primo è già a posto. Ecco la sequenza dei risultati delle varie passate.

Si noti che al termine del secondo e terzo passaggio il vettore non ha subito cambiamenti, poiché accidentalmente il secondo e terzo elemento sono già nella corretta posizione in partenza. Comunque l’algoritmo, per potersene accorgere, ha bisogno di scorrere tutto l’insieme di valori. Per potere far passare tutti gli elementi del vettore si usano due cicli per, uno dentro l’altro:

per i=1 fino a 5
per j=i fino a 6
fine per

fine per

 

Il ciclo più esterno gestisce le varie passate, che infatti sono 5. Dopo la quinta l’ultimo elemento è sicuramente in posizione giusta. Il ciclo per più interno invece parte dalla porzione del vettore non ancora ordinata per cercare il minimo. Infatti con la prima passata (i=1) non abbiamo ancora trovato il più piccolo e quindi devo scorrere tutto il vettore a partire dall’inizio (j=1). Con la seconda (i=2), il primo elemento lo abbiamo già messo al suo posto e quindi la ricerca procede dal secondo in avanti (j=2) e così via. Si generalizza il ragionamento rendendosi conto che il valore da cui parte j coincide con il valore attuale di i. Vediamo l’algoritmo completo.

inizio
per i=1 fino a 6
leggi elenco(i)
fine per

per i=1 fino a 5
per j=i fino a 6
se i=j allora

pos=j
altrimenti
se elenco(j)<elenco(pos) allora
pos=j
fine se
fine se
fine per

temp=elenco(i)
elenco(i)=elenco(pos)
elenco(pos)=temp

fine per
per i=1 fino a 6
stampa elenco(i)
fine per

fine

Analizziamo le varie fasi.

per i=1 fino a 6
leggi elenco(i)
fine per

Questa fase corrisponde all’acquisizione in ingresso in maniera ordinata dei valori dell’elenco uno alla volta. Seguono i due per commentati sopra:

per i=1 fino a 5
per j=i fino a 6
fine per

fine per

Quindi dentro il ciclo più interno troviamo:

se i=j allora
pos=j
altrimenti
se elenco(j)<elenco(pos)
allora

pos=j
fine se
fine se

La logica di questa parte di programma risiede nella considerazione che, se si sta iniziando una nuova passata, sicuramente il primo valore che viene letto (i = j) è temporaneamente il primo nell’ordine alfabetico (se ne è letto solo 1) e se ne memorizza la posizione nella variabile pos, altrimenti si dovrà fare un confronto tra ciò che è stato determinato essere il più piccolo fino ad ora e quello che si sta leggendo attualmente. Nel caso sia alfabeticamente antecedente si aggiorna il valore di pos, annotando il risultato parziale. Terminato il ciclo più interno, si conclude la prima passata ed è possibile effettuare lo scambio. Nell’algoritmo lo scambio viene fatto lo stesso anche se logicamente non necessario anche nel caso di elemento già in ordine. Scambiare una variabile con se stessa comunque non ne altera il valore. Abbiamo infine:

per i=1 fino a 6
stampa elenco(i)
fine per

che è semplicemente la stampa dei valori nel corretto ordine alfabetico.
II metodo che abbiamo considerato viene detto ingenuo perché è il più semplice ed intuitivo. Questo metodo ha lo svantaggio, rispetto ad altri, di richiedere molti più passi.

Metodo degli interscambi
Consideriamo adesso una procedura più vantaggiosa. È detta metodo degli interscambi. Consiste nel percorrere il vettore confrontando tra di loro gli elementi adiacenti e scambiandoli nel caso non siano in ordine.
Nel caso raffigurato in figura abbiamo cominciato a scandire il vettore ed abbiamo determinato che i primi due elementi non sono in ordine e quindi vengono invertiti.

Mostriamo ora, in sequenza, l’evolversi del contenuto del vettore durante una scansione completa:

La scansione ha avuto termine con il confronto tra il penultimo e l’ultimo elemento, quindi il ciclo for (per) che la gestisce partirà dal primo indice del vettore ed arriverà al penultimo. Abbiamo ottenuto una versione dell’elenco più vicina all’ordinamento finale. Saltando i passi intermedi si mostra lo stato del vettore alla fine degli altri passaggi dell’algoritmo. Qui non si è portato in prima posizione il primo degli elementi quindi ogni nuovo passaggio riparte dalla prima posizione.
L’algoritmo ha termine in 4 passaggi e quindi è più veloce di quello visto prima che ne richiedeva 5. Qualcuno potrà obbiettare che in realtà al terzo passo, il vettore risulta ordinato. Ciò è vero, però necessita un’ulteriore passaggio per potere terminare il compito. Infatti non conoscendo a priori il numero di scansioni da compiere l’unico modo per riconoscere che si è giunti al termine dell’opera è una passata del vettore durante la quale non si hanno scambi, che, valendo la proprietà transitiva della relazione d’ordine, garantisce il termine a buon fine dell’algoritmo.
Non sapendo quante volte va iterata la scansione del vettore, non possiamo controllarla con un ciclo per. Avremo bisogno di una struttura iterativa controllata da una condizione logica in un mentre oppure in un ripeti.

Il nucleo centrale dell’algoritmo sarà costituito dai due cicli annidati seguenti:

ripeti
per i=1 fino a 6
fine per
finché non è ordinato

che meglio dettagliati diventano:

ripeti
per i=1 fino a 6
fine per
finché non ci sono più scambi da fare

Ancora non siamo arrivati al dettaglio algoritmico di una serie di istruzioni univocamente interpretabili. Dobbiamo specificare come denotare l’avvenimento di operazioni di scambio. Lo facciamo utilizzando una variabile ausiliaria, che chiamiamo scambio, la quale parte da 0 ogni volta che inizia il ciclo più esterno e viene posta ad 1 quando viene effettuato un qualsiasi scambio. Alla fine, se il suo valore è rimasto 0 si avrà il riconoscimento dell’ordine del vettore e si potrà uscire. In altri termini avremo:

ripeti
scambio=0
per i=1 fino a 6
qui viene eventualmente alterato il valore di scambio se si scambiano tra loro due elementi.
fine per
finché scambio=1

L’algoritmo completo diventa:

inizio
per i=1 fino a 6
leggi elenco(i)
fine per

ripeti
scambio=0
per i=1 fino a 5
se elenco (i)>elenco (i+1)
allora
temp=elenco(i)
elenco(i)=elenco(i+1)
elenco(i+1)=temp

scambio=1
fine se
fine per

finché scambio=1
per i=1 fino a 6
stampa elenco(i)
fine per

fine

Ricerca sequenziale
Oltre all’ordinamento, ci sono molti altri algoritmi da considerare, ad esempio, un’altra classe di problemi tipici con i vettori è la ricerca entro un elenco. L’algoritmo più semplice è quello della ricerca sequenziale. Si tratta di passare in rassegna uno dopo l’altro i valori memorizzati confrontandoli con l’elemento da ricercare. Se lo si trova si termina la ricerca, altrimenti si arriva alla fine del vettore e si annota l’assenza del dato ricercato. L’algoritmo si presenta nel seguente modo:

inizio
leggi valore
trovato=falso
i=1

ripeti
se valore=elenco (i) allora
trovato=vero
altrimenti
i=i+1
fine se
finché trovato=vero oppure i>dimensione
se trovato=vero allora
stampa “Ho trovato il valore nel vettore”
altrimenti
stampa “Non ho trovato il valore nel vettore”
fine se
fine

Per gestire la ricerca utilizziamo un ciclo ripeti finché la cui condizione di terminazione è la seguente:

trovato=vero oppure i > dimensione

È una condizione composta, infatti si esce dal ciclo se si è determinata la presenza del valore nell’elenco e la variabile trovato ha assunto valore vero, oppure se si è arrivati alla fine del vettore nel momento in cui la variabile i ha superato il valore di dimensione che si suppone sia l’indice maggiore all’interno del vettore. Dovrebbe essere chiaro che mediamente bisogna scorrere metà del vettore per trovare un elemento e bisogna arrivare alla fine per determinarne l’assenza.

Consideriamo ora algoritmi più efficienti.
Vediamo il classico esempio della ricerca binaria. Bisogna avere a disposizione un vettore precedentemente ordinato.
Supponiamo di dover determinare la presenza del valore 12 nella struttura in figura:

Il metodo utilizza 3 valori associati agli indici del vettore in cui effettuare la ricerca. Sono sin, centro e des rappresentati nella figura. Inoltre, riceve in input un valore da ricercare: a=12. All’inizio le prime tre variabili coincidono, rispettivamente, sin con il primo indice, centro con il valore medio, arrotondato all’intero inferiore, e des con l’ultimo. Da sin e des si può determinare centro ed a questo punto si va a leggere il valore memorizzato nel vettore nella posizione di indice centro. Se a è superiore a ciò che viene trovato in posizione centro, 7 nel caso della figura, si considera la porzione superiore del vettore altrimenti quella inferiore. Essendo il vettore precedentemente ordinato, se a è inferiore all’11 non può che essere nella prima parte del vettore. sin resterà identico a se stesso, mentre des viene aggiornato assumendo valore pari a centro. Qualora a risultasse superiore al valore memorizzato in posizione centro, l’aggiornamento dovrà coinvolgere sin che assumerà valore pari a centro, mentre des non cambierà. Nel caso in cui si abbia coincidenza tra il valore memorizzato in centro e a la ricerca ha ovviamente successo.

L’ultimo passo della ricerca è il seguente:

Per capire come strutturare l’algoritmo consideriamo anche il caso di ricerca di un elemento assente, ad esempio il 6:

Essendo venuti a coincidere centro e i due estremi, l’algoritmo ha termine e si stabilisce l’assenza dell’elemento ricercato. Per paragonare l’efficienza di questa strategia rispetto alla ricerca sequenziale consideriamo che cosa avviene in una ricerca entro un vettore di dimensione pari ad una potenza del 2 ad esempio 1024, 210. Al primo passaggio la ricerca si riduce alla metà degli elementi cioè 512. Poi 256, 128, 64, 32, 16, 8, 4, 2, 1. In 10 passaggi si arriva sicuramente a determinare la presenza o l’assenza del dato. In una ricerca sequenziale anche se il vettore è ordinato, in media bisogna scorrerlo a metà e cioè in
questo caso fare 512 confronti. Consideriamo ora l’algoritmo relativo:

inizio
trovato=falso
leggi a
sin=1

des=dimensione
ripeti
centro=(sin+des)/2

se a=elenco(centro) allora
trovato=vero
altrimenti
se a>elenco(centro) allora
sin=centro
altrimenti
des=centro
fine se
fine se

finché trovato=vero oppure sin=des
se trovato=vero allora
stampa “Ho trovato il valore cercato”
altrimenti
stampa “Non ho trovato il valore cercato”
fine se
fine

L’algoritmo comincia con l’assegnazione dei valori iniziali alle variabili che ci interessano e la lettura del valore da ricercare:

trovato=falso
leggi a
sin=1

des=dimensione

La variabile trovato ci serve per indicare l’avvenuto reperimento dell’informazione. Quindi troviamo un ciclo ripeti così strutturato:

ripeti

finché trovato=vero oppure sin=des

La ricerca va avanti fino a che si trova il dato cercato (trovato = vero), oppure l’intervallo si è ristretto fino a far coincidere i due estremi.
All’interno del ripeti si calcola il valore intermedio:

centro=(sin+des)/2

A questo punto si confronta il dato da cercare con quello memorizzato nella posizione centrale:

se a=elenco(centro) allora
trovato=vero
altrimenti
se valore>elenco (centro) allora
sin=centro
altrimenti
des=centro
fine se
fine se

Eseguite queste istruzioni si testa la condizione del ripeti e se è il caso il ciclo termina. In funzione del valore che la variabile trovato assume si effettua la stampa del messaggio di output dell’algoritmo.

se trovato=vero allora
stampa “Ho trovato il valore cercato”
altrimenti
stampa “Non ho trovato il valore cercato”
fine se

Le matrici

Oltre agli array unidimensionali, cioè i vettori, possono servire, in alcune situazioni, delle strutture a due o più dimensioni. In questo caso si parla di matrici. Una matrice è una struttura contenente una serie di valori distribuiti in righe e colonne come nel caso in figura.

Si tratta di una matrice a quattro righe e quattro colonne. Non è detto che il numero di righe coincida con il numero di colonne. Se ciò avviene si parla di matrice quadrata. Ai dati si accede specificando il nome della struttura, riga e colonna in cui si trova il valore che interessa. Ad esempio, a(2,4) vale proprio 18 (l’elemento in seconda riga e quarta colonna). Così come per scandire un vettore è necessario un ciclo per, nel caso di una matrice se ne devono usare 2, uno per spostarsi di riga e l’altro per seguire le colonne. Si consideri il seguente algoritmo:

per i=1 fino a 4
per j=1 fino a 4
leggi a(i,j)

fine per
fine per

Il primo ciclo è associato ai valori del contatore i che viene utilizzato per indicare la riga, mentre il secondo è associato ai valori della colonna. Dunque per ogni riga si scandiscono tutte le colonne e volta in volta si inseriscono i valori. La matrice viene riempita così una riga per volta. Se consideriamo invece, le seguenti istruzioni:

per j=1 fino a 4
per i=1 fino a 4
leggi a(i,j)

fine per
fine per

stiamo effettuando un inserimento dei valori colonna per colonna poiché è l’indice di colonna ad essere inserito nel per più esterno.

Prato fiorito
In figura abbiamo catturato una schermata di «Prato fiorito», un gioco disponibile in Windows. Vediamo quale può essere l’algoritmo con cui si controlla quanti fiori siano adiacenti ad una data cella. Letti i valori di un indice di riga e di colonna, si dovrà accedere alle celle contigue a quella così determinata per vedere se è presente un fiore. I dati nella matrice che codifica la partita di prato fiorito sono 0 se non c’è il fiore, 1 se viceversa è presente.

La generica casella di indici i e j è circondata da tre fiori. Per scoprirlo dobbiamo eseguire un codice del genere:

fiori=0
per h=i—1 fino a i+1
per k=j—1 fino a j+1
se (h>=1 e h<=dimensione righe) e (k>=1 e k<=dimensione colonne)
allora
se non(h=i e k=j) allora
se matrice (h,k)=1 allora
fiori=fiori+1

fine se
fine se

fine se
fine per
fine per

Si inizializza la variabile fiori a zero; con due per annidati si scandisce la porzione di matrice adiacente alla cella matrice(i, j). Bisogna stare attenti a gestire i casi particolari di celle ai confini della matrice per le quali non ci sono tutte le otto caselle adiacenti. Ciò è fatto dal controllo seguente:

se (h>=1 e h<=dimensione righe) e (k>=1 e k<=dimensione colonne) allora

in cui effettivamente si testa se le variabili h e k sono comprese nell’intervallo ammesso per gli indici di riga e colonna. Solo se è così, si va a leggere il contenuto della cella indicizzata da h e k che effettivamente esiste. Si tenga presente che la cella centrale non deve essere letta. Infatti in seguito troviamo il codice:

se non(h=i e k=j) allora
se matrice (h,k)=1 allora
fiori=fiori+1

fine se
fine se

esclude la lettura della cella centrale, controllando che h e k non siano uguali ad i e j.
Il se più interno controlla che nella cella sia memorizzato un 1, nel qual caso si incrementa il numero di fiori.

se matrice(h,k)=1 allora
fiori=fiori+1
fine se

ESEMPIO 2
Scacchiera
Abbiamo rappresentato una scacchiera nella quale nella casella (7, 2) (usiamo tale notazione anche se nel mondo degli scacchi si individuano le colonne con le lettere invece che con i numeri) si trova piazzata una Regina. Si tratta per chi non lo sapesse, di un pezzo che può essere spostato in orizzontale, verticale ed in diagonale. Le caselle con i cerchi indicano le possibili posizioni in cui spostare la Regina. La Regina può, muovendosi, mangiare il Re prendendone il posto. Non può nel caso in figura mangiare il Cavallo. Inoltre non può neanche saltare dei pezzi e quindi anche la Torre non può essere mangiata.

Vogliamo costruire un algoritmo che elenchi in uscita tutti i pezzi che possono essere presi dalla Regina che si trova nella generica casella (i, j) della scacchiera.
Dobbiamo gestire dei possibili spostamenti in 8 direzioni. In verticale ci si muove lasciando fissa la colonna, in orizzontale lasciando fissa la riga. Per quanto concerne gli spostamenti in diagonale incrementando o decrementando di un’unità, a seconda della direzione del movimento, sia l’indice di riga sia l’indice di colonna. Ricordiamoci che dobbiamo arrestarci non appena troviamo qualcosa. Vediamo gli spostamenti divisi per direzione.

Spostamento orizzontale

h=i
k=j+1
trovato=0

mentre (k<=8 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
k=k+1
fine mentre
trovato=0
k=j—1

mentre (k>=1 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
k=k—1
fine mentre

Si assegnano i valori iniziali alle variabili che ci servono.

h=i
k=j+l

trovato=0

h scandisce la riga, k la colonna; trovato indica se abbiamo lungo la direzione di movimento incontrato qualcosa.
Inizia il ciclo che gestisce la scansione da sinistra verso destra.

mentre (k<=8 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
k=k+1
fine mentre

La condizione di arresto del ciclo è:

k<=8 e trovato=0

Infatti ci si ferma o quando si è arrivati al bordo della scacchiera oppure se abbiamo trovato un pezzo da mangiare. Si controlla se nella casella attuale ci sia un pezzo, supponendo che le caselle vuote contengano uno 0 con il seguente gruppo di istruzioni:

se scacchiera(h,k)<>0 allora
trovato=1
stampa(“puoi mangiare ciò che si trova nella casella h,k”)
fine se
k=k+1

Segue l’incremento di k.
In modo analogo ci si comporta per lo spostamento verso il bordo sinistro della scacchiera. k partirà da j – 1 e verrà decrementato di volta in volta invece che essere incrementato. Con una logica del tutto simile viene gestito lo spostamento in verticale.

Spostamento verticale

h=i+1
k=j
trovato=0

mentre (h<=8 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h, k”)
fine se
h=h+1
fine mentre
trovato=0
h=i—1

mentre (h>=1 e trovato=0) fai
se scacchiera (h, k) <>0 allora
trovato=1
stampa (“puoi mangiare ciò che si trova nella casella h, k”)
fine se
h=h—1
fine mentre

Passiamo a considerare gli spostamenti in diagonale
Spostamento lungo la diagonale principale

h=i+1 k=j+1
trovato=0
mentre (h<=8 e k<=8 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
h=h+1
k=k+1

fine mentre
trovato=0
h=i—1

k=k—1
mentre (h>=1 e k>=1 trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
h=h—1 k=k—1
fine mentre

La logica dello spostamento su questa diagonale prevede, andando verso il basso, un incremento unitario degli indici e un corrispondente decremento per lo spostamento verso l’alto. Visto che sia h sia k variano, bisogna controllare che entrambi i valori non fuoriescano dai limiti della scacchiera. Scendendo, aumentano tutti e due, bisogna verificare che non superino il valore 8. Salendo bisogna verificare che rimangano superiori all’1.

Spostamento lungo la diagonale secondaria

h=i—1
k=j+1
trovato=0

mentre (h>=1 e k<=8 e trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
h=h—1
k=k+l

fine mentre
trovato=0
h=i+1

k=k—1
mentre (h<=8 e k>=1 trovato=0) fai
se scacchiera(h,k)<>0 allora
trovato=1

stampa (“puoi mangiare ciò che si trova nella casella h,k”)
fine se
h=h+l
k=k—1

fine mentre

ESEMPIO 3
Quadrato magico
Osservate la figura, si tratta di un quadrato magico, cioè una particolare disposizione dei primi nove numeri interi tale per cui, eseguendo la somma di tutti i valori lungo una riga, una colonna e lungo le due diagonali si ottiene sempre lo stesso risultato, cioè 15 nel nostro caso. Proviamo a descrivere un algoritmo in grado di controllare se una matrice quadrata di interi è un quadrato magico.
Una prima parte dell’algoritmo deve memorizzare la somma di una qualsiasi riga o colonna o diagonale. Poi si esegue una scansione delle righe calcolando i vari totali. Se continuano a coincidere con il primo calcolo si prosegue, altrimenti l’algoritmo si deve arrestare. Una seconda fase scandisce le colonne, infine si avrà la fase che esamina le due diagonali.

Scansione orizzontale

totale=0
per j=l fino a n
totale=totale+quadrato(l,j)

fine per
somma=totale i=2

mentre (somma=totale e i<=8) fai
somma=0
per j=1 fino a n
somma=somma+quadrato (i,j)

fine per
i=i+l
fine mentre

L’algoritmo comincia calcolando la somma sulla prima riga ed assegnando il risultato alla variabile totale. A questo punto passa a considerare le altre righe assegnando ad i il valore 2 e alla variabile somma il valore di totale. In questo modo si può entrare nel ciclo mentre essendo la sua condizione logica soddisfatta. Si deve usare un mentre invece di un per perché l’algoritmo non è obbligato a scorrere tutta la matrice. E possibile arrestare il processo in qualsiasi momento non avendo trovato più coincidenza nei risultati. Per ogni riga si ricalcola da capo il valore di somma entro il ciclo per controllato da j. Alla fine della scansione di tutte le righe se ha avuto successo il controllo vale l’uguaglianza somma = totale e quindi per la scansione in verticale è possibile evitare l’assegnamento.

Scansione verticale

se somma=totale allora
j=1
mentre (somma=totale e j<=8) fai
somma=0
per i=1 fino a n
somma=somma+quadrato
(i,j)
fine per

j=j+1
fine mentre
fine se

La logica è del tutto simile a quella della passata in orizzontale tranne che vincoliamo l’esecuzione solo al caso in cui la passata orizzontale abbia dato esito favorevole. Questo è il senso del se iniziale.

Scansione della diagonale principale

se somma=totale allora
somma=0
per i=1 fino a n
somma=somma+quadrato(i,i)
fine per

fine se

Per la diagonale principale ci basta un solo indice poiché gli elementi che la costituiscono hanno la caratteristica di essere posizionati su caselle con uguali valori di riga e colonna. Il generico elemento sarà del tipo quadrato (i,i).
Risulta un pochino meno immediato definire la caratteristica che individua univocamente gli elementi dell’altra diagonale. Se ci fate caso la somma degli indici degli elementi della diagonale secondaria fornisce sempre il valore 4 nel caso del nostro quadrato. In generale vale n+1.
Generalizzando la caratteristica sarà che i + j = n +1 e cioè j = n + 1 – i. Avendo definito i valori dell’indice j in funzione di i posso usare un solo per anche per l’ultima scansione.

Il codice è il seguente:

se somma=totale allora
somma=0
per i=1 fino a n
somma=somma+quadrato(i,n+1-i)

fine per
fine se

se somma=totale allora
stampa “è un quadrato magico”
altrimenti
stampa “non è un quadrato magico”
fine

Abbiamo aggiunto alla fine dell’ultima fase le istruzioni per la stampa dei risultati.

Le strutture dati astratte
Le liste
Per introdurre il concetto di lista consideriamo la figura.

Abbiamo una variabile, testa, ed una tabella le cui due colonne contengono dati di diverso significato. La prima colonna rappresenta l’informazione utile, mentre la seconda servirà per collegare tra loro le informazioni. Testa rappresenta la posizione della prima informazione da leggere. Si accede dunque alla colonna informazione della tabella in riga 2. Il valore che viene memorizzato è il 3. Questa informazione è collegata ad un’altra tramite il numero al suo fianco nel campo collegamenti. Tale valore è 4 e sta ad indicare che il prossimo dato da leggere si trova in riga 4. Si va a leggerlo trovando il valore 5. Si consideri il campo Collegamenti. Vi è memorizzato un 1 e dunque si dovrà passare alla prima riga leggendo il numero 9 e come collegamento il valore 3. Ci si sposta nella terza riga leggendo il 13 e poi uno 0 come collegamento. Tale valore indica che dopo il 13 non c’è più informazione utile. Se si riconsidera la sequenza dei numeri letti, la si trova pari a 3, 5, 9, 13. In altri termini grazie all’uso dei valori di collegamento si accede alla sequenza di valori in modo ordinato, senza dover applicare alcun algoritmo specifico per tale operazione.
Dunque si può dire che una lista non è nient’altro che un elenco mantenuto costantemente ordinato. La lista è un oggetto non fornito direttamente nei linguaggi di programmazione per cui viene detta struttura dati astratta, differenziandola dalle strutture dati concrete (vettori e matrici) direttamente previste dalla sintassi di tutti i linguaggi.

Consideriamo ora la sequenza dei passi con cui viene costruita una lista.
Viene acquisito in ingresso il valore 9 e lo si memorizza nella prima posizione libera nella matrice. La variabile testa vale 1, il campo collegamento resta a 0 poiché l’elenco contiene solo 1 valore.

Si legge il valore 3 e viene immesso nella prima posizione libera nella matrice. Il valore della variabile testa dovrà essere coerentemente aggiornato perché dovrà indicare la posizione del valore più piccolo ed anche il campo collegamento sarà di conseguenza adattato. Se si prova a scorrere l’elenco, seguendo la regola di leggere prima le informazioni, partendo da quella di riga testa, e poi proseguendo usando i valori di collegamento, ci si accorge che l’ordine di lettura è 3,9.


Viene letto il tredici e lo si posiziona nella prima riga libera. Non deve essere aggiornato il valore di testa, ma si deve creare il collegamento tra il 9 ed il 13 cambiando il valore memorizzato nella cella di collegamento del 9 in modo da garantire che la sequenza di accesso ai dati sia ora 3,9,13. L’ultimo inserimento produce ora la situazione:


In questo caso si è dovuto cambiare il collegamento relativo al numero 3. Infatti adesso non deve più legarsi al 9, ma al 5 e sarà il 5 ad essere collegato al 9.


Si sarebbe potuto rappresentare astrattamente la sequenza di operazioni che sono state effettuate anche con la seguente sequenza di diagrammi:

Questo tipo di rappresentazione cerca di evidenziare la natura della lista come catena di valori agganciati uno all’altro e reperibili sequenzialmente partendo dalla posizione iniziale. Le liste hanno la caratteristica di essere strutture ad accesso sequenziale. Per capire tale concetto si pensi ad una musicassetta. In essa i vari brani musicali sono registrati in modo tale che per poter ascoltare una qualsiasi canzone si è costretti a svolgere il nastro fino a quando non la si incontri.
Viceversa un lettore di CD ROM permette di ascoltare le canzoni posizionando il dispositivo di lettura e riproduzione direttamente sul brano che interessa. In situazioni di questo tipo si parla di dispositivi ad accesso diretto. Riconsiderando le caratteristiche della struttura a lista, cioè ordinamento dinamico ed accesso sequenziale è possibile apprezzarne i vantaggi e guardarsi dai suoi difetti. Quando l’esigenza primaria dell’applicazione informatica è il mantenimento di informazione ordinata, la scelta delle liste risulta vantaggiosa. Se invece risulta prioritaria la velocità di reperimento dell’informazione e i dati sono immessi raramente o solo all’inizio dell’utilizzo del programma potrebbe essere preferibile una soluzione che utilizzi dei vettori.
Infatti, per la sua natura intrinsecamente sequenziale la lista permette una ricerca di durata media n/2, se n è il numero di dati memorizzati, mentre si era visto in un vettore ordinato la ricerca binaria permette prestazioni decisamente migliori. Usando i vettori si tenga però conto della necessità di un riordinamento dopo ogni immissione. Altro svantaggio della soluzione con le liste è l’uso di una quantità di memoria doppia rispetto al vettore, vista la necessità dei valori di collegamento. Sul modello astratto considerato in precedenza è facile rendersi conto delle operazioni che, da un punto di vista algoritmico, sono necessarie per gestire una lista.
Distinguiamo tra la ricerca e l’inserimento.

Ricerca con successo
Si voglia determinare la presenza del 9 nella lista. La freccia verticale indica a quale anello della catena si è arrivati ad ogni passo:

Ricerca con fallimento
Questa volta andiamo alla ricerca del valore 7

L’operazione di ricerca non presenta particolari difficoltà concettuali ed è del tutto analoga ad una ricerca sequenziale su un vettore ordinato. Il procedimento che si è dettagliato è di natura semi-algoritmica poiché esso va realmente condotto simulando la lista con la matrice considerata ad inizio paragrafo. Maggiori problemi concettuali pone l’inserimento di un elemento nella lista.

Inserimento in testa
Si deve inserire un nuovo valore ed esso risulta pari ad 1.

Inserimento in posizione intermedia
Si deve inserire un nuovo valore pari a 4.

Inserimento in coda
Si vuole immettere il valore 15

Le code
Una coda viene detta anche struttura di tipo FIFO (First In First Out, il primo ad entrare è il primo ad uscire). Si pensi a qualsiasi fila in attesa di un certo servizio (cassa, sportello di banca, casello autostradale. ecc.).
Si può schematizzare tale situazione con un vettore opportuno che è la struttura concreta corrispondente alla struttura astratta coda.

Si supponga che siano arrivate ad un casello autostradale un certo numero di macchine, diciamo 10, ed ancora nessuna sia stata servita. Avremmo la situazione di figura.

Nel momento in cui viene fatto il pagamento del pedaggio da parte del primo automobilista la situazione diventa quella di figura.

L’utente servito è scomparso dalla struttura e gli altri sono scalati di una posizione. Se nel frattempo arriva un’altra macchina, la coda si modifica come in figura.

Viene effettuato un altro pagamento e dunque si avrà:

Dovrebbe essere chiaro come viene gestita la situazione. In generale una coda è associata ad un vettore e a due indici, uno rappresenta l’inizio della coda, l’altro la fine.

Da un punto di vista logico le operazioni su una coda sono due: l’arrivo di un nuovo elemento ed il servizio del primo utente in attesa. Sembrerebbe molto facile programmare i due eventi:

nuovo arrivo:
coda(fine)=nuovo elemento               l’ultimo arrivato va in fondo
fine=fine+1                             viene aggiornata la prima

                                        posizione libera
servizio di un utente:
coda(inizio)=0                          si cancella la posizione di chi è stato servito
inizio=inizio+1                         si aggiorna la posizione iniziale

Si tengano però presenti i seguenti problemi: per prima cosa il vettore che rappresenta la coda avrà una certa dimensione massima oltre la quale non sarà più possibile memorizzare informazione; inoltre, si pensi al fatto che man mano che la situazione evolve nel tempo le informazioni nel nostro vettore slittano verso destra. Si avrà ad un certo punto a che fare con la situazione di figura a.
Nel vettore ci sono posti liberi per nuovi arrivi ma non si trovano più alla destra dell’array, quindi si deve ricominciare da capo inserendo gli eventuali nuovi utenti a partire dall’inizio. Arrivano altri due elementi e si consideri cosa succede se nel frattempo non è stato svolto alcun servizio figura b.

Da questo punto in poi, essendo completamente riempito il vettore non potrà essere più accettato nessun arrivo. Bisogna aspettare l’espletamento di un servizio. Fatte queste considerazioni le due operazioni vengono modificate nel seguente modo:

nuovo arrivo:
se fine<>inizio allora
coda(fine)=nuovo elemento
se fine<ultimoindice
fine=fine+1

altrimenti
fine=1
altrimenti
rifiutare l’ingresso
fine se

servizio di un utente:
coda(inizio)=vuoto

se inizio=ultimoindice
inizio=inizio+1

altrimenti
inizio=1
fine se

la variabile ultimoindice nell’algoritmo rappresenta la dimensione del vettore.

Le pile
Le pile invece sono dette strutture LIFO (Last In First Out, l’ultimo arrivato è il primo ad essere servito). Si pensi, per figurarsi un utilizzo di una struttura del genere, l’apertura di più finestre sul desktop di Windows.
Nella schermata si sovrappongono le tre finestre di Excel Word e Power Point, nell’ordine in cui sono stati aperti, Word Excel e Power Point dopo Word. Se si richiudono le finestre sparirà per prima la superiore e così via in ordine contrario a quello di apertura. L’ultimo ad essere aperto è il primo ad essere chiuso.

Questa è l’essenza delle pile. A volte tali strutture sono denotate con il nome di stack, in italiano catasta, per l’analogia con un insieme di oggetti che vanno a sovrapporsi. Anche una pila può essere gestita con un semplice vettore.

Basta un solo indice, per indicare la cima della struttura. Le due operazioni possibili sono:

push, ovvero inserimento di un elemento
cima=cima+1
se cima<=ultimoindice allora
pila(cima)=nuovo elemento
altrimenti
rifiuta l’inserimento
fine se
pop, ovvero estrazione di un elemento
se cima>0 allora
estrai l’elemento
cima=cima-1

altrimenti
non ci sono elementi da estrarre
fine se

Si noti che rappresentando la pila con un vettore di dimensioni finite abbiamo dovuto trattare opportunamente i due casi di tentativo di estrazione da una pila vuota ed inserimento in una pila ormai ricolma.

Gli alberi
Proseguendo nella trattazione delle strutture dati astratte, arriviamo a considerare gli alberi. Si erano già incontrati in un altro modulo degli esempi di albero. Ne consideriamo altri.

ESEMPIO 1
File system

Nella parte destra della figura è presente la rappresentazione gerarchica delle cartelle di Windows. A partire dalle risorse del computer si osserva una divisione in: floppy, C:, D: che a loro volta contengono altre sottocartelle. Questa gerarchia è memorizzata in un albero di cui risorse del computer è la radice, floppy, C:, D: sono i figli, nuovi nodi della struttura, che a loro volta contengono altre cartelle figli, e così via fino ad arrivare ai file che sono le foglie dell’albero.

ESEMPIO 2
Espressioni matematiche
Si consideri l’espressione matematica: a·b+c·d–a/e. Quando va calcolata la formula precedente, bisogna eseguire le operazioni a precedenza più elevata, moltiplicazioni e divisioni, poi le altre. A parità di precedenza si stabilisce che l’ordine di valutazione dell’espressione sia da destra verso sinistra. In altri termini per prima cosa si esegue a·b, poi c·d, poi a/e quindi la somma ed infine la differenza. La struttura di questa espressione può essere rappresentata con il seguente schema ad albero:

La struttura indica esplicitamente come eseguire i calcoli. Si parte dal basso a sinistra, con le due foglie a e b, si risale di un livello a determinare l’operazione da fare su queste due variabili contenuta nel loro nodo genitore. Questo nodo viene sostituito con il risultato dell’operazione. Si cercano le prossime due foglie andando verso destra e si ripete l’operazione. Vediamo graficamente come avviene l’esecuzione dell’espressione nei vari passaggi:

Questo esempio introduce un caso particolare, ma molto importante, di albero, cioè l’albero binario. Si ha un albero binario quando ogni nodo ha al più due figli. Si ricordi come erano state rappresentate le liste, cioè con due vettori di cui uno conteneva le informazioni, l’altro i collegamenti. Avendo, nel caso di albero binario, per ogni elemento due potenziali figli si dovranno rappresentare i collegamenti con due vettori uno per i figli destri l’altro per i figli sinistri

Ad esempio l’albero binario dell’espressione dell’esempio 2 è memorizzato con i vettori di figura.

Partendo dalla radice, se si seguono i collegamenti nei vettori dei figli destri e sinistri si dovrebbe senza fatica ricostruire l’albero.
Se l’albero non è binario, ovvero possiede più di due figli per ogni nodo, la situazione si complica alquanto. Accenniamo al fatto che potremmo usare, per rappresentare tale struttura astratta, una lista per ogni nodo. La lista conterrebbe i collegamenti ai vari figli. Un modo ingegnoso per memorizzare un generico albero è simularlo con un albero binario.

L’albero di figura non è binario in quanto il nodo a possiede tre figli così come il nodo b.

Si trasforma l’albero di partenza con il seguente metodo. Si parte dalla radice e si genera un elenco di successori che vengono memorizzati alla sinistra del nodo originario.

In seconda battuta aggiungiamo a b i suoi eventuali figli. Visto che l’albero trasformato dovrà essere binario aggiungerò l’elenco dei nodi figli uno di seguito all’altro nell’unico collegamento libero che il nodo b al momento possiede, cioè a destra.

Infine dobbiamo ancora memorizzare i figli di d. Per coerenza con la logica di costruzione dell’albero, se li mettessimo a sinistra di d, diventerebbero dei fratelli di d stesso rispetto alla struttura dell’albero originario. Pertanto si è costretti ad inserirli nella direzione opposta. Osservando la figura si nota che l’albero trasformato è effettivamente binario e dunque rappresentabile con solo tre vettori.

I grafi
L’ultima struttura astratta che verrà trattata sono i grafi. Si supponga di dover schematizzare la struttura dei collegamenti di una rete, sia ferroviaria, sia telefonica, sia Internet. Si avranno delle entità (stazioni, centraline, computer) dette nodi tra loro connesse da dei collegamenti detti archi. Si osservi la figura. Gli archi in questa situazione sono orientati e possono essere percorsi in una sola direzione. Ad ogni arco si suppone sia associato un dato informativo (distanza, tempo di percorrenza. ecc.). Ci si pone adesso il problema di trovare una struttura concreta per rappresentare nella memoria di un calcolatore tale informazione.

Si tratta semplicemente di una matrice quadrata di dimensioni pari al numero dei nodi. Ogni riga verrà riempita indicando in essa per ogni collegamento il valore numerico associato. In altri termini, se dal nodo 1 si può giungere al nodo 2 con un costo pari a 10, in riga 1, colonna 2 della matrice è posto il valore 10 e così proseguendo. Si noti che, è possibile che i collegamenti siano bidirezionali ed il costo nelle due direzioni sia il medesimo. Gli archi nel grafo non saranno più orientati ed il valore entro la matrice dovrà essere memorizzato due volte per i due possibili sensi di percorrenza.

    Click to listen highlighted text! I vettoriFino ad ora abbiamo considerato sempre algoritmi adatti a risolvere problemi in cui comparivano variabili semplici. A volte può essere necessario raggruppare insieme valori sotto un unico nome. Abbiamo considerato in precedenza algoritmi per calcolare medie, massimi e minimi. Si basavano sull’acquisizione ripetuta di valori ed opportuni calcoli. La sequenza di dati letti in ingresso era scandita dai valori di una variabile che di volta in volta ne assumeva uno nuovo perdendo gli altri. In questo modo non è possibile, ad esempio, calcolare gli scarti tra i vari valori e la media. Si potrebbe pensare di memorizzare i dati in variabili diverse. Tutto ciò funziona solo se il numero di informazioni da elaborare è piccolo. Pensate ad un algoritmo che contiene 100 istruzioni del tipo: leggi a1 leggi a2...leggi a100 Per situazioni di questo tipo si introduce il concetto di vettore o array unidimensionale. Si tratta di una variabile composta che racchiude in un unico nome più valori distinti. L’acquisizione dei dati avverrebbe nel seguente modo: per i=1 fino a 100 leggi a(i)fine per Le diverse informazioni sono accessibili usando il nome del vettore a, seguito da un numero tra parentesi, l’indice, che può variare da 1 fino al massimo numero dei dati. Si pensi ad un vettore come una struttura graficamente rappresentabile come in figura.  Possiamo ora strutturare un algoritmo che risolva il problema accennato poc’anzi: inizio totale=0per i=1 fino a 100 leggi a(i) totale=totale + a(i) fine per media=totale/100 per i=1 fino a 100 scarti(i)=a(i)-media stampa scarti(i) fine perfine Si pone a 0 il valore del totale e poi si acquisiscono i valori dei dati con il ciclo per seguente: per i=1 fino a 100 leggi a(i) totale=totale + a(i) fine per Nel ciclo si aggiorna anche il valore del totale. Calcolata la media, un nuovo ciclo per ci permette di determinare gli scarti tra i valori in ingresso e la media. per i=1 fino a 100 scarti(i)=a(i)-media stampa scarti(i) fine per I dati così calcolati vengono anche stampati. Consideriamo un altro esempio. Si tratta dell’algoritmo di Eratostene per determinare i vari numeri primi compresi tra 1 ed un dato valore. Si basa su un ragionamento di questo tipo: si costruisce un vettore contenente i numeri interi tra 1 ed un determinato valore come si può vedere in figura. In questo caso abbiamo generato un vettore fino al 18 con un ciclo per di questo tipo: per i=1 fino a 18 primi(i)=ifine per Il prossimo passo consiste nello scorrere il vettore andando a cancellare i multipli di 2, ottenendo un risultato di questo tipo: Quindi si eliminano i multipli del 3. Si passa ad esaminare la prossima casella. Dovrebbe essere quella del 4, ma essendo multiplo del 2 è già stato eliminato, così come tutti i suoi multipli. Dunque eliminiamo i multipli del 5, poi del 7 e così via. Alla fine del processo le caselle non vuote conterranno numeri primi. L’algoritmo si arresta quando si arriva alla metà del vettore. Infatti dopo la metà non ci possono essere più multipli di alcun numero considerabile.Le successive scansioni avvengono con un algoritmo di questo genere: per i=2 fino a 9se primi(i)<>0 allora per j=i fino a 18se primi(j) Mod primi(i)=0 alloraprimi(j)=0 fine per fine sefine perper i=1 fino a 18se primi(i)<>0 allorastampa primi(i) fine sefine per Il per esterno gestisce la ricerca dei multipli dal 2 al 9. Entro di esso troviamo l’istruzione: se primi(i)<>0 allora Il simbolo < > significa diverso da. Se troviamo un numero che non è stato ancora eliminato procediamo alla rimozione dei suoi multipli entro il ciclo per controllato dalla variabile j. per j=i fino a 18se primi(j) Mod primi(i)=0 alloraprimi(j)=0fine per La variabile j parte dal valore attuale di i e scandisce tutto il vettore. L’ultimo ciclo per stampa l’elenco dei numeri primi. per i=1 fino a 18se primi(i)<>0 allorastampa primi(i) fine se fine per Ordinamento ingenuoUna categoria di problemi tipicamente affrontata utilizzando i vettori è l’ordinamento. Consideriamo un elenco di valori, ad esempio dei nomi, che forniamo uno dopo l’altro ad un dato algoritmo. Partendo dall’assunto che è meglio far fare il lavoro agli altri, i nomi non verranno inseriti in ordine alfabetico, ma sarà l’algoritmo stesso ad ordinarli. Rappresentiamo graficamente l’elenco: Elenco è il nome simbolico per indicare l’insieme dei nomi. È un vettore a 6 posizioni ciascuna corrispondente ad una singola variabile. Ricordiamo che per accedere a un valore bisogna specificare la casella a cui si fa riferimento con una notazione del tipo elenco(5). Per memorizzare Nadia abbiamo dovuto eseguire l’assegnamento elenco(5) = Nadia. Di fronte ad un caso così semplice l’operazione di ordinamento sembra immediata. Se supponiamo che l’elenco sia di 10.000 nomi non è più così semplice. Si rende necessaria una strategia sistematica. Il primo metodo che consideriamo, detto a ordinamento ingenuo, determina, dopo una lettura di tutti gli elementi del vettore da sinistra verso destra, quale sia il primo in ordine alfabetico. A questo punto tale valore viene portato in prima posizione. Concretamente pensate che i valori corrispondano a tessere del domino affian­cate. Per scambiare di posizione la tessera Alessandro con la tessera Mario, bisogna spostare il tassello Mario da qualche parte, in modo da lasciare libero il posto, spostare Alessandro nel buco che si è creato, ed infine posizionare Mario nel vuoto lasciato da Alessandro. Un’altra analogia che spesso viene fatta per descrivere situazioni di questo tipo è lo scambio del contenuto di due bicchieri. Provate a farlo senza usarne un terzo. A questo proposito usiamo entro l’algoritmo una variabile ausiliaria, chiamiamola Temp, per poter veicolare lo scambio. Resta da dettagliare come sia possibile determinare quale debba essere l’elemento da portare in prima posizione. Nel nostro esempio lo si vede subito; si provi a trovarlo in un elenco che si estende per 100 pagine. Scorrendo la lista ci si annota da qualche parte quello che fino a un dato momento risulta essere il primo in ordine alfabetico. Quando se ne trova uno che lo precede si cancella ciò che si era annotato e lo si scrive al suo posto.Bisogna ricordarsi la posizione in cui questo potenziale primo elemento si trova, di modo da potere poi fare lo scambio senza perdita di alcun dato. Vediamo anche qui graficamente come avviene lo scorrimento del vettore. Si usa la variabile pos per memorizzare la posizione attuale del primo in ordine alfabetico trovato fino ad un dato momento. La freccia indica in quale momento della scansione ci si trova. Siamo arrivati alla fine della scansione e sapendo che è il quarto elemento quello da portare in prima posizione possiamo effettuare lo scambio. Si tratta ora di ripetere il tutto. La nuova scansione partirà dal secondo elemento, il primo è già a posto. Ecco la sequenza dei risultati delle varie passate. Si noti che al termine del secondo e terzo passaggio il vettore non ha subito cambiamenti, poiché accidentalmente il secondo e terzo elemento sono già nella corretta posizione in partenza. Comunque l’algoritmo, per potersene accorgere, ha bisogno di scorrere tutto l’insieme di valori. Per potere far passare tutti gli elementi del vettore si usano due cicli per, uno dentro l’altro: per i=1 fino a 5 per j=i fino a 6 fine perfine per   Il ciclo più esterno gestisce le varie passate, che infatti sono 5. Dopo la quinta l’ultimo elemento è sicuramente in posizione giusta. Il ciclo per più interno invece parte dalla porzione del vettore non ancora ordinata per cercare il minimo. Infatti con la prima passata (i=1) non abbiamo ancora trovato il più piccolo e quindi devo scorrere tutto il vettore a partire dall’inizio (j=1). Con la seconda (i=2), il primo elemento lo abbiamo già messo al suo posto e quindi la ricerca procede dal secondo in avanti (j=2) e così via. Si generalizza il ragionamento rendendosi conto che il valore da cui parte j coincide con il valore attuale di i. Vediamo l’algoritmo completo. inizioper i=1 fino a 6 leggi elenco(i) fine perper i=1 fino a 5 per j=i fino a 6 se i=j allorapos=jaltrimentise elenco(j)<elenco(pos) allorapos=j fine se fine se fine pertemp=elenco(i) elenco(i)=elenco(pos) elenco(pos)=tempfine perper i=1 fino a 6 stampa elenco(i) fine perfine Analizziamo le varie fasi. per i=1 fino a 6 leggi elenco(i) fine per Questa fase corrisponde all’acquisizione in ingresso in maniera ordinata dei valori dell’elenco uno alla volta. Seguono i due per commentati sopra: per i=1 fino a 5 per j=i fino a 6 fine perfine per Quindi dentro il ciclo più interno troviamo: se i=j allorapos=jaltrimentise elenco(j)<elenco(pos) allorapos=j fine se fine se La logica di questa parte di programma risiede nella considerazione che, se si sta iniziando una nuova passata, sicuramente il primo valore che viene letto (i = j) è temporaneamente il primo nell’ordine alfabetico (se ne è letto solo 1) e se ne memorizza la posizione nella variabile pos, altrimenti si dovrà fare un confronto tra ciò che è stato determinato essere il più piccolo fino ad ora e quello che si sta leggendo attualmente. Nel caso sia alfabeticamente antecedente si aggiorna il valore di pos, annotando il risultato parziale. Terminato il ciclo più interno, si conclude la prima passata ed è possibile effettuare lo scambio. Nell’algoritmo lo scambio viene fatto lo stesso anche se logicamente non necessario anche nel caso di elemento già in ordine. Scambiare una variabile con se stessa comunque non ne altera il valore. Abbiamo infine: per i=1 fino a 6 stampa elenco(i) fine per che è semplicemente la stampa dei valori nel corretto ordine alfabetico.II metodo che abbiamo considerato viene detto ingenuo perché è il più semplice ed intuitivo. Questo metodo ha lo svantaggio, rispetto ad altri, di richiedere molti più passi. Metodo degli interscambiConsideriamo adesso una procedura più vantaggiosa. È detta metodo degli interscambi. Consiste nel percorrere il vettore confrontando tra di loro gli elementi adiacenti e scambiandoli nel caso non siano in ordine.Nel caso raffigurato in figura abbiamo cominciato a scandire il vettore ed abbiamo determinato che i primi due elementi non sono in ordine e quindi vengono invertiti. Mostriamo ora, in sequenza, l’evolversi del contenuto del vettore durante una scansione completa: La scansione ha avuto termine con il confronto tra il penultimo e l’ultimo elemento, quindi il ciclo for (per) che la gestisce partirà dal primo indice del vettore ed arriverà al penultimo. Abbiamo ottenuto una versione dell’elenco più vicina all’ordinamento finale. Saltando i passi intermedi si mostra lo stato del vettore alla fine degli altri passaggi dell’algoritmo. Qui non si è portato in prima posizione il primo degli elementi quindi ogni nuovo passaggio riparte dalla prima posizione.L’algoritmo ha termine in 4 passaggi e quindi è più veloce di quello visto prima che ne richiedeva 5. Qualcuno potrà obbiettare che in realtà al terzo passo, il vettore risulta ordinato. Ciò è vero, però necessita un’ulteriore passaggio per potere terminare il compito. Infatti non conoscendo a priori il numero di scansioni da compiere l’unico modo per riconoscere che si è giunti al termine dell’opera è una passata del vettore durante la quale non si hanno scambi, che, valendo la proprietà transitiva della relazione d’ordine, garantisce il termine a buon fine dell’algoritmo.Non sapendo quante volte va iterata la scansione del vettore, non possiamo controllarla con un ciclo per. Avremo bisogno di una struttura iterativa controllata da una condizione logica in un mentre oppure in un ripeti. Il nucleo centrale dell’algoritmo sarà costituito dai due cicli annidati seguenti: ripetiper i=1 fino a 6fine perfinché non è ordinato che meglio dettagliati diventano: ripetiper i=1 fino a 6fine perfinché non ci sono più scambi da fare Ancora non siamo arrivati al dettaglio algoritmico di una serie di istruzioni univocamente interpretabili. Dobbiamo specificare come denotare l’avvenimento di operazioni di scambio. Lo facciamo utilizzando una variabile ausiliaria, che chiamiamo scambio, la quale parte da 0 ogni volta che inizia il ciclo più esterno e viene posta ad 1 quando viene effettuato un qualsiasi scambio. Alla fine, se il suo valore è rimasto 0 si avrà il riconoscimento dell’ordine del vettore e si potrà uscire. In altri termini avremo: ripetiscambio=0per i=1 fino a 6qui viene eventualmente alterato il valore di scambio se si scambiano tra loro due elementi.fine perfinché scambio=1 L’algoritmo completo diventa: inizioper i=1 fino a 6 leggi elenco(i) fine perripetiscambio=0per i=1 fino a 5se elenco (i)>elenco (i+1) allora temp=elenco(i) elenco(i)=elenco(i+1) elenco(i+1)=tempscambio=1 fine se fine perfinché scambio=1 per i=1 fino a 6 stampa elenco(i) fine perfine Ricerca sequenzialeOltre all’ordinamento, ci sono molti altri algoritmi da considerare, ad esempio, un’altra classe di problemi tipici con i vettori è la ricerca entro un elenco. L’algoritmo più semplice è quello della ricerca sequenziale. Si tratta di passare in rassegna uno dopo l’altro i valori memorizzati confrontandoli con l’elemento da ricercare. Se lo si trova si termina la ricerca, altrimenti si arriva alla fine del vettore e si annota l’assenza del dato ricercato. L’algoritmo si presenta nel seguente modo: inizioleggi valore trovato=falso i=1ripetise valore=elenco (i) alloratrovato=veroaltrimentii=i+1fine sefinché trovato=vero oppure i>dimensionese trovato=vero allorastampa “Ho trovato il valore nel vettore”altrimentistampa “Non ho trovato il valore nel vettore”fine se fine Per gestire la ricerca utilizziamo un ciclo ripeti finché la cui condizione di terminazione è la seguente: trovato=vero oppure i > dimensione È una condizione composta, infatti si esce dal ciclo se si è determinata la presenza del valore nell’elenco e la variabile trovato ha assunto valore vero, oppure se si è arrivati alla fine del vettore nel momento in cui la variabile i ha superato il valore di dimensione che si suppone sia l’indice maggiore all’interno del vettore. Dovrebbe essere chiaro che mediamente bisogna scorrere metà del vettore per trovare un elemento e bisogna arrivare alla fine per determinarne l’assenza. Consideriamo ora algoritmi più efficienti.Vediamo il classico esempio della ricerca binaria. Bisogna avere a disposizione un vettore precedentemente ordinato.Supponiamo di dover determinare la presenza del valore 12 nella struttura in figura: Il metodo utilizza 3 valori associati agli indici del vettore in cui effettuare la ricerca. Sono sin, centro e des rappresentati nella figura. Inoltre, riceve in input un valore da ricercare: a=12. All’inizio le prime tre variabili coincidono, rispettivamente, sin con il primo indice, centro con il valore medio, arrotondato all’intero inferiore, e des con l’ultimo. Da sin e des si può determinare centro ed a questo punto si va a leggere il valore memorizzato nel vettore nella posizione di indice centro. Se a è superiore a ciò che viene trovato in posizione centro, 7 nel caso della figura, si considera la porzione superiore del vettore altrimenti quella inferiore. Essendo il vettore precedentemente ordinato, se a è inferiore all’11 non può che essere nella prima parte del vettore. sin resterà identico a se stesso, mentre des viene aggiornato assumendo valore pari a centro. Qualora a risultasse superiore al valore memorizzato in posizione centro, l’aggiornamento dovrà coinvolgere sin che assumerà valore pari a centro, mentre des non cambierà. Nel caso in cui si abbia coincidenza tra il valore memorizzato in centro e a la ricerca ha ovviamente successo. L’ultimo passo della ricerca è il seguente: Per capire come strutturare l’algoritmo consideriamo anche il caso di ricerca di un elemento assente, ad esempio il 6: Essendo venuti a coincidere centro e i due estremi, l’algoritmo ha termine e si stabilisce l’assenza dell’elemento ricercato. Per paragonare l’efficienza di questa strategia rispetto alla ricerca sequenziale consideriamo che cosa avviene in una ricerca entro un vettore di dimensione pari ad una potenza del 2 ad esempio 1024, 210. Al primo passaggio la ricerca si riduce alla metà degli elementi cioè 512. Poi 256, 128, 64, 32, 16, 8, 4, 2, 1. In 10 passaggi si arriva sicuramente a determinare la presenza o l’assenza del dato. In una ricerca sequenziale anche se il vettore è ordinato, in media bisogna scorrerlo a metà e cioè inquesto caso fare 512 confronti. Consideriamo ora l’algoritmo relativo: inizio trovato=falso leggi a sin=1des=dimensione ripeti centro=(sin+des)/2se a=elenco(centro) alloratrovato=veroaltrimentise a>elenco(centro) allorasin=centroaltrimentides=centro fine se fine sefinché trovato=vero oppure sin=desse trovato=vero allorastampa “Ho trovato il valore cercato”altrimentistampa “Non ho trovato il valore cercato”fine se fine L’algoritmo comincia con l’assegnazione dei valori iniziali alle variabili che ci interessano e la lettura del valore da ricercare: trovato=falso leggi a sin=1des=dimensione La variabile trovato ci serve per indicare l’avvenuto reperimento dell’informazione. Quindi troviamo un ciclo ripeti così strutturato: ripeti…finché trovato=vero oppure sin=des La ricerca va avanti fino a che si trova il dato cercato (trovato = vero), oppure l’intervallo si è ristretto fino a far coincidere i due estremi.All’interno del ripeti si calcola il valore intermedio: centro=(sin+des)/2 A questo punto si confronta il dato da cercare con quello memorizzato nella posizione centrale: se a=elenco(centro) alloratrovato=veroaltrimentise valore>elenco (centro) allorasin=centroaltrimentides=centro fine se fine se Eseguite queste istruzioni si testa la condizione del ripeti e se è il caso il ciclo termina. In funzione del valore che la variabile trovato assume si effettua la stampa del messaggio di output dell’algoritmo. se trovato=vero allorastampa “Ho trovato il valore cercato”altrimentistampa “Non ho trovato il valore cercato”fine se Le matrici Oltre agli array unidimensionali, cioè i vettori, possono servire, in alcune situazioni, delle strutture a due o più dimensioni. In questo caso si parla di matrici. Una matrice è una struttura contenente una serie di valori distribuiti in righe e colonne come nel caso in figura. Si tratta di una matrice a quattro righe e quattro colonne. Non è detto che il numero di righe coincida con il numero di colonne. Se ciò avviene si parla di matrice quadrata. Ai dati si accede specificando il nome della struttura, riga e colonna in cui si trova il valore che interessa. Ad esempio, a(2,4) vale proprio 18 (l’elemento in seconda riga e quarta colonna). Così come per scandire un vettore è necessario un ciclo per, nel caso di una matrice se ne devono usare 2, uno per spostarsi di riga e l’altro per seguire le colonne. Si consideri il seguente algoritmo: per i=1 fino a 4per j=1 fino a 4 leggi a(i,j) fine per fine per Il primo ciclo è associato ai valori del contatore i che viene utilizzato per indicare la riga, mentre il secondo è associato ai valori della colonna. Dunque per ogni riga si scandiscono tutte le colonne e volta in volta si inseriscono i valori. La matrice viene riempita così una riga per volta. Se consideriamo invece, le seguenti istruzioni: per j=1 fino a 4per i=1 fino a 4 leggi a(i,j)fine per fine per stiamo effettuando un inserimento dei valori colonna per colonna poiché è l’indice di colonna ad essere inserito nel per più esterno. Prato fioritoIn figura abbiamo catturato una schermata di «Prato fiorito», un gioco disponibile in Windows. Vediamo quale può essere l’algoritmo con cui si controlla quanti fiori siano adiacenti ad una data cella. Letti i valori di un indice di riga e di colonna, si dovrà accedere alle celle contigue a quella così determinata per vedere se è presente un fiore. I dati nella matrice che codifica la partita di prato fiorito sono 0 se non c’è il fiore, 1 se viceversa è presente. La generica casella di indici i e j è circondata da tre fiori. Per scoprirlo dobbiamo eseguire un codice del genere: fiori=0per h=i—1 fino a i+1per k=j—1 fino a j+1se (h>=1 e h<=dimensione righe) e (k>=1 e k<=dimensione colonne)allorase non(h=i e k=j) allora se matrice (h,k)=1 allora fiori=fiori+1 fine se fine se fine se fine per fine per Si inizializza la variabile fiori a zero; con due per annidati si scandisce la porzione di matrice adiacente alla cella matrice(i, j). Bisogna stare attenti a gestire i casi particolari di celle ai confini della matrice per le quali non ci sono tutte le otto caselle adiacenti. Ciò è fatto dal controllo seguente: se (h>=1 e h<=dimensione righe) e (k>=1 e k<=dimensione colonne) allora in cui effettivamente si testa se le variabili h e k sono comprese nell’intervallo ammesso per gli indici di riga e colonna. Solo se è così, si va a leggere il contenuto della cella indicizzata da h e k che effettivamente esiste. Si tenga presente che la cella centrale non deve essere letta. Infatti in seguito troviamo il codice: se non(h=i e k=j) allora se matrice (h,k)=1 allora fiori=fiori+1 fine se fine se esclude la lettura della cella centrale, controllando che h e k non siano uguali ad i e j.Il se più interno controlla che nella cella sia memorizzato un 1, nel qual caso si incrementa il numero di fiori. se matrice(h,k)=1 allorafiori=fiori+1fine se ESEMPIO 2ScacchieraAbbiamo rappresentato una scacchiera nella quale nella casella (7, 2) (usiamo tale notazione anche se nel mondo degli scacchi si individuano le colonne con le lettere invece che con i numeri) si trova piazzata una Regina. Si tratta per chi non lo sapesse, di un pezzo che può essere spostato in orizzontale, verticale ed in diagonale. Le caselle con i cerchi indicano le possibili posizioni in cui spostare la Regina. La Regina può, muovendosi, mangiare il Re prendendone il posto. Non può nel caso in figura mangiare il Cavallo. Inoltre non può neanche saltare dei pezzi e quindi anche la Torre non può essere mangiata. Vogliamo costruire un algoritmo che elenchi in uscita tutti i pezzi che possono essere presi dalla Regina che si trova nella generica casella (i, j) della scacchiera.Dobbiamo gestire dei possibili spostamenti in 8 direzioni. In verticale ci si muove lasciando fissa la colonna, in orizzontale lasciando fissa la riga. Per quanto concerne gli spostamenti in diagonale incrementando o decrementando di un’unità, a seconda della direzione del movimento, sia l’indice di riga sia l’indice di colonna. Ricordiamoci che dobbiamo arrestarci non appena troviamo qualcosa. Vediamo gli spostamenti divisi per direzione. Spostamento orizzontale h=i k=j+1 trovato=0mentre (k<=8 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine se k=k+1 fine mentre trovato=0 k=j—1mentre (k>=1 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine sek=k—1fine mentre Si assegnano i valori iniziali alle variabili che ci servono. h=i k=j+ltrovato=0 h scandisce la riga, k la colonna; trovato indica se abbiamo lungo la direzione di movimento incontrato qualcosa.Inizia il ciclo che gestisce la scansione da sinistra verso destra. mentre (k<=8 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine sek=k+1fine mentre La condizione di arresto del ciclo è: k<=8 e trovato=0 Infatti ci si ferma o quando si è arrivati al bordo della scacchiera oppure se abbiamo trovato un pezzo da mangiare. Si controlla se nella casella attuale ci sia un pezzo, supponendo che le caselle vuote contengano uno 0 con il seguente gruppo di istruzioni: se scacchiera(h,k)<>0 alloratrovato=1stampa(“puoi mangiare ciò che si trova nella casella h,k”)fine sek=k+1 Segue l’incremento di k.In modo analogo ci si comporta per lo spostamento verso il bordo sinistro della scacchiera. k partirà da j – 1 e verrà decrementato di volta in volta invece che essere incrementato. Con una logica del tutto simile viene gestito lo spostamento in verticale. Spostamento verticale h=i+1 k=j trovato=0mentre (h<=8 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h, k”)fine se h=h+1 fine mentre trovato=0 h=i—1mentre (h>=1 e trovato=0) faise scacchiera (h, k) <>0 alloratrovato=1stampa (“puoi mangiare ciò che si trova nella casella h, k”)fine seh=h—1fine mentre Passiamo a considerare gli spostamenti in diagonaleSpostamento lungo la diagonale principale h=i+1 k=j+1 trovato=0mentre (h<=8 e k<=8 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine se h=h+1 k=k+1fine mentre trovato=0 h=i—1k=k—1mentre (h>=1 e k>=1 trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine seh=h—1 k=k—1fine mentre La logica dello spostamento su questa diagonale prevede, andando verso il basso, un incremento unitario degli indici e un corrispondente decremento per lo spostamento verso l’alto. Visto che sia h sia k variano, bisogna controllare che entrambi i valori non fuoriescano dai limiti della scacchiera. Scendendo, aumentano tutti e due, bisogna verificare che non superino il valore 8. Salendo bisogna verificare che rimangano superiori all’1. Spostamento lungo la diagonale secondaria h=i—1 k=j+1 trovato=0mentre (h>=1 e k<=8 e trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine se h=h—1 k=k+lfine mentre trovato=0 h=i+1k=k—1mentre (h<=8 e k>=1 trovato=0) fai se scacchiera(h,k)<>0 allora trovato=1stampa (“puoi mangiare ciò che si trova nella casella h,k”)fine se h=h+l k=k—1fine mentre ESEMPIO 3Quadrato magicoOsservate la figura, si tratta di un quadrato magico, cioè una particolare disposizione dei primi nove numeri interi tale per cui, eseguendo la somma di tutti i valori lungo una riga, una colonna e lungo le due diagonali si ottiene sempre lo stesso risultato, cioè 15 nel nostro caso. Proviamo a descrivere un algoritmo in grado di controllare se una matrice quadrata di interi è un quadrato magico.Una prima parte dell’algoritmo deve memorizzare la somma di una qualsiasi riga o colonna o diagonale. Poi si esegue una scansione delle righe calcolando i vari totali. Se continuano a coincidere con il primo calcolo si prosegue, altrimenti l’algoritmo si deve arrestare. Una seconda fase scandisce le colonne, infine si avrà la fase che esamina le due diagonali. Scansione orizzontale totale=0per j=l fino a n totale=totale+quadrato(l,j)fine per somma=totale i=2mentre (somma=totale e i<=8) faisomma=0per j=1 fino a n somma=somma+quadrato (i,j)fine peri=i+lfine mentre L’algoritmo comincia calcolando la somma sulla prima riga ed assegnando il risultato alla variabile totale. A questo punto passa a considerare le altre righe assegnando ad i il valore 2 e alla variabile somma il valore di totale. In questo modo si può entrare nel ciclo mentre essendo la sua condizione logica soddisfatta. Si deve usare un mentre invece di un per perché l’algoritmo non è obbligato a scorrere tutta la matrice. E possibile arrestare il processo in qualsiasi momento non avendo trovato più coincidenza nei risultati. Per ogni riga si ricalcola da capo il valore di somma entro il ciclo per controllato da j. Alla fine della scansione di tutte le righe se ha avuto successo il controllo vale l’uguaglianza somma = totale e quindi per la scansione in verticale è possibile evitare l’assegnamento. Scansione verticale se somma=totale alloraj=1mentre (somma=totale e j<=8) faisomma=0per i=1 fino a n somma=somma+quadrato (i,j) fine per j=j+1 fine mentre fine se La logica è del tutto simile a quella della passata in orizzontale tranne che vincoliamo l’esecuzione solo al caso in cui la passata orizzontale abbia dato esito favorevole. Questo è il senso del se iniziale. Scansione della diagonale principale se somma=totale allorasomma=0per i=1 fino a n somma=somma+quadrato(i,i) fine perfine se Per la diagonale principale ci basta un solo indice poiché gli elementi che la costituiscono hanno la caratteristica di essere posizionati su caselle con uguali valori di riga e colonna. Il generico elemento sarà del tipo quadrato (i,i).Risulta un pochino meno immediato definire la caratteristica che individua univocamente gli elementi dell’altra diagonale. Se ci fate caso la somma degli indici degli elementi della diagonale secondaria fornisce sempre il valore 4 nel caso del nostro quadrato. In generale vale n+1.Generalizzando la caratteristica sarà che i + j = n +1 e cioè j = n + 1 – i. Avendo definito i valori dell’indice j in funzione di i posso usare un solo per anche per l’ultima scansione. Il codice è il seguente: se somma=totale allorasomma=0per i=1 fino a n somma=somma+quadrato(i,n+1-i)fine per fine sese somma=totale allorastampa “è un quadrato magico”altrimentistampa “non è un quadrato magico”fine Abbiamo aggiunto alla fine dell’ultima fase le istruzioni per la stampa dei risultati. Le strutture dati astratteLe listePer introdurre il concetto di lista consideriamo la figura. Abbiamo una variabile, testa, ed una tabella le cui due colonne contengono dati di diverso significato. La prima colonna rappresenta l’informazione utile, mentre la seconda servirà per collegare tra loro le informazioni. Testa rappresenta la posizione della prima informazione da leggere. Si accede dunque alla colonna informazione della tabella in riga 2. Il valore che viene memorizzato è il 3. Questa informazione è collegata ad un’altra tramite il numero al suo fianco nel campo collegamenti. Tale valore è 4 e sta ad indicare che il prossimo dato da leggere si trova in riga 4. Si va a leggerlo trovando il valore 5. Si consideri il campo Collegamenti. Vi è memorizzato un 1 e dunque si dovrà passare alla prima riga leggendo il numero 9 e come collegamento il valore 3. Ci si sposta nella terza riga leggendo il 13 e poi uno 0 come collegamento. Tale valore indica che dopo il 13 non c’è più informazione utile. Se si riconsidera la sequenza dei numeri letti, la si trova pari a 3, 5, 9, 13. In altri termini grazie all’uso dei valori di collegamento si accede alla sequenza di valori in modo ordinato, senza dover applicare alcun algoritmo specifico per tale operazione.Dunque si può dire che una lista non è nient’altro che un elenco mantenuto costantemente ordinato. La lista è un oggetto non fornito direttamente nei linguaggi di programmazione per cui viene detta struttura dati astratta, differenziandola dalle strutture dati concrete (vettori e matrici) direttamente previste dalla sintassi di tutti i linguaggi. Consideriamo ora la sequenza dei passi con cui viene costruita una lista.Viene acquisito in ingresso il valore 9 e lo si memorizza nella prima posizione libera nella matrice. La variabile testa vale 1, il campo collegamento resta a 0 poiché l’elenco contiene solo 1 valore. Si legge il valore 3 e viene immesso nella prima posizione libera nella matrice. Il valore della variabile testa dovrà essere coerentemente aggiornato perché dovrà indicare la posizione del valore più piccolo ed anche il campo collegamento sarà di conseguenza adattato. Se si prova a scorrere l’elenco, seguendo la regola di leggere prima le informazioni, partendo da quella di riga testa, e poi proseguendo usando i valori di collegamento, ci si accorge che l’ordine di lettura è 3,9. Viene letto il tredici e lo si posiziona nella prima riga libera. Non deve essere aggiornato il valore di testa, ma si deve creare il collegamento tra il 9 ed il 13 cambiando il valore memorizzato nella cella di collegamento del 9 in modo da garantire che la sequenza di accesso ai dati sia ora 3,9,13. L’ultimo inserimento produce ora la situazione: In questo caso si è dovuto cambiare il collegamento relativo al numero 3. Infatti adesso non deve più legarsi al 9, ma al 5 e sarà il 5 ad essere collegato al 9. Si sarebbe potuto rappresentare astrattamente la sequenza di operazioni che sono state effettuate anche con la seguente sequenza di diagrammi: Questo tipo di rappresentazione cerca di evidenziare la natura della lista come catena di valori agganciati uno all’altro e reperibili sequenzialmente partendo dalla posizione iniziale. Le liste hanno la caratteristica di essere strutture ad accesso sequenziale. Per capire tale concetto si pensi ad una musicassetta. In essa i vari brani musicali sono registrati in modo tale che per poter ascoltare una qualsiasi canzone si è costretti a svolgere il nastro fino a quando non la si incontri.Viceversa un lettore di CD ROM permette di ascoltare le canzoni posizionando il dispositivo di lettura e riproduzione direttamente sul brano che interessa. In situazioni di questo tipo si parla di dispositivi ad accesso diretto. Riconsiderando le caratteristiche della struttura a lista, cioè ordinamento dinamico ed accesso sequenziale è possibile apprezzarne i vantaggi e guardarsi dai suoi difetti. Quando l’esigenza primaria dell’applicazione informatica è il mantenimento di informazione ordinata, la scelta delle liste risulta vantaggiosa. Se invece risulta prioritaria la velocità di reperimento dell’informazione e i dati sono immessi raramente o solo all’inizio dell’utilizzo del programma potrebbe essere preferibile una soluzione che utilizzi dei vettori.Infatti, per la sua natura intrinsecamente sequenziale la lista permette una ricerca di durata media n/2, se n è il numero di dati memorizzati, mentre si era visto in un vettore ordinato la ricerca binaria permette prestazioni decisamente migliori. Usando i vettori si tenga però conto della necessità di un riordinamento dopo ogni immissione. Altro svantaggio della soluzione con le liste è l’uso di una quantità di memoria doppia rispetto al vettore, vista la necessità dei valori di collegamento. Sul modello astratto considerato in precedenza è facile rendersi conto delle operazioni che, da un punto di vista algoritmico, sono necessarie per gestire una lista.Distinguiamo tra la ricerca e l’inserimento. Ricerca con successoSi voglia determinare la presenza del 9 nella lista. La freccia verticale indica a quale anello della catena si è arrivati ad ogni passo: Ricerca con fallimentoQuesta volta andiamo alla ricerca del valore 7 L’operazione di ricerca non presenta particolari difficoltà concettuali ed è del tutto analoga ad una ricerca sequenziale su un vettore ordinato. Il procedimento che si è dettagliato è di natura semi-algoritmica poiché esso va realmente condotto simulando la lista con la matrice considerata ad inizio paragrafo. Maggiori problemi concettuali pone l’inserimento di un elemento nella lista. Inserimento in testaSi deve inserire un nuovo valore ed esso risulta pari ad 1. Inserimento in posizione intermediaSi deve inserire un nuovo valore pari a 4. Inserimento in codaSi vuole immettere il valore 15 Le codeUna coda viene detta anche struttura di tipo FIFO (First In First Out, il primo ad entrare è il primo ad uscire). Si pensi a qualsiasi fila in attesa di un certo servizio (cassa, sportello di banca, casello autostradale. ecc.).Si può schematizzare tale situazione con un vettore opportuno che è la struttura concreta corrispondente alla struttura astratta coda. Si supponga che siano arrivate ad un casello autostradale un certo numero di macchine, diciamo 10, ed ancora nessuna sia stata servita. Avremmo la situazione di figura. Nel momento in cui viene fatto il pagamento del pedaggio da parte del primo automobilista la situazione diventa quella di figura. L’utente servito è scomparso dalla struttura e gli altri sono scalati di una posizione. Se nel frattempo arriva un’altra macchina, la coda si modifica come in figura. Viene effettuato un altro pagamento e dunque si avrà: Dovrebbe essere chiaro come viene gestita la situazione. In generale una coda è associata ad un vettore e a due indici, uno rappresenta l’inizio della coda, l’altro la fine. Da un punto di vista logico le operazioni su una coda sono due: l’arrivo di un nuovo elemento ed il servizio del primo utente in attesa. Sembrerebbe molto facile programmare i due eventi: nuovo arrivo:coda(fine)=nuovo elemento               l’ultimo arrivato va in fondo fine=fine+1                             viene aggiornata la prima                                        posizione liberaservizio di un utente:coda(inizio)=0                          si cancella la posizione di chi è stato servitoinizio=inizio+1                         si aggiorna la posizione iniziale Si tengano però presenti i seguenti problemi: per prima cosa il vettore che rappresenta la coda avrà una certa dimensione massima oltre la quale non sarà più possibile memorizzare informazione; inoltre, si pensi al fatto che man mano che la situazione evolve nel tempo le informazioni nel nostro vettore slittano verso destra. Si avrà ad un certo punto a che fare con la situazione di figura a.Nel vettore ci sono posti liberi per nuovi arrivi ma non si trovano più alla destra dell’array, quindi si deve ricominciare da capo inserendo gli eventuali nuovi utenti a partire dall’inizio. Arrivano altri due elementi e si consideri cosa succede se nel frattempo non è stato svolto alcun servizio figura b. Da questo punto in poi, essendo completamente riempito il vettore non potrà essere più accettato nessun arrivo. Bisogna aspettare l’espletamento di un servizio. Fatte queste considerazioni le due operazioni vengono modificate nel seguente modo: nuovo arrivo:se fine<>inizio allora coda(fine)=nuovo elemento se fine<ultimoindice fine=fine+1altrimentifine=1altrimentirifiutare l’ingresso fine seservizio di un utente: coda(inizio)=vuotose inizio=ultimoindice inizio=inizio+1altrimenti inizio=1 fine se la variabile ultimoindice nell’algoritmo rappresenta la dimensione del vettore. Le pileLe pile invece sono dette strutture LIFO (Last In First Out, l’ultimo arrivato è il primo ad essere servito). Si pensi, per figurarsi un utilizzo di una struttura del genere, l’apertura di più finestre sul desktop di Windows.Nella schermata si sovrappongono le tre finestre di Excel Word e Power Point, nell’ordine in cui sono stati aperti, Word Excel e Power Point dopo Word. Se si richiudono le finestre sparirà per prima la superiore e così via in ordine contrario a quello di apertura. L’ultimo ad essere aperto è il primo ad essere chiuso. Questa è l’essenza delle pile. A volte tali strutture sono denotate con il nome di stack, in italiano catasta, per l’analogia con un insieme di oggetti che vanno a sovrapporsi. Anche una pila può essere gestita con un semplice vettore. Basta un solo indice, per indicare la cima della struttura. Le due operazioni possibili sono: push, ovvero inserimento di un elementocima=cima+1se cima<=ultimoindice allorapila(cima)=nuovo elementoaltrimentirifiuta l’inserimentofine sepop, ovvero estrazione di un elementose cima>0 allora estrai l’elemento cima=cima-1altrimentinon ci sono elementi da estrarrefine se Si noti che rappresentando la pila con un vettore di dimensioni finite abbiamo dovuto trattare opportunamente i due casi di tentativo di estrazione da una pila vuota ed inserimento in una pila ormai ricolma. Gli alberiProseguendo nella trattazione delle strutture dati astratte, arriviamo a considerare gli alberi. Si erano già incontrati in un altro modulo degli esempi di albero. Ne consideriamo altri. ESEMPIO 1File systemNella parte destra della figura è presente la rappresentazione gerarchica delle cartelle di Windows. A partire dalle risorse del computer si osserva una divisione in: floppy, C:, D: che a loro volta contengono altre sottocartelle. Questa gerarchia è memorizzata in un albero di cui risorse del computer è la radice, floppy, C:, D: sono i figli, nuovi nodi della struttura, che a loro volta contengono altre cartelle figli, e così via fino ad arrivare ai file che sono le foglie dell’albero. ESEMPIO 2Espressioni matematicheSi consideri l’espressione matematica: a·b+c·d–a/e. Quando va calcolata la formula precedente, bisogna eseguire le operazioni a precedenza più elevata, moltiplicazioni e divisioni, poi le altre. A parità di precedenza si stabilisce che l’ordine di valutazione dell’espressione sia da destra verso sinistra. In altri termini per prima cosa si esegue a·b, poi c·d, poi a/e quindi la somma ed infine la differenza. La struttura di questa espressione può essere rappresentata con il seguente schema ad albero: La struttura indica esplicitamente come eseguire i calcoli. Si parte dal basso a sinistra, con le due foglie a e b, si risale di un livello a determinare l’operazione da fare su queste due variabili contenuta nel loro nodo genitore. Questo nodo viene sostituito con il risultato dell’operazione. Si cercano le prossime due foglie andando verso destra e si ripete l’operazione. Vediamo graficamente come avviene l’esecuzione dell’espressione nei vari passaggi: Questo esempio introduce un caso particolare, ma molto importante, di albero, cioè l’albero binario. Si ha un albero binario quando ogni nodo ha al più due figli. Si ricordi come erano state rappresentate le liste, cioè con due vettori di cui uno conteneva le informazioni, l’altro i collegamenti. Avendo, nel caso di albero binario, per ogni elemento due potenziali figli si dovranno rappresentare i collegamenti con due vettori uno per i figli destri l’altro per i figli sinistri Ad esempio l’albero binario dell’espressione dell’esempio 2 è memorizzato con i vettori di figura. Partendo dalla radice, se si seguono i collegamenti nei vettori dei figli destri e sinistri si dovrebbe senza fatica ricostruire l’albero.Se l’albero non è binario, ovvero possiede più di due figli per ogni nodo, la situazione si complica alquanto. Accenniamo al fatto che potremmo usare, per rappresentare tale struttura astratta, una lista per ogni nodo. La lista conterrebbe i collegamenti ai vari figli. Un modo ingegnoso per memorizzare un generico albero è simularlo con un albero binario. L’albero di figura non è binario in quanto il nodo a possiede tre figli così come il nodo b. Si trasforma l’albero di partenza con il seguente metodo. Si parte dalla radice e si genera un elenco di successori che vengono memorizzati alla sinistra del nodo originario. In seconda battuta aggiungiamo a b i suoi eventuali figli. Visto che l’albero trasformato dovrà essere binario aggiungerò l’elenco dei nodi figli uno di seguito all’altro nell’unico collegamento libero che il nodo b al momento possiede, cioè a destra. Infine dobbiamo ancora memorizzare i figli di d. Per coerenza con la logica di costruzione dell’albero, se li mettessimo a sinistra di d, diventerebbero dei fratelli di d stesso rispetto alla struttura dell’albero originario. Pertanto si è costretti ad inserirli nella direzione opposta. Osservando la figura si nota che l’albero trasformato è effettivamente binario e dunque rappresentabile con solo tre vettori. I grafiL’ultima struttura astratta che verrà trattata sono i grafi. Si supponga di dover schematizzare la struttura dei collegamenti di una rete, sia ferroviaria, sia telefonica, sia Internet. Si avranno delle entità (stazioni, centraline, computer) dette nodi tra loro connesse da dei collegamenti detti archi. Si osservi la figura. Gli archi in questa situazione sono orientati e possono essere percorsi in una sola direzione. Ad ogni arco si suppone sia associato un dato informativo (distanza, tempo di percorrenza. ecc.). Ci si pone adesso il problema di trovare una struttura concreta per rappresentare nella memoria di un calcolatore tale informazione. Si tratta semplicemente di una matrice quadrata di dimensioni pari al numero dei nodi. Ogni riga verrà riempita indicando in essa per ogni collegamento il valore numerico associato. In altri termini, se dal nodo 1 si può giungere al nodo 2 con un costo pari a 10, in riga 1, colonna 2 della matrice è posto il valore 10 e così proseguendo. Si noti che, è possibile che i collegamenti siano bidirezionali ed il costo nelle due direzioni sia il medesimo. Gli archi nel grafo non saranno più orientati ed il valore entro la matrice dovrà essere memorizzato due volte per i due possibili sensi di percorrenza.   Powered By GSpeech

Esercizi

1. Si mostri un algoritmo che determini contemporaneamente il più grande ed il più piccolo valore in un vettore.
2. Si mostri un algoritmo in grado di invertire i valori entro un vettore, cioè se il vettore inizialmente contiene la sequenza 1,3,5,4,6,7 alla fine del procedimento dovrà contenere 7,6,4,5,3,1.
3. Si mostri un algoritmo che riempie una matrice di dati riga per riga.
4. Si mostri un algoritmo che riempie una matrice di dati colonna per colonna.
5. Si mostri un algoritmo che determina il più grande valore dentro ogni riga di una matrice.
6. Data una generica lista la si rappresenti come tabella.
7. Si rappresenti l’evoluzione nel tempo che il contenuto della tabella dell’esercizio precedente ha subito per mantenere la struttura costantemente ordinata.
8. Dato un generico albero binario lo si rappresenti con tre vettori.
9. Data un’espressione matematica se ne costruisca l’equivalente albero binario.
10. Dato un generico albero lo si rappresenti con un albero binario memorizzando poi il tutto concretamente in tre vettori.
11. Dato un generico grafo lo si memorizzi con una tabella.
12. Per chi conosce EXCEL. Che strutture dati servono per gestire il ricalcolo delle formule quando cambia un qualche valore di una cella?

Esercizi

1. Che cosa si intende col termine ordinamento?
2. Che differenza c’è tra una ricerca sequenziale ed una binaria?
3. Si disegni un vettore non ordinato e si segua passo per passo l’algoritmo di ordinamento ingenuo.
4. Stesso compito per l’algoritmo di interscambio.
5. Si illustrino i concetti di pila e di coda.
6. Che differenza c’è tra una struttura dati astratta ed una concreta?
7. Quale struttura dati usereste per un programma che deve gestire i clienti allo sportello di una banca? Si facciano le ipotesi ritenute necessarie.
8. Quale struttura dati usereste per un programma che deve gestire una partita a Dama?
9. Quale struttura dati usereste in un programma di disegno di circuiti elettrici? Spiegare.
10. Quale struttura dati viene usata nei vari programmi applicativi per gestire il tasto di annullamento delle ultime operazioni? Ed in Explorer per gestire il tasto pagina precedente?

 Esercizi

1. Un vettore:
* contiene informazione accessibile tramite un indice
* contiene dati ordinati
* è un array bidimensionale
* deve essere scandito dalla prima all’ultima posizione

2. L’indice di un vettore
* indica un valore memorizzato
* serve per calcolare la posizione
* permette l’accesso all’informazione memorizzata
* indica il massimo valore contenuto nel vettore

3. L’ordinamento ingenuo:
* è più efficace del metodo degli interscambi
* funziona se il vettore è ordinato
* permette solo ordinamenti crescenti
* è meno efficace del metodo degli interscambi

4. Una matrice:
* è un vettore bidimensionale
* ha lo stesso numero di righe e di colonne
* è un array
* ha numero di righe diverso dal numero delle colonne

5. Gli elementi della diagonale principale di una matrice quadrata:
* hanno indici costanti
* hanno lo stesso indice
* hanno indici diversi
* sono i più importanti

6. Una matrice:
* può essere letta per righe o per colonne
* deve essere letta riga per riga
* deve essere letta colonna per colonna
* deve contenere dati ordinati

7. Una lista:
* è simulata da un vettore
* deve essere periodicamente riordinata
* ammette accesso diretto
* è simulata da una tabella

8. Una lista:
* è più conveniente di un vettore
* consente una rapida ricerca dell’informazione
* è costantemente ordinata
* consente una ricerca di tipo binario

9. Una pila:
* è una struttura FIFO
* è gestita da un vettore con un indice di inizio ed uno di fine
* è gestita da un vettore ed un solo indice particolare
* è gestita con una matrice

10. Una coda:
* è detta anche stack
* è gestita da un vettore ed un solo indice particolare
* è una struttura FIFO
* è gestita solo con un vettore

11. In un albero binario:
* tutti i nodi hanno due figli
* tutti i nodi hanno almeno due figli
* esiste un nodo particolare chiamato radice
* le foglie sono gli ultimi figli

12. Un generico albero:
* ha parecchi nodi e radici
* può essere rappresentato con due vettori
* può essere rappresentato con tre vettori
* può simulare un albero binario