Problem solving elementare su dati...

Problem solving elementare su dati vettoriali

5

I vettori nel problem solving

I vettori come contenitori di datiVettori ordinatiLa corrispondenza indice ↔ dato

7

Vettore = insieme di dati dello stesso tipo

Un vettore può essere utilizzato come contenitoredi dati (omogenei) senza alcun criterio di ordine

4-186312-9321473535

7

1432

-92

631-18

4

8

Vettore come contenitore

UtilizzoProblemi in cui è sufficiente raccogliere un insieme di dati, senza relazioni di ordineUn dato può essere in qualunque posizione nel vettoreAccesso ai dati mediante generazione (iterativa) di tutti gli indici

EsempiCollezionare dati in input, per elaborazioni successive, o preparare dati per l’outputOperazioni su insiemi di dati

10

Vettore = insieme di dati ordinati

I dati nel vettore sono organizzati secondo un criterio di ordine (es. valori crescenti)

631353214742-9-1835

7

1432

-92

631-18

4

11

Vettore e dati ordinati (1/2)

UtilizzoProblemi in cui occorre ordinare e/o mantenere ordinato un insieme di dati, secondo un certo criterioIl caso più frequente è il vettore mono-dimensionale: ordine lineare (totale o parziale)L’indice di un dato indica la posizione nell’ordinamento

12

Vettore e dati ordinati (2/2)

EsempiOrdinare dati mediante criterio cronologico (inverso all’input) o secondo valori (crescenti/decrescenti)Sequenze di campioni (numeri) di grandezze fisicheCalcoli matematici e/o statistici su successioni di numeri

14

Corrispondenza indice ↔ dato

Ad ogni indice (intero nell’intervallo 0..NDATI-1) corrisponde un dato (e viceversa)

...

012345678...

“Ancona”

“Bari”

“Catania”

“Gorizia”

“Messina”

“Milano”

“Padova”

“Rovigo”

“Torino”

15

Corrispondenza indice ↔ dato

Ad ogni indice (intero nell’intervallo 0..NDATI-1) corrisponde un dato (e viceversa)

...

012345678...

“Ancona”

“Bari”

“Catania”

“Gorizia”

“Messina”

“Milano”

“Padova”

“Rovigo”

“Torino”

Indici Dati

16

Da indice a dato

A partire dall’indice, calcolare il dato. Operazioneimmediata, grazie al meccanismo di accesso aivettori

...

012345678...

“Ancona”

“Bari”

“Catania”

“Gorizia”

“Messina”

“Milano”

“Padova”

“Rovigo”

“Torino”

6 “Padova”

17

Da dato a indice

A partire dal dato, calcolarne l’indice. Operazionenon immediata, in quanto occorre cercare il dato

...

012345678...

“Ancona”

“Bari”

“Catania”

“Gorizia”

“Messina”

“Milano”

“Padova”

“Rovigo”

“Torino”

2 “Catania”

18

Indici e dati (1/3)

La relazione indice ↔ datoOgni casella di un vettore è caratterizzata da un indice (o più indici, nel caso multi-dimensionale) e da un datoLa casella del vettore può essere quindi utilizzata per mettere in relazione indice e dato

19

Indici e dati (2/3)

UtilizzoProblemi in cui esistono relazioni/corrispondenze tra numeri interi e dati (numerici o non numerici)L’intero è associato all’indice di una casella, il dato al contenutoAttenzione!

L’intero (indice) non può essere troppo grandeÈ possibile che occorra un dato vuoto (nullo) per le caselle non utilizzate

20

Indici e dati (3/3)

EsempiCodifica/decodifica numerica di informazioni (non numeriche)Tabulazione di funzione nel piano cartesiano y=f(x), con ascissa intera o riconducibile a intero

2

Problemi numerici

IntroduzioneProblemi su insiemi di numeriProblemi su sequenze di numeriProblemi su statistiche per gruppi

Problemi numerici

4

Introduzione

Problemi di algebra, geometria, statistica, ecc., simili a quelli risolti mediante dati scalariI vettori possono essere utilizzati

Per collezionare e manipolare (insiemi di) numeri Per rappresentare dati di tipo vettoriale/matricialePer gestire corrispondenze tra numeri (indice e dato)

Problemi numerici

6

Problemi su insiemi di numeri

Problemi nei quali si gestiscono insiemi (gruppi) di dati numerici, con operazioni di I/O, unione, intersezione, …La soluzione spesso si basa su costrutti iterativi(eventualmente annidati) tali da

Percorrere gli elementi di un insiemePercorrere, per ogni elemento di un insieme, tuttigli elementi di un altro insieme

7

Intersezione tra insiemi di numeri

ProblemaAcquisire da tastiera un primo gruppo di 10 interi(privo di numeri ripetuti)Acquisire da tastiera un secondo gruppo di 10 interi (privo di numeri ripetuti)Calcolare e visualizzare tutti i numeri che sonopresenti in entrambi i gruppi

