Fondamenti di Informatica

(1)

Fondamenti di Informatica

© 2007 Pier Luca Montessoro, Davide Pierattoni 1 (si veda la nota di copyright alla slide n. 2)

Fondamenti di Informatica - Linguaggio C - Scegliere un algoritmo

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Ing. DAVIDE PIERATTONI

Facoltà di Ingegneria Università degli Studi di Udine

Linguaggio C Scegliere un algoritmo

© 2007 Pier Luca Montessoro - Davide Pierattoni (vedere nota di copyright a pag. 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà degli autori prof. Pier Luca Montessoro e ing. Davide Pierattoni, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. Gli autori non assumono alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Scegliere un algoritmo

• Gli algoritmi classici sono descritti in letteratura e vanno scelti in base alla complessità del problema, al tipo di dati, ecc.

• Ogni problema ha poi bisogno di elaborazioni specifiche dei dati in ingresso e in uscita

• Due grandi famiglie di problemi:

– mantengo tutti i dati in memoria e li elaboro – elaboro e/o trasformo i dati man mano che li leggo

Mantengo tutti i dati in memoria e li elaboro

definisco una struttura dati adeguata (es. vettore di struct)

while (ci sono ancora dati) leggo i dati e li memorizzo

elaboro i dati

genero il risultato (es. scrivo in un file)

Mantengo tutti i dati in memoria e li elaboro

• NOTE:

– devo sapere la dimensione MASSIMA dei dati da memorizzare

– la lettura dei dati tipicamente richiede una funzione che interpreta il formato di ingresso

– l’elaborazione dei dati richiede una o più funzioni che NON ESEGUONO input né output

Elaboro e/o trasformo i dati man mano che li leggo

definisco una struttura dati adeguata per rappresentare un singolo dato

(es. una stuct, una stringa, un numero)

while (ci sono ancora dati) {

leggo il dato e lo memorizzo in una variabile elaboro il dato

genero il risultato

(es. scrivo il dato trasformato in un file)

}

(2)

Fondamenti di Informatica

© 2007 Pier Luca Montessoro, Davide Pierattoni 2 (si veda la nota di copyright alla slide n. 2)

Elaboro e/o trasformo i dati man mano che li leggo

• NOTE:

– utile quando NON CONOSCO LA DIMENSIONE MASSIMA dei dati in ingresso

– la lettura del singolo dato tipicamente richiede una funzione che interpreta il formato di ingresso

– l’elaborazione dei dati richiede una o più funzioni che NON ESEGUONO input né output

Lettura del dato

• Caso 1: devo elaborare un testo

→ lettura carattere per carattere (es. fgetc)

• Caso 2: devo leggere dei dati testuali e numerici in formato fisso (es. numero predefinito di parole in ogni riga)

→ lettura formattata (fscanf con opportuni codici di formato)

• Caso 3: i dati sono organizzati per righe, di formato variabile

→ lettura riga per riga (fgets) e poi interpretazione del formato lavorando sulla stringa

Caso 1: esempio

...

while ((ch = fgetc (fp)) != EOF) {

if (ch == '/') trovato_slash = 1;

**else if ((ch == '*') && trovato_slash)** {

in_commento = 1;

trovato_slash = 0;

} else

trovato_slash = 0;

...

Caso 2: esempio

...

while (fscanf (fpin, "%s %d %d",

s, &n1, &n2) != EOF) {

totale += elabora (s, n1, n2, s_mod);

fprintf (fpout, "%s %d", s_mod, n1);

}

return totale;

Caso 3: esempio

...

while (fgets (s, NMAX, fp) != NULL) {

dato_corrente = estrai_dato (s);

if (cerca_nome (dato_corrente.codice, codice_cercato)) {

fprintf (fpout, "%s %d", dato_corrente.codice, dato_corrente.prezzo);

} }

Ricerche

• Ricordarsi sempre che gli algoritmi di ricerca sono asimmetrici:

...

while (ci sono ancora dati) {

if (dato corrente == dato cercato) return informazioni cercate

procedi al prossimo dato }

return informazione di dato non trovato

(3)

Fondamenti di Informatica

Fondamenti di Informatica

Fondamenti di Informatica

© 2007 Pier Luca Montessoro, Davide Pierattoni 1 (si veda la nota di copyright alla slide n. 2)

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Ing. DAVIDE PIERATTONI

Facoltà di Ingegneria Università degli Studi di Udine

Linguaggio C Scegliere un algoritmo

Nota di Copyright

Scegliere un algoritmo

• Gli algoritmi classici sono descritti in letteratura e vanno scelti in base alla complessità del problema, al tipo di dati, ecc.

• Ogni problema ha poi bisogno di elaborazioni specifiche dei dati in ingresso e in uscita

• Due grandi famiglie di problemi:

– mantengo tutti i dati in memoria e li elaboro – elaboro e/o trasformo i dati man mano che li leggo

Mantengo tutti i dati in memoria e li elaboro

definisco una struttura dati adeguata (es. vettore di struct)

while (ci sono ancora dati) leggo i dati e li memorizzo

elaboro i dati

genero il risultato (es. scrivo in un file)

Mantengo tutti i dati in memoria e li elaboro

• NOTE:

– devo sapere la dimensione MASSIMA dei dati da memorizzare

– la lettura dei dati tipicamente richiede una funzione che interpreta il formato di ingresso

– l’elaborazione dei dati richiede una o più funzioni che NON ESEGUONO input né output

Elaboro e/o trasformo i dati man mano che li leggo

definisco una struttura dati adeguata per rappresentare un singolo dato

(es. una stuct, una stringa, un numero)

while (ci sono ancora dati) {

leggo il dato e lo memorizzo in una variabile elaboro il dato

genero il risultato

(es. scrivo il dato trasformato in un file)

}

Fondamenti di Informatica

© 2007 Pier Luca Montessoro, Davide Pierattoni 2 (si veda la nota di copyright alla slide n. 2)

Elaboro e/o trasformo i dati man mano che li leggo

• NOTE:

– utile quando NON CONOSCO LA DIMENSIONE MASSIMA dei dati in ingresso

– la lettura del singolo dato tipicamente richiede una funzione che interpreta il formato di ingresso

– l’elaborazione dei dati richiede una o più funzioni che NON ESEGUONO input né output

Lettura del dato

• Caso 1: devo elaborare un testo

→ lettura carattere per carattere (es. fgetc)

• Caso 2: devo leggere dei dati testuali e numerici in formato fisso (es. numero predefinito di parole in ogni riga)

→ lettura formattata (fscanf con opportuni codici di formato)

• Caso 3: i dati sono organizzati per righe, di formato variabile

→ lettura riga per riga (fgets) e poi interpretazione del formato lavorando sulla stringa

Caso 1: esempio

...

while ((ch = fgetc (fp)) != EOF) {

if (ch == '/') trovato_slash = 1;

else if ((ch == '*') && trovato_slash) {

in_commento = 1;

trovato_slash = 0;

} else

trovato_slash = 0;

...

Caso 2: esempio

...

while (fscanf (fpin, "%s %d %d",

s, &n1, &n2) != EOF) {

totale += elabora (s, n1, n2, s_mod);

fprintf (fpout, "%s %d", s_mod, n1);

}

return totale;

Caso 3: esempio

...

while (fgets (s, NMAX, fp) != NULL) {

dato_corrente = estrai_dato (s);

if (cerca_nome (dato_corrente.codice, codice_cercato)) {

fprintf (fpout, "%s %d", dato_corrente.codice, dato_corrente.prezzo);

} }

Ricerche

• Ricordarsi sempre che gli algoritmi di ricerca sono asimmetrici:

...

while (ci sono ancora dati) {

if (dato corrente == dato cercato) return informazioni cercate

procedi al prossimo dato }

return informazione di dato non trovato

Fondamenti di Informatica

© 2007 Pier Luca Montessoro, Davide Pierattoni 3 (si veda la nota di copyright alla slide n. 2)

Avanzare in una stringa

**else if ((ch == '*') && trovato_slash)** {