Vettori , Matrici, Record e tabelle

1 10 2008

Vettori e Matrici

Un vettore è una variabile strutturata costituita da n variabili di tipo semplice identificata da un nome

collettivo e da un indice che ne seleziona il valore. La nomenclatura sui vettori suole indicare i vettori con

il nome collettivo seguito da una coppia di parentesi al cui interno è indicato l’indice che

obbligatoriamente indicando una posizione è intero. Ad esempio a(3) indica il terzo elemento del vettore,

a(i) indica l’i-mo elemento del vettore. Alcuni linguaggi di programmazione ammettono la dichiarazione

della dimensione del vettore nella parte dichiarativa (pascal, fortran) altri invece consentono un

dimensionamento dinamico nel programma. Normalmente anche sel la dimensione del vettore deve

essere fissata all’inizio prima dell’esecuzione dell’algoritmo non è un grosso problema ricondurlo ad una

gestione dinamica come vedremo in alcuni esempi. Il vettore graficamente può essere rappresentato

con un insieme di caselline al cui interno vi sono i valori che possono essere sia di tipo semplice che

composto (come vedremo nelle prossime lezioni). Normalmente per l’utilizzo del vettore è opportuno

procedere al caricamento dei valori attraverso l’utilizzo di un ciclo. Supponiamo di voler caricare un

vettore di nome b composto da 10 elementi interi; l’algoritmo è:

1. Inizio
2. Per i= 1 a 10 esegui
3. ciclo
4. scrivi “dammi elemento”
5. leggi b(i)
6. fine ciclo
7. fine

In questo esempio viene chiesto all’utente di inserire dei valori da tastiera che verranno memorizzati nel

vettore b(). Come primo esercizio si scambino gli elementi di posto pari con quelli di posto dispari di un

vettore di 10 elementi interi. Dopo aver caricato il vettore come fatto in precedenza l’algoritmo che

risponde la problema dovrebbe essere:

1. Per i=1 a 5 esegui
2. ciclo
3. temp=a(i)
4. a(i)=a(2i)
5. a(2i)=temp
6. fine ciclo
7. fine

In questo algoritmo si è utilizzata la variabile temp per memorizzare temporaneamente i valori che

vengono soprascritti con l’istruzione 4. Un altro esercizio potrebbe essere dato un vettore di 10 elementi

contare e visualizzare quante volte un elemento introdotto da tastiera si ripete. in questo problema oltre

al vettore a() è necessario utilizzare una variabile cont intera che conti il numero delle occorrenze, una

variabile num che contenga l’elemento inserito da tastiera di cui si vuole verificare il numero delle

occorrenze. La procedura per il caricamento è sempre la stessa per cui la omettiamo. L’algoritmo che

risolve il problema richiesto sarà:

1. inizio
2. cont=0
3. scrivi “inserisci l’elemento da cercare”
4. leggi num
5. Per i=1 a 10 esegui
6. ciclo
7. se a(i)=num allora
8. cont=cont+1
9. fine ciclo scrivi “il numero di volte che si ripete il valore inserito è: ” ,num
10. fine

In questo algoritmo si inserisce l’elemento da contare da tastiera, poi si confronta ogni elemento del

vettore con il valore di riferimento attraverso un ciclo e alla fine si visualizza il risultato ottenuto. Nei

vettori sono molto diffuse le procedure di ricerca di elementi specifici in strutture ordinate. Si supponga

di avere un vettore di 20 elementi numerici interi ordinati in ordine crescente. La ricerca di un elemento

specifico può avvenire in modo sequenziale come nel caso dell’algoritmo precedente o attraverso il

metodo dicotomico. Con questo metodo si riduce notevolmente il numero di scansioni degli elementi del

vettore. Nella ricerca dicotomica utilizza il metodo delle divisioni successive. Per meglio chiarire

riportiamo di sotto un vettore di 10 elementi interi ordinato in modo crescente:

1 3 4 5 6 8 9 12 15 18;

ora supponiamo che l’elemento da cercare è “9”. La dimensione del vettore è 10, quindi lsi introducono

tre indici sinistro, destro e centrale. Al primo passaggio sinistro=1, destro=10, centrale=(sinistro +

destro)/2=6 (intero successivo) ora gli elementi del vettore di posizione sinistro=1 (“1”), destro (“18”),