SoluzioneSi tratta di un problema di intersezione tra insiemi, che richiede di determinare, per ogni elemento del primo insieme, se appartiene anche al secondo

8

Strategia

AlgoritmoInput: due iterazioni per acquisire i dati dei due gruppiElaborazioni: doppia iterazione per confrontare tutti i dati del primo gruppo con tutti quelli del secondo (o viceversa)Output: iterazione sui dati dell’insieme intersezione. Le tre parti possono essere distinte, oppure (parzialmente) integrate: mentre si esegue l’input si calcola l’intersezione e si scrivono i risultati in output

9

Strategia

Struttura datiLa scelta dipende dall’algoritmo adottato

È necessario almeno un vettore, per i dati del primo insiemeL’utilizzo di un secondo vettore dipende dal fatto di adottare uno schema

Input, elaborazioni, output, tre fasi separateElaborazioni ed output fatte durante l’input del secondo gruppo (per ogni numero del secondo gruppo, si determina direttamente se appartiene anche al primo e si fornisce il relativo output)

La soluzione proposta utilizza due vettori, con tre fasi separate. Il risultato (intersezione) viene sovrapposto al primo vettore

10

#define NDATI 10#include <stdio.h>void leggiVettore (int *dati, int n);void scriviVettore (int *dati, int n);int main(void) {

int dati0[NDATI], dati1[NDATI];int i, j, ni, trovato;/* input */leggiVettore(dati0,NDATI);leggiVettore(dati1,NDATI);/* calcolo intersezione */.../* output */scriviVettore(dati0,ni);

}

insiemiDiNumeri.c

Intersezione tra insiemi (1/2)

11

.../* calcolo intersezione */for (i=ni=0; i<NDATI; i++) {

trovato=0;for (j=0; j<NDATI&&(!trovato); j++) {

if (dati0[i]==dati1[j])trovato=1;

}/* se dato appartiene ad intersezione

riscrivi nella parte iniziale delvettore dati0 (già confrontato) */

if (trovato)dati0[ni++]=dati0[i];

}

insiemiDiNumeri.c

Intersezione tra insiemi (2/2)

Problemi numerici

13

Problemi su sequenze di numeri

I problemi interessano sequenze di dati (ordinati) che debbono essere immagazzinati in un vettoreprima di venir elaborati, perchè

È necessario attendere l’ultimo dato prima di poterelaborare i datiOppure sono necessarie elaborazioni (ripetute) sututti i dati

Non si possono trattare sequenze infinite, ma insiemi (ordinati) finiti di dati, organizzato in vettori mono- o multi-dimensionali (matrici)

14

Normalizzazione di dati

ProblemaScrivere una funzione C che

Acquisisca da file testo una sequenza di dati reali: La prima riga contiene il numero N (intero) di datiSeguono i dati (reali) separati da spazi o a-capo

Determini, per l’i-esimo dato di (0≤i<N), le mediedei dati predecedenti (pi) e dei successivi (si)Scriva su un secondo file i dati, normalizzatisecondo la seguente regola:

Ogni dato (di) viene sostituito dalla media aritmeticatra di, pi e si

I nomi dei due file sono ricevuti come parametri

15

Strategia

SoluzioneOccorre calcolare, in modo iterativo, le medie, quindi, con una successiva iterazione, le normalizzazioni dei dati

Struttura datiUn vettore per acquisire i dati dal file Un vettore per calcolare le medie

Si potrebbero evitare i vettori rileggendo più volte il file (soluzione suggerita come esercizio)

16

Strategia

AlgoritmoInput: vettore dinamico e lettura iterativaElaborazioni: è sufficiente calcolare

La sommatoria di tutti dati (STOT)Per ogni dato, la somma dei predecessori (sommei) A partire da questa è possibile calcolare

pi = sommei/i, si = (STOT-di-sommei)/(N-i-1)

I valori normalizzati (sostituendo i dati sul vettore iniziale)

Output del vettore ricalcolato

17

void normalizzaNumeri (char *nfin, char *nfout

) {float *dati, *somme;int i, j, N, STOT;/* input */dati = leggiDaFile(nfin,&N);/* alloca e calcola somme parziali */somme = malloc(N*sizeof(float));somme[0]=dati[0];for (i=1; i<N; i++)

somme[i] = somme[i-1]+dati[i];STOT = somme[N-1];...

}

normalizzaNumeri.c

Funzione normalizzaNumeri (1/2)

18

void normalizzaNumeri (char *nfin, char *nfout

) {.../* normalizza */dati[0] = (dati[0] + (STOT-dati[0])/(N-1))/2;for (i=1; i<N-1; i++)

dati[i] = (dati[i] + somme[i-1]/i +(STOT-somme[i]-dati[i])/(N-i-1))/3;

dati[N-1] = (dati[N-1] + somme[N-2])/2;/* output */scriviSuFile(nfout,dati,N);free(dati); free(somme);

}

