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