centro (“8”) non sono uguali all’elemento richiesto. A questo punto se l’elemnto di centro è minore del

valore da cercare  sinistro =centro+1 altrimenti destro=centro-1, e si ripete la procedura. in questo caso

l’uscita dal ciclo è condizionata o all’evento che è stato trovato l’elemento o che sinistro è diventato

maggiore di destro (sconfinamento dell’indice). Sulla base di quetso esempio l’algoritmo escludendo la

parte di caricamento è:

1. inizio
2. scrivi “dammi il valore da cercare”
3. leggi valore
4. trovato=falso // sto utilizzando una variabile logica
5. sinistro=1
6. destro=10 // o la dimensione del vettore
7. centro=(sinistro + destro)/2
8. ripeti
9. Se a(sinistro)=valore o a(destro)=valore o a(centro)=valore allora
10. trovato=vero
11. altrimenti
12. se a(centro)<valore allora
13. sinistro=centro+1
14. altrimenti
15. destro=centro-1
16. finché trovato=vero o sinistro>destro
17. Se trovato=vero allora
18. scrivi “valore trovato all’interno del vettore”
19. altrimenti
20. scrivi “valore non trovato”
21. fine

In questo algoritmo si fa uso di tre indici per la ricerca dell’elemento. Tale metodo riduce la ricerca di N/2

scansioni ad ogni passaggio di divisione. Nell’utilizzo dei vettori spesso è necessario operare con più

vettori in simultanea. Ad esempio in un vettore di 5 elementi di stringhe si inseriscano i nomi delle città, in

un altro composto da 5 elementi reali il reddito medio per abitante. Supponiamo di voler calcolare e

visualizzare in quale città un abitante ha il reddito massimo. Allora fermiamoci un at6timo a descrivere le

variabili in gioco nel problema. Esse sono:

Classe     Nome             Tipo
Inupt         cit                    vettore di stringhe di 5 elementi
Input         reddito             vettore di 5 elementi reali
Interna      i                    indice vettori
Output      cit_max        stringa
Output     max             numero reale conterrà il reddito massimo

Nella tabella precedente sono presenti due variabili di output max che rappresenta il massimo reddito e

cit_max che rappresenta il nome della città ove ogni abitante ha il reddito più alto.
L’algoritmo sarà:

* inizio
* per i=1 a 5 esegui
* ciclo
* scrivi “dammi il nome della città”
* leggi cit(i)
* fine ciclo
* inizio
* per i= 1 a 5 esegui
* ciclo
* scrivi “inserisci il reddito per abitante”
* leggi reddito(i)
* fine ciclo
* max=0
* cit_max=””
* per i=1 a 5 esegui
* se redditi(i)> max allora
* max=redditi(i)
* cit_max=cit(i)
* fine ciclo
* scrivi “la città con reddito più alto è”
* scrivi cit_max
* scrivi “con reddito per abitante di ”
* scrivi max
* fine

Questo problema è un esempio tipico di problemi risolti attraverso l’uso di vettori paralleli. La risoluzione

risulta agevole se le dimensioni dei vettori sono uguali altrimenti occorre utilizzare più indici.

Ordinamento di vettori

Ordinamento sequenziale
Consiste nell’ordinare il vettore mediante scambi successivi, Si Fissa l’elemento più a sinistra poi con un

altro indice si fa selezionano gli elementi rimanenti del vettore ogni volta che l’elemento fisso è maggiore

si scambia con quello selezionato (ordinamento crescente viceversa per il decrescente).
In altri termini se si ha un vettore di così composto:

3 5 6 10 2
Nel primo passaggio i=1 x(i)=3 mentre k=i+1..5 e quindi x(k) varia sugli elementi 5,6,10,2. Dopo una

prima serie di passaggi il vettore sarà:
2 5 6 10 3
Ora i=2 e k=i+1..5 perchè siamo sicuri che l’elemento di posto 1 è il più piccolo. Iterando ottieniamo

l’algoritmo di ordinamento che è così scritto:

inizio
ciclo su i=1..5
ciclo su k=i+1..5
se x(i)> x(k) allora
tmp=x(i)
x(i)=x(k)
x(k)=tmp
fine se
fine ciclo su k
fine ciclo su i
fine

La variabile tmp viene ad essere utilizzata come variabile temporanea.

Matrici

