Corso di Informatica
(Programmazione)
Esercitazione 2 (3 dicembre 2008)
1
Esercizi sugli array
Esercizio 1
dato un array A di N interi verificare se
gli elementi sono in ordine crescente
Esempio1 (N=10)
A
4 15 20 40 46 60 80 92 110 121
Risultato  gli elementi di A sono
in ordine crescente
2
Esercizi sugli array
Esempio2 (N=10)
A
4 15 92 121 46 60 80 20 110 40
Risultato  gli elementi di A NON sono
in ordine crescente
3
Esercizi sugli array
Algoritmo: uso una variabile di tipo boolean che
chiamo ad esempio isCrescent che, alla fine, deve
contenere il valore true se A è crescente e il
false se A non è crescente. Parto dal presupposto
che A sia crescente e quindi inizializzo isCrescent
a true. Poi esamino uno alla volta gli elementi di A
dal primo (in posizione 0) al penultimo (in posizione
N-2). Se per una posizione i esaminata...
4
Esercizi sugli array
… trovo che A[i] >= A[i+1] (tra l’elemento in
posizione i e il successivo), allora posso dire
con certezza senza bisogno di proseguire che A
non è crescente. A questo punto assegno il valore
false alla variabile isCrescent e interrompo la
scansione di A. Quindi al termine della scansione…
5
Esercizi sugli array
… di A, mi basta testare il contenuto di isCrescent
per dire se A è crescente o non lo è. Se infatti
isCrescent è rimasto a true significa che non
c’è nessuna posizione i tale che A[i] >= A[i+1]
e quindi A è crescente.
6
Esercizi sugli array
Esecuzione dell’algoritmo per l’array A di 10
interi dell’esempio1 precedente:
- all’inizio ho isCrescent=true
- step 1  i=0 (i è l’indice che scandisce gli elementi di A)
A
4 15 20 40 46 60 80 92 110 121
A[0] >= A[1]? NO! Quindi vado avanti
7
Esercizi sugli array
- step 2  i=1
A
4 15 20 40 46 60 80 92 110 121
A[1] >= A[2]? NO! Quindi vado avanti
- step 3  i=2
A
4 15 20 40 46 60 80 92 110 121
A[2] >= A[3]? NO! Quindi vado avanti
8
Esercizi sugli array
- step 4  i=3
A
4 15 20 40 46 60 80 92 110 121
A[3] >= A[4]? NO! Quindi vado avanti
- step 5  i=4
A
4 15 20 40 46 60 80 92 110 121
A[4] >= A[5]? NO! Quindi vado avanti
9
Esercizi sugli array
- step 6  i=5
A
4 15 20 40 46 60 80 92 110 121
A[5] >= A[6]? NO! Quindi vado avanti
- step 7  i=6
A
4 15 20 40 46 60 80 92 110 121
A[6] >= A[7]? NO! Quindi vado avanti
10
Esercizi sugli array
- step 8  i=7
A
4 15 20 40 46 60 80 92 110 121
A[7] >= A[8]? NO! Quindi vado avanti
- step 9  i=8
A
4 15 20 40 46 60 80 92 110 121
A[8] >= A[9]? NO! Sono arrivato al penultimo e…
11
Esercizi sugli array
… la variabile isCrescent è rimasta a true 
A è crescente.
Esecuzione dell’algoritmo per l’array A di 10
interi dell’esempio2 precedente:
- all’inizio ho isCrescent=true
- step 1  i=0 (i è l’indice che scandisce gli elementi di A)
A
4 15 92 121 46 60 80 20 110 40
A[0] >= A[1]? NO! Quindi vado avanti
12
Esercizi sugli array
- step 2  i=1
A
4 15 92 121 46 60 80 20 110 40
A[1] >= A[2]? NO! Quindi vado avanti
- step 3  i=2
A
4 15 92 121 46 60 80 20 110 40
A[2] >= A[3]? NO! Quindi vado avanti
13
Esercizi sugli array
- step 4  i=3
A
4 15 92 121 46 60 80 20 110 40
A[3] >= A[4]? SI’! Quindi assegno il valore false
a isCrescent e interrompo la scansione.
Dal momento che il valore finale di
isCrescent è false, A è NON crescente
Per verificare che un vettore è decrescente il
discorso è analogo!
14
Esercizi sugli array
public class VerificaVettoreCrescente {
public static void main(String arg[]) {
int[] A={4,15,20,21,40,6,7,9,10,1};
int i;
int length;
boolean isCrescent;
length=10;
i=0;
isCrescent=true;
while(i <= lentgth-2 && isCrescent == true){
//Verifico se l’elemento i-esimo
//è >= dell’elemento (i+1)-esimo
if(A[i] >= A[i+1]){
isCrescent=false;
}
i=i+1;
}
System.out.println(“Vettore crescente: “+isCrescent);
}
}
15
Esercizi sugli array
public class VerificaVettoreDecrescente {
public static void main(String arg[]) {
int[] A={4,15,20,21,40,6,7,9,10,1};
int i;
int length;
boolean isDecrescent;
length=10;
i=0;
isDecrescent=true;
while(i <= lentgth-2 && isDecrescent == true){
//Verifico se l’elemento i-esimo
//è <= dell’elemento (i+1)-esimo
if(A[i] <= A[i+1]){
isDecrescent=false;
}
i=i+1;
}
System.out.println(“Vettore decrescente: “+isDecrescent);
}
}
16
Esercizi sugli array
NOTA BENE: il confronto A[i] >= A[i+1] nel
costrutto IF viene utilizzato per verificare che
un array sia STRETTAMENTE crescente (cioè un
array in cui compaiono due elementi consecutivi
uguali non è considerato STRETTAMENTE
crescente). Se invece si vuole verificare che un
array sia crescente non in senso stretto, allora il
confronto da testare in IF è A[i] > A[i+1].
17
Esercizi sugli array
… Il discorso è analogo per testare che un array
sia STRETTAMENTE descrescente
(A[i] <= A[i+1]) o non STRETTAMENTE
descrescente (A[i] < A{i+1])
18
Scarica

ProgrammazioneES2