normalizzaNumeri.c

Funzione normalizzaNumeri (2/2)

Problemi numerici

20

Problemi su statistiche per gruppi

I problemi sono caratterizzati dalla suddivisionedei numeri in classi/gruppi numerabili ed identificabili da un interoLa raccolta di conteggi o dati statistici può essereeffettuata sulle caselle di un vettore

A ogni classe o gruppo corrisponde un indice (e una casella del vettore)

21

Suddivisione in classi (1/2)

ProblemaScrivere una funzione C che

Riceva come parametro un vettore di interi di valore compreso tra 0 e 100 (il secondo parametroindica la dimensione del vettore)Suddivida gli interi in decine, calcoli e visualizzi i conteggi dei numeri appartenenti a ciascunadecina

22

Suddivisione in classi (2/2)

Esempio: si supponga di ricevere i seguenti 20 valori:

3 6 9 16 22 23 30 32 40 48 65 78 7 8 10 15 25 90 27 26

I numeri saranno raggruppati come segue:(3, 6, 9, 7, 8), (16, 10, 15), (22, 23, 25, 26, 27), (30, 32), (40, 48), (-), (65), (78), (-), (90), (-)

I conteggi visualizzati saranno:5, 3, 5, 2, 2, 0, 1, 1, 0, 1, 0

23

Strategia

SoluzioneOccorre utilizzare un vettore di contatori, sfruttando la corrispondenza indice-dato. Per ogni dato in ingresso si calcola l’indice corrispondente alla decina di appartenenza, e si aggiorna il relativo contatore

Struttura datiUn vettore di interi come parametro alla funzioneUn vettore di contatori (con indici da 0 a 100)

24

Strategia

AlgoritmoAzzeramento dei contatori, per ogni decina (le decine sono numerate da 0 a 10)Iterazione sui dati interi. Per ognuno

Si calcola la decina di appartenenza Si accede al vettore dei conteggi (utilizzando la decina come indice) incrementando il contenuto

Iterazione sui contatori per visualizzare i conteggi

25

void contaPerDecine (int *dati, int n){

int i, d, conta[11];for (i=0; i<=10; i++) conta[i]=0;for (i=0; i<n; i++)

d = dati[i]/10;conta[d] = conta[d]+1;

}for (i=0; i<=10; i++)

printf (“%d “, conta[i]);printf(“\n”);

}

Funzione contaPerDecine

2

Problemi di codifica/decodifica

IntroduzioneCodifica di numeriCodifica di caratteri

4

Introduzione

Problemi nei quali occorre riconoscere o generare la codifica di informazioni di carattere numerico o non numericoI vettori possono essere utilizzati per

Tabelle di codifica o conversioneContenitori per generazione e/o modifica dei codici

6

Problemi di codifica di numeri

Nei problemi di codifica di numeri, i vettoripossono essere utilizzati

Per immagazzinare le cifre in una data codificaManipolare i numeri, lavorando a livello di codificain cifre

7

Codifica binaria di un intero

ProblemaRealizzare una funzione C che, ricevuto come parametro un intero (>=0)

Ne determini la codifica binaria e visualizzi i bit

SoluzioneCostruzione iterativa dei bit, a partire dai menosignificativiDivisioni successive per 2, i resti delle divisionisono i bit della codifica

8

Strategia

Struttura dati Un parametro formale (intero): nUn vettore (bit) per i bit della codifica

Algoritmo Iterazione per generare, in bit, i bit, a partire dai meno significativi (al massimo 32 bit)Iterazione per visualizzare i bit (dal piùsignificativo)

9

void binarioVettore (int n){int i, n, bit[32];i=0;do {bit[i++] = n%2;n = n/2;

} while (n>0);while (i>=0) {printf(“%d”,bit[i--]);

}printf(“%d\n”,n);

}

Numero binario

10


} while (n>0);while (i>=0) {printf(“%d”,bit[i--]);


}

Numero binario

Calcola bit meno significativo

11


} while (n>0);while (i>0) {printf(“%d”,bit[--i]);


}

Numero binario

Continua finchè n non è 0Se inizialmente n=0 calcola 1 bit

13

Codifica di caratteri

Problemi di codifica, ricodifica o crittografiaapplicati a testi, nei quali un vettore può essereutilizzato per

Tabella di codifica o ricodificaMediante la corrispondenza indice-datoCome insieme di coppie dato-codice o codice0-codice1

Raccoglitore (ordinato o non) per dati intermedi

14

Crittografia mediante tabella

ProblemaCrittografare il contenuto di un file testo, immagazzinando il risultato in un secondo fileI codici dei caratteri vengono modificati, in base allatabella di ricodifica contenuta in un file:

Ogni riga del file contiene due numeri interi (compresitra 0 e 255), che rappresentano, rispettivamenteLa codifica ASCII di un carattere, il codice ASCII del carattere ricodificatoI codici non presenti non vanno modificatiLa tabella garantisce l’univocità della ricodifica

15

Crittografia mediante tabella (1/2)

SoluzioneLeggere la tabella da file, costruendo una vettore di ricodifica indice (codice iniziale) → dato (nuovocodice)Leggere iterativamente i caratteri dal primo file

Calcolare la ricodifica del carattereScrivere il carattere sul secondo file

16

Crittografia mediante tabella (2/2)

Struttura datiDue variabili di tipo FILE* per gestire i due file in lettura e scrittura; una stringa per i nomi dei file Un vettore di caratteri per la tabella di ricodificaUna variabile char per lettura e ricodifica dei caratteri

17

Strategia

AlgoritmoAcquisizione dei nomi di file e loro aperturaInizializzazione della tabella di codifica (per codici invariati)Lettura tabella di ricodificaIterazione di lettura di un carattere, ricodifica, scrittura nel secondo file

La ricodifica viene fatta mediante passaggio indice → dato nella tabella

18

Crittografia a tabella: programma (1/2)

#define MAXRIGA 30int main(void){char ch, nomefile[MAXRIGA];char tabella[256];FILE *fpin, *fpout, *ftab;int i, nuovo;printf(“nome file in ingresso: “);scanf(“%s”, nomefile);fpin = fopen(nomefile,”r”);printf(“nome file in uscita: “);scanf(“%s”, nomefile);fpout = fopen(nomefile,”w”);...

crittografiaTabella.c

19

Crittografia a tabella: programma (2/2)

...printf(“nome file tabella: “);scanf(“%s”, nomefile);ftab = fopen(nomefile,”r”);for (i=0; i<256; i++)tabella[i] = (char)i;

while (fscanf(ftab,“%d%d”,&i,&nuovo)==2)tabella[i] = (char)nuovo;

while (!feof(fpin)) {fscanf(fpin, “%c”, &ch);fprintf(fpout,”%c”,tabella[(int)ch]);

}fclose(fpin);fclose(fpout);fclose(ftab);

}

crittografiaTabella.c

2

Problemi testuali

IntroduzioneSelezione basata su stringheElaborazione di testi carattere per carattereElaborazione di testi mediante stringhe

Problemi testuali

4

Introduzione

Problemi nei quali occorre manipolare sequenze di caratteri e/o stringhe. Es. costruzione o modifica di testo, creazione di messaggio in un dato formatoVettori (o matrici) di caratteri (o di stringhe) sono spesso necessari per

Generazione di testi a partire da regole o funzioniTrasformazione di testi esistenti

Problemi testuali

6

Vettori e selezione su stringhe

La selezione basata direttamente su stringherichiede confronti (strcmp) e costrutticondizionali if (non sono possibli switch)I vettori (usati come tabelle) possono consentirela traduzione da codici testuali a codici numerici, con cui

È possibile la selezione mediante switch

Si ottiene una migliore gestione/organizzazione deicasi da trattareSi ottengono informazioni più compatte, trasferibilitra moduli, come parametri o valori di ritorno di funzioni (es. Codici di errore)

7

La tabella di conversione (A)

Per la conversione da stringa a intero si puòutilizzare la corrispondenza dato → indice

...

012345678

...

“Gennaio”

“Febbraio”

“Marzo”

“Agosto”

......

8



...

012345678

...

“Gennaio”

“Febbraio”

“Marzo”

“Agosto”

......

Si cerca la riga contenente il nome

“Marzo”

9



...

012345678

...

“Gennaio”

“Febbraio”

“Marzo”

“Agosto”

......

Si ritorna l’indice corrispondente

“Marzo”2

10

La tabella di conversione (B)

Se i valori interi sono grandi (non adatti come indici) si può realizzare un vettore di struct (codice,nome)

...

...

“Gennaio”

“Febbraio”

“Marzo”

“Agosto”

012345678

30110020491901050

64506

11

La tabella di conversione (B)

Se i valori interi sono grandi (non adatti come indici) si può realizzare un vettore di struct (codice,nome)

...

...

“Gennaio”

“Febbraio”

“Marzo”

“Agosto”

012345678

30110020491901050

64506Si cerca la riga contenente il nome

“Marzo”

12

Menu con scelta su una parola

Scrivere una funzione che, iterativamente, acquisisca da tastiera una stringa (al massimo 50 caratteri, contenente eventuali spazi)

