Algoritmi - Parte 3

La ricerca stile 'dizionario'

1. Apri il classificatore

2. Prendi la scheda X al centro dello schedario

3. Confronta il campo autore e titolo di X con quelli cercati

4. Se sono uguali, allora termina e restituisci la scheda, altrimenti prosegui

5. Se il campo autore di X è minore di quello cercato allora prosegui la ricerca sulla metà successiva delle schede, altrimenti considera la metà precedente

6. Se la metà selezionata al passo 5 è vuota allora termina (lo schedario non contiene il libro cercato), altrimenti scegli come X la scheda al centro della metà scelta e vai al passo 3 4

Informatica Generale Maria De Marsico

La ricerca stile 'dizionario'

1. Apri l'elenco

2. Prendi la pagina X al centro dell'elenco

3. Confronta la prima coppia cognome e nome di X con quelli cercati

4. Se sono uguali, allora termina e restituisci il numero, altrimenti prosegui

5. Se il campo cognome di X è minore di quello cercato allora prosegui

La ricerca sulla metà successiva delle pagine (compresa la pagina X) altrimenti considera la metà precedente

Se la metà selezionata al passo 5 contiene una sola pagina cerca cognome e nome cercati in tutta la pagina, altrimenti scegli come X la pagina al centro della metà selezionata e vai al passo 37.

Se cognome e nome cercati sono nella pagina restituisci il numero, altrimenti l'elenco non contiene la persona corrispondente.

Informatica Generale Maria De Marsico

La ricerca stile 'dizionario' schedario

Informatica Generale Maria De Marsico 2

La ricerca binaria

Ogni volta elimino la metà delle schede, oppure mi fermo perché ho trovato la scheda cercata.

Ogni volta divido il numero N delle schede per 2, al peggiomi fermo quando N è diventato 1 oppure 0, quindi non è più possibile dividere per 2.

Scheda cercata

Al più eseguo x passi dove x è il logaritmo in base 2 di N.

Informatica Generale Maria De

MarsicoOrdinamento di N numeriinteri

• Servono N variabili X_1 … X_N per memorizzare inumeri letti dall’esterno
• Supponiamo che max_N restituisca una coppia di valori(m,i) dove m è il valore del massimo ed i è la posizioneall’interno della sequenza cui corrisponde
• es (45,3), il massimo valore è 45 e corrisponde al terzonumero nella sequenza lunga N 8

Informatica Generale Maria De Marsico

Il massimo fra N numeri interi

• Algoritmo max_Ni
1. Leggi il valore di N dall’esterno
2. Leggi i primi due numeri in posizione 1 e 2
3. Trova il maggiore fra i primi due numeri (con emax_xy)assegna il suo valore alla variabile m e la sua posizione allavariabile i
4. Finchè (hai esaminato meno di N numeri)
1. Leggi un nuovo numero x dalla posizione k all’esternob
2. Trova il maggiore fra m e x usando l’algoritmo max_xyc
3. Assegna il valore e la posizione del maggiore a m e i
5. Restituisci il valore di m e di i

Informatica

1. Algoritmo ordina_N
1. Leggi il valore di N dall'esterno
2. Finché (hai letto meno di N numeri)
• Leggi un nuovo numero nella variabile X_i
3. Trova il maggiore (m, i) fra X_1 ... X_N (con max_Ni)
4. Scambia fra loro X_i e X_N
5. Considera adesso solo i primi N-1 numeri (N=N-1)
6. Se N = 1 termina, altrimenti vai al passo 3

10Informatica Generale Maria De Marsico

Ordinare N numeri interi

Numeri ordinati

Numeri da ordinare N=4 Max_N = 10 in posizione 1

10 8 3 1 Scambio la posizione 1 e 4

N=3 Max_N = 8 in posizione 2

1 8 3 10 Scambio la posizione 2 e 3

1 3 8 10 N=2 Max_N = 3 in posizione 2

