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 e restituisci la scheda.

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