La prima parola diversa da spazio costituisce il selettoreSe la parola è “fine”, occorre terminare l’iterazioneSe la parola è uno tra “cerca”, “modifica”, “stampa” (ignorare differenza maiuscole/minuscole), occorre attivare, rispettivamente, le funzioni cerca, sostituisci, stampa, passando loro come parametro il resto della stringa (oltre la parola di selezione)Ogni altra parola va segnalata come errata

13

Soluzione (corrispondenza dato-indice)

ModularizzazioneDefinizione costanti enumerative (per codici)Vettore di stringhe (tabella)Funzione di input e conversione da stringa a codice

Gestione costanti mediante tipo enumIl tipo enum è assimilabile ad un intervallo di valori interi 0..N, con N = numero_di_valori-1

TabellaVettore inizializzato mediante (puntatori a ) costanti stringa

Conversione da stringa a codiceIterazione di ricerca su vettore

14

const int MAXL=51;typedef enum {

c_cerca, c_modifica, c_stampa, c_fine, c_err

} t_comandi;void menuParola (void){

t_comandi codiceComando;char riga[MAXL];int i, continua=1;while (continua) {codiceComando = leggiComando();gets(riga); /* resto della riga */...

}}

Funzione menuParola (1/2)

menuParolaVet.c

15





}}


menuParolaVet.c

Definizione tipo enumerativo per i codici di comando corrispondenti agli interi da 0 a 4

16





}}


menuParolaVet.c

Lettura comando e conversione da stringa a codice

17

while (continua) {...switch (codiceComando) {

case c_cerca: cerca(riga);break;

case c_modifica: sostituisci(riga);break;

case c_stampa: stampa(riga);break;

case c_fine: continua=0;break;

case c_err:default: printf (“comando errato\n”);

}}


menuParolaVet.c

18

t_comandi leggiComando (void){

t_comandi c;char cmd[MAXL];char *tabella[c_err] = {

“cerca”,”modifica”,”stampa”,”fine”}printf(“comando (cerca/modifica“);printf(“/stampa/uscita): “);scanf(“%s”,cmd); strToLower(cmd);c=c_cerca;while (c<c_err && strcmp(cmd,tabella[c])!=0)

c++;return (c);

}

Funzione leggiComando

menuParolaVet.c

19

t_comandi leggiComando (void){

t_comandi c;char cmd[MAXL];char *tabella[c_err] = {

“cerca”,”modifica”,”stampa”,”fine”}printf(“comando (cerca/modifica“);printf(“/stampa/uscita): “);scanf(“%s”,cmd); strToLower(cmd);c=c_cerca;while (c<c_err && strcmp(cmd,tabella[c])!=0)

c++;return (c);

}

Funzione leggiComando

menuParolaVet.c

Problema di selezione/ricerca(vedi lezione successiva)

Problemi testuali

21

Manipolare testi a livello carattere

Un testo può essere costruito o modificato a livello di caratteri utilizzando un vettore o unamatrice come

Rappresentazione (a caratteri) del testo daesaminareArea dati temporanea per costruire o manipolareuna stringa o una matrice di caratteri

22

Elaborazione di parole o frasi

Una parola (o una frase), può essere analizzata a livello di singoli caratteriUn vettore si rende necessario se occorre accedere direttamente ai caratteri Esempi

Verifica di palindromiaTaglia e incolla parte di stringa da una prima ad una seconda collocazioneRicerca/sostituzione di sottostringa

23

Parola palindroma (1/2)

Si realizzi una funzione C in grado di verificare se una stringa, ricevuta come parametro, sia o meno palindroma (trascurando la differenza tra caratteri maiuscoli e minuscoli)

Una parola si dice palindroma se letta dall’ultimo al primo carattere, risulta invariataEsempi di palindromia: Anna, madam, otto, abcdefgFEDCBA

24

Parola palindroma (2/2)

SoluzioneIl vettore è la stringa stessa ricevuta come parametro Algoritmo: iterazione di confronto tra caratteri corrispondenti (primo-ultimo, secondo-penultimo, …)

25

int palindroma (char *parola, int n){

int i, pal=1;

for (i=0; i<n/2; i++)if (toupper(parola[i]) !=

toupper(parola[n-1-i]))pal = 0;

return pal;}

Funzione palindroma

26

Costruzione di figure/grafici

Le figure o grafici rappresentati su video visto come matrice di caratteri di 25 righe e 80 colonne, possono essere preparate su una matrice di caratteri

Ciò consente di costruire la figura senza rispettare la successione di righe che caratterizza l’output sequenziale (su video o su file testo)La figura viene preparata su una matrice di caratteri, sfruttando l’accesso diretto ad ogni casellaLa figura viene successivamente stampata seguendo la successione sequenziale tra righe

27

Grafico di funzione (con asse Ox orizzontale)

ProblemaÈ data la parabola di equazione

y = ax2 + bx + c = 0Si scriva un programma che,

