CAPITOLO 6 Ordinamento di array e array a più dimensioni

Programmazione Mod A - Cap 6 - prof. Burattini

1


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.


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.


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.


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.


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.


7

ORDINAMENTO = SORTING

10

19

9

30

29

12

18

1

2

3

4

5

6

7

19

30

10

29

12

9

18


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


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


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


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.


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


13

k=4

9101218192930

9101218192930

9101218192930

k=5

9101218192930

9101218192930

9101218192930

k=6

N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2


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.


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.


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.


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


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


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.


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.


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


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.


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


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

D:\Documents and Settings\marina\Desktop\C++ lezioni\C++ lezioni mod A\Cap.6 C++\eserbuble.exe


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


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.


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).


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


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


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


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


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.


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


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


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


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


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


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


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.


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


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;}


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; }


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”


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*/


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())


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


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’}}


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


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


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:


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


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)


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.


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


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.


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");}


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; } }


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.


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),


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 *****************


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


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


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.


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]

}


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.


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.


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


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


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.


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.


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.


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.


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)).


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


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.


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;


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


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


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.


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.


81

CAPITOLO 6 Ordinamento di array e array a più dimensioni

Documents

Transcript of CAPITOLO 6 Ordinamento di array e array a più dimensioni