Nessuno scambio

1 3 8 10 N=1

Termina

1 3 8 10 11Informatica Generale Maria De Marsico

Uso di array

• Ci occorrono più variabili X_i che dobbiamo poter identificare ogni volta
• N cambia ad ogni ripetizione (iterazione) del passo 3 ...
• Usiamo una rappresentazione 'più potente' della singola variabile, in

grado di mantenere una sequenza di valori e di cui sia possibile "conservare" la lunghezza in una variabile:

• Abbiamo già accennato ai tipi di dato strutturati (strutture dati)
• Il tipo strutturato più semplice è l'array (vettore) a 1 dimensione:
• contiene una lista di elementi TUTTI dello stesso tipo (interi, caratteri, ecc.)
• ogni elemento è raggiungibile attraverso il suo indice (posizione)... attenzione, di solito partono da 0!

5 6 7 8 90 1 2 3 4 IndiciLista

7 4 9 85 3 61 0 2 Valori12 Informatica Generale Maria De Marsico 4

Array:

• Possiamo definire una sequenza lunga N per il nostro problema di ordinamento
• Array di 4 valori interi (a una sola dimensione):

1 3 7 8

• Possiamo definire una tabella a due dimensioni, ad esempio per memorizzare le vendite di alcuni prodotti nei trimestri dell'anno

	II	III	IV
Prod 1	100	32	7
Prod 2	69	3	50
Prod 3	14	3	723

Array 3x4 (a due dimensioni) di 12 valori interi

13Informatica Generale Maria De MarsicoArray

• Abbiamo già detto che la struttura si specifica con il tipo e l'ampiezza di ogni dimensione
• es : 1 3 7 8
• int lista[4] II IIII IV
• int tabella[3][4] 1 32 7 8
• Prod 1 9 3 3 8
• Prod 2
• Nomi delle strutture 14 3 723 82
• Prod 3

Informatica Generale Maria De MarsicoArray