Un’altra struttura di dati molto utilizzata in informatica è la matrice ovvero un vettore bidimensionale

organizzato in una serie di elementi organizzati in righe e colonne. Infatti se supponiamo che la matrice si

chiama mat per indicare l’elemento di riga i e colonna j, si utilizza la simbologia mat(i,j). Come per i

vettori sulle matrici è possibile compiere alcune operazioni come caricamento ovvero inserimento di

elementi, ordinamento, ricerca di elementi. E’ bene notare che viene definita matrice un vettore

bidimensionale i cui elementi sono costituiti da variabili semplici tutte dello stesso tipo. La dimensione

delle matrici in alcuni linguaggi di programmazione devono essere fissate a priori in altri casi si può

definirla dinamicamente. Supponiamo di voler risolvere il seguente problema: dato una serie di voti per n

alunni calcolare e visualizzare le medie. Tale problema all’apparenza sembra complesso ma se

correttamente impostato si risolve in modo molto semplice. Ipotizziamo che ogni riga della matrice è

costituita da 8 elementi rappresentanti i voti degli alunni nelle 8 materie di studio. una volta caricata la

matrice basterà calcolare la media di riga per visualizzare la media di un alunno. Nel problema non è

dato il numero degli alunni. In questo caso dimensioniamo le righe della matrice a 30 elementi, e

richiediamo il numero degli alunni in input. La tabella delle variabili sara:
Classe     Nome                                 Tipo
Input     voti                                       matrice di 30 righe e 8 colonne
Input     n                                           numero di alunni
Interna     i,j                                       indici matrice
Interna     somma                              reale somma dei voti di alunno
Output     media                                reale media dei voti di un alunno

L’algoritmo verrà svolto in un unico blocco senza l’ausilio delle procedure per esporre i concetti. Le

strutture cicliche idonee per le matrici sono strutture nidificate in quanto si deve tener conto che un indice

sposta la riga e l’altro la colonna. Una volta richiesto in input il numero degli alunni memorizzato nella

variabile n, il ciclo esterno sarà svolto fino a n, mentre quello interno fino a 8.

1. inizio
2. somma=0
3. media=0
4. scrivi “dammi il numero degli alunni”
5. leggi n
6. per i=1 a n esegui
7. ciclo 1
8. per j=1 a 8 esegui
9. ciclo 2
10. scrivi “dammi il voto dell’alunno”,i,”-mo”
11. leggi voti(i,j)
12. fine ciclo 2
13. fine ciclo 1
14. per i=1 a n esegui
15. ciclo 1
16. per j=1 a 8 esegui
17. ciclo 2
18. somma=somma+voti(i,j)
19. fine ciclo 2
20. media=somma/8
21. scrivi voti(i,j)
22. somma=0 //queste due righe sono necessarie per ricominciare il calcolo della media//
23. media=0
24. fine ciclo 1
25. fine

Alcuni chiarimenti sulle istruzioni di scrittura come:
scrivi “dammi il voto dell’alunno”,i,”-mo”

questa infatti non fa altro che stampare le stringhe fra virgolette (messaggi) concatenate al valore della

variabile i. Inoltre come si vede nell’algoritmo è necessario chiudere prima il ciclo interno e poi quello

esterno. Questo è solo un esempio di quello che è possibile fare con le matrici. Un esempio molto utile a

chiarire il concetto e l’uso delle matrici può essere dato dal seguente problema:

Siano date 4 ruote del lotto napoli, roma, milano, venezia. Su ogni ruota vengono estratti 5 numeri. Un

giocatore vuole verificare una giocata di € 5 fatta di tre numeri. Se su una ruota è presente un numero il

giocatore vince 5 volte la puntata, 10 per due numeri, e 50 per il terno per ogni ruota. Si chiedano in

input al giocatore i tre numeri e si verifichi se ha vinto e in caso positivo la somma vinta. Questo

algoritmo all’apparenza complesso può essere risolto con l’ausilio delle matrici dando come dimensione

una matrice 4 per 5. ogni riga della matrice costituirà la ruota di una delle quattro città. Ad esempio sulla

prima riga vi sarà la ruota di napoli, sulla seconda roma e così via. Una volta richiesti i tre numeri

bisognerà contare quanti di questi sono usciti su una ruota. La tabella delle variabili è pertanto:

