Post on 01-May-2015
1
Corso di Informatica
(Programmazione)Esercitazione 3 (5 dicembre 2008)
2
Esercizi sugli arrayEsercizio 1
dato un array A di N interi calcolare la
media e contare gli elementi > della media
Esempio (N=10)
8011020 40 46 60 4 92 15121
Risultato 58 (in realtà 58.8) e ci
sono 5 elementi superiori a 58
A
3
Esercizi sugli arrayAlgoritmo: eseguo la somma S di tutti gli elementi
di A scandendo gli elementi di A dal primo (in
posizione 0) all’ultimo (in posizione N-1).
Divido poi S per la dimensione N ottenendo
la media M dei valori.
Esamino di nuovo uno alla volta gli elementi di A
dal primo all’ultimo e incremento di 1 un contatore
(variabile conta) ogni volta che la posizione i...
4
Esercizi sugli array… contiene un valore A[i] > M.
5
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- all’inizio ho somma=0- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
somma = somma+A[0] = 0 + 80 = 80
8011020 40 46 60 4 92 15121
6
Esercizi sugli array
A
- step 2 i=1
- step 3 i=2
8011020 40 46 60 4 92 15121
somma = somma+A[1] = 80 + 110 = 190
A 8011020 40 46 60 4 92 15121
somma = somma+A[2] = 190 + 20 = 210
7
Esercizi sugli array
A
- step 4 i=3
- step 5 i=4
8011020 40 46 60 4 92 15121
somma = somma+A[3] = 210 + 40 = 250
A 8011020 40 46 60 4 92 15121
somma = somma+A[4] = 250 + 46 = 296
8
Esercizi sugli array
A
- step 6 i=5
- step 7 i=6
8011020 40 46 60 4 92 15121
somma = somma+A[5] = 296 + 60 = 356
A 8011020 40 46 60 4 92 15121
somma = somma+A[6] = 356 + 4 = 360
9
Esercizi sugli array
A
- step 8 i=7
- step 9 i=8
8011020 40 46 60 4 92 15121
somma = somma+A[7] = 360 + 92 = 452
A 8011020 40 46 60 4 92 15121
somma = somma+A[8] = 452 + 15 = 467
10
Esercizi sugli array
A
- step 10 i=9
8011020 40 46 60 4 92 15121
somma = somma+A[9] = 467 + 121 = 588
- step 11calcolo la media:
M=somma / 10 = 588 /10 = 58 (arrotondoperché uso variabili intere)
11
Esercizi sugli array
A
- step 12 conta = 0- step 13 i=0 (nuova inizializzazione di i)
- step 14 i=1
8011020 40 46 60 4 92 15121
A[0] è > 58? Sì! Quindi conta = conta + 1 = 0 + 1 = 1
A 8011020 40 46 60 4 92 15121
A[1] è > 58? Sì! Quindi conta = conta + 1 = 1 + 1 = 2
12
Esercizi sugli array
A
- step 15 i=2
- step 16 i=3
8011020 40 46 60 4 92 15121
A[2] è > 58? NO! Quindi conta rimane a 2
A 8011020 40 46 60 4 92 15121
A[3] è > 58? NO! Quindi conta rimane a 2
13
Esercizi sugli array
A
- step 17 i=4
- step 18 i=5
8011020 40 46 60 4 92 15121
A[4] è > 58? NO! Quindi conta rimane a 2
A 8011020 40 46 60 4 92 15121
A[5] è > 58? SI’! Quindi conta = conta + 1 = 2 +1 = 3
14
Esercizi sugli array
A
- step 19 i=6
- step 20 i=7
8011020 40 46 60 4 92 15121
A[6] è > 58? NO! Quindi conta rimane a 3
A 8011020 40 46 60 4 92 15121
A[7] è > 58? SI’! Quindi conta = conta + 1 = 3 +1 = 4
15
Esercizi sugli array
A
- step 21 i=8
- step 22 i=9
8011020 40 46 60 4 92 15121
A[8] è > 58? NO! Quindi conta rimane a 4
A 8011020 40 46 60 4 92 15121
A[9] è > 58? SI’! Quindi conta = conta + 1 = 4 +1 = 5
16
Esercizi sugli arraypublic class CalcoloMedia {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i;int length;int somma=0, media=0, conta=0;
length=10;i=0;while(i <= lentgth-1){
somma=somma+A[i];i=i+1;
}media=somma/length;i=0;while(i <= lentgth-1){
if(A[I] > media){conta=conta+1;
}i=i+1;
}
System.out.println(conta+” elementi sono > di “+media);}
}
17
Esercizi sugli arrayEsercizio 2
dato un array A di N interi verificare se A
contiene almeno 3 elementi consecutivi
Esempio (N=10)
Risultato il vettore contiene almeno
3 elementi consecutivi
8011040 40 40 60 4 92 15121A
18
Esercizi sugli arrayAlgoritmo: dichiaro la variabile booleana
threeElements che all’inizio ha valore false (cioè
parto dall’ipotesi che l’array non abbia almeno 3
elementi consecutivi). Poi scandisco l’array dal
primo elemento (in posizione 0) a quello in
posizione N-3 (ovvero l’ultimo elemento dell’array
che è seguito da almeno 2 elementi), dove N è
la lunghezza dell’array.
19
Esercizi sugli array…Se trovo che, per la posizione generica i,
A[i] è uguale a A[i+1] e A[i+1] è uguale a
A[i+2], allora posso dire che nell’array ci sono
almeno 3 elementi consecutivi. In tale caso
assegno true alla variabile threeElements e
interrompo la scansione dell’array.
20
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- all’inizio threeElements è false- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
A[0] è uguale a A[1] e A[1] è uguale a A[2]?NO! Allora proseguo
8011040 40 40 60 4 92 15121
21
Esercizi sugli array
A
- step 2 i=1
- step 3 i=2
A[1] è uguale a A[2] e A[2] è uguale a A[3]?NO! Allora proseguo
A
A[2] è uguale a A[3] e A[3] è uguale a A[4]?SI’! Allora assegno true a threeElementse interrompo la scansione
8011040 40 40 60 4 92 15121
8011040 40 40 60 4 92 15121
22
Esercizi sugli arraypublic class ThreeElements {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i;int length;boolean trhreeElements=false;
length=10;i=0;while(i <= lentgth-1 && threeElements == false){
if(A[i]==A[i+1] && A[i+1]==A[i+2]){threeElements=true;
}i=i+1;
}
System.out.print(“Ci sono 3 elementi consecutivi: “);System.out.println(trhreeElements);
}}
23
Esercizi sugli arrayEsercizio 3
dato un array A di N interi e un intero k
verificare se A contiene k
Esempio (N=10, k=40)
Risultato il vettore contiene 40
8011039 12 40 60 4 92 15121A
24
Esercizi sugli arrayAlgoritmo: dichiaro la variabile booleana
found che all’inizio ha valore false (cioè
parto dall’ipotesi che l’array non contenga l’intero
k). Poi scandisco l’array dal primo elemento
(in posizione 0) all’ultimo (in posizione N-1). Se
trovo una posizione i tale che A[i] è
uguale a k, allora assegno alla variabile found
il valore true e interrompo la scansione
25
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- all’inizio found è false- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
A[0] è uguale a 40? NO! Allora proseguo
8011039 12 40 60 4 92 15121
26
Esercizi sugli array
A
- step 2 i=1
- step 3 i=2
A[1] è uguale a 40? NO! Allora proseguo
A
A[2] è uguale a 40? NO! Allora proseguo
8011039 12 40 60 4 92 15121
8011039 12 40 60 4 92 15121
27
Esercizi sugli array
A
- step 4 i=3
- step 5 i=4
A[3] è uguale a 40? NO! Allora proseguo
A
A[2] è uguale a 40? SI’! Allora assegno true afound e interrompo la scansione
8011039 12 40 60 4 92 15121
8011039 12 40 60 4 92 15121
28
Esercizi sugli arraypublic class SearchK {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i, k;int length;boolean found=false;
length=10;i=0;k=40;while(i <= lentgth-1 && found == false){
if(A[i]==k){found=true;
}i=i+1;
}
System.out.print(“Trovato: “+found);}
}
29
Esercizi sugli arrayNOTA BENE: il programma precedente vale
anche nel caso in cui A sia un array di caratteri
e al posto dell’intero k ci sia un carattere c.
La modifica del codice è contenuta nella
slide successiva.
30
Esercizi sugli arraypublic class SearchChar {
public static void main(String arg[]) {char[] A={‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’l’};int i;char c;int length;boolean found=false;
length=10;i=0;c=‘b’;while(i <= lentgth-1 && found == false){
if(A[i]==c){found=true;
}i=i+1;
}
System.out.print(“Trovato: “+found);}
}
31
Esercizi sugli arrayEsercizio 4
dato un array A di N interi e un intero k
contare le occorrenze di k in A
Esempio (N=10, k=40)
Risultato 40 compare 3 volte
80 40 39 12 40 60 4 92 40121A
32
Esercizi sugli arrayAlgoritmo: dichiaro la variabile intera
count che alla fine conterrà il numero di
occorrenze di k in A. Poi scandisco l’array
dal primo elemento (in posizione 0) all’ultimo
(in posizione N-1) e incremento di 1 la variabile
count ogni volta che incontro una posizione i
in cui A[i] è uguale a k.
33
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- all’inizio count è 0- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
A[0] è uguale a 40? NO! Allora proseguo
80 40 39 12 40 60 4 92 40121
34
Esercizi sugli array
A
- step 2 i=1
- step 3 i=2
A[1] è uguale a 40? SI’! Allora count = count +1= 0 + 1 = 1
A
A[2] è uguale a 40? NO! Allora count rimane a 1
80 40 39 12 40 60 4 92 40121
80 40 39 12 40 60 4 92 40121
35
Esercizi sugli array
A
- step 4 i=3
- step 5 i=4
A[3] è uguale a 40? NO! Allora count rimane a 1
A
A[4] è uguale a 40? SI’! Allora count = count + 1= 1 + 1 = 2
80 40 39 12 40 60 4 92 40121
80 40 39 12 40 60 4 92 40121
36
Esercizi sugli array
A
- step 6 i=5
- step 7 i=6
A[5] è uguale a 40? NO! Allora count rimane a 2
A
A[6] è uguale a 40? NO! Allora count rimane a 2
80 40 39 12 40 60 4 92 40121
80 40 39 12 40 60 4 92 40121
37
Esercizi sugli array
A
- step 8 i=7
- step 9 i=8
A[7] è uguale a 40? NO! Allora count rimane a 2
A
A[8] è uguale a 40? SI’! Allora count = count + 1= 2 + 1 = 3
80 40 39 12 40 60 4 92 40121
80 40 39 12 40 60 4 92 40121
38
Esercizi sugli array
A
- step 10 i=9
A[9] è uguale a 40? NO! Allora count rimane a 3
80 40 39 12 40 60 4 92 40121
39
Esercizi sugli arraypublic class CountK {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i, k;int length, count;
length=10;i=0;k=40;count=0;while(i <= lentgth-1){
if(A[i]==k){count=count+1;
}i=i+1;
}
System.out.print(“Occorrenze=“+count);}
}
40
Esercizi sugli arrayNOTA BENE: il programma precedente vale
anche nel caso in cui A sia un array di caratteri
e al posto dell’intero k ci sia un carattere c.
La modifica del codice è contenuta nella
slide successiva.
41
Esercizi sugli arraypublic class CountChar {
public static void main(String arg[]) {char[] A={‘a’,’b’,’c’,’a’,’e’,’f’,’a’,’h’,’i’,’l’};int i;char c;int length, count;
length=10;i=0;c=‘a’;count=0;while(i <= lentgth-1){
if(A[i]==c){count=count+1;
}i=i+1;
}
System.out.print(“Occorrenze=“+count);}
}
42
Esercizi sugli arrayEsercizio 5
dato un array A di N interi e un intero k
verificare che tutti gli elementi sono < k
Esempio (N=10, k=40)
Risultato non tutti gli elementi
sono < 40
30 25 39 12 40 60 4 92 40121A
43
Esercizi sugli arrayAlgoritmo: dichiaro la variabile booleana ok che
inizializzo a true in quanto faccio l’ipotesi che
tutti gli elementi di A siano < k. Poi scandisco
l’array dal primo elemento (in posizione 0)
all’ultimo (in posizione N-1) e se trovo
una posizione i in cui A[i] >= k, allora la mia ipotesi
di partenza è falsa, quindi assegno alla variabile
ok il valore false e interrompo la scansione.
44
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- all’inizio ok è true- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
A[0] è < 40? SI’! Allora proseguo
30 25 39 12 40 60 4 92 40121
45
Esercizi sugli array
A
- step 2 i=1
- step 3 i=2
A[1] è < 40? SI’! Allora proseguo
A
A[3] è < 40? SI’! Allora proseguo
30 25 39 12 40 60 4 92 40121
30 25 39 12 40 60 4 92 40121
46
Esercizi sugli array
A
- step 4 i=3
- step 5 i=4
A[3] è < 40? SI’! Allora proseguo
A
A[4] è < 40? NO! Allora false a ok e interrompo
30 25 39 12 40 60 4 92 40121
30 25 39 12 40 60 4 92 40121
47
Esercizi sugli arraypublic class CheckLessThanK {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i, k;int length;boolean ok=true;
length=10;i=0;k=40;while(i <= lentgth-1 && ok == true){
if(A[i]>=k){ok=false;
}i=i+1;
}
System.out.print(“Sono tutti < k: “+ok);}
}
48
Esercizi sugli arrayNOTA BENE: il programma precedente può
essere esteso agli altri tipi di confronto:
- Verifica che tutti gli elementi sono uguali a k
il test dell’if diventa: A[i] != k
- Verifica che tutti gli elementi sono diversi da k
il test dell’if diventa: A[i] == k
- Verifica che tutti gli elementi sono > k
il test dell’if diventa: A[i] <= k
49
Esercizi sugli array...
- Verifica che tutti gli elementi sono <= k
il test dell’if diventa: A[i] > k
- Verifica che tutti gli elementi sono >= k
il test dell’if diventa: A[i] < k
50
Esercizi sugli arrayEsercizio 6
dato un array A di N interi scambiare il
l’elemento in posizione I (compresa tra 0
e N-1) con l’elemento in posizione j
(compresa tra 0 e N-1) diversa da i
51
Esercizi sugli arrayEsempio (N=10, i=0, j=9)
30 25 39 12 40 60 4 92 40121A
12125 39 12 40 60 4 92 40 30
52
Esercizi sugli arrayAlgoritmo: dichiaro la variabile intera help che
mi serve per conservare il valore di A[i] prima
di sovrascriverlo con A[j]. Poi assegno a A[i]
il valore di A[j] e a A[j] il valore di help a cui
era stato assegnato il valore originale di A[i].
53
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- step 1 help = A[0]- step 2 A[0] = A[9]
12125 39 12 40 60 4 92 40121
- step 3 A[9] = help
A 12125 39 12 40 60 4 92 40 30
54
Esercizi sugli arraypublic class Scambia {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i, j;int length, help;
length=10;i=0;j=9;help=A[i];A[i]=A[j];A[j]=help;
}}
55
Esercizi sugli arrayEsercizio 6
dato un array A di N invertire gli elementi
di A
Esempio (N=10)
30 25 39 12 40 60 4 92 40121A
12140 92 4 60 40 12 39 25 30A
56
Esercizi sugli arrayAlgoritmo: eseguo uno scambio dell’elemento in
posizione i e del suo simmetrico in posizione
N-i-1. Questo scambio lo faccio per tutte le
posizioni i che vanno da 0 a N/2-1
57
Esercizi sugli array
A
Esecuzione dell’algoritmo per l’array A di 10interi dell’esempio precedente:
- step 1 i=0 (i è l’indice che scandisce gli elementi di A)
scambio A[0] con A[9]
30 25 39 12 40 60 4 92 40121
12125 39 12 40 60 4 92 40 30
58
Esercizi sugli array
A
- step 2 i=1
scambio A[1] con A[8]
12125 39 12 40 60 4 92 40 30
12140 39 12 40 60 4 92 25 30
59
Esercizi sugli array
A
- step 3 i=2
scambio A[2] con A[7]
12140 39 12 40 60 4 92 25 30
12140 92 12 40 60 4 39 25 30
60
Esercizi sugli array
A
- step 4 i=3
scambio A[3] con A[6]
12140 92 12 40 60 4 39 25 30
12140 92 4 40 60 12 39 25 30
61
Esercizi sugli array
A
- step 5 i=4 (N/2-1=10/2-1=4)
scambio A[4] con A[5]
12140 92 4 40 60 12 39 25 30
12140 92 4 60 40 12 39 25 30
Risultato finale
62
Esercizi sugli arraypublic class InvertArray {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i;int length;int help;
length=10;i=0;while(i <= lentgth/2-1){
help=A[i];A[i]=A[j];A[j]=help;i=i+1;
}}
}
63
Esercizi sugli arrayNOTA BENE: il programma precedente vale
anche nel caso in cui N sia dispari. Le posizioni
da scambiare sono sempre I e N-I-1 con
I che va da 0 a N/2-1, in quanto esiste un
elemento centrale in posizione N/2 che rimane
fisso nella stessa posizione.
64
Esercizi sugli arrayEsercizio 7
dato un array A di N calcolare per ogni A[i]
la somma dei primi A[i] interi (da 1 a A[i])
Esempio (N=10)
30 25 39 12 40 60 4 92 40121A
per i=0, calcolo 1+2+3+…+30per i=1, calcolo 1+2+3+…+25...
65
Esercizi sugli arrayAlgoritmo: eseguo una scansione di A per i che va
da 0 a N-1 e per ogni A[i] eseguo un ciclo più
interno che calcola la somma 1+2+3+…A[i].
66
Esercizi sugli arraypublic class InvertArray {
public static void main(String arg[]) {int[] A={4,15,20,21,40,6,7,9,10,1};int i, j;int length;int somma;
length=10;i=0;while(i <= lentgth-1){
j=1;somma=0;while(j<=A[i]){
somma=somma+j;j=j+1
}System.out.println(“Somma=“+somma);i=i+1;
}}
}