Linguaggio C++ 7 Vettori

2009-2010
Ingegneria Aerospaziale
Prof. A. Palomba - Elementi di Informatica (E-Z)
Linguaggio C++
7
Vettori
Linguaggio C++ 7
1
Un dato strutturato.
Array monodimensionale (Vettore)
Un insieme di variabili tutte dello stesso tipo identificate con un nome comune ;
uno specifico elemento referenziabile tramite un indice (funzione di accesso)
A
A
A
A
A
1
2
3
4
5
A
6
A
A
7
8
Pensiamo all’array come ad un insieme di cassetti numerati. Per accedere
al contenuto di uno specifico cassetto si deve specificare il numero d’ordine
ad esso associato (indice)
Accesso diretto
Linguaggio C++ 7
A[5]
2
Gli elementi del vettore vengono allocati alla traduzione (compilazione) in
celle di memoria adiacenti(successive)
Per tale motivo è necessario dichiarare il vettore prima del suo utilizzo in
modo che il compilatore possa riservare in memoria lo spazio (nro celle) per
contenerlo e possa altresi controllare ogni utilizzo di indici eccedenti le sue
reali dimensioni
Cardinalità Numero di celle definite all’atto della dichiarazione del vettore
Sintassi dichiarazione di vettore :
identificatoretipo nome_variabile [cardinalità] ;
int numero[10];
Dichiarazione di un vettore chiamato numero
contenente un massimo di 10 elementi interi.
Il C++ assegna gli indici agli elementi di un array a partire da 0; gli elementi
dell'array di interi appena dichiarato vanno da indice 0 ad indice 9
numero[0] a numero[9]
Linguaggio C++ 7
3
Inizializzazione elementi array
Per singola inizializzazione direttamente nel programma;
a[0]=5;
…………………. A[9]=9;
Direttamente alla dichiarazione della struttura:
int a[10]= 5,8,3,6,2,0,4,1,7,9 
Per inizializzazione in fase di esecuzione (da tastiera)
int a[10];
cin>>riemp;
for (i=0;i<=riemp;i++)
cin >> a[ i ];
int
inta[
a[]=1,2,3,4,5
]=1,2,3,4,5
Linguaggio C++ 7
Riemp <=cardinalità
Dichiarazione di array valida
Dalla lista degli inizializzatori ricava la cardinalità
del vettore
4
ERRORE
Numero elementi inizializzati > Cardinalità dichiarata
12 > 10
INDICE
INDICE
00
11
22
33
44
55
66
77
88
99
Linguaggio C++ 7
VALORE
VALOREELEM
ELEM
11
11
32
32
00
00
00
00
00
00
00
00
Se
Segli
glielemento
elementoinizializzati
inizializzatisono
sonoinferiori,
inferiori,in
innumero,
numero,
alla
allacardinalità
cardinalitàdichiarata,
dichiarata,i irimanenti
rimanentivengono
vengono
automaticamente
azzerarti.
automaticamente azzerarti.
5
Per inizializzazione in fase di esecuzione (da tastiera)
Scrittura array
0 0 0
int a[10]
for (i=0; i <= riemp; i++)
cin >> a[ i ];
5
Riemp
0
0
0
0
0
0
0
legge riemp
i=0
legge a[ i ]
No
Verifica che i <riemp
Si
Fine lettura
i=i+1
Linguaggio C++ 7
7
4
3
2
1
0
0
0
0
0
6
Conversione esplicita di tipo
Linguaggio C++ 7
7
Esercizio
Assegnato un vettore di interi di riempimento N, produrre la
trasposizione del vettore
N=7
Vett = 1 2 3 4 5 6 7
a)
N pari
7 6 5 4 3 2 1
b) N dispari
1
1
2
2
3
3
4
4
5
Numero scambi = N / 2
N=5
N=4
Linguaggio C++ 7
2
2
Per
PerNNdispari
disparil’elemento
l’elementocentrale
centralenon
non
soggetto
soggetto aaspostamento
spostamento
8
dimez=N/2;
for (int i=0; i<dimez; i++)
{
temp = vett [ N –i -1 ];
vett[ N-i-1 ] = vett[ i ];
vett[ i ] = temp;
}
1
2
3
4
5
N=5
i=0
Vett[N – i -1] =Vett[5-0-1] =Vett[4]
Vett[i] =Vett[0]
5
1
4
2
i=1
Vett[N – i -1] =Vett[5-1-1] =Vett[3]
Vett[i] =Vett[1]
Linguaggio C++ 7
9
Linguaggio C++ 7
10
Esercizio
Assegnato un vettore di max 10 valori interi, determinare valore max e
valore min e rispettive posizioni (indice)
5 7 2 10
1
4
Max = 10
Min = 1
Posmax =3
Posmin =4
Descrizione algoritmo
Si parte supponendo che gli elementi MAX e MIN coincidano con il primo
elemento del vettore; di conseguenza Posmax e Posmin sono entrambi
localizzati in posizione indice 0 del vettore
Gli elementi MAX e MIN vengono confrontati in sequenza con tutti gli
elementi del vettore a partire dall’elemento in seconda posizione (indice 1)
Durante i confronti se si trova un valore maggiore di MAX si provvede a
caricarlo in MAX e ad aggiornare Posmax con l’indice dell’elemento
trovato. Stesso aggiornamento qualora si trova un valore minore di MIN
Linguaggio C++ 7
11
5 7
2
10
1
4
Maxcorrente=5
Posmax=0
Indice vettore=1
Si
Max corrente =5 < vett[1]=7  Maxcorrente =7 Posmax=1;
Indice vettore=2
Max corrente =7 > vett[2]=2  Maxcorrente =7 Posmax=1;
Si
Indice vettore=3
Max corrente =7 > vett[3]=10  Maxcorrente =10 Posmax=3;
Indice vettore=4
Max corrente =10 > vett[4]=1  Maxcorrente =10 Posmax=3;
Indice vettore=5
Max corrente =10 > vett[5]=4  Maxcorrente =10 Posmax=3;
Analogamente per la ricerca del minimo e della posizione
Linguaggio C++ 7
12
Analisi delle informazioni
Informazioni di ingresso
Nome
Vettore
N
Tipo
Descrizione significato
vettore interi cardinalità 10
vettore su cui operare
variabile intera
riempimento del vettore
Informazioni di uscita
Nome
Tipo
Descrizione significato
Max
Variabile intera
Max corrente
Min
variabile intera
Min corrente
Posmax
Variabile intera
Posizione max corrente
Posmin
Variabile intera
Posizione min corrente
Informazioni di algoritmo
Nome
Tipo
Descrizione significato
Valore
Variabile intera
Elemento del vettore che viene letto
I
variabile intera
Indice del vettore
Linguaggio C++ 7
13
Inizio
Leggi riempimento del vettore;
Se riempimento <= 10 allora
inizio blocco1
Leggi vettore;
Assegna a maxcorrente primo valore del vettore;
Assegna a mincorrente primo valore del vettore;
Assegna a posizionemaxcorrente 0;
Assegna a posizionemincorrente 0;
per posizione indice corrente da 1 a riempimento-1 incrementandosi di 1
inizio blocco2
Se maxcorrente < elemento corrente vettore allora
inizio blocco3
Aggiorna maxcorrente con elemento corrente;
Aggiorna posmaxcorrente con indice corrente;
fine blocco3
Se mincorrente > elemento corrente vettore allora
inizio blocco4
Aggiorna mincorrente con elemento corrente;
Aggiorna posmincorrente con indice corrente;
fine blocco4
fine blocco2
Produci risultati
fine blocco1
altrimenti
Linguaggio
Produci C++
frase 7“ Riempimento eccedente cardinalità del vettore”:
Fine
14
Linguaggio C++ 7
15
Linguaggio C++ 7
16
Esercizio
Assegnato un vettore A di interi di cardinalità 50 elementi e riempimento N, si
determini la somma degli elementi di indice pari
7
Linguaggio C++ 7
5
3
2
8
1
9
5
Somma=27
17
Esercizio
Si scriva un programma che assegnati in input due vettori A e B di interi
entrambi di riempimento N ed un numero intero K <=N restituisca la somma
dei primi K elementi di A e degli ultimi K elementi di B.
N=6
A 1 2 3
B 0 3 6
4
9
5
4
6
2
K=3
Somma primi K elementi di A=6
Somma ultimi K elementi di B=15
Linguaggio C++ 7
18
Linguaggio C++ 7
19
Linguaggio C++ 7
20
Esercizio
Si scriva un programma che assegnato in input un vettore A di interi, di
riempimento N, generi un vettore B i cui elementi siano la differenza di
ciascuna coppia di valori di A considerate procedendo da sinistra verso
destra
A
B
 31 22 18 14 25 6 17
 9 4 4 -11 19 -11 9