Classe     Nome                      Tipo
Input         lotto                      matrice di 4 righe e 5 colonne di interi contenente i numeri estratti
Input         n1,n2,n3               interi numeri giocati
Interna     i,j                           indici matrice
Interna     cont                       intera numeri di estratti indovinati dal giocatore
Output     somma                  intera somma eventualmente vinta dal giocatore

L’algoritmo consiste in una prima parte ove si carica la matrice con gli estratti, e poi di una parte che

controlla il numero degli estratti indovinati. Alla fine del ciclo si comunicherà la giocatore se ha vinto

oppure no. Pertanto l’algoritmo è:

1. inizio
2. cont=0
3. somma=0
4. per i= 1 a 4 esegui
5. ciclo 1
6. per j=1 a 5 esegui
7. ciclo 2
8. scrivi “dammi i numeri estratti su tutte le ruote”
9. leggi lotto(i,j)
10. fine ciclo 2
11. fine ciclo 1
12. scrvi “dammi i numeri giocati”
13. leggi n1,n2,n3
14. per i=1 a 4 esegui
15. ciclo 1
16. per j=1 5 esegui
17. ciclo 2
18. se lotto(i,j)=n1 o lotto(i,j)=n2 o lotto(i,j)=n3 allora
19. cont=cont+1
20. fine ciclo 2
21. se cont=1 allora
22. somma=somma+5*5
23. se cont=2 allora
24. somma=somma+5*10
25. se cont=3 allora
26. somma=somma +5*50
27. cont=0
28. fine ciclo 1
29. se somma =0 allora
30. scrivi “non hai vinto niente”
31. altrimenti
32. scrivi “hai vinto €” , somma
33. fine

In questo problema due osservazioni la prima è che la puntata è fissa come richiesto dal problema ed è

quindi una costante dell’algoritmo. La seconda invece risiede nell’utilizzo dell’operatore logico “o” nel

confronto per verificare l’uguaglianza dei numeri giocati con ogni singolo estratto. E’ stata fatta questa

scelta per ridurre il numero delle condizioni che altrimenti sarebbero state tre. Per comprendere ancora

l’utilizzo delle matrici sia dato il seguente problema: data una matrice quadrata di dimensione n i cui

elementi sono interi dopo aver inserito i dati calcolare la somma della diagonale principale (per intenderci

gli elmenti che hanno stessa coordinata di riga e di colonna). La tabella dati dell’algoritmo che segue

sara:
classe     nome e descrizione                                      tipo
input             mat matrice di dimensione n                         tipo matrice n per n di interi
input             n numero di righe e colonne della matrice    intero
interne          i,j indici della matrice                                 interi
output          somma                                                        intera

L’algoritmo sarà:

1. Inizio
2. somma=0 // inizializzaizone
3. scrivi “dammi il numero delle righe e delle colonne”
4. leggi n
5. per i=1 a n esegui
6. ciclo 1
7. per j=1 a n esegui
8. ciclo 2
9. scrvi “dammi elemento di riga “,i,” colonna “,j
10. leggi mat(i,j)
11. fine ciclo 1
12. fine ciclo 2
13. per i= 1 a n esegui
14. ciclo 3
15. somma=mat(i,i)+somma
16. fine ciclo 3
17. scrivi “la somma degli elementi della diagonale è:”
18. scrivi somma
19. fine

Come si può notare dall’algoritmo nel calcolare la somma è stato necessario un solo ciclo, perchè gli

elementi di diagonale principale hanno la caratteristica di avere indice di riga e colonna uguali. Nelle

matrici si definisce anche la diagonale secondaria come gli elementi della matrice che partono

dall’elemento di riga 1 e colonna n e arrivano all’elmento di riga n e colonna 1 passando per l’elemento

carattarizzato dall’avere coordinata di riga e colonna uguali. Un algoritmo molto più complesso del

precedente potrebbe essere quello di calcolare la somma degli elementi di diagonale secondaria

attraverso sempre l’uso dei cicli di una matrice di ordine n. In questo caso basta osservare che gli

elementi di diagonale secondaria sono caratterizzati dal fatto che la somma degli indici è pari alla

dimensione della matrice che ricordo essere quadrata aumentata di un’unità.
3     2     0
1     2     6
5     5     7

In questa matrice 3 per 3 sopra rappresentata si nota che i valori 0,2 e 5 sono caratterizzati dal fatto