Acquisisca da tastiera i coefficienti a, b, c, e i valori degli estremi (xmin, xmax) e (ymin, ymax), rispettivamente di un intervallo per le ascisse e per le ordinateStampi, in un rettangolo di 20 righe per 70 colonne, un grafico (con asse delle ascisse orizzontale) che rappresenti la funzione nel rettangolo del piano cartesiano compreso negli intervalli [xmin,xmax], [ymin,ymax]

28

Esempio di esecuzione

Coefficienti (a b c): 1.0 2.0 1.0Intervallo per ascisse: -1.0 4.0Intervallo per ordinate: -1.0 10.0

**

***

***

*****

****

*****

******

**********

******

29

Struttura dati

Sono sufficienti variabili scalari, per rappresentareCoefficienti: a, b, c (float)Intervalli: xmin, xmax, ymin, ymax (float)Dati intermedi: passoX passoY (lunghezza degli intervalli) x, y (float)Indici: i, j (int)

È necessaria una matrice (di char) per costruire il grafico

30

Algoritmo

Input dati e calcolo passo (= lunghezza intervalli)Inizializzazione matrice di caratteriIterazione su valori di x

Calcolo y(x)Se è nell’intervallo [ymin,ymax] converti in intero (j) e assegna ‘*’ nella matrice

Iterazioni su righe e colonne, per stampare matrice

31

#include <stdio.h>#include <math.h>const int NR=20, NC=70;int main(void){

float a,b,c,x,y,passoX,passoY,xmin,xmax,ymin,ymax;

int i, j, n;char pagina[NR][NC];printf(“Coefficienti (a b c): “);scanf(“%f%f%f”,&a,&b,&c);printf(“Intervallo per ascisse: “);scanf(“%f%f”,&xmin,&xmax);printf(“Intervallo per ordinate: “);scanf(“%f%f”,&ymin,&ymax);

graficoParabolaOriz.c

Grafico di parabola (1/3)

32

/* inizializza matrice */for (i=0; i<NR; i++)

for (j=0; j<NC; j++)pagina[i][j] = ‘ ‘;

passoX = (xmax-xmin)/(NC-1);passoY = (ymax-ymin)/(NR-1);/* calcola punti della parabola */for (j=0; j<NC; j++) {

x = xmin + j*passoX;y = a*x*x + b*x + c;if (y<ymin || y>ymax) continue;i = (y-ymin)/passoY;pagina[i][j] = ‘*’;

}



33

/* stampa matrice per righe */for (i=NR-1; i>=0; i--){

for (j=0; j<NC; j++) printf(“%c”,pagina[i][j]);

printf(“\n”);}

}



Problemi testuali

35

Manipolare testi a livello di stringhe

Un testo può essere costruito o modificato a livello di stringhe se

È possibile identificare sottostringhe (sequenze di caratteri) sulle quali applicare operazioni di tipounitarioLe operazioni su stringhe debbono trovarsi in libreria, oppure essere chiamate funzioni realizzatedal programmatore

Un vettore può essere necessario per costruire o immagazzinare temporaneamente stringhe daelaborare

36

Formattazione di testo (1/2)

ProblemaÈ dato un file testo, le cui righe sono scomponibili in sottostringhe (di non più di 20 caratteri) separate da spazi (oppure ‘\t’ o ‘\n’)Si realizzi una funzione C che, letto il file, ne copi il contenuto in un altro file, dopo aver

Ridotto le sequenze di più spazi ad un solo spazioInserito (in sostituzione di spazi) o eliminato caratteri a-capo (‘\n’) in modo tale che ogni riga abbia la massima lunghezza possibile, minore o uguale a lmax (terzo parametro della funzione) Centrato il testo rispetto alla lunghezza lmax

37

Formattazione di testo (2/2)

SoluzioneLa soluzione è simile al problema senza centratura del testoPer effettuare la centratura occorre tutta una riga di testo prima di stamparla (per calcolare il numero di spazi da stampare)

Si può utilizzare un vettore come buffer La centratura (su lmax caratteri) di una riga di lcaratteri, si effettua stampando, prima della riga, (lmax-l)/2 spazi

38

void formatta (char *nin, char *nout, int lmax

) {const int STRLEN=21;FILE *fin=fopen(nin,”r”);FILE *fout=fopen(nout,”w”);char parola[STRLEN], *riga;int i,l;

l=0;riga = malloc(lmax*sizeof(char));while (fscanf(fin,”%s”,parola)>0) {...

}fclose(fin); fclose(fout);

}

formattaCentraTesto.c

Programma di formattazione (1/2)

39

while (fscanf(fin,”%s”,parola)>0) {if (l+1+strlen(parola) > lmax) {

for (i=0; i<(lmax-l)/2; i++)fprintf(fout,” “);

fprintf(fout,”%s\n”,riga);strcpy(riga,parola);l=strlen(parola);

}else {

strcat(riga,” “); strcat(riga,parola);l+=1+strlen(parola);

}}