8
N=8
Necessario determinare la differenza fra N-1 coppie
La differenza viene valutata come A[i] - A[i+1] con l’indice i che varia da 0
a <N-1
Il vettore B avrà riempimento N-1 (numero coppie differenziate)
5
7
6
4
i=0
A[0] – A[1]  -2 = B[0]
i=1
A[1] – A[2]  1 = B[1]
i=3 C++A[2]
Linguaggio
7 – A[3]  2 = B[2]
N=4
21
Linguaggio C++ 7
22
Esercizio proposto
Si scriva un programma che assegnati in input due vettori A e B di reali, di
riempimento N, generi un vettore C i cui elementi siano al valore VERO
se il valore dell’elemento i-mo di A è >= al corrispondente valore del
vettore B,Falso in caso opposto
A
B
C
3.1 2.2 1.8
2.0 2.4 3.4
V F
F
Linguaggio C++ 7
1.4
1.1
V
2.5
1.9
V
0.6
1.1
F
1.7
3. 9
F
N=7
23
Esercizio
Assegnato un vettore di interi di riempimento N, provvedere a scambiare
ogni coppia di elementi. Nel caso di N dispari, la posizione dell’ultimo
elemento resta invariata.
N=7
A1 2 3 4 5 6 7
A2 1 4 3 6 5 7
Sia che N sia dispari o pari il numero di coppie soggette a scambio è N/2
for (int i=0;i<=N/2;i++)
effettua scambio di coppia
Lo scambio interessa per ogni ciclo l’elemento i-mo e l’elemento i-mo+1.
Si parte con posizionamento iniziale sull’elemento di indice 0 che viene
incrementato di 2 ad ogni ciclo
Linguaggio C++ 7
24
Linguaggio C++ 7
25
Esercizio
Dato un vettore di N elementi interi non ordinato, si inserisca un assegnato
valore in una determinata posizione (indice) del vettore
11 22 33 44 66 77 88
Pos=4
Elem=5
N=7
11 22 33 44 55 66 77 88
Problema : Il riempimento del vettore deve essere inferiore alla cardinalità
del vettore
L’inserimento nel vettore richiede prioritariamente lo spostamento di una
posizione a destra di tutti gli elementi a partire dalla posizione di inserimento
per evitare perdita di informazioni
Numero di elementi da spostare = N - pos
Linguaggio C++ 7
26
Linguaggio C++ 7
27
Esercizio
Dato un vettore di N elementi interi non ordinato, si vuole eliminare il valore
esistente in una determinata posizione del vettore
11 22 33 44 66 77 88
Pos=4
Gli elementi alla destra della
posizione di cancellazione
vanno semplicemente spostati
di un posto a sinistra
N=7
11 22 33 44 77 88
Numero di elementi da spostare = N – pos-1
Necessario , a spostamento completato,decrementare il
riempimento del vettore
Linguaggio C++ 7
28
Linguaggio C++ 7
29
Ricerca binaria
Assegnato un valore intero K verificare la sua esistenza in un vettore di
interi ordinato in senso crescente (condizione necessaria) di riempimento N
3
5
7
8
9
12
15
8
Casi: K
coincidente con primo elemento dl vettore
coincidente con ultimo elemento del vettore
coincidente con elemento interno del vettore
non coincidente con nessun elemento del vettore
1a soluzione
Confronto del valore K con tutti gli N elementi del vettore procedendo dal
primo all’ultimo
Si parte dal presupposto di valore inesistente (var logica) che si aggiorna
ad esistente se l’elemento realmente esiste nel vettore
Necessari N confronti
Linguaggio C++ 7
Non necessario vettore ordinato
30
Linguaggio C++ 7
31
2a soluzione : Ricerca binaria (o dicotomica)
Supera il limite imposto dalla ricerca sequenziale ( scansione di tutti gli
elementi del vettore e confronto con il valore da cercare. Necessario
vettore ordinato.
Sapendo che il vettore è ordinato in modo crescente, si determina
l’elemento centrale (N-1)/2 che confrontato con l’elemento da cercare
porta ad eliminare
-o la parte destra del vettore (considerando come ultimo elemento quello
di indice (N-1)/2 -1
-o la parte sinistra del vettore (considerando come primo elemento quello
di indice (N-1)/2 + 1
Iterando il procedimento si può raggiungere la condizione
o di elemento trovato
o di elemento inesistente (indice inferiore > indice superiore)
Linguaggio C++ 7
32
2a soluzione : Ricerca binaria
Valore da trovare : 10
centrale
estrinf
estrinf
1 3 5 10 15 23 31 47 49 56 61
0
1
2
3
4
5
6
7
8
9
10
1 3 5 10 15 23 31 47 49 56 61
0
1
2
3
4
5
6
7
8
9
10
1 3 5 10 15 23 31 47 49 56 61
0
1
2
3
4
5
6
7
8
9
10
Applicabilità : Vettore ordinato
Linguaggio C++ 7
33
Linguaggio C++ 7
34
Esercizio
Dato un vettore di N elementi interi ordinato in senso crescente,si vuole
inserire un assegnato valore mantenendo l’ordinamento del vettore
10 20 30 50 60 70
Elemento da inserire 40
10 20 30 40 50 60 70
Ipotesi di algoritmo
Valuta se elemento va in prima posizione (in tal caso provvedere prima a
N spostamenti a destra di una posizione)
Valuta se elemento va in ultima posizione; in tal caso nessun spostamento,
semplicemente accodare l’elemento
Trova posizione di inserimento (posizione interna) e determina quanti
spostamenti a destra effettuare prima di inserire l’elemento nella giusta
posizione
Controlli: non eccedere con l’inserimento la cardinalità definita per il vettore
Linguaggio C++ 7
35
Linguaggio C++ 7
36
Linguaggio C++ 7
37
Linguaggio C++ 7
38
Ordinamento crescente di un vettore
Metodo SCAMBI SUCCESSIVI (o bolla)
Il processo si evolve in più passi ripetitivi. In ognuno gli elementi del vettore
vengono confrontati a coppie procedendo al loro scambio posizionale nel
caso che l’elemento i-mo sia > dell’elemento i-mo+1.
N=5
Necessari N-1 passi ripetitivi (condizione di vettore all’origine ordinato
in senso decrescente)
Il numero di passi ripetivi si riduce (terminazione anticipata) quando in un
passo non si producono scambi
56 15 10 2 1
15 10 2 1 56
10 2 1 15 56
2 1 10 15 56
15 56 10 2 1
10 15 2 1 56
2 10 1 15 56
1 2 10 15 56
15 10 56 2 1
10 2 15 1 56
2 1 10 15 56
1 2 10 15 56
15 10 2 56 1
10 2 1 15 56
2 1 10 15 56
1 2 10 15 56
15 10 2 1 56
10 2 1 15 56
2 1 10 15 56
1 2 10 15 56
Linguaggio
C++ 7
1° passaggio
2° passaggio
3° passaggio
4° passaggio 39
Detto metodo richiede nel caso peggiore ( vettore già ordinato in senso
decrescente) la necessità di N * ( N – 1)/2 scambi
4
3
2
3
2
1
2
1
3
1
4
4
primo passaggio
N-1 scambi 3
secondo passaggio N-2 scambi 2
terzo passaggio
N-3 scambi 1
6
Numero scambi = 4 *3/2 =6
10 5 1 16 56
1 5 10 16 56
5 10 1 16 56
1 5 10 16 56
5 1 10 16 56
1 5 10 16 56
5 1 10 16 56
1 5 10 16 56
5 1 10 16 56
1 5 10 16 56
Almeno uno scambio avvenuto
necessario altro passaggio
Linguaggio C++ 7
Nessun scambio avvenuto
condizione di terminazione anticipata
40
Linguaggio C++ 7
41
Linguaggio C++ 7
42
Ordinamento di un vettore con metodo MINIMI SUCCESSIVI
passo1
15 56 10 2 1 23 47 64 31 5 3
0
passo2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
15 2 10 56 15 23 47 64 31 5 3
0
passo4
2
1 56 10 2 15 23 47 64 31 5 3
0
passo3
1
1
2
3
4
5
6
7
8
9
10
15 2 3 56 15 23 47 64 31 5 10
0
1
2
3
4
5
6
7
8
9
10
----------------------------------------------------------------------------
Linguaggio C++ 7
43
minimo
In sintesi:
(passo1) Fissa il minimo al primo elemento del vettore e cerca, se
esiste,un nuovo minimo fra gli elementi dalla posizione 2 ad N. Se
esiste scambia di posizione l’elemento trovato con quello in prima
posizione
(passo2) Fissa il minimo al secondo elemento del vettore e cerca, se
esiste,un nuovo minimo fra gli elementi dalla posizione 3 ad N
Se esiste scambia di posizione l’elemento trovato con quello in
seconda posizione
(passoN-1) Fissa il minimo all’elemento N-1del vettore e confronta
con elemento N
Necessari N-1 passi
Linguaggio C++ 7
44
Linguaggio C++ 7
45
Metodo :Ordinamento dinamico di un vettore durante il caricamento
Ipotesi algoritmo
Lettura primo elemento-Inserimento in prima posizione
Per i rimanenti valori
Lettura elemento da inserire
Se risulta > ultimo inserito lo si accoda nel vettore
altrimenti
si determina posizione di inserimento
da questa posizione si spostano gli elementi di un posto a dx
nella posizione si inserisce elemento letto
Linguaggio C++ 7
46
Elementi da inserire 5 8 9 6
passo1
passo2
passo3
passo4
5
0
1
2
3
4
5
6
7
8
9
10
5
8
0
1
2
3
4
5
6
7
8
9
10
5
8
9
0
1
2
5
8
9
0
1
2
3
8
9
5
9 >8
3
0
1
2
3
5
6
8
9
0
1
2
3
Linguaggio C++ 7
8 >5
4
5
6
7
8
9
10
4
5
6
7
8
9
10
4
5
6
7
8
9
10
4
5
6
7
8
9
10
6 <9
6<8
6>5
pos=2
47
Linguaggio C++ 7
48
Assegnata una parola, determinare
le occorrenze di ciascun carattere
precipitevolissimevolmente
N=26
Linguaggio C++ 7
p
r
e
c
i
t
v
o
l
s
m
n
2
1
5
1
4
2
2
2
2
2
2
1
49
Esercizio
Dati due vettori vett1 e vett2 ordinati in senso crescente ,di riempimento
vario riemp1 < = > riemp2 ,produrre un vettore vett3, effetto della fusione
dei due vettori iniziali, anch’esso ordinato in senso crescente
Vett1
20 40 80
Vett2
10 30 50 55
Vett3
10 20 30 40 50
70
55 60 80
Mentre non tutti gli elementi di vett1 e vett2
sono stati inseriti in vett3 ……
…..preleva da vett1 o vett2 l’elemento che,
nell’ordinamento crescente di vett3 segue
l’ultimo elemento già inserito
Linguaggio C++ 7
IfIf((vett1[
vett1[i i]] << vett2[
vett2[j j])])
{{
vett3[
vett3[kk]]==vett1[
vett1[i i]]
i=i+1
i=i+1
}}
else
else
{{
vett3[
vett3[kk]]==vett2[
vett2[j j]]
j=j+1
j=j+1
}}
K=k+1
K=k+1
50
Linguaggio C++ 7
51
Linguaggio C++ 7
52
Linguaggio C++ 7
53
Esercizio proposto
Sia assegnato un vettore A di interi di riempimento N.
Nella ipotesi che il primo elemento A[0] sia minore del secondo elemento A[1]
si eliminino dal vettore tutti gli elementi che risultano inferiori ad A[0] oppure
superiori ad A[1].
riempimento N=10
vettore ingresso A  2 10 8 7 6 13 1 4 11 20
vettore uscita
A  2 10 8 7 6 4
Esercizio proposto
Dato un vettore A di interi di cardinalità 50 e il riempimento N , si generi
il vettore B contenente gli elementi del vettore A senza le ripetizioni.
Si produca la stampa del vettore B
N=6
A= 1 2 3 3 2 1
B= 1 2 3
Linguaggio C++ 7
54
Esercizio proposto
Assegnati N valori interi ed un valore di
riferimento, individuare tutte le coppie di
valori la cui somma superi il valore di
riferimento
Metodo di soluzione
N=7
9 5 7 2 3 8 4
Riferimento =11
9
9
9
9
9
5
5
7
8
5
7
3
8
4
7
8
8
4
Ogni elemento (dal primo al penultimo)
viene relazionato nella somma con
tutti i rimanenti elementi
for (int i=0;i<N-1;i++)
for (int j=i+1;j<N;j++)
Se la somma supera il valore di
riferimento la coppia individuata
viene memorizzata in un vettore
di appoggio
if ((vett[ i ]+vett [ j ]) > rifer)
{
k=k+1;
appo[ k ][ 0 ]=vett[ i ];
appo[ k] [ 1]=vett[ j ];
}
Linguaggio C++ 7
55
Esercizio proposto
Assegnato un vettore di N elementi interi, individuare nel vettore la più
lunga sequenza di numeri pari, producendo:
la lunghezza
la sequenza
la posizione di inizio della sequenza nel vettore
N=12
1 12 3 12 3 65 4
6 65 6 12
Lunghezza =3
Sequenza = 6 12 8
Posizione =9
8
Esercizio proposto
Assegnati due vettori di interi A e B con lo stesso riempimento N ed un
valore intero K<=N, si modifichi il vettore A sostituendo, per ogni
Indice i<K A[i] con di A[i] + B[i].
A
B
1 2 3
0 3 6
4
9
Linguaggio C++ 7
5
4
6
2
K=2
A
1 5 9 4
5 6
56
Esercizio proposto
Assegnati in input due vettori di interi A e B, di riempimenti rispettivamente
N1 e N2, si individuino gli elementi in comune nei due vettori e se ne indichi
le posizioni nei due vettori
Si supponga che in ciascuno dei vettori A e B non ci siano ripetizioni di valori.
N1=5
N2=8
A  1 5 7
B  3 4 5
8 12
7 10 9 6
0
valore 5  1
valore 7  2
2
3
Esercizio proposto
Assegnato un vettore A di interi di cardinalità 10 e di riempimento N ed
un valore di riferimento VAL:
-generare un secondo vettore B contenente tutti e solo gli elementi di A
che risultano multipli di VAL
-determinare la somma degli elementi di A che non appartengono a B
N =7
A
B
4 5 2 3 7 6 1
4 2 6
Linguaggio C++ 7
VAL =2
Somma=16
57