Algoritmi - Parte 3

Informatica Generale

Algoritmi 3 1

Due problemi “classici”

• Ricerca

• Ordinamento 2

Informatica Generale Maria De Marsico

Algoritmo di ricerca

‘sequenziale’ nello schedario

1. Apri il classificatore

2. Prendi la prima scheda

3. Confronta il campo autore e titolo con quelli

cercati

4. Se sono uguali, allora la ricerca è terminata,

esci

restituisci la scheda ed

5. Se le schede sono finite, allora il libro cercato

non esiste, restituisci un messaggio di errore ed

esci

• Si può fare meglio ? .... 3

Informatica Generale Maria De Marsico 1

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

6. 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 3

7.Se cognome e nome cercati sono nella pagina restituisci il numero,

altrimenti l’elenco non contiene la persona corrispondente 5

Informatica Generale Maria De Marsico

La ricerca stile ‘dizionario’

schedario 6

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 peggio

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

Informatica Generale Maria De Marsico

Ordinamento di N numeri

interi

• Servono N variabili X_1 … X_N per memorizzare i

numeri letti dall’esterno

• Supponiamo che max_N restituisca una coppia di valori

(m,i) dove m è il valore del massimo ed i è la posizione

all’interno della sequenza cui corrisponde

• es (45,3), il massimo valore è 45 e corrisponde al terzo

numero 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 e

max_xy)

assegna il suo valore alla variabile m e la sua posizione alla

variabile i

4. Finchè (hai esaminato meno di N numeri)

a. Leggi un nuovo numero x dalla posizione k all’esterno

b. Trova il maggiore fra m e x usando l’algoritmo max_xy

c. Assegna il valore e