Programma di formattazione (2/2)

formattaCentraTesto.c

2

Problemi di verifica e filtro dati

IntroduzioneVerifiche su sequenze di datiSelezione o ricerca di dati

4

Introduzione (1/2)

I problemi di verifica consistono nel decidere se un insieme di informazioni o dati rispettano un determinato criterio di accettazioneSelezionare significa verificare i dati e scegliere quelli che corrispondono al criterio di verificaLa ricerca è una delle modalità di selezione

Spesso si cerca il dato che corrisponde a un criterioTalvolta i dati possono essere molteplici

5

Introduzione (2/2)

I vettori possono essere utilizzatiCome contenitori per l’insieme di dati, su cui applicare il criterio di verificaCome insieme dei dati tra i quali ricercare/selezionare

7

Verifiche su sequenze

Verificare una sequenza di dati significa deciderese la sequenza rispetta un criterio di accettazioneUn vettore può essere necessario nel caso di criterio di accettazione che richieda elaborazionisu tutti i dati

8

Dati ripetuti (1/2)

ProblemaUn file testo contiene una sequenza di datinumerici (reali)

La prima riga del file indica (mediante un intero) quanti sono i dati nella sequenzaSeguono i dati, separati da spazi o a-capo

Si scriva una funzione C che, ricevuto come parametro il puntatore al file (già aperto), verifichiche ogni dato sia almeno ripetuto una volta nellasequenza

Un dato si considera ripetuto se, nella sequenza, se ne trova almeno un altro tale che la loro differenza, in valore assoluto, sia inferiore a 1%

9

Dati ripetuti (2/2)

SoluzioneAnalizzare i dati, mediante una doppia iterazione, verificando, per ognuno, che ne esista almeno unouguale (differenza ≤ 1% rispetto al massimo tra i due in valore assoluto)

Struttura datiVettore per contenere i dati letti da fileVariabili scalari: indici e altro

AlgoritmoAcquisizione dati, su vettore dinamicoVerifica mediante doppia iterazione

10

int datiRipetuti (FILE *fp){

float *dati;int ndati, i, j, ripetuto;fscanf(fp,“%d”,&ndati);dati = malloc (ndati*sizeof(float));for (i=0; i<ndati; i++)

fscanf(fp,“%f”,&dati[i]);for (i=0; i<ndati; i++) {

ripetuto = 0;for (j=0; j<ndati; j++)

if (i!=j && simili(dati[i],dati[j]))ripetuto=1;

if (!ripetuto) return 0;}return 1;

}

Funzione datiRipetuti

11

int simili (float a, float b){

if (abs(a)>abs(b))return (abs(a-b)/abs(a) < 0.01);

elsereturn (abs(a-b)/abs(b) < 0.01);

}

Funzione simili

13

Selezione di dati

Contestualmente alla verifica di più dati (o sequenze/insiemi) di dati, è possibile discriminarei dati (o il dato) che corrispondono al criterio di verifica, rispetto agli altriLa selezione può essere vista come una variantedella verifica:

I dati vengono dapprima verificatiQuelli (o quello) che corrispondono al criterio di accettazione vengono scelti

La ricerca è un caso particolare di selezioneSi seleziona il dato (se esiste) che corrisponde al criterio di ricerca

14

Conversione matricola→nome (1/2)

ProblemaSi realizzi una funzione C in grado di determinare ilnome di uno studente, a partire dal numero di matricola (primo parametro alla funzione)Siccome i numeri di matricola sono grandi (6 cifredecimali) non si vuole sfruttare la corrispondenzaindice-dato in un vettore. Le matricole sonorappresentate mediante stringheLa tabella di conversione è fornita, come secondoparametro alla funzione, mediante un vettore di struct, aventi come campi (stringhe) numero di matricola e nome. Il terzo parametro (intero) è la dimensione della tabella

15

SoluzioneAnalizzare iterativamente i dati nel vettore, confrontando di volta in volta la matricola correntecon quella richiesta

Struttura datiLa tabella è un vettore (fornito come parametro)Il numero di matricola richiesto (secondoparametro) è una stringa

AlgoritmoLa ricerca consiste in una verifica dei datiLa funzione ricerca la matricola e ritorna il nomecorrispondente (NULL per indicare fallimento)

Conversione matricola→nome (2/2)

16

typedef struct {char *matricola, *nome;

} t_stud;...char *matrNome(char *m, t_stud *tabella, int n){

int i;for (i=0; i<n; i++) {

if (strcmp(m,tabella[i].matricola)==0)return(tabella[i].nome);

}return NULL;

}

Da matricola a nome

2

Problemi di ordinamento

IntroduzioneOrdinamento di un vettore

4

Introduzione

