Programmazione Mod A - Cap 6 - prof. Burattini
1
Programmazione Mod A - Cap 6 - prof. Burattini
2
Variabili strutturate
Le variabili dei tipi predefiniti del C++ float, double, int, e boolean prendono il nome di variabili scalari.
Una variabile è invece strutturata se è composta di altre variabili che a loro volta possono essere variabili strutturate o scalari, queste a loro volta sono comunemente chiamate elementi della variabile strutturata.
Ogni variabile strutturata deve possedere un meccanismo o modalità di accesso alle variabili che la compongono in modo che sia possibile riferirsi ad esse ed eventualmente modificarle.
Programmazione Mod A - Cap 6 - prof. Burattini
3
Variabili strutturate
L’array monodimensionale rappresenta il primo tipo di variabile strutturata.
Le sue componenti sono variabili tutte dello stesso tipo ed il meccanismo di accesso consiste di una espressione di tipo intero che viene valutato a run time e sommato all’indirizzo base dell’array per fornire direttamente l’indirizzo della componente voluta (meccanismo di accesso diretto).
In generale un array pur essendo sempre formato da variabili tutte dello stesso tipo può accedere alle sue componenti attraverso un numero finito di espressioni intere.
Si parla in tal caso di array multidimensionali. Particolarmente utili sono gli array bidimensionali altrimenti detti matrici.
Programmazione Mod A - Cap 6 - prof. Burattini
4
Array monodimensionali: ordinamento (sort)
Supponiamo che Vet sia una variabile dichiarata come int Vet[10];
essa ha un indice compreso tra 0 e 9.
Un array monodimensionale di interi è ordinato in ordine crescente se all’aumentare dell’indice aumenta anche il valore dell’elemento; è ordinato in ordine decrescente se all’aumentare dell’indice il valore dell’elemento diminuisce; per esempio dei tre vettori
A=[2, 4, 5, 7, 7, 9, 12, 15] B=[2, 5, 8, 3, 7, 11] C=[15, 9, 8, 6, 5, 5, 3, 1]
A è ordinato in ordine crescente, C lo è in ordine decrescente, B non è ordinato.
Programmazione Mod A - Cap 6 - prof. Burattini
5
Tenendo presente che un vettore di dimensione 1 è sempre ordinato, per un vettore di dimensione N>1 possiamo dare le seguenti definizioni:
Gli elementi di un vettore sono ordinati in ordine crescente se e solo se per ogni indice i compreso tra 0 e N -2 si ha Vettore[ i ]<=Vettore[i+1].
Gli elementi del vettore sono ordinati in ordine decrescente se e solo se per ogni indice i compreso tra 0 e N -2 si ha Vettore[ i ]>=Vettore [i+1].
Le stesse definizioni possono valere sia per i numeri reali (float o double) che per le stringhe.
Programmazione Mod A - Cap 6 - prof. Burattini
6
L’ordinamento per le stringhe è, di solito, quello lessicografico (l’ordine alfabetico) che rispecchia l’ordine ASCII; in questo caso è necessario anche tener presente che tutte le lettere maiuscole precedono tutte quelle minuscole per cui una parola che inizia con lettera maiuscola precede le altre:
andare precede correre ma andare segue Correre
Per questo motivo prima di ordinare lessicograficamente un insieme di parole che possono iniziare anche con una lettera maiuscola occorre convertire tale carattere iniziale in minuscolo prima di eseguire il confronto.
Programmazione Mod A - Cap 6 - prof. Burattini
7
ORDINAMENTO = SORTING
10
19
9
30
29
12
18
1
2
3
4
5
6
7
19
30
10
29
12
9
18
Programmazione Mod A - Cap 6 - prof. Burattini
8
Supponiamo di voler ordinare in modo crescente gli elementi dell’array vet; a questo scopo definiamo la seguente procedura:
void Ordina (int[] vet, int N) {IN : Vettore di interi di dimensione N non ordinatoOUT : Vettore di interi ordinato in modo crescente }Un possibile modo di risolvere il problema dell’ordinamento è pensare di dover
iterare la seguente situazione:siamo in uno stato in cui nel nostro vettore si trovano già nel loro posto definitivo i primi k elementi, che quindi nel vettore occupano le posizioni da zero a k-1. Operiamo in modo da portare nella posizione k l’elemento giusto
24 36 …………… 87 125 ……………. 120 156
0 1 ………… k-1 k ………………… N-2 N-1
Tutti ordinati Tutti di valore maggiore agli ordinati
Programmazione Mod A - Cap 6 - prof. Burattini
9
Gli elementi compresi tra 0 e k-1 sono non solo ordinati in ordine crescente, ma sono anche inseriti nella loro posizione definitiva; gli elementi da k in poi, anche se sono disordinati, sono comunque maggiori di quelli compresi tra 0 e k-1. Possiamo affermare in definitiva che sono ordinati i primi k+1 elementi (compresi tra 0 e k).
Scriviamo il ciclo:
for (k=0; k<N-1;k++) porta l’elemento giusto nella posizione k
k è inizializzato a 0 dunque porta l’elemento giusto nella posizione k è banalmente soddisfatto poiché un solo elemento non può essere disordinato (anche se in generale non sarà l’elemento più piccolo).
Inoltre esso è ovviamente soddisfatto per definizione in uscita da ogni passo. Dopo l’ultimo passo k è diventato N-1 il che significa che l’intero vettore è ordinato allorché si esce dal ciclo.
0 1 ………… k-1 k ………………… N-2 N-1
24 36 …………… 87 125 ……………. 120 156
Programmazione Mod A - Cap 6 - prof. Burattini
10
Per “portare l’elemento giusto nella posizione k” occorrerà in
qualche modo scorrere la seconda parte dell’array , quella
ancora disordinanta da k in poi, dunque occorrerà un altro
loop.
24 36 …………… 87 125 ……………. 120 156
0 1 ………… k-1 k ………………… N-2 N-1
Tutti ordinati Tutti di valore maggiore agli ordinati
Programmazione Mod A - Cap 6 - prof. Burattini
11
BUBBLE SORT La tecnica adoperata nel bubble sort per portare in posizione k il più piccolo
degli elementi compresi tra gli indici k..N-1, consiste nello scambiare di posto tutte le coppie adiacenti ‘disordinate’ partendo dall’indice N-2 fino ad arrivare all’indice k
for(k=0; k<N-1; k++) Ciclo esterno: Incrementa k solo quando tutti gli elementi da 0 a k sono ordinati in via
definitiva
for (j=N-2; j>=k; j--) Ciclo Interno: cerca il più piccolo dei valori di vet[j] compresi tra N-2 e k
if (vet[j] > vet[j+1]) allora scambia (vet[j],vet[j+1]);
Al termine del ciclo interno sarà verificata la condizione: vet[k] è il più piccolo tra tutti gli elementi compresi tra k ed N-1.
Inoltre altri elementi si saranno avvicinati alla loro posizione definitiva.
Programmazione Mod A - Cap 6 - prof. Burattini
12
k=0
10199
30291218
10199
30291218
1019930122918
10199
12302918
10199
12302918
109
1912302918
9101912302918
k=1
9101912302918
9101912301829
9101912183029
9101912183029
9101219183029
9101219183029
9101219183029
9101219182930
9101219182930
9101219182930
9101218192930
9101219182930
9101219182930
9101219182930
9101218192930
k=2 k=3
j=N-2
Programmazione Mod A - Cap 6 - prof. Burattini
13
k=4
9101218192930
9101218192930
9101218192930
k=5
9101218192930
9101218192930
9101218192930
k=6
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
Programmazione Mod A - Cap 6 - prof. Burattini
14
L’algoritmo è composto da due cicli nidificati.
Applichiamolo al seguente esempio:
indici 0, 1, 2, 3, 4vet = [6, 8, 11, 5, 7]CICLO ESTERNO k=0CICLO INTERNO j=3 vet[3] > vet[4] : NO lascia il vettore invariato j=2 vet[2] > vet[3] : SI scambia gli elementi; il vettore diventa: [6, 8, 5,11, 7] j=1 vet[1] > vet[2] : SI scambia gli elementi; il vettore diventa: [6, 5 ,8, 11, 7] j=0 vet[0] > vet[1] : SI scambia gli elementi; il vettore diventa: [5, 6 ,8, 11, 7]
CICLO ESTERNO k=1CICLO INTERNO j=3 vet[3] > vet[4] : SI scambia gli elementi; il vettore diventa: [5, 6 ,8, 7, 11 ] j=2 vet[2] > vet[3] : SI scambia gli elementi; il vettore diventa [5, 6, 7, 8, 11] j=1 vet[1] > vet[2] : NO lascia il vettore invariato
Notiamo che in questo caso non solo i primi due elementi sono già nella loro posizione definitiva, come richiesto, ma anche gli altri. Nelle successive iterazioni non ci saranno altri scambi.
Programmazione Mod A - Cap 6 - prof. Burattini
15
ESERCIZI1. Scrivere una procedura Bubble-Sort.Utilizzando la libreria sui vettori, scrivere un programma che provi
l’algoritmo.Il main del programma potrebbe essere il seguente:
dichiara un vettore v di interi con massimo 100 elementi;inserisce la dimensione N del vettore in input;Richiama la procedura di riempimento dei primi N-1 posti del vettorerichiama la procedura di ordinamento;richiama la procedura di stampa.
Velocizzare il programma precedente introducendo un controllo nel loop interno per registrare se è avvenuto almeno uno scambio; se non c’è stato nessuno scambio significa che il vettore è già ordinato ed il loop esterno può essere interrotto.
2. Adoperare la tecnica del bubble sort per trasformare il vettore in uno contenente prima i numeri pari seguiti da tutti i numeri dispari.
3. Trasformare il vettore in uno contenente all’inizio tutti gli zeri, seguiti da tutti i negativi e terminante con i numeri positivi.
Programmazione Mod A - Cap 6 - prof. Burattini
16
SELECTION SORT
Usa lo stesso ciclo esterno del bubble sort, mentre per portare l’elemento giusto al posto k determina dapprima l’indice dell’elemento più piccolo tra i numeri di indice da k a N-1 ed in uscita dal ciclo lo scambia con l’elemento in posizione k
for (k=0; k<N-1;k++) { // Ciclo Esterno
// PRE: gli elementi da 0 a k-1 sono nella loro posizione definitiva
IndiceMinimo k ; // // Ciclo Interno
for (j=k+1; j< N ; j++) // se l’elemento di ordine j è più piccolo di quello di
if vet[j] < vet[IndiceMinimo] // ordine IndiceMinimo, allora IndiceMinimo di
IndiceMinimo j; // il j-esimo elemento. Alla fine del ciclo si scambia
Scambia(vet[k], vet[IndiceMinimo];// l’elemento di ordine IndiceMinimo con quello di ordine
// k in modo che sia verificata la postcondizione: //POST: vet[k] è il più piccolo di tutti gli elementi compresi tra k ed N e dunque tutti
gli elementi da 0 a k sono nella loro posizione definitiva.
Programmazione Mod A - Cap 6 - prof. Burattini
17
k=0
k=1
k=2
SELECTION SORT
10199
30291218
3
110199
30291218
3
110199
30291218
3
110199
30291218
3
110199
30291218
3
1
9191030291218
3
29191030291218
3
29191030291218
3
29191030291218
3
29191030291218
3
2
9101930291218
3
3
10199
30291218
1
1
9101930291218
3
3
9101930291218
6
3
9101930291218
6
3
Programmazione Mod A - Cap 6 - prof. Burattini
18
k=3
k=4
k=5 SELECTION SORT
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
9101230291918
5
4
9101230291918
6
4
9101230291918
7
4
9101218302919 6
5
9101218293019
7
5
9101218193029
7
6
9101218192930
7
Programmazione Mod A - Cap 6 - prof. Burattini
19
ESERCIZIO
Scrivere una procedura per l’algoritmo di Selection-Sort.
In seguito, utilizzando la libreria sui vettori, scrivere un programma che provi l’algoritmo.
Programmazione Mod A - Cap 6 - prof. Burattini
20
Insertion Sort
Questo algoritmo di ordinamento è il più intuitivo dei tre presentati essendo molto simile al modo in cui operiamo manualmente.
E’ l’algoritmo più intuitivo. Se ad esempio si ha un mazzo di carte non ordinato possiamo ordinarlo scorrendo le carte una alla volta e inserendo
ogni carta immediatamente dopo la carta più piccola tra quelle che la precedono.
Osserviamo però che in questo caso le k schede già ordinate non sono ancora al loro posto definitivo, come accadeva nei due casi precedenti.
Solo al termine della procedura esse acquisteranno tutte la loro giusta posizione.
Programmazione Mod A - Cap 6 - prof. Burattini
21
AlgoritmoSupponiamo di essere al passo j. Confrontiamo il valore dell’elemento di vet[j] con i suoi predecessori. Se chi lo precede ha un valore più elevato lo spostiamo di un posto in avanti. Se incontriamo nella posizione i un valore più basso allora poniamo in vet[i+1] vet[j].
vet[1] UltimoElemento
Tutti ordinati Non ancora ordinati
6311 61 65
Inserisci tra questi due elementi
vet[PostoSuccessivo]
33
Programmazione Mod A - Cap 6 - prof. Burattini
22
Poiché il primo elemento è sicuramente parzialmente ordinato, il for esterno può iniziare da 1. Al termine si uscirà dal loop allorché tutti gli N elementi
sono parzialmente (e quindi definitivamente) ordinati. Prima che inizi il ciclo interno conserviamo il valore di vet[k] in vet[N], il posto k ora è ‘libero’ e può essere sfruttato per spostare verso destra ogni elemento già parzialmente ordinato, a partire dall’ultimo che ha indice k-1, che risulti maggiore di vet[N].
In definitiva avremo:for ( k=1;k<= N-1; k++) vet[N] vet[k] j k - 1 while ( j>=0)and (vet[j]>vet[N]) vet[j+1] vet[j] jj-1 vet[j+1] vet[N]
In uscita dal loop interno sappiamo che in vet[j] si trova il più grande dei numeri più piccoli di vet[0] e dunque possiamo terminare il loop interno sistemando vet[N] nella posizione libera j+1. Naturalmente è possibile adoperare questo algoritmo solo se N non rappresenta la dimensione fisica dell’array a run time.
Programmazione Mod A - Cap 6 - prof. Burattini
23
k
19 9 30 29 12 18 1910
[0] [1] [2] [3] [4] [5] [6] [7]
2
3 19 9 30 29 12 18 910
[0] [1] [2] [3] [4] [5] [6] [7]
10 9 19 30 29 12 18 9
9 10 19 30 29 12 18 9
410 19 30 29 12 118 309
[0] [1] [2] [3] [4] [5] [6] [7]
510 19 30 29 12 18 299
[0] [1] [2] [3] [4] [5] [6] [7]
9 10 19 29 30 12 18 29
j
j
j
j
Programmazione Mod A - Cap 6 - prof. Burattini
24
610 19 29 30 12 18 129
[0] [1] [2] [3] [4] [5] [6] [7]
9 10 19 29 12 30 18 12
9 10 19 12 29 30 18 12
9 10 12 19 29 30 18 12
7
[0] [1] [2] [3] [4] [5] [6] [7]
9 10 12 19 29 30 18 18
9 10 12 19 29 18 30 18
9 10 12 19 18 29 30 18
9 10 12 18 19 29 30 18
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
j
j
k
eserbuble
Programmazione Mod A - Cap 6 - prof. Burattini
25
Se dobbiamo leggere da un file o da tastiera una successione di elementi che deve essere ordinata, potremmo dapprima inserirli in un array e poi ordinarli, ma in genere è preferibile eseguire le due operazioni contemporaneamente adoperando la tecnica dell’insertion sort. Si ottiene il seguente algoritmo:
int main () { char ch; int a[100], elemento,j,N; cout<<" Fine inserimento= 0"<<endl; cout<<" Elemento "; cin>>elemento; a[0]=elemento; N=-1; while (elemento!=0) {
cout<<" Elemento "; cin>>elemento; N=N+1; j=N; while ((j>=0) && (a[j]>elemento)) { a[j+1]=a[j]; j=j-1; a[j+1]=elemento; } }StampaVettore(a, N+1,'a');system("pause"); return 0; }
esersorttast
Programmazione Mod A - Cap 6 - prof. Burattini
26
Al termina del loop N indica il numero di elementi letti.
Naturalmente questo algoritmo funziona se il numero di elementi da leggere è inferiore alla dimensione fisica del vettore, altrimenti occorrerà un opportuno test su N prima di entrare nel loop interno.
I tre algoritmi di ordinamento illustrati prevedono un numero di operazioni,
scambi o confronti, all’incirca proporzionale al quadrato del numero N di elementi da ordinare.
Dunque per ordinare un vettore di mille elementi occorrono circa un milione di operazioni.
Programmazione Mod A - Cap 6 - prof. Burattini
27
ESERCIZI
1. Scrivere una procedura per l’algoritmo di Insertion-Sort. In seguito, utilizzando la libreria sui vettori, scrivere un driver per l’algoritmo.
2. Leggere ed ordinare una sequenza di interi letti da tastiera (uno zero indicherà che la sequenza è terminata).
Programmazione Mod A - Cap 6 - prof. Burattini
28
Ricerca lineare
Un problema molto comune è la ricerca di un elemento in un insieme. Nel caso di una variabile array, l’algoritmo di ricerca deve dire se un certo valore appartiene o no all’array.
A questo scopo, detto A l’array ed x l’elemento da cercare, si esaminano sistematicamente tutti gli elementi dell’array per trovare un valore i dell’indice che soddisfa la condizione A[i] =x.
Se, invece, x non appartiene all’array si restituisce, ad esempio, il valore -1.Si tratta dunque di un tipico algoritmo “esiste”. L’algoritmo di ricerca lineare è :
i0trovatofalsewhile NOT trovato AND i < N if A[i]=x trovatotrue else i=i+1if trovato indice=ielse indice=-1
Programmazione Mod A - Cap 6 - prof. Burattini
29
Possiamo eliminare la variabile sentinella trovato in questo modo: Scorriamo il vettore con un ciclo while controllato da una espressione booleana
che termina il ciclo o quando A[i] = x, oppure quando arriva alla fine del vettore (si noti che questo si ottiene con un AND!!)
ESERCIZIO
Scrivere una function che implementi questo algoritmo qualunque sia il tipo di numero contenuto nell’array (int, float, double).
i0while A[i]<>x AND i < =N i=i+1 ;
if A[i]=x indice=ielse indice=-1
Programmazione Mod A - Cap 6 - prof. Burattini
30
L’algoritmo di ricerca lineare può essere migliorato se si hanno delle informazioni opportune sul tipo di array da esaminare.
Ad esempio l’algoritmo di ricerca potrebbe essere migliorato se è noto che il vettore pur essendo disordinato presenta solo numeri negativi fino alla posizione k seguiti da valori non negativi . Infatti in questo caso se il numero da cercare non è negativo possiamo scartare i primi k+1 elementi.
In altri termini ogni informazione che ci permette di scartare potenziali candidati è utile per migliorare la ricerca.
Ricerca binaria
Programmazione Mod A - Cap 6 - prof. Burattini
31
Cosa si può fare se il nostro array è ordinato? Si potrebbe
adoperare una ricerca lineare modificata nel senso che o
l’algoritmo si arresta non appena trova l’elemento in questione
o si interrompe dando in uscita –1 non appena incontra un
numero maggiore.
Si avrebbe un certo miglioramento in media, ma nel caso peggiore
occorre comunque esaminare tutto l’array.
i0while A[i]<x AND i < =N i=i+1 ;
if A[i]=x indice=ielse indice=-1
Programmazione Mod A - Cap 6 - prof. Burattini
32
Che informazione otteniamo se confrontiamo il nostro x con un generico elemento di indice k?
Se x=A[k] la ricerca è finita, se è maggiore allora possiamo scartare tutti i candidati da 0 fino a k, altrimenti scartiamo tutti quelli da k in poi.
Conviene scegliere k =n/2, in tal modo un confronto fallito dimezza il numero di possibili candidati. Iterando questo procedimento con cui dimezziamo l’indice e confrontiamo i valori, ad ogni fallimento i due estremi dell’intervallo di ricerca che contiene i candidati ancora non scartati si avvicinano sempre di più.
L’algoritmo terminerà in una delle seguenti situazioni :a) uno dei confronti ha successo.b) gli estremi dell’intervallo di ricerca danno un intervallo vuoto. Nel qual caso l’elemento non è nell’array.
Programmazione Mod A - Cap 6 - prof. Burattini
33
Lo pseudocodice dell’algoritmo viene proposto di seguito.
basso 0
Alto N-1
i -1
while (basso<=Alto)and (i=-1)
Medio = (basso+Alto) / 2
if x = vet[Medio]
i=Medio
else
if x>vet[Medio]
basso = Medio+1
else
Alto =Medio-1
Programmazione Mod A - Cap 6 - prof. Burattini
34
Vogliamo sapere se 21 appartiene alla seguente lista
21 29 30 35
[4] [5] [6] [7]
2
21 29
[4] [5]
3
21
[4]
4
vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ] di dimensione 8.
1 10 15 18 21 29 30 35[1] [2] [3] [4] [5] [6] [7]
9[0]
N
N/2
N/4
1
N/20
N/21
N/22
N/2k
k=log2N
N O(N) LOG(N)1.000 1.000 9,97
1.000.000 1.000.000 19,93100.000.000 100.000.000 26,58
Programmazione Mod A - Cap 6 - prof. Burattini
35
Utilizzando l’algoritmo , vogliamo verificare se 21 appartiene al vettore di interi:vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ] di dimensione 8.
Nel nostro esempio x=21, basso=0 ed Alto=7.
Inizialmente Medio=(0+7)/2=3, per cui, essendo vet[3]=18, si ha x > vet[medio] è veroanalizziamo il sub-array superiore che va dall’indice 4 fino ad Alto; per questo scopo basta porre basso=Medio+1=4.
Abbiamo basso=4, Alto =7 Medio=(4+7)/2=5 e vet[Medio]=29. Dal confronto x > vet[medio] falsoscaturisce che dobbiamo analizzare il subarray inferiore (da 5 a 4), per cui Alto=Medio-
1=6; poiché basso=4, Alto=6 e Medio=(4+6)/2=5 si ottiene ancorax > vet[medio] falso
per cui vale Alto=Medio-1=5, basso=4, Medio=(4+5)/2=4 ed infine vet[Medio]=19 e l’algoritmo
restituisce l’indice del valore cercato, i=4.
basso 0Alto N-1i -1while (basso<=Alto)and (i=-1) Medio = (basso+Alto) / 2 if x = vet[Medio] i=Medio else
if x>vet[Medio] basso = Medio+1 else Alto =Medio-1
0 1 2 3 4 5 6 7
Programmazione Mod A - Cap 6 - prof. Burattini
36
vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ]
Analizziamo la ricerca con x=17. Scrivendo i vari passaggi in maniera più compatta, otteniamo
basso Alto Medio x =vet[Medio] x > vet[Medio] 0 7 3 falso falso 0 2 1 falso vero 1 2 2 falso vero 2 2 2 falso vero 3 2 poiché basso è maggiore di Alto non esiste più alcun intervallo di
ricerca.
0 1 2 3 4 5 6 7
Programmazione Mod A - Cap 6 - prof. Burattini
37
Se applicato ad un array ordinato in cui sono possibili ripetizioni l’algoritmo termina con successo dando uno dei possibili indici per cui l’uguaglianza risulta verificata. E’ possibile trovare il più piccolo indice per cui l’uguaglianza è verificata eliminando il test su i.
Il loop si riduce a:
basso 0Alto N-1while (basso<=Alto) Medio (basso+Alto) / 2 if x > vet[Medio] basso Medio+1 else
Alto Medio-1
Osserviamo che allorché x<= vet[Medio] noi modifichiamo Alto
Programmazione Mod A - Cap 6 - prof. Burattini
38
Nel caso sia vera la condizione x > vet[Medio] allora possiamo affermare che
la ricerca va effettuata nel sub-array superiore e che in uscita dal loop si avrà:
x > vet[basso-1] (poiché basso-1=Medio in uscita)
inoltre tale condizione resta vera anche quando basso non viene modificato,visto che l’elemento basso-1 è stato escluso dai possibili candidati
Se, invece, è vera la condizionex <= vet[Medio]
allora la ricerca va effettuata nel sub-array inferiore; inoltre, risulta verificatala condizione
x <= vet[Alto + 1] (poiché Alto+1=Medio in uscita), condizione ovviamente soddisfatta se Alto non viene alterato. Dunquequalunque strada si prende nel loop è sempre vero che in uscita si ha:
Vet[basso-1] < x <= vet[Alto + 1]Il ciclo termina con la negazione di (basso <= Alto), cioè con
basso > Alto
Programmazione Mod A - Cap 6 - prof. Burattini
39
Analizzando gli esempi, possiamo verificare che all’uscita si habasso = Alto + 1
Se in un certo punto del programma risulta che vet[Medio] coincide col valorecercato x; nell’algoritmo precedente si esce dal ciclo. In questo caso l’algoritmocontinua e, poiché siamo nella situazione che segue l’else, avremo
Alto= Medio –1;da cui
Medio = Alto + 1
Quindi il valore cercato è conservato nell’indice Alto + 1. Poiché l’intervallo con
cui proseguire la ricerca è [basso, alto], se gli elementi sono tutti distinti, lericerche successive non cambieranno mai il valore di Alto, essendo tali elementipiù piccoli dell’elemento cercato; alla fine il ciclo terminerà con l’uguaglianza
basso = Alto + 1e quindi l’elemento cercato sarà posizionato nell’indice contenuto nellavariabile basso.
Programmazione Mod A - Cap 6 - prof. Burattini
40
Nel caso in cui vi siano più elementi uguali, l’algoritmo troverà altri indici compresi nell’intervallo [basso, alto] che contengono il valore x cercato.
Se applichiamo ancora il ragionamento precedente è chiaro che l’algoritmo determinerà il primo indice in cui appare x.
Cosa accade nel caso in cui l’elemento cercato x non esiste nell’array?
Poiché l’algoritmo termina in ogni caso con
basso = Alto +1
dobbiamo distinguere il caso in cui l’indice basso<=N-1 dal caso particolare incui basso=N che si verifica se l’elemento cercato è più grande di tutti glielementi dell’array.
Occorre quindi aggiungere al termine del loop il seguente test:
If (basso=N) or not(vett[basso]=x)Indice= -1
else indice = Basso
Programmazione Mod A - Cap 6 - prof. Burattini
41
Ecco un programma che utilizza le due ricerche binarie sotto la forma di functions; esse restituiscono un intero che rappresenta l’indice dell’elemento cercato. La function RicercaBinB rappresenta la ricerca con la variabile booleana, RicercaBin invece non utilizza tale variabile.
#include <iostream>#include <cstdlib>#include "InsertArray.h"using namespace std;
int RicercaBinB (int[], int, int, int);int RicercaBin (int[], int, int, int);void ordinaB(int[], int n); void scambia (int&, int&);
int main () { char ch; int a[100], n, cerca; cout<<" Lunghezza vettore="; cin>>n; LeggeVettore ( a, n, 'a'); ordinaB (a,n); StampaVettore (a, n,'a');
do {cout<<"Valore da cercare="; cin>>cerca;if ((RicercaBinB(a,0,n,cerca)>=0)||(RicercaBin(a,0,n,cerca)>=0)) { cout<<"Il valore "<<cerca<<" ha la posizione="<<RicercaBinB(a,0,n,cerca)<<endl; cout<<"Senza Flag, il valore "<<cerca<<" ha la posizione="<<RicercaBin(a,0,n,cerca)<<endl; }else cout<<"Il valore "<<cerca<<" non e' nel vettore"<<endl; cout<<" f per terminare "; cin>>ch; } while (ch!='f'); return 0;
}
void scambia (int &x1, int &x2) { int s; s=x1; x1=x2; x2=s;}
Programmazione Mod A - Cap 6 - prof. Burattini
42
void ordinaB ( int vet[], int N) { int j, k; for (k=0; k<N-1; k++) for (j=k+1; j<N; j++) if (vet[k] > vet[j]) scambia (vet[k],vet[j]); }
int RicercaBinB ( int vet[], int basso, int alto, int x) { int medio,i=-1; while ((basso<=alto) && i==-1) { medio=(basso+alto)/2; if (vet[medio]==x) i=medio ; else if (vet[medio]<x) basso=medio+1; else alto=medio-1; } return i;}
int RicercaBin ( int vet[], int basso, int alto, int x) { int medio, Ntot=alto; while (basso<=alto) { medio=(basso+alto)/2; if (vet[medio]<x) basso=medio+1; else alto=medio-1; } if (( basso==Ntot) || (vet[basso]!=x)) return -1; else return basso; }
Programmazione Mod A - Cap 6 - prof. Burattini
43
s [i] Restituisce il carattere di indice i (se i>= della lunghezza della stringa, il risultato è indefinito
s.size ( ) Restituisce la lunghezza di ss.empty ( ) Restituisce true se s è vuota, false altrimentis.find( c ) Restituisce l’indice della prima occorrenza di cs.find (str) Restituisce l’indice del primo carattere della prima
occorrenza di strs.rfind ( c ) Come s.find( c ), solo che la ricerca ha inizio dalla fines.rfind (str) Come s.find(str), solo che la ricerca ha inizio dalla fines.replace (i, n, str) Sostituisce n caratteri, a partire dalla posizione i, con la
stringa str.s.insert (i, str) Inserisce la stringa str a partire dalla posizione is.erase (i, n) Elimina n caratteri a partire dalla posizione is.resize (n,car) Fissa a n la lunghezza di s; gli altri caratteri fino alla
lunghezza della stringa sono riempiti con il carattere cars.c_str ( ) Restituisce la stringa corrispondente in stile Cs.substr (i,n) Restituisce una stringa che parte dalla posizione i ed ha
lunghezza n; per esempio se s=”ciao mamma”, s.substr(5,5) restituisce la stringa “mamma”
Programmazione Mod A - Cap 6 - prof. Burattini
44
#include <iostream>#include <cstdlib>#include <string>using namespace std;// PROTOTIPIvoid leggi_dati(char[]);void cerca_kple(string,int);bool controlla(string,string,int);// MAINint main () { string s; char rigo[120]; int k; leggi_dati(rigo); s=rigo; cout<<"\n Dammi k "; cin>>k; cerca_kple(s,k); system("pause"); }
// DEFINIZIONIvoid leggi_dati(char r1[]) { cout<<" Dammi la stringa "; cin>>r1; } bool controlla(string sx, string sy, int k1) { int j=0; bool uguale=false; while ((j<=k1) && (sx[j]==sy[j])) j++; if ((j-1)==k1) uguale=true; return uguale; }void cerca_kple(string s1, int k1) { int j=0; while (j<(s1.size()-k1-1)) { if (controlla(s1.substr(j,k1),s1.substr(j+k1,k1),k1)==true) cout<<" trovato "<<s1.substr(j,k1)<<endl; j=j+k1; } }
/* DATA UNA STRINGA E UN NUMERO K MOSTRARE A VIDEO TUTTE LE K-PLE UGUALI ALLA K-PLA SUCCESSIVA . ES. K=3 A=SBFGBJGBJNOGDFRDFROUTPUT GBJ DFR*/
Programmazione Mod A - Cap 6 - prof. Burattini
45
EsercizioData una stringa S, eliminare la sottostringa centrale di dimensioni k. Se la stringa rimanente è strettamente palindroma allora restituire la stringa vuota.Esempio:S=abcdfghtrdcba , k=5eliminata fghtr resta abcddcba che è palindroma.
Pseudo codiceLeggi s e kControlla coerenza s e kCancella da s la sottostringa centrale di ampiezza kControlla se la stringa rimanente è palindroma(s)Stampa il risultato
Palindroma(s)lung=s.size()while lung>0 AND s[0]=s[lung-1] { s.erase (lung-1, 1)
s-erase (0,1)lung=s.size()
}return (s.empty())
Programmazione Mod A - Cap 6 - prof. Burattini
46
/* Data una stringa S di lunghezza pari (dispari), eliminare la sottostringa centrale di dimensioni k con k pari (dispari). Se la stringa rimanente è strettamente palindroma allora restituire la stringa vuota.*/#include <iostream>#include <cstdlib>#include <string>using namespace std;// PROTOTIPIvoid leggi_dati(char[]);bool palindroma(string);// MAINint main () { int k; string s; char rigo[120]; leggi_dati(rigo); s=rigo; cout<<"\n Dammi k "; cin>>k; if ((s.size()%2)!= (k%2)) { cout<<" Lunghezza stringa e
valore di k non coerenti"<<endl; return -1; } s.erase((s.size()-k)/2,k); if (palindroma(s)) cout<<" La stringa e‘ palindroma "<<endl; else cout<<" La stringa non e‘ palindroma "<<endl;}
// DEFINIZIONI
void leggi_dati(char r1[]) { cout<<" Dammi la stringa "; cin>>r1; } bool palindroma(string s1) { int lung; lung=s1.size(); while (((lung>0)) && (s1[0]==s1[lung-1])) { s1.erase (lung-1, 1); s1.erase (0, 1); lung=s1.size(); } return (s1.empty()); }
eserSTRING2c
Programmazione Mod A - Cap 6 - prof. Burattini
47
Array bidimensionali
Un array multidimensionale è un array definito in modo tale che per poter accedere ad un suo elemento sono necessari più indici.
In particolare, un array definito in termini di due indici è detto array bidimensionale o matrice.
Esempi di dichiarazione di una matrice:
int C[4][3]; // dichiara una matrice di interi con quattro righe e tre colonne
float f[M][N]; // dichiara una matrice di reali con M righe ed N colonne: a runtime i valori di M ed N devono essere noti
int A[ ][3]= { 1,2,3,4,5,6,7,8,9 }; // specifica una matrice con 9 elementi: il compilatore ne deduce che la matrice ha anche 3
righe, quindi come se la dichiarazione fosse A[3][3]
char b[2][3]={{‘a’, ’b’, ’c’},{‘d’, ‘e’, ‘f’}}
Programmazione Mod A - Cap 6 - prof. Burattini
48
L’array bidimensionale C può essere rappresentato nella seguente forma tabellare:
C[3][2]C[3][1]C[3][0]Riga 3
C[2][2]C[2][1]C[2][0]Riga 2
C[1][2]C[1][1]C[1][0]Riga 1
C[0][2]C[0][1]C[0][0]Riga 0
righe
Colonna 2Colonna 1Colonna 0 colonne
Programmazione Mod A - Cap 6 - prof. Burattini
49
Ogni elemento viene scritto utilizzando due coppie di parentesi quadre: la prima coppia di parentesi contiene l’indice della riga, la seconda coppia l’indice della colonna. Se inseriamo nella matrice C dei valori interi otteniamo la seguente rappresentazione:
In questo caso abbiamo, per esempio
C[0][0]=3 ; C[2][1]=0 ; C[3][2]=1.
-619Riga 3
620Riga 2
-184Riga 1
7-53Riga 0
righe
Colonna 2Colonna 1Colonna 0 colonne
Programmazione Mod A - Cap 6 - prof. Burattini
50
Esempio.
Una classe composta da 32 studenti ha sostenuto durante l’anno 5 compiti in classe. Supponiamo di voler scrivere un programma che calcoli la media dei voti ottenuti dagli studenti .
Si potrebbe allora dichiarare una matrice del tipo: int A[31][7] in cui inserire i
voti riportati da ciascun studente in ciascun compito. Siccome però in una classe ci potrebbero essere più studenti o i compiti potrebbero essere di più, conviene adoperare per maggior generalità la seguente dichiarazione:
int const R=40; int const C=8; int A[R][C]; int n=30, m=4.
Adotteremo la convenzione che il valore 0 indicherà un compito non consegnato perché lo studente era assente quel giorno. Una volta inseriti i voti di ciascun studente la matrice sarà del tipo:
Programmazione Mod A - Cap 6 - prof. Burattini
51
40
.
.
. NON USATA
I compiti sono indicati con i numeri da 0 a 7, mentre il numero di studenti è rappresentato sulla sinistra con i numeri compresi tra 0 e 40. Supponendo che gli studenti siano 32 e che i compiti siano 5, otteniamo la situazione a lato, in cui alcune parti dell’array non sono utilizzate.Se indichiamo con A tale matrice, per conoscere il voto conseguito dallo studente numero 3 nell’esame numero 2, dobbiamo incrociare la riga contrassegnata con 3 con la colonna contrassegnata con 2: il voto sarà rappresentato dal valore letto nel loro punto d’incontro, cioè 5; scriveremo allora
A[3][2]=5
0 1 2 3 4
0 9 6 0 7 7
1 5 6 6 0 6
2 8 6 7 0 0
3 4 6 5 4 4
… … … … … …
… … … … … …
… … … … … …
31 2 4 4 5 4
5 6 7 8
N O N
U S A T A
Programmazione Mod A - Cap 6 - prof. Burattini
52
Tenendo presente l’ultimo esempio, scrivere un algoritmo che stampi il numero d’ordine di ogni studente con accanto il numero di esami superato e la loro media.
Descrizione algoritmo. Per ogni riga i che rappresenta uno studente Scandire le colonne relative alla riga i e sommare e contare ogni esame il cui
risultato è >0 Stampa(i, conta, media)
Pseudocodice.
for (i=0; i<30; i++) conta0; somma0 for (j=0; j<5; j++) if A[i][j] > 0 contaconta+1 sommasomma+A[i][j] if (somma0) stampa(i, conta, somma/conta)
else stampa(messaggio)
Programmazione Mod A - Cap 6 - prof. Burattini
53
Passaggio di array bidimensionali ad una function
Nel passaggio di un array monodimensionale ad una function è necessario indicare soltanto il nome seguito dalle due parentesi quadre, perché passando alla function l’indirizzo del primo elemento essa è in grado di determinare l’indirizzo di ogni elemento successivo.
Naturalmente un altro parametro deve rappresentare il numero di elementi effettivamente presenti nell’array
Anche nel caso di un array bidimensionale viene fornito alla function l’indirizzo del primo elemento; in questa situazione, però, sorge un problema che andiamo ad analizzare con un esempio.
Programmazione Mod A - Cap 6 - prof. Burattini
54
Sia assegnato una matrice A di interi di dimensioni massime 4x5 (il primo numero, 4, indica le righe, il secondo, 5, le colonne); essa sarà dichiarata come
int A[4][5] il compilatore allocherà per tale array uno spazio rappresentato dalla seguente
tabella:
Supponiamo che, durante l’esecuzione, vengano riempite soltanto le prime tre righe e le prime due colonne Se a questo punto si volesse utilizzare una procedura esempio che abbia come parametro la matrice A la chiamata sarebbe esempio(A,3,2) per indicare alla procedura che solo le prime tre righe e le prime due colonne sono significative.
X X
X X
X X
Programmazione Mod A - Cap 6 - prof. Burattini
55
Tuttavia la intestazione della function non potrebbe essere:void esempio (int A[ ] [ ], int n, int m);
Infatti poiché con A[ ][ ] s’intende l’indirizzo del primo elemento A[0][0], la function comincerà ad eseguire i calcoli sulla prima riga; per determinare l’indirizzo della seconda riga non è sufficiente conoscere il numero logico di colonne, che è 2, ma occorre anche saperne il numero fisico che invece è 5;
per andare sulla seconda riga il compilatore deve saltare 5 locazioni di memoria e non 3!
Solo in questo modo è in grado di determinare l’indirizzo iniziale di ogni riga successiva alla prima.
Per questa ragione la chiamata di una matrice deve includere anche il massimo numero di colonne; la function esempio dovrà avere la seguente intestazione:
void esempio (int A[ ] [5], int n);
Se un array possiede più di due dimensioni, può essere richiamato da una function soltanto nel caso in cui vengono assegnate tutte le dimensioni massime esclusa la prima.
Programmazione Mod A - Cap 6 - prof. Burattini
56
L’esercizio che segue mostra un’esemplificazione di quanto appena detto.Sono definite tre funzioni che utilizzano matrici: la prima, GeneraMat, genera una matrice in modo randomla seconda, LeggiMat, legge i valori di una matricela terza, StampaMat, stampa i valori sul monitor
#include <iostream>#include <cstdlib>#include <ctime>using namespace std;const int rigmax=10;const int colmax=10;void GeneraMat(char, int [][colmax], int, int);void LeggiMat(char, int [][colmax], int, int);void StampaMat(char, const int [][colmax], int, int);int main() { int A[rigmax][colmax],B[rigmax][colmax]; int righe,colonne; srand(time(0)); cout<<"Righe ( max 10)="; cin>>righe; cout<<"Colonne( max 10)="; cin>>colonne; LeggiMat('B',B,righe,colonne); cout<<endl; GeneraMat('A',A,righe,colonne); cout<<endl; StampaMat('A',A,righe,colonne); system("pause");}
Programmazione Mod A - Cap 6 - prof. Burattini
57
void GeneraMat(char nomemat,int mat[][colmax], int righe,int colonne) { int i,j; for (i=0;i<righe;i++) for (j=0; j<colonne; j++) { mat[i][j]=rand()%100 - 50; cout<<nomemat<<"["<<i<<"]["<<j<<"]="<<mat[i][j]<<endl; } }void LeggiMat(char nomemat,int mat[][colmax], int righe,int colonne) { int i,j; for (i=0;i<righe;i++) for (j=0; j<colonne; j++) { cout<<nomemat<<"["<<i<<"]["<<j<<"]="; cin>>mat[i][j]; } }void StampaMat(char nomemat,const int mat[][colmax], int righe,int colonne) { int i,j; for (i=0;i<righe;i++) { for (j=0; j<colonne; j++) cout<<nomemat<<"["<<i<<"]["<<j<<"]="<<mat[i][j]<<" "; cout<<endl; } }
Programmazione Mod A - Cap 6 - prof. Burattini
58
Esempio.
Assegnata una matrice di A dimensioni MxN stampare le somme totali di ogni riga.
Per gestire una matrice abbiamo sempre la necessità di utilizzare due cicli nidificati, uno che scorre le righe ed un altro le colonne:
for (i=0; i<M ; i++) for (j=0; j<N ; j++)
poiché dobbiamo determinare la somma degli elementi di una riga qualsiasi dobbiamo scrivere
somma somma +A[i][j]
in cui i deve rimanere costante e j deve variare; l’istruzione precedente deve allora essere inserita nel secondo for, mentre subito dopo il primo for dobbiamo inizializzare la variabile somma.
Programmazione Mod A - Cap 6 - prof. Burattini
59
In definitiva l’algoritmo che risolve il problema è il seguente:
for (i=0; i<M ; i++) somma=0; for (j=0; j<N ; j++) somma somma +A[i][j]; stampa(i ,somma),
Programmazione Mod A - Cap 6 - prof. Burattini
60
5) Sono dati i numeri di pezzi prodotti ogni giorno (dal lunedì al venerdì) da una ditta in n settimane lavorative. Scrivere una function per ottenere:a) La somma settimana per settimana della produzione visualizzata in forma di diagramma di asterischi (un asterisco corrisponde a 10 pezzi prodotti);b) il numero medio di pezzi prodotti giornalmente;c) l’elenco dei giorni suddivisi nelle varie settimane, in cui la produzione è stata inferiore alla media con il relativo valore.
Come esempio, supponendo che sia n=4, disponiamo i dati in modo che le righe siano le settimane e le colonne i giorni lavorativi della settimana:
Il punto a) deve restituire
b) deve restituire 42,1 ed infinec) deve restituire il numero progressivo della settimana ed il giorno (lunedì,
martedì, …); per esempio per la prima settimana deve scriveremercoledìgiovedì1 venerdì.
L M M G V
S1 26 34 45 46 54
S2 36 44 38 55 53
S3 30 45 35 48 42
S4 32 40 44 46 48
205 ****************
226 *******************
200 ****************
210 *****************
Programmazione Mod A - Cap 6 - prof. Burattini
61
6) Sia dato un array bidimensionale A di interi positivi di dimensione NxN. Scrivere una funzione che restituisca True se e solo se nell’array A
• c’è almeno un numero pari in ogni riga i
• c’è almeno un numero dispari in ogni riga
• ci sono almeno “i” numeri pari nella riga i-esima
• ci sono esattamente “i” numeri dispari nella riga i-esima
• ci sono almeno “i” numeri pari consecutivi nella riga i-esima
• ci sono esattamente “i” numeri dispari nella colonna i-esima
Programmazione Mod A - Cap 6 - prof. Burattini
62
7) Supponiamo di avere sul un file di testo studenti.txt, i seguenti dati:
Scrivere un programma che, dopo aver letto tutti i dati ed averli inseriti in una matrice, risolva i seguenti passi:
stampi la media di ogni esame;stampi i numeri di matricola degli studenti che hanno ottenuto il voto più alto per ogni
esame;stampi il numero di studenti che, per ogni esame, hanno superato la media già calcolata;conservi in un file, uno per riga, il numero di matricola degli studenti che in almeno un
esame, hanno ottenuto un voto maggiore di un valore prefissato.
Numeroprogres
sivo
Numeromatrico
la
Esame1
Esame2
Esame3
Esame4
Esame5
Esame6
Esame7
Esame8
1 1024 18 25 28 0 26 25 28 0
2 1038 0 30 28 26 24 28 27 25
3 1045 24 30 27 28 26 28 0 0
4 1087 23 25 24 20 24 23 0 0
5 1102 22 25 24 26 24 25 28 0
6 1120 23 28 27 26 30 25 28 0
7 1125 24 27 30 22 0 0 28 23
8 1142 22 25 26 23 24 25 0 24
9 1157 21 24 26 27 28 30 30 24
10 1164 22 25 0 0 25 0 0 24
11 1177 23 24 25 22 23 0 20 0
12 1185 19 22 20 21 22 20 0 0
Programmazione Mod A - Cap 6 - prof. Burattini
63
8) Scrivere un programma che, assegnata una matrice quadrata di ordine N di reali, risolva i seguenti problemi con una funzione o procedura:
• restituisce la somma di tutti i suoi elementi;• restituisce la somma di tutti gli elementi per cui è pari la somma degli
indici;• calcola la somma ed il prodotto degli elementi della diagonale principale e
secondaria;• restituisce true se la matrice è diagonale superiore od inferiore, false
altrimenti;• restituisce true se la matrice è unitaria, false altrimenti;• restituisce true se la matrice è simmetrica, false altrimenti.
Il programma deve essere strutturato con procedure e funzioni e con un menù che le richiami.
Programmazione Mod A - Cap 6 - prof. Burattini
64
Alcuni algoritmi classici per l’elaborazione di matrici
Allorché occorre ricavare dell’informazione da una matrice A occorre sempre ricordare cosa rappresenta una riga, cosa rappresenta un array e che cosa rappresenta un generico elemento a[i][j].
In genere il problema da risolvere cade in uno dei quattro schemi seguenti:
Elaborazione riga per colonna. Il loop più esterno agisce sulle righe quello più interno sulle colonne.
Supponendo che A sia una matrice avente m righe ed n colonne:
Algoritmo riga per colonna:for(i=0,i<m,i++){for(j=0,j<m,j++)elabora A[i,j]
}
Programmazione Mod A - Cap 6 - prof. Burattini
65
Elaborazione colonna per riga.
Qui il loop più esterno agisce sulle colonne quello più interno sulle righe.
Algoritmo colonna per riga:for(j=0,j<n,j++){for(i=0,i<m,i++)elabora A[i,j]
}
In alcuni casi i due algoritmi sono equivalenti .
Ritornando alla matrice contenente i voti riportati ai compiti dai singoli studenti, se si volesse calcolare la media dei voti su tutti i compiti svolti dagli studenti si potrebbe adoperare uno qualsiasi dei due.
Se invece, come nel nostro esempio, si vuole conoscere il voto medio riportato da ogni singolo studente è indispensabile adoperara il primo.
Una elaborazione colonna per riga ci fornirebbe il voto medio riportato dalla classe per ogni compito.
Programmazione Mod A - Cap 6 - prof. Burattini
66
Elaborazione di una riga di una matriceProcurarsi l’indice i della riga
for(j=0,j<n,j++)elabora A[i,j]
Elaborazione di una colonna di una matriceProcurarsi l’indice j della colonnafor(i=0,i<m,i++)elabora A[i,j]
Ritornando al nostro esempio, trovare le insufficienze riportate dallo studente numero k comporta una elaborazione sulla riga k, mentre trovare lo studente col voto migliore nel compito r, comporta una elaborazione sulla colonna r.
EsercizioSi riprendano gli esercizi 7, 7b, 8b e 8f precedenti: stabilire se è necessario
adoperare una elaborazione riga per colonna o è necessario adoperare una elaborazione colonna per riga oppure è indifferente adoperare uno dei due metodi.
Programmazione Mod A - Cap 6 - prof. Burattini
67
7) Supponiamo di avere sul un file di testo studenti.txt, i seguenti dati:
Scrivere un programma che, dopo aver letto tutti i dati ed averli inseriti in una matrice, risolva i seguenti passi:
stampi la media di ogni esame;stampi i numeri di matricola degli studenti che hanno ottenuto il voto più alto per ogni
esame;stampi il numero di studenti che, per ogni esame, hanno superato la media già calcolata;conservi in un file, uno per riga, il numero di matricola degli studenti che in almeno un
esame, hanno ottenuto un voto maggiore di un valore prefissato.
Numeroprogres
sivo
Numeromatrico
la
Esame1
Esame2
Esame3
Esame4
Esame5
Esame6
Esame7
Esame8
1 1024 18 25 28 0 26 25 28 0
2 1038 0 30 28 26 24 28 27 25
3 1045 24 30 27 28 26 28 0 0
4 1087 23 25 24 20 24 23 0 0
5 1102 22 25 24 26 24 25 28 0
6 1120 23 28 27 26 30 25 28 0
7 1125 24 27 30 22 0 0 28 23
8 1142 22 25 26 23 24 25 0 24
9 1157 21 24 26 27 28 30 30 24
10 1164 22 25 0 0 25 0 0 24
11 1177 23 24 25 22 23 0 20 0
12 1185 19 22 20 21 22 20 0 0
Programmazione Mod A - Cap 6 - prof. Burattini
68
Pseudo codice
1. Leggi il file e metti i dati in un array2. Elabora l’array• Cerca massimo x studente e costruisce vettore medie• esame stampa il numero di studenti che superano la media• Metti in un vettore le matricole degli studenti che superano la media• Salva il vettore su un nuovo file
Programmazione Mod A - Cap 6 - prof. Burattini
69
Complessità di un algoritmo.
Dati due differenti algoritmi per risolvere lo stesso problema
quale dei due programmi che li implementano dobbiamo
scegliere?
Innanzitutto osserviamo che ogni programma necessita di una
certa quantità di memoria ed impiega una certa quantità di
tempo per essere eseguito. Queste due risorse, tempo e spazio
di memoria, sono spesso in conflitto tra di loro: aumentando la
memoria occupata dal programma si può diminuire il tempo
di calcolo.
Ci occuperemo della valutazione dell’efficienza o complessità di
un programma in termini del solo tempo di calcolo
trascurando la quantità di memoria utilizzata e supponendo
quindi che non ci sia alcun limite alla quantità di memoria
utilizzata dal programma.
Programmazione Mod A - Cap 6 - prof. Burattini
70
Complessità di un algoritmo.
Nonostante questa astrazione, restano due problemi:
1- Il tempo di calcolo dipende dalla velocità con cui una
particolare macchina esegue le operazioni elementari:
addizione, moltiplicazione, valutazione delle espressioni
booleane elementari.
2- Il tempo di calcolo varia al variare dei dati di ingresso.
Consideriamo, ad esempio, uno dei qualsiasi algoritmi relativi
all’ordinamento; ebbene il tempo di esecuzione sarà diverso se
introduciamo un vettore già ordinato, un vettore formato da
numeri generati a caso, un vettore ordinato in verso opposto,
etc.
Programmazione Mod A - Cap 6 - prof. Burattini
71
Ciò a cui siamo interessati è di trovare un metodo che ci permetta
di valutare la complessità di un algoritmo al variare delle
dimensioni dei dati in ingresso.
Considerata l’enorme velocità di calcolo anche di un semplice
personal computer, possiamo per quel che riguarda il punto 1
adottare la seguente semplicazione:
Si assegni ad ogni istruzione elementare (assegnamento o
valutazione di una espressione) un costo o complessità pari ad
1.
Programmazione Mod A - Cap 6 - prof. Burattini
72
Il punto 2 potrebbe essere aggirato tentando di calcolare il costo
computazionale medio dell’algoritmo.
In genere tale misura però non è facile da trovare.
Si preferisce pertanto parlare di complessità nel caso peggiore.
Ciò anche in considerazione del fatto che un programma che in
infiniti casi fornisca la soluzione in tempi rapidissimi non è di
alcuna utilità se negli altri casi ci costringe ad attese
lunghissime.
Programmazione Mod A - Cap 6 - prof. Burattini
73
La complessità del caso peggiore si calcola tenendo presente le
seguenti regole:
1- Se E è una qualsiasi espressione booleana oppure un’enunciato
di assegnazione,
C(E) = 1
2- Una sequenza di istruzioni E1,E2,…,En ha come costo
C(E1)+C(E2)+….+C(En).
3- C(if (cond) istruzione1 else istruzione2) =
1+max(C(istruzione1), C(istruzione2)).
Programmazione Mod A - Cap 6 - prof. Burattini
74
4- C(for (i=N1; I<=N2; i++)istruzione) =
5- Solo se la complessità del corpo del for non dipende da i si avrà:
C(for (i=N1; I<=N2; i++)istruzione) = (N2-N1+1)C(istruzione)• Nel caso di un while loop detto Max il massimo numero di
iterazioni possibili si ha:
C(while(cond)istruzione) = Max(1+C(istruzione)). • La situazione è anologa per il loop do..While.• Se tutti i parametri di una function che rappresentano
strutture complesse sono riferimenti o indirizzi come nel caso
degli array, allora il costo di una function avente n parametri
sarà dato da n moltiplicato il costo del corpo della function.
N2
C(istruzione(i))i=N1
Programmazione Mod A - Cap 6 - prof. Burattini
75
L’unica regola non effettiva che abbiamo dato è la regola 5). In alcuni casi è semplice trovare il numero massimo di iterazioni. In altri casi ci si può accontentare di un maggiorante di Max, visto che si è interessati all’andamento asintotico della complessità al crescere delle dimensioni dei dati, ma in generale ciò è impossibile.
In altri termini non esiste alcun algoritmo in grado di determinare, dato un qualsiasi while loop quanto vale il massimo numero di iterazioni ed in particolare non esiste un algoritmo in grado di decidere, dato un qualsiasi while loop, se questo termina sempre in un numero finito di passi oppure no. Un tipico esempio si basa sulla:
Congettura di Collatz: partendo da un numero naturale qualsiasi a>0 e applicando la regola
=3an+1 se an è dispari > 1 an+1
=an / 2 se an è parisi raggiunge sempre il valore 1.
Programmazione Mod A - Cap 6 - prof. Burattini
76
La congettura di Collatz non è stata dimostrata. Pertanto non si è in grado di stabilire se la complessità della function qui sotto definita è infinita oppure no.
intl function collatz(int a)WHILE (a>1) { if (a % 2=1)
a=3*a+1; else
a= a / 2; return a;
Programmazione Mod A - Cap 6 - prof. Burattini
77
EsempioCalcoliamo il costo dell’algoritmo di Bubble-Sort. for(k=0; k<N-1; k++)
for (j=N-2; j>=k; j--) if (vet[j] > vet[j+1]) scambia (vet[j],vet[j+1]);
Come primo passo determiniamo il costo della funzione scambia(x,y). Esso sarà pari a 2 più il costo del corpo della funzione che comprende tre
assegnazioni; quindiC(scambia)=5
Ancora, il costo della condizione relativa all’istruzione if è :C(if) = 1 + C(scambia) = 6
Tale costo è anche il costo del corpo del loop interno ed è indipendente dall’indice j.
Siccome il corpo del for interno è eseguito (N –2) - k +1 = N – k -1 volte si avrà:C(for interno) = (N – k-1) • 6
Dunque la complessità del for interno dipende dal valore dell’indice k
Programmazione Mod A - Cap 6 - prof. Burattini
78
Quindi il costo complessivo dell’algoritmo sarà dato da:
C(bubblesort) = = 6N(N-1) – 6(1+2+...+N-2)-6(N-1)=
=6N2-6N –6(N-1)(N-2))/2 -6N-6== 6N2-6N-3(N2-2N-N+2)-6N-6=3N2-3N
N2
(6N-6k-6)i=N1
Programmazione Mod A - Cap 6 - prof. Burattini
79
Esempio
Calcoliamo il costo dell’algoritmo di ricerca binaria.Abbiamo a che fare con un solo loop. E’ quindi ovvio che se k rappresenta il
massimo numero di iterazioni otterremo per la complessità un valore del tipo ak+b. Sappiamo che nel caso peggiore, cioe’ quando l’elemento non è presente nell’array, il ciclo termina con l’indice basso>alto , cioè quando l’intervallo corrispondente è vuoto. Osserviamo che dopo un passo il numero dei possibili candidati si è ridotto ad N/2, dopo due passi a N/22, dopo tre a N/23, etc quindi possiamo dire che nel caso peggiore il ciclo terminerà dopo un numero k di passi tale che N/2k è all’inrcica uguale a 1.
Dunque k è tale che 2k è all’incirca N e quindi k è dato da log2N. La complessità computazionale dell’algoritmo di ricerca binaria varia in
maniera proporzionale a log2N, dove N è la dimensione dell’array. Si suole scrivere:
C(ricerca binaria) = O(log2N)Mentre O(N) rappresenta l’andamento asintotico della ricerca lineare ed in
genere di ogni loop for applicato ad un array, O(N2) è l’andamento asintotico degli algoritmi di ordinamento illustrati ed in generale di due for innestati.
I migliori algoritmi di ordinamento, quicksort e mergesort vanno invece come N log2N.
Programmazione Mod A - Cap 6 - prof. Burattini
80
Esercizio
Calcolare il costo dell’algoritmo di insertion sort ed il costo dell’algoritmo di selection sort .
Verificare che anche essi hanno un costo proporzionale al quadrato del numero di elementi degli array.
Programmazione Mod A - Cap 6 - prof. Burattini
81
Top Related