• Ogni elemento di ogni dimensione è identificato da un valore da 1 a N (o da 0 a N-1, dipende dall'linguaggio) che rappresenta la sua posizione (indice)
• 0 2 1 3 7 8 valore lista[1]
• 0 2 indice 1 3 II IIII IV
• 1 32 7 8 0 Prod 1 19 3 3 8 Prod 2 14 3 723 82 Prod 3 2 tab[1][0] valore

Informatica Generale Maria De Marsico 5

Usiamo gli array ...

• Costruiamo una versione dell'algoritmo ordina_N che usa un array int numeri[N] per memorizzare i numeri della sequenza da ordinare
• Chi inserisce i numeri nell'array ?
• Come trovo il massimo in un array ?

Informatica Generale Maria De MarsicoUsiamo gli array ...

prima 2 sottoalgoritmi

• che legge gli N numeri da ordinare e li inserisce nell'array numeri
• che trova il valore del massimo numero in max_N e la sua posizione numeri

Informatica Generale Maria De Marsico

Sottoalgoritmo per la lettura di N numeri

Inizio (leggi_N)

Input : N

Leggi il valore di N

Attenzione, partiamo dalla posizione 0 !

I = 0

Strutture dati:

Si Int X[N] // la sequenza

No I < N ? Restituisci N Fine

e la sequenza X[N]

Leggi il nuovo numero in X[I]

Output : Int X[N] // la sequenza letta

I = I + 1

Int N // la sua lunghezza

Informatica Generale Maria De Marsico 6

Esempio di esecuzione di leggi_N

N=4 Sequenza di numeri da leggere : 8, 1, 9, 7

X = Inizialmente X è vuoto

0 posizione 2

1 3

Passo 1, leggo il primo numero

Leggo 8 e lo scrivo nella posizione 0, cioè X[0]=8

I=0 8

Passo 2, leggo il secondo numero

Leggo 1 e lo scrivo nella posizione 1, cioè X[1]=1

I=1

Passo 3, leggo il terzo numero

Leggo 9 e lo scrivo nella posizione 2, cioè X[2]=9

8 1

9I=2Passo 4, leggo il quarto numero
Leggo 7 e lo scrivo nella posizione 3, cioè X[3]=7 8 1 9 7
I=3Termina I=4, quindi I< N non è più verificata 19
Informatica Generale Maria De Marsico

Sottoalgoritmo per la
Inizio trovare il massimo in unarray di N numeri (max_N)
Leggi N e X[N]
Input:
Int X[N],Int N m = X[0]k = 1 i = 0
Strutture dati:
Si No Int X[N] // la sequenzak < N ? Restituisci m Fine
e la sua posizione iSim > X[k] k = k + 1 Output:? Int m //il valore del massimo
No Int i // l’indice del massimo
Scorro l’arraym = X[k], i = k Equivale all’azione di leggere il prossimo numeroin entrata che era presente nel vecchio algoritmo

20Informatica Generale Maria De Marsico
Esempio di max_N
Trova il valore m del massimo in X e la sua posizione i . La lunghezza di X è N=4 e la sequenza da ordinare e’ 8, 1, 9, 7
numeri già esaminati punta all’attuale massimo 8 1 9 7
X = 0 2
indice 1 3
Inizializzazione m=X[0]=8, i=0 8 1 9 7
Passo 1, k=1 esamino

X[1]=1m > X[1] (infatti 8 > 1 ) quindi m e i non cambiano 8 1 9 7

Passo 2, k=2 esamino X[2]=9m < X[2] (infatti 8 < 9 ) quindi m e i cambiano 8 1 9 7 m = 9 i = 2

Passo 3, k = 3 esamino X[3]=7m > X[3] (infatti 9 > 7 ) quindi m e i non cambiano 8 1 9 7

k=4, quindi k< N non è più verificata

Termina 21

Informatica Generale Maria De Marsico 7

Ordinare N numeri interi

N=4 Max_Na = 8 in posizione 1

8 7 3 1 Scambio la posizione 1 e 4

N=3 1 7 3 8 Max_Na = 7 in posizione 2

Scambio la posizione 1 e 3

1 3 7 8 N=2 Max_Na = 3 in posizione 2

Nessuno scambio

1 3 7 8 N=1

Termina

1 3 7 8 22

Informatica Generale Maria De Marsico

Ordinare N numeri interi

• Algoritmo ordina_Na

1. Leggi il valore di N dall’esterno

2. Leggi gli N numeri della sequenza nell’array numeri (con leggi_N)

3. Trova il maggiore (m, i) fra i primi N numeri dell’array (con numeri max_N)

4. Scambia fra loro X[i] e X [N]

5. Considera adesso solo i primi N-1 numeri dell’array (N=N-1)

6. Se N = 1 continua

altrimenti vai al passo 37. Stampa X, termina 23

Informatica Generale Maria De Marsico

Osservazioni

• Ogni algoritmo può utilizzare più sotto-algoritmi
• Input = può essere dall'utente o da un algoritmo chiamante
• Output = può essere verso l'utente o verso un algoritmo chiamante

24

Informatica Generale Maria De Marsico

8

Algoritmo per ordinare N numeri (N, X[N]) = leggi_N()

Inizio (ordina_N)

L'input in realtà

Input: vuoto

Lung = N arriva da leggi_N

Si

No

il cui output viene

N > 1 ?

assegnato alla variabile N

e all'array X

(m, i) = max_N(N, X)

Stampa(Lung, X[N])

Strutture dati:

Int X[N]

Fine

T = X[N] // la sequenza

Output:

X[N] = X[i]

Int Lung // la lunghezza di X

Int X[N] // l'array X ordinato

X[i] = T // Scambio dei due valori

Notare l'uso di una variabile di appoggio

N = N-1

25

Informatica Generale Maria De Marsico

Strutture dati