Un problema di ordinamento consiste nella richiesta di permutare una sequenza di dati, in modo tale che (dopo la permutazione) sia verificato un criterio di ordinamentoPer ordinare dei dati in modo totale, si opera molto spesso su un vettore, adatto a fornire una successione lineare di dati, con valori crescenti (o decrescenti) secondo la progressione crescente degli indici

6

Ordinamento mediante selection sort (1/2)

ProblemaSi scriva una funzione C che

Ricevuti come parametri un vettore di numeri interie la sua dimensioneOrdini i dati in modo crescente mediante l’algoritmodi selection sort

Soluzione: selection sortAlgoritmo di ordinamento basato su ripetutericerche di minimo

7

Ordinamento mediante selection sort (2/2)

Struttura dati e algoritmoDati: vettore A di N interi (A[0] ... A[N-1]), diviso in 2 sotto-vettori:

Di sinistra: ordinatoDi destra: disordinato

Un vettore di un solo elemento è ordinatoApproccio incrementale:

Passo i: il minimo del sotto-vettore (A[i] ... A[N-1]) è assegnato a A[i]; incremento di i

Terminazione: tutti gli elementi inseriti ordinatamente

8

Esempio

6 3 5 1 7 21 8 4 12 0 9 8 4

0 3 5 1 7 21 8 4 12 6 9 8 4

0 1 5 3 7 21 8 4 12 6 9 8 4

Già ordinati Non ancora considerati

i min

i min

9

void selectionSort (int A[], int N){

int i, j, imin, temp;for (i=0; i<N-1; i++) {

/*cerca indice del minimo in A[i]..A[N-1]*/imin = i;for (j = i+1; j < N; j++)

if (A[j] < A[imin]) imin = j;/*scambia minimo con A[i]*/temp = A[i];A[i] = A[imin];A[imin] = temp;

}}

Funzione selectionSort

selectionSort.c

10

void selectionSort (int A[], int n){

int i, j, imin, temp;for (i=0; i<n-1; i++) {

/*cerca indice del minimo in A[i]..A[N-1]*/imin = i;for (j = i+1; j < n; j++)

if (A[j] < A[min]) imin = j;/*scambia minimo con A[i]*/temp = A[i];A[i] = A[imin];A[imin] = temp;

}}


selectionSort.c

Iterazione esterna, eseguita n-1 volte

11





}}


selectionSort.c

Iterazione interna, eseguita n-i-1 volte

12





}}


selectionSort.c

Algoritmo in loco, perché scambia i dati sul vettore

13





}}


selectionSort.c

Algoritmo stabile, perché non scambia due dati di ugual valore

14

Chiave di ordinamento

ProblemaOrdinare un vettore di dati strutturatiUno del campi delle strutture è detto chiave di ordinamentoIl confronto tra due dati si basa sulla chiaveLo scambio di dati è fatto su tutta la struttura

EsempioOdinare un insieme di dati su studenti in base a numeri di matricola crescenti

SoluzioneLasciata come esercizio

2

Argomenti trattati

I vettori nel problem solvingI vettori come contenitori di datiVettori ordinatiLa corrispondenza indice ↔ dato

Problemi numericiProblemi di codifica/decodificaProblemi testualiProblemi di verifica e filtro di datiProblemi di ordinamento

3

L’utilizzo dei vettori

Come scegliere se utilizzare o meno un vettoreUn vettore NON è necessario se si può operare su singoli dati senza doverli “ricordare” tuttiUn vettore può essere necessario come

Contenitore di dati (eventualmente ordinati)Tabella

Come operare sui vettoriUn vettore può essere utilizzato mediante accesso iterativo a tutti i (o parte dei) datiL’accesso diretto a una casella (dati l’indice) permette operazioni di corrispondenza indice-dato

4

Suggerimenti

Dato un problemaDeterminare se siano necessari o meno vettoriDecidere se siano necessari vettori dinamici o statici (dimensioni note o vettore sovra-dimensionabile)

Dato un vettoreAttenzione agli accessi non validi (indici fuori dai limiti) non verificati dal CNel caso di vettori di stringhe, il vettore di puntatori a stringhe è più efficace per spostamenti di dati (basta copiare i puntatori e non i caratteri)

5

Materiale aggiuntivo

Sul CD-ROMTesti e soluzioni degli esercizi trattati nei lucidiScheda sinteticaEsercizi risoltiEsercizi proposti

Esercizi proposti da altri libri di testo

Programmazione in C

2


I vettori nel problem solvingProblemi numericiProblemi di codifica/decodificaProblemi testualiProblemi di verifica e filtro di datiProblemi di ordinamentoSommario

3

Riferimenti al materiale

TestiKernighan & RitchieCabodi, Quer, Sonza ReordaDietel & Dietel

DispenseScheda: “Problem solving elementare su dati scalari”

Problem solving elementare su dati...

Documents

Transcript of Problem solving elementare su dati...