che la somma dei loro indice è pari sempre a 4, ma se la dimensione della matrice è 3 vuol dire che il

tutto è aumentato di un’unità. L’algoritmo pertanto è:

somma=0

1. Inizio
2. scrivi “dammi la dimensione”
3. leggi n
4. per i = 1 a n esegui
5. ciclo 1
6. per j=1 a n esegui
7. ciclo 2
8. scrivi “dammi gli elementi della matrice”
9. leggi mat(i,j)
10. fine ciclo 1
11. fine ciclo 2
12. se n è pari allora
13. per i= 1 a n esegui
14. ciclo 1
15. per j=n 1 esegui
16. ciclo 2
17. se i+j=n+1 allora
18. somma=somma + mat(i,j)
19. fine ciclo 1
20. fine ciclo 2
21. altrimenti //n è dispari
22. per i= 1 a n esegui
23. ciclo 1
24. per j=n a 1 esegui
25. ciclo 2
26. se i+j=n+1 allora
27. somma=somma + mat(i,j)
28. fine ciclo 1
29. fine ciclo 2
30. scrvi “la somma è”, somma
31. fine

Record e tabelle

Quanto le informazioni da gestire sono di tipo diverso allora è opportuno definire delle strutture di dati

eterogenee dette record. Un record è una variabile strutturata astratta identificata da un nome collettivo i

cui elementi sono di tipo diverso. Ogni componente è detta campo. Un insieme di record raggruppati in

un vettore ovvero un vettore di record è detta tabella. La prima fase di analisi del problema che

coinvolgono i record è la definizione del tracciato record che indica i campi che costituiscono il record la

loro tipologia e dimensione. Ad esempio supponiamo che dato un elenco di alunni di una classe si vuole

visualizzare i dati relativi ai maggiorenni. Possiamo pertanto definire un tracciato record come segue:

Cognome     Nome     Età
Stringa * 16 caratteri     Stringa * 16 Caratteri     Intero
Nome Record A

Abbiamo definito il tracciato record con nome modello A e campi cognome, nome, età con i loro tipi. Si

definisce modello una struttura dati astratta definita dall’utente infatti nella fase di dichiarazione delle

variabili si definisce una variabile di tipo tabella formata da righe di tipo A. Il record così come la tabella

sono variabili ad accesso diretto ovvero la selezione di un elemento avviene indicando direttamente il

nome del campo preceduto dal nome del record separato dal carattere “.”. Quindi A.Nome richiama il

campo nome del record A. Vediamo la tabella delle variabili per il problema posto.
Classe     Nome     Tipo
Input     tabella     vettore di N elementi di tipo A
Input     N     intero
Interno     K,NC,C     Intero, Stringa*16, Stringa*16
Output     tabella     vettore di N elementi di tipo A

L’algoritmo per comodità verrà frammentato in due procedure carica e visualizza.

1. Inizio carica
2. Scrivi “Dammi il numero degli alunni”
3. Leggi N
4. Ciclo 1
5. Per k=1 a N esegui
6. Scrivi “Inserisci il nome”
7. Leggi tabella(k).nome
8. Scrivi “Inserisci il cognome”
9. Leggi tabelle(k).cognome
10. Scrivi “Inserisci età”
11. Leggi tabella(k).eta
12. Fine ciclo 1
13. Fine Carica

1. Inizio Visualizza
2. NC=””
3. C=””
4. Ciclo 1
5. Per k=1 a N esegui
6. Se tabella(k).eta >= 18 allora
7. NC=tabella(k).nome
8. C=tabella(k).coginome
9. Scrivi NC
10. Scrivi C
11. Fine Se
12. Fine Ciclo
13. Fine

Il programma principale è pertanto costituito dalla chiamata delle due procedure.

1. Inizio
2. Carica
3. Visualizza
4. Fine

Un altro esempio può essere dato dall’ordinamento di una tabella secondo un criterio prestabilito

ovvero in ordine alfabetico di nome, cognome o età. Gli algoritmi di ordinamento sono simili a quelli

utilizzati per i vettori ovvero ordinamento sequenziale o a bolle.


Azioni

Information

Lascia un commento

Effettua il login con uno di questi metodi per inviare il tuo commento:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...




%d blogger cliccano Mi Piace per questo: