Esercizi su web per il testo Informatica: Arte e mestiere, II...

Dino Mandrioli, Stefano Ceri, Licia Sbattella, Paolo Cremonesi, Gianpaolo Cugola

Informatica: arte e mestiere

IV edizione

Esercizi aggiuntivi (con soluzione)

Informatica: Arte e Mestiere, Quarta edizione Esercizi

Capitolo 1 Introduzione..............................................................................................................6Esercizio 1.1*............................................................................................................................6Esercizio testo 1.11...................................................................................................................6

Capitolo 2 Architettura di un calcolatore.................................................................................7Premessa agli esercizi relativi a questo capitolo.......................................................................7Esercizio 2.1..............................................................................................................................9Esercizio 2.2..............................................................................................................................9Esercizio 2.3..............................................................................................................................9Esercizio 2.4............................................................................................................................10Esercizio 2.5............................................................................................................................10Esercizio 2.6............................................................................................................................10Esercizio 2.7 *IND*................................................................................................................11Esercizio 2.8............................................................................................................................11Esercizio 2.9............................................................................................................................11Esercizio 2.10 *IND*..............................................................................................................12

Capitolo 3 Codifica degli algoritmi in un linguaggio di alto livello.....................................13Esercizio 3.1............................................................................................................................13Esercizio 3.2............................................................................................................................13Esercizio 3.3............................................................................................................................16

Capitolo 4 Esecuzione di programmi C su macchine reali....................................................17Esercizio 4.1............................................................................................................................17Esercizio 4.2............................................................................................................................18Esercizio 4.3............................................................................................................................19Esercizio 4.4............................................................................................................................20

Capitolo 5 Tipi di dati...............................................................................................................21Esercizio 5.1............................................................................................................................21Esercizio 5.2............................................................................................................................21Esercizio 5.3............................................................................................................................22Esercizio 5.4............................................................................................................................23Esercizio 5.5............................................................................................................................23Esercizio 5.6............................................................................................................................24Esercizio 5.7............................................................................................................................25Esercizio 5.8............................................................................................................................25Esercizio 5.9............................................................................................................................27Esercizio 5.10..........................................................................................................................27Esercizio 5.11..........................................................................................................................28Esercizio 5.12 *IND*..............................................................................................................29Esercizio 5.13 *IND*..............................................................................................................30Esercizio 5.14 *IND*..............................................................................................................31Esercizio 5.15..........................................................................................................................32

D.Mandrioli, S. Ceri, L. Sbattella, P. Cremonesi, G. Cugola, Informatica. Arte e mestiere, 4e, © McGraw-Hill Education (Italy) srl 2


Capitolo 6 Strutture di controllo.............................................................................................36Esercizio 6.1............................................................................................................................36Esercizio 6.3............................................................................................................................37Esercizio 6.4............................................................................................................................38Esercizio 6.5............................................................................................................................40Esercizio 6.6............................................................................................................................40Esercizio 6.7............................................................................................................................42Esercizio 6.8............................................................................................................................43Esercizio 6.9............................................................................................................................44Esercizio 6.10..........................................................................................................................45

Capitolo 7 Funzioni e procedure..............................................................................................46Esercizio 7.1............................................................................................................................46Esercizio 7.2............................................................................................................................46Esercizio 7.3............................................................................................................................47Esercizio 7.4............................................................................................................................48Esercizio 7.5............................................................................................................................49Esercizio 7.6............................................................................................................................50Esercizio 7.7............................................................................................................................52

Capitolo 8 Introduzione alla programmazione ricorsiva......................................................53Esercizio 8.1............................................................................................................................53Esercizio 8.2............................................................................................................................53Esercizio 8.3............................................................................................................................54Esercizio 8.4............................................................................................................................54Esercizio 8.5............................................................................................................................55Esercizio 8.6............................................................................................................................56Esercizio 8.7............................................................................................................................56

Capitolo 9 Gestione dei file.......................................................................................................58Esercizio 9.1............................................................................................................................58Esercizio 9.2............................................................................................................................59Esercizio 9.3............................................................................................................................62Esercizio 9.4............................................................................................................................63Esercizio 9.5............................................................................................................................64Esercizio 9.6............................................................................................................................65Esercizio 9.7............................................................................................................................69Esercizio 9.8............................................................................................................................72Esercizio 9.9............................................................................................................................74Esercizio 9.10..........................................................................................................................75Esercizio 9.11..........................................................................................................................77Esercizio 9.12..........................................................................................................................79Esercizio 9.13..........................................................................................................................81



Capitolo 10 Strutture dati dinamiche......................................................................................83Esercizio 10.1..........................................................................................................................83Esercizio 10.2..........................................................................................................................84Esercizio 10.3..........................................................................................................................87Esercizio 10.4..........................................................................................................................89Esercizio 10.5..........................................................................................................................92Esercizio 10.6..........................................................................................................................94Esercizio 10.7..........................................................................................................................95Esercizio 10.8..........................................................................................................................97Esercizio 10.9..........................................................................................................................97Esercizio 10.10......................................................................................................................101Esercizio 10.11......................................................................................................................104Esercizio 10.12......................................................................................................................105Esercizio 10.13......................................................................................................................106

Capitolo 11 Tipi di dato astratti, classi, e la programmazione a oggetti in Java..............108Esercizio 11.1........................................................................................................................108Esercizio 11.2........................................................................................................................108Esercizio 11.3........................................................................................................................109Esercizio 11.4........................................................................................................................110Esercizio 11.5........................................................................................................................112Esercizio 11.6........................................................................................................................113Esercizio 11.7........................................................................................................................115Esercizio 11.8........................................................................................................................115Esercizio testo 11.4...............................................................................................................116Esercizio testo 11.8...............................................................................................................116

Capitolo 12 Estensioni dell’architettura di von Neumann..................................................118Esercizio 12.1........................................................................................................................118Esercizio 12.2........................................................................................................................118Esercizio 12.3........................................................................................................................119Esercizio 12.4........................................................................................................................119Esercizio 12.5........................................................................................................................120

Capitolo 14 Archivi e basi di dati...........................................................................................122Esercizio 14.1........................................................................................................................122Esercizio 14.2........................................................................................................................122Esercizio 14.3........................................................................................................................123Esercizio 14.4........................................................................................................................123

Capitolo 17 Sicurezza dei calcolatori e delle reti..................................................................125Esercizio 17.1........................................................................................................................125



Capitolo 18 La visione dei sistemi informatici da parte dell’utente finale.........................127Esercizio 18.1........................................................................................................................127Esercizio 18.2........................................................................................................................127Esercizio 18.3........................................................................................................................127Esercizio 18.5........................................................................................................................129

Capitolo 19 La produzione industriale del software............................................................130Esercizio 19.1........................................................................................................................130Esercizio 19.2........................................................................................................................130Esercizio 19.3........................................................................................................................130Esercizio 19.4........................................................................................................................131Esercizio 19.5........................................................................................................................131Esercizio 19.6........................................................................................................................132Esercizio 19.7........................................................................................................................132Esercizio testo 19.3...............................................................................................................133Esercizio testo 19.4...............................................................................................................133Esercizio testo 19.5...............................................................................................................134Esercizio testo 19.7...............................................................................................................134Esercizio testo 19.8...............................................................................................................136Esercizio testo 19.10.............................................................................................................136Esercizio testo 19.11.............................................................................................................136Esercizio testo 19.13.............................................................................................................137



Capitolo 1Introduzione

Esercizio 1.1*Si consideri il seguente problema: una tavoletta di cioccolato rettangolare consiste di h.k “quadratini” (h righe e k colonne) e la si vuole dividere in modo da poter distribuire un quadratino a testa ad altrettanti bambini. La suddivisione deve avvenire spezzando sempre una porzione di tavoletta lungo una riga o colonna: ad esempio se una porzione è di 5 righe e due colonne e la spezzo lungo la terza riga ne ottengo due nuove porzioni, rispettivamente 3.2 e 2.2. Si procede quindi con suddivisioni successive fino ad ottenere esattamente h.k quadratini singoli.Quante operazioni di spezzamento sono necessarie per giungere allo scopo? esistono strategie di spezzamento migliori di altre, ossia che portano a un numero totale di operazioni inferiore ad altre? In tal caso che cosa si può ottenere da una strategia ottima?

Soluzione dell’Esercizio 1.1Anche se ad ogni operazione è possibile scegliere in diversi modi come spezzare la porzione di tavoletta –lungo una riga o lungo una colonna, in quale posizione- l’effetto di ogni spezzamento sarà di aumentare di un’unità il numero di pezzi della tavoletta: la prima volta dalla tavoletta intera si otterranno due pezzi, indipendentemente dalle loro dimensioni, la seconda volta uno dei due pezzi verrà spezzato in due ulteriori pezzi e così via. Di conseguenza, dovendo ottenere esattamente h.k pezzi di dimensione unitara (1.1) qualsiasi ordine si scelga per procedere ai diversi spezzamenti, alla fine ne serviranno comunque h.k - 1.

Soluzioni di esercizi del testoEsercizio testo 1.11La difficoltà principale di questo problema consiste nel dover integrare le informazioni contenute nelle varie “tavole” della cartina. Un modo per affrontarla è il seguente:

1. Si trasformi la rappresentazione planimetrica tipica delle cartine urbane in una forma più “astratta” analoga a quella usata nella Figura 1.3 dell’esempio esteso: gli incroci possono essere rappresentati mediante nodi e le strade mediante archi che congiungono i vari nodi; ad ogni arco viene associata la distanza in metri come nelle altre carte automobilistiche.Quando una via “esce” dalla cartina per proseguire in una cartina contigua la si “termini” con un nodo fittizio etichettato con il nome della via (si suppone che esso sia univoco).

2. Si costruisca poi un unico grafo giustapponendo i vari grafi ottenuti dalle cartine locali e unificando i nodi (provvisoriamente) etichettati con il nome della via. La distanza da associare al nuovo arco è la somma delle distanze parziali ricavate nelle due tavole confinanti (nel caso una via attraversi più di due tavole, lo schema può essere facilmente generalizzato).

3. A questo punto è possibile applicare lo stesso algoritmo sviluppato nell’esempio esteso.



Capitolo 2Architettura di un calcolatore

Premessa agli esercizi relativi a questo capitoloPer facilitare la soluzione degli esercizi che richiedono lo sviluppo di codice nel linguaggio della macchina di von Neumann, si consiglia di usare la seguente versione simbolica del linguaggio, in cui i codici operativi binari sono sostituiti dalle corrispondenti parole chiave indicate in Tabella 2.1 di più facile uso mnemonico. Similmente gli operandi possono essere indicati in numerazione decimale invece che in binario. Sono inoltre fornite alcune ulteriori istruzioni oltre a quelle già fornite nel testo.

Codice simbolico Codice binario Azione

Read xx 0100 Leggi un dato e memorizzalo nella cella xx

Write xx 0101 Scrivi il dato memorizzato nella cella xx

LoadA xx 0000 Carica il registro A con il contenuto della cella xx

LoadB xx 0001 Carica il registro B con il contenuto della cella xx

StoreA xx 0010 Memorizza il contenuto del registro A nella cella xx

StoreB xx 0011 Memorizza il contenuto del registro B nella cella xx

SumAB 0110 Somma il contenuto di A e B e lascia il risultato in A

SubAB 0111 Sottrai il contenuto di B da A e lascia il risultato in A

Branch xx 1110 Salta all’istruzione contenuta nella cella xx

BEQA xx 1001 Se il contenuto del registro A è 0, salta all’istruzione contenuta nella cella xx; altrimenti prosegui

BLA 1101 Se il contenuto del registro A è < 0, salta all’istruzione contenuta nella cella xx; altrimenti prosegui

BGA 1111 Se il contenuto del registro A è > 0, salta all’istruzione contenuta nella cella xx; altrimenti prosegui

ClearA 1010 Azzera il contenuto di A

IncA 1011 Incrementa di 1 il contenuto di A

DecA 1100 Decrementa di 1 il contenuto di A

Inoltre sono stati inseriti alcuni esercizi che richiedono la conoscenza delle diverse modalità di indirizzamento, che non sono state trattate nel testo. La modalità di indirizzamento specifica in che modo si accede all’operando dell’istruzione:

L’indirizzamento diretto indica che l’operando è il contenuto della cella il cui indirizzo è specificato nel relativo campo dell’istruzione; esso è la modalità utilizzata nell’architettura descritta nel testo e non comporta l’aggiunta di alcun simbolo al codice operativo dell’istruzione.

L’indirizzamento immediato –denotato dall’aggiunta del simbolo = al codice operativo dell’istruzione– indica che il contenuto del campo indirizzo è già il valore dell’operando: ad esempio LoadA= 456 significa “carica nel registro A il valore 456, non il contenuto della cella 456”

L’indirizzamento indiretto –denotato dall’aggiunta del simbolo @ al codice operativo dell’istruzione– indica che l’operando è il contenuto della cella il cui indirizzo è a sua



volta contenuto nel campo indirizzo dell’istruzione. Quindi assumendo che la cella 456 contenga il valore 569, l’istruzione LoadA@ 456 significa “carica nel registro A il valore contenuto nella cella 569, non il contenuto della cella 456”.

Gli esercizi che richiedono la conoscenza delle diverse modalità di indirizzamento sono marcati dall’etichetta *IND*.



Esercizio 2.1Si scriva la rappresentazione binaria in complemento a 2 del numero -13,45 assumendo che vengano utilizzati 5 bit per la parte intera e 5 per la parte decimale. Si assuma inoltre che la parte decimale sia espressa in binario come potenze negative di 2, non codificando il numero 45 come un intero separato.

Soluzione dell’Esercizio 2.1La rappresentazione di 13 in binario è 01101; la rappresentazione –approssimata!– di 0,45 in binario è 0,01110; quindi la rappresentazione –approssimata– di 13,45 in binario è 01101,01110. Operando il complemento a 2 con m = 5, ossia sottraendo 13,45 a 2m, si ottiene 10010,10010.

Esercizio 2.2Si trasformi il numero seguente dalla codifica in base 2 alla base 3 (usando almeno 3 cifre dopo la virgola): 1101,011.

Soluzione dell’Esercizio 2.2La rappresentazione binaria 1101,0110 significa (nella abituale base 10): 1·20 + 0·21 + 1·22 +1·23 + 0·2-1 + 1·2-2 + 1·2-3 + 0·2-4 = 13 + 1/4 + 1/8 =1·30 + 3·31 + 1·32 + 1·3-1 + 0·3-2 + 1·3-3 + … (con un resto di 1/24 – 1/27)Quindi la rappresentazione del numero in base 3 –fermandosi alla terza cifra dopo la virgola– è: 111,101.

Esercizio 2.3Si assuma che nella macchina di von Neumann le celle 101 e 102 contengano due numeri interi non negativi. Si scriva una sequenza di istruzioni nel linguaggio della macchina, contenute nelle celle a partire dalla cella 10 che producano rispettivamente, nella cella 111 e 112 il risultato e il resto della divisione intera tra il primo dato e il secondo. È preferibile che il contenuto delle celle 101 e 102 non sia alterato dall’esecuzione delle istruzioni.

Soluzione dell’Esercizio 2.310. LoadA 10211. BEQA 25 /* si verifica che il divisore non sia 0*/12. ClearA13. StoreA 111 /* si inizializza il risultato a 0 */14. LoadB 10115. StoreB 112 /* si inizializza 112 con il dividendo*/16. LoadA 112 /* inizia un ciclo di sottrazioni successiv e*/17. LoadB 10218. SubAB19. BLA 26 /* si terminano le ripetizioni del ciclo*/20. StoreA 11221. LoadA 11122. IncA23. StoreA 111 /* si incrementa la cella per il risultato*/24. Branch 16 /* si ripete il ciclo*/25. Write zzz /* si assume che la cella zzz contenga un messaggio

di errore per segnalare la divisione per 0*/26. …

Esercizio 2.4



Si rappresentino in complemento a due i numeri 45 e 64, usando parole di 16 bit. Quindi si esegua la differenza, in binario, 45 – 64 e si riconverta il risultato in formato decimale.

Soluzione dell’Esercizio 2.445: 000000000010110164: 0000000001000000–64: 111111111100000045-64: 0000000000101101 +

1111111111000000 =1111111111101101

Che è il complemento di 10011, cioè –19, come dovrebbe essere.

Esercizio 2.5Eseguire, in complemento a due l’operazione–13.45 –18.25assumendo di usare celle di 10 bit, di cui 3 per la parte decimale.

Soluzione dell’Esercizio 2.5Utilizzando per caiscun numero 10 bit , di cui 3 riservati alla parte decimale, la codifica binaria in complemento a due dei numeri in questione è pari a:–13,4510 1110010,1012 –18,2510 1101101,1102

Di conseguenza, il risultato dell’operazione richiesta, espresso con una codifica binaria in complemento a due è: 1100000,011 (con l’aggiunta di un ulteriore bit di overflow).

Esercizio 2.6Si consideri la funzione a valori logici f(A, B) definita dalla tabella seguente (dove 0 indica FALSE e 1 indica TRUE)

Si realizzi tale funzione mediante un’opportuna combinazione delle funzioni base OR e NOT (e non altre!).

Soluzione dell’Esercizio 2.6f(A, B) = (NOT (NOT A OR B) OR (NOT (A OR NOT B)

D.Mandrioli, S. Ceri, L. Sbattella, P. Cremonesi, G. Cugola, Informatica. Arte e mestiere, 4e, © McGraw-Hill Education (Italy) srl

A

B

0

1

0 1

0

0

1

1

10


Esercizio 2.7 *IND*Si consideri una macchina la cui parola di memoria sia di 32 bit.Il formato di un’istruzione di tale macchina è organizzato come in figura:I primi h bit contengono il codice operativo, i successivi k bit servono per indicare la modalità di indirizzamento, che può assumere i 3 valori: immediato (denotato dal simbolo = nella versione simbolica) diretto, e indiretto (denotato dal simbolo @ nella versione simbolica). I restanti bit contengono il campo indirizzo dell’istruzione. Tenuto conto che la macchina in questione ha un repertorio di 100 istruzioni, quante celle possono essere indirizzate da una generica istruzione della macchina?

OP-Code: h bit Address mode: k bit Address: r bit

Soluzione dell’Esercizio 2.7Per rappresentare i 3 valori della modalità di indirizzamento occorrono 2 bit, per rappresentare 100 diversi codici operativi occorrono almeno 7 bit. Restano quindi 23 bit per rappresentare l’indirizzo dell’istruzione. Quindi le celle indirizzabili sono 223.

Esercizio 2.8Si rappresentino in complemento a due i numeri 72 e –15, usando parole di 8 bit. Quindi si rappresenti il numero –72,15, assumendo che vengano usati 8 bit per la parte intera e altri 8 bit per la parte decimale, e che la parte decimale sia espressa (in maniera approssimata!) mediante le potenze negative di 2.

Soluzione dell’Esercizio 2.87210 = 010010002

1510 = 000011112

–1510 = 111100012

72,1510 = 01001000,001001102

–72,1510 = 10110111,110110102

Esercizio 2.9Si converta il numero 1027,54 dalla base 10 alla base 7, utilizzando comunque non più di 4 cifre dopo la virgola.

Soluzione dell’Esercizio 2.9La rappresentazione in base 7 di 1027 è 2665, mentre la rappresentazione –approssimata– di 0,54 in base 7 è 0,3531 (ottenuta svolgendo i calcoli con 4 cifre decimali). Dunque, la rappresentazione in base 7 di 1027,54 è 2665,3531


…..…..

11


Esercizio 2.10 *IND*Si vuole leggere da input una sequenza di numeri di lunghezza imprecisata “terminata” da uno zero (di conseguenza, tutti gli altri numeri della sequenza non possono essere zero!); la sequenza va poi riscritta in ordine inverso senza riscrivere il “terminatore zero”.In questo caso si suggerisce di sfruttare il meccanismo di indirizzamento indiretto nel seguente modo: una cella viene destinata a contenere l’indirizzo dove memorizzre di volta in volta i vari elementi della sequenza; ad ogni nuova lettura il suo contenuto viene incrementato di un’unità e il nuovo dato letto viene memorizzato nella cella il cui indirizzo è il contenuto della cella. Successivamente, nella fase di scrittura si procede in ordine inverso decrementando per ogni scrittura il contatore realizzato dalla cella.

Soluzione dell’Esercizio 2.10La cella 101 viene utilizzata come contatore dei numeri letti; la cella 102 contiene l’indirizzo in/da cui memorizzare/prelevare il prossimo elemento della sequenza. I dati letti vengono memorizzati a partire dalla cella 110.

10. ClearA11. StoreA 101 /* inizializza il contatore 101*/12. LoadA= 11013. StoreA 102 /* inizializza l’indirizzo di memorizzazione */14. Read@ 102 /* leggi il prossimo dato e memorizzalo il dato nella

cella “indicata” dalla 102 *15. LoadA@ 10216. BEQA 24 /* se il dato letto è 0 salta a fine ciclo lettura*/17. LoadA 10118. IncA19. StoreA 101 /* incrementa il contatore 101*/20. LoadA 10221. IncA22. StoreA 102 /* incrementa l’indirizzo variabile 102*/23. Branch 14 /* ritorna all’inizio del ciclo*/24. LoadA 10125. BEQA 34 /* se il contatore è 0 salta a fine ciclo */26. LoadA 10127. DecA28. StoreA 101 /* decrementa il contatore 101*/29. LoadA 10230. DecA31. StoreA 101 /* decrementa l’indirizzo 102*/32. Write@ 102 /* scrivi il dato nella cella “indicata” dalla 102 */33. Branch 2634. ...



Capitolo 3 Codifica degli algoritmi in un linguaggio di alto livello

Il nucleo del linguaggio C: input/output semplificato, variabili, istruzioni condizionali e cicli, vettori.

Esercizio 3.1Si descriva un algoritmo, utilizzando il nucleo del linguaggio C descritto nel Capitolo 3, che legga dallo standard input due numeri interi positivi e stampi in uscita un messaggio che indichi se i due numeri sono primi tra loro oppure no.

Soluzione dell’Esercizio 3.1Due numeri m e n sono primi tra loro se e solo se vale che MCD(m, n) = 1. Il problema si riduce quindi a trovare il massimo comun divisore tra m e n e verificarne il valore. Utilizziamo l’algoritmo di Euclide descritto nell’Esempio 3.7.

main (){

/* Si utilizza l’algoritmo di Euclide per calcolare l’MCD */scanf (m);scanf (n);while (m != n)if (m > n)

m = m - n;else

n = n - m;mcd = n;

/* A questo punto si aggiungono le istruzioni che valutano l’MCD */if (mcd == 1)

printf ("I due numeri sono primi tra loro");else

printf ("I due numeri non sono primi tra loro");}

Esercizio 3.2Si vuole memorizzare in forma compatta un elenco di parole ordinato alfabeticamente. Allo scopo si osserva che spesso due parole consecutive hanno una parte iniziale comune. Ogni parola che ha una parte iniziale comune con la precedente viene quindi rappresentata con una cifra decimale compresa tra ‘2’ e ‘9’ indicante un numero di lettere uguali a quelle nella parole precedente, seguita dalle altre lettere della parola. L’assenza di cifra all’inizio della parola ha lo stesso significato della cifra ‘0’. Ogni parola è separata dalla successiva da uno o più spazi bianchi. Esempio:

abaco 3te 2bandonare 9to 2normale ammiraglio 6re bitume 3orzolo 8uto …

Scrivere un programma, utilizzando il nucleo del linguaggio C descritto nel Capitolo 3, che esegue lo ‘scompattamento’ di tale rappresentazione, cioè legge dallo standard input una sequenza di caratteri che rappresenta la codifica abbreviata del testo (si assuma che la sequenza sia terminata dal carattere speciale ‘#’) e la riscrive nello standard output togliendo le cifre e aggiungendo i caratteri necessari in modo da rappresentare tutte le parole per esteso. Esempio, dalla sequenza sopra riportata si ottenga la seguente:



abaco abate abbandonare abbandonato abnormale ammiraglio ammirare bitume bitorzolo bitorzoluto …

Si scriva poi un programma che esegue l’operazione inversa.

Soluzione dell’Esercizio 3.2

main (){

/* Fase di inserimento del testo compatto */ContatoreTestoCompatto = 0;scanf (carattere);while (carattere != ‘#’){

TestoCompatto[ContatoreTestoCompatto] = carattere;ContatoreTestoCompatto = ContatoreTestoCompatto + 1;scanf (carattere);

}LunghTestoCompatto = ContatoreTestoCompatto;

/* Fase di scompattamento del testo */ContatoreTestoCompatto = 0;ContatoreTestoNormale = 0; CaratterePrecedente = ‘ ‘;while (ContatoreTestoCompatto < LunghTestoCompatto){

carattere = TestoCompatto[ContatoreTestoCompatto];

/* Se il carattere non è un numero, copialo nel vettore del testo normale */

if (carattere < ‘0’ || carattere> ‘9’){

TestoNormale[ContatoreTestoNormale] = carattere;

/* Tiene traccia dell’inizio dell’ultima parola nel testo normale */if (CaratterePrecedente == ‘ ‘ && carattere != ‘ ‘)

ContatoreInizioParola = ContatoreTestoNormale; ContatoreTestoNormale = ContatoreTestoNormale + 1;

}/* Se è un numero, copia caratteri dall’ultima

parola inserita nel testo normale */else{

NumLettereUguali = TestoCompatto[ContatoreTestoCompatto] - ‘0’; for (i = 0; i < NumLettereUguali; i++){

TestoNormale[ContatoreTestoNormale + i] = TestoNormale[ContatoreInizioParola + i];

}ContatoreInizioParola = ContatoreTestoNormale;ContatoreTestoNormale = ContatoreTestoNormale + NumLettereUguali;

}ContatoreTestoCompatto = ContatoreTestoCompatto + 1;CaratterePrecedente = carattere;

}/* Fase di stampa del testo scompattato */

for (i = 0; i < ContatoreTestoNormale; i++)printf (TestoNormale[i]);

}

Adesso scriviamo il programma che eseugue l’operazione inversa: genera il testo ‘compattato’ a partire da quello esteso.



main (){

/* Fase di inserimento del testo normale */ContatoreTestoNormale = 0;scanf (carattere);while (carattere != ‘#’){

TestoNormale[ContatoreTestoNormale] = carattere;ContatoreTestoNormale = ContatoreTestoNormale + 1;scanf (carattere);

}LunghTestoNormale = ContatoreTestoNormale;

/* Fase di compattamento del testo */ContatoreTestoCompatto = 0;ContatoreTestoNormale = 0;ContatoreInizioParola = -1;ContatoreLettere = 0;ContatoreInizioParolaPrec = 0;CaratterePrecedente = ‘ ‘;while (ContatoreTestoNormale < LunghTestoNormale){

carattere = TestoNormale[ContatoreTestoNormale];/* Tiene traccia dell’inizio della parola precedente

nel testo normale */if (CaratterePrecedente == ‘ ‘ && carattere != ‘ ‘){

ContatoreInizioParolaPrec = ContatoreInizioParola;ContatoreInizioParola = ContatoreTestoNormale;

/* Controlla le lettere della parola corrente */controlla = 1;

}

/* Se il carattere è presente nella corrispondente posizione della parola precedente */

if (controlla == 1 && carattere == TestoNormale[ContatoreInizioParolaPrec + ContatoreLettere])

{ContatoreLettere = ContatoreLettere + 1;ContatoreTestoNormale = ContatoreTestoNormale + 1;

}/* Se il carattere non è presente nella corrispondente posizione

della parola precedente */else{

/* Non controllare più per la parola corrente */controlla = 0;

/* Se vi erano lettere uguali, scrivi il contatore */if (ContatoreLettere > 0){

TestoCompatto[ContatoreTestoCompatto] = ContatoreLettere + ‘0’;ContatoreLettere = 0;

}/* Altrimenti, scrivi il carattere */

else{

TestoCompatto[ContatoreTestoCompatto] = carattere;ContatoreTestoNormale = ContatoreTestoNormale + 1;

}ContatoreTestoCompatto = ContatoreTestoCompatto + 1;

}CaratterePrecedente = carattere;

}/* Fase di stampa del testo compattato */

for (i = 0; i < ContatoreTestoCompatto; i++)printf (TestoCompatto[i]);

}



Esercizio 3.3Uno dei problemi più ricorrenti nell’elaborazione automatica delle informazioni è l’ordinamento: data una sequenza di elementi – numeri, parole, fatture, date, …appartenenti ad un insieme per cui sia definita una relazione d’ordine, che qui indicheremo con l’usuale simbolo <=, o < nel caso si tratti di relazione “stretta” – si vogliono ridistribuire gli stessi elementi in modo che, letti in sequenza, rispettino la relazione d’ordine. Per esempio, se la sequenza fosse [10, 55, 5, 90, 17], il risultato cell’ordinamento dovrebbe essere [5, 10, 17, 55, 90].Si può facilmente immaginare l’importanza di un tale problema per quasi tutte le applicazioni di elaborazione delle informazioni; per questo motivo sono stati messi a punto numerosi algoritmi per risolverlo, alcuni dei quali anche molto sofisticati. Uno tra i più semplici ed intuitivi può essere descritto informalmente nel modo seguente:

Si legga da input la sequenza di dati (si assuma qui che i dati siano interi) e la si memorizzi in un array seq di lunghezza n.

Si divida l’array seq in due parti contigue in modo che la prima, quella di sinistra, sia ordinata in ordine crescente, sia indichi con j l’indice del primo elemento della parte destra dell’array: si noti che questo scopo può essere ottenuto immediatamente per qualsiasi array scegliendo come parte sinistra il solo primo elemento (una sequenza di un solo elemento è ovviamente sempre ordinata) e quindi la partizione desiderata può essere ottenuta inizialmente semplicemente assegnando alla variabile j il valore 1 corrispondenete al secondo elemento dell’array.

Si noti poi che se invece la parte destra dell’array si riducesse ad una sequenza vuota la parte sinistra consisterebbe nell’intero array ordinato. Si costruisce quindi un ciclo che ad ogni iterazione sposta l’elemento seq[j] dalla posizione j-esima all’interno della parte sinistra, la cui lunghezza quindi cresce di un’unità, nella posizione adatta affinché la parte sinistra si mantenga ordinata.

Per ottenere questo effetto si memorizzi il valore di seq[j] in una variabile temporanea temp; indi si facciano scorrere gli elementi della parte sinistra dell’array maggiori di temp di una posizione a destra finché non si trova il primo di valore <= temp: il valore di temp viene quindi memorizzato alla sua immediata destra. Si noti che come caso particolare seq[j], e quindi temp, potrebbe essere <= di tutti gli elementi della parte sinistra dell’array.

Si codifichi mediante il nucleo semplificato del C l’algoritmo informalmente descritto sopra.


main (){scanf(n);i = 0; while (i < n) {scanf(seq[i]); i = i+1};j = 1;while (j < n){

temp = seq[j]; i = j -1;while (i >= 0 && seq[i] > temp)

/* si noti che se seq[j] fosse < di tutti gli elementi della parte sinistra si uscirebbe da questo ciclo quando i < 0*/

{ seq[i+1] = seq[i]; i = i -1}seq[i+1] = temp; j = j + 1

};printf(“il risultato dell’ordinamento e’:”);i = 0; while (i < n) {printf(seq[i]); i = i+1}}



Capitolo 4Esecuzione di programmi C su macchine reali

Il C completo: dichiarazione delle variabili, stringhe di formato, direttiva #include.

Esercizio 4.1Scrivere un programma C che legge da tastiera una sequenza di numeri reali; la lettura termina quando la somma dei numeri immessi è maggiore di 50, e comunque non si possono immettere più di 100 numeri (se anche dopo avere immesso 100 numeri la loro somma non supera 50 la lettura termina comunque). Dopo avere letto tutti i numeri, se l’utente ha inserito almeno 3 valori, cercare se esiste una coppia di numeri tali che il loro rapporto (o il suo inverso) sia uguale al primo numero immesso e, se esiste, stamparla.Esempio di funzionamento del programma:

Inserisci numero: 6.25Inserisci numero: -2.5Inserisci numero: 20Inserisci numero: 13.863Inserisci numero: -15.625Inserisci numero: 4Inserisci numero: 38.192

Il rapporto (o il suo inverso) tra -2.5 e -15.625 vale 6.25


#include <stdio.h>

int main (){

float dati[100], sum, rapp, inv_rapp;int i, j, n_dati;unsigned int trovata;

sum = 0;n_dati = 0;do{

printf("Inserisci numero: ");scanf("%f", &dati[n_dati]);sum += dati[n_dati];n_dati++;

} while (sum <= 50 && n_dati < 50);

trovata = 0;if (n_dati >= 3) {

i = 1;while (trovata == 0 && i < n_dati - 1){

j = i+1;while (trovata == 0 && j < n_dati){

if (dati[i] == 0 || dati[j] == 0){

if (dati[0] == 0)trovata = 1;



}else{

rapp = dati[i] / dati[j];inv_rapp = dati[j] / dati[i];if (rapp - dati[0] < 0.0000001 && rapp - dati[0] > -0.0000001 || inv_rapp - dati[0] < 0.0000001 &&

inv_rapp - dati[0] > -0.0000001)trovata = 1;

}if (trovata == 1)

printf("Il rapporto (o il suo inverso) tra %f e %f vale %f\n", dati[i], dati[j], dati[0]);

j++;}i++;

}}else

printf("Sono stati inseriti solo %d elementi\n", n_dati);}

Esercizio 4.2Scrivere un programma C che esegua la seguente funzionalità. Si legge da tastiera una sequenza di n interi positivi (massimo 100 numeri; la sequenza termina quando l’utente inserisce il numero 0); dopo avere letto tutti i numeri, per ogni numero letto viene stampato, ogni volta su una riga diversa e da sinistra verso destra, un numero di asterischi pari al numero in questione.Esempio di funzionamento del programma:

Inserisci numero (0 per terminare): 3Inserisci numero (0 per terminare): 6Inserisci numero (0 per terminare): 3Inserisci numero (0 per terminare): 5Inserisci numero (0 per terminare): 0*****************


#include <stdio.h>

int main (){

unsigned int dati[100], dato_corr;int i, j, n_dati;

n_dati = 0;do{

printf("Inserisci numero (0 per terminare): ");scanf("%u", &dato_corr);

if (dato_corr != 0){

dati[n_dati] = dato_corr;n_dati++;

}} while (dato_corr != 0 && n_dati < 100);



for (i=0; i<n_dati; i++){

for (j=0; j<dati[i]; j++)printf("*");

printf("\n");}

}

Esercizio 4.3Scrivere un programma che legge da tastiera una sequenza di numeri interi e:a) verifica che siano tutti non negativi (nel caso si trovi un numero negativo, il programma dovrà

terminare);b) stampa a video:

a. la media dei numeri pari;b. la media dei numeri dispari;c. la media di tutti i numeri.

La sequenza sarà composta al massimo da 100 numeri.


#include <stdio.h>

int main (){

unsigned int i, num_dati;int dati[100];unsigned int negativo;int media, somma, media_pari, somma_pari, media_dispari, somma_dispari;int cont_pari, cont_dispari;

/* Lettura dei dati; massimo 100 dati*/do{

printf("Quanti numeri vuoi inserire?: ");scanf("%u", &num_dati);

} while (num_dati == 0 || num_dati > 100); for (i = 0; i < num_dati; i++){

printf("Inserisci numero (%u/%u): ", i + 1, num_dati);scanf("%d", &dati[i]);

}/* Controlla se i dati sono tutti non negativi */

negativo = 0;i = 0;while (i < num_dati && negativo == 0){

if (dati[i] < 0)negativo = 1;

i = i + 1; }

/* Se i dati sono tutti non negativi, continua con l’elaborazione */if (negativo == 0){

/* Calcola medie */somma = 0;somma_pari = 0;somma_dispari = 0;cont_pari = 0;cont_dispari = 0;for (i = 0; i < num_dati; i++){

somma = somma + dati[i];/* L’operatore ‘percentuale’ calcola il resto



della divisione intera, detto ‘modulo’ */if (dati[i] % 2 == 0){

somma_pari = somma_pari + dati[i];cont_pari = cont_pari + 1;

}else{

somma_dispari = somma_dispari + dati[i];cont_dispari = cont_dispari + 1;

}}media = somma / num_dati;media_pari = somma_pari / cont_pari;media_dispari = somma_dispari / cont_dispari;printf ("Media totale: %d\n", media);printf ("Media numeri pari: %d\n", media_pari);printf ("Media numero dispari: %d\n", media_dispari);

}/* Se c’è almeno un numero negativo, termina l’esecuzione */

elseprintf ("I numero devono essere tutti non negativi\n");

}

Esercizio 4.4Si scriva un programma che calcola la media, il minimo e il massimo di una sequenza di numeri reali letti dallo standard input. Il programma deve prima chiedere la lunghezza della sequenza di numeri da inserire. I valori risultanti devono essere scritti sullo standard output.


#include <stdio.h>

int main (){

float x, s, min, max;unsigned int n, num_dati;

printf("Quanti numeri vuoi inserire?: ");scanf("%u", &num_dati);

s = 0.0;for (n = 0; n < num_dati; n++) {

printf ("Numero: ");scanf (“%f”, &x);s = s + x;if (n == 0){

min = x;max = x;

}else if (x < min)

min = x;else if (x > max)

max = x;}if (n == 0)

printf ("nessun numero inserito");else

printf ("La media è %f \n il minimo è %f \n" " il massimo è %f \n", s / n, min, max);}





Capitolo 5Tipi di dati

Inizializzazione delle variabili, definizione di nuovi tipi, puntatori, direttiva #define.

Esercizio 5.1Si definisca un tipo di dato Giocattolo costituito dal nome del giocattolo (ad esempio “Trenino_elettrico”), dalla data di fabbricazione, e dal prezzo. Se necessario, si definiscano in precedenza ulteriori tipi di dato utili per la definizione del tipo Giocattolo. Si definisca poi un nuovo tipo Bambino, costituito dal nome del bambino e da una sequenza giocattoliPosseduti. Tale sequenza è costituita a sua volta da un array di 10 elementi, ognuno dei quali essendo di tipo Giocattolo. Si dichiarino successivamente due variabili, Giocattoli e Bambini, consistenti in due array, rispettivamante di MAX_GIOCATTOLI elementi del tipo Giocattolo e MAX_BAMBINI elementi del tipo Bambino. MAX_GIOCATTOLI e MAX_BAMBINI, pure da definire, sono i due valori costanti 20 e 30.Si può assumere che nè i nomi dei giocattoli, nè i nomi dei bambini siani più lunghi di 30 caratteri.


#define MAX_GIOCATTOLI 20#define MAX_BAMBINI 30

typedef struct{

int giorno;int mese;int anno;

} Data;

typedef char string[30];

typedef struct{

string nome;Data dataFabbricazione;float prezzo;

} Giocattolo;

typedef struct{

string nome;Giocattolo giocattoliPosseduti[10];

} Bambino;

Giocattolo Giocattoli[MAX_GIOCATTOLI];Bambino Bambini[MAX_BAMBINI];

Esercizio 5.2Si definiscano i tipi di dato che servono per contenere le informazioni di un pubblico registro automobilistico dedicato ai motoveicoli. I tipi da definire sono i seguenti.TipoDatiMotoveicolo rappresenta i dati di un motoveicolo. Questi dati si compongono di: targa del motoveicolo (7 lettere), marca del motoveicolo (massimo 15 caratteri), modello (massimo 20



caratteri), cilindrata (in cc), potenza (in kW), categoria (motorino, scooter, motocicletta, motocarro).TipoDatiProprietario rappresenta i dati di una persona (il proprietario del motoveicolo): nome (massimo 30 caratteri), cognome (massimo 40 caratteri), codice fiscale (16 caratteri).TipoVocePRA rappresenta una singola voce nel registro automobilistico; una voce si compone di 2 elementi, i dati del proprietario del motoveicolo ed i dati del motoveicolo stesso.TipoPRA rappresenta un tipo adatto a contenere i dati di un PRA. Questo tipo di dati è un elenco di voci del PRA (si suppone che un PRA non possa contenere più di 10.000 elementi), più un contatore che dice quante voci sono effettivamente presenti nel PRA. (se si ritiene utile, si possono definire altri tipi di dati, di supporto a quelli richiesti)


typedef enum {motorino, scooter, motocicletta, motocarro} TipoCategoria;

typedef struct{

char targa[7];char marca[15];char modello[20];int cilindrata;float potenza;TipoCategoria categoria;

} TipoDatiMotoveicolo;

typedef struct{

char nome[30];char cognome[40];char codiceFiscale[16];

} TipoDatiProprietario;

typedef struct{

TipoDatiMotoveicolo motoveicolo;TipoDatiProprietario proprietario;

} TipoVocePRA;

typedef struct{

TipoVocePRA elementi[10000];int nElementi;

} TipoPRA;

Esercizio 5.3Siano P, Q, R, tre puntatori a interi e x, y due variabili intere. Si dica quanto valgono rispettivamente x, y, *P, *Q, *R dopo l’esecuzione della seguente sequenza di istruzioni.

x = 3;y = 5;P = &x;Q = &y;R = P;*R = 10;y = x + *Q;x = x + *P;Q = R;P = Q;

Soluzione esercizo 5.3



Al termine dell’esecuzione della sequenza di istruzioni le variabili valgono:x = 20, y = 15

P, Q, R puntano tutti a x e quindi: *P = *Q = *R = 20.

Esercizio 5.4Definire un tipo di dati che contiene le informazioni riguardanti un esame sostenuto da un qualunque studente universitario.Queste informazioni si compongono di: nome dell’esame (nessun nome è più lungo di 40 caratteri), codice alfanumerico (al massimo 6 lettere, per esempio AG0012), voto compreso tra 18 e 30 e lode (si scelga un’opportuna rappresentazione dell’eventuale lode, tenendo conto che non sono ammesse le frazioni di voto), numero di crediti associati all’esame (sono ammesse le frazioni di credito, per esempio 7,5).Di ogni studente si vogliono memorizzare le seguenti informazioni: nome (si suppone che un nome non sia composto da più di 50 lettere), matricola (un numero naturale), data di immatricolazione, numero di esami sostenuti, lista degli esami sostenuti (essendo un singolo esame descritto come in precedenza), media dei voti riportati. Ogni studente può sostenere al massimo 29 esami.(se si ritiene utile, si possono definire altri tipi di dati, di supporto a quelli richiesti)


typedef struct{

unsigned short giorno;unsigned short mese;unsigned int anno;

} Tipo_data;

typedef struct{

char nome[40];char codice[6];unsigned short voto;bool lode;float crediti;

} Tipo_esame;

typedef struct{

char nome[50];unsigned int matricola;Tipo_data data_immatricolazione;Tipo_esame esami[29];unsigned short numero_esami;float media;

} Tipo_studente;

Esercizio 5.5 Definire un tipo di dato TipoStrumentista che descrive i dati relativi ad un musicista jazz. Ogni musicista è definito da un nome (massimo 40 caratteri), da una data di nascita, e dallo strumento che suona. Ogni musicista suona un solo strumento, ed il tipo di strumento suonato può essere solo uno dei seguenti (non sono ammessi altri strumenti): pianoforte, basso, batteria, sax, tromba, trombone, flauto, clarinetto, voce.



Definire un tipo TipoQuartetto che contiene i dati relativi ad un quartetto di musicisti. Ogni quartetto è caratterizzato da un nome (al massimo 30 caratteri) e da esattamente 4 musicisti (non uno di più, non uno di meno).Definire infine una variabile ElencoQuartetti che può contenere al massimo 100 quartetti.(se si ritiene utile, si possono definire altri tipi di dati, di supporto a quelli richiesti)


#define L_NOME_MUS 40#define L_NOME_QUAR 30#define MAX_QUARTETTI 100

typedef struct{

short giorno; short mese; int anno;} TipoData;

typedef enum {pianoforte, basso, batteria, sax, trombone, flauto, clarinetto, voce} TipoStrumento;

typedef struct{ char nome[L_NOME_MUS + 1]; TipoData data_nascita; TipoStrumento strumento;} TipoStrumentista;

typedef struct{ char nome[L_NOME_QUAR + 1]; TipoStrumentista musicisti[4];} TipoQuartetto;

TipoQuartetto ElencoQuartetti[MAX_QUARTETTI];

Esercizio 5.6Si vuole scrivere un programma che tiene traccia del numero di CD acquistati per ogni mese dell’anno nell’arco di 10 anni.Definire un tipo TipoDatiCD che contiene i dati di ogni CD: il titolo (lungo al massimo 50 caratteri), l’autore (massimo 60 caratteri), l’anno di pubblicazione, il numero di copie acquistate (anche più di una, se per esempio si vuole fare un regalo).Definire un tipo di dato CDAcqInMese che contiene l’elenco dei CD comprati in un dato mese (si può assumere che non vengano acquistati più di 50 diversi titoli al mese) ed il numero di titoli diversi acquistati in quel mese.Definire una variabile globale elencoCD che contiene l’elenco dei CD acquistati mese per mese negli anni dal 1990 al 1999. Se si fa uso di tipi accessori, anche questi vanno definiti.


#define MAX_L_TITOLO 50#define MAX_L_AUTORE 60#define MAX_TIT_IN_MESE 50

typedef struct{

char titolo[MAX_L_TITOLO]; char autore[MAX_L_AUTORE];



int anno; int n_copie;} TipoDatiCD;

typedef struct{

TipoDatiCD cd[MAX_TIT_IN_MESE]; int n_titoli;} CDAcqInMese;

/* Le righe di ‘elencoCD’ corrispondono agli anni dal 1990 al 1999, le colonne ai 12 mesi di ciascun anno */

CDAcqInMese elencoCD[10][12];

Esercizio 5.7Si considerino le seguenti dichiarazioni:

typedef int *tipo1;int x, y;int *a;tipo1 b;tipo1 seq[10];

Si dica, per ognuna delle seguenti sequenze di istruzioni C, se essa è corretta o no; in caso positivo si dica qual è il risultato prodotto; in caso negativo si dica in che cosa consiste l’errore e se si tratta di errore a compile-time o a run-time.

Sequenza 1:x = 0; y = 1; seq[0] = a; *b = x; *a = y; x = **seq + *b; printf ("il valore di x e y è, rispettivamente, %d, %d, \n", x, y);

Sequenza 2:x = 10; scanf ("%d", &y); a = NULL; b = &y ; if (x > y) *a = 5; else *b = 5;

Sequenza 3:y = 0; a = &y; x = 2; *a = y + x; b = a; a = NULL; *b = x/y;printf ("il valore di x e y è, rispettivamente, %d, %d, \n", x, y);


Sequenza 1: è corretta: infatti seq è un array di puntatori, un array essendo a sua volta un puntatore; quindi *seq equivale a seq[0]. Il risultato prodotto è 1 sia per x che per y.

Sequenza 2: è scorretta in quanto, se il valore y immesso dall’utente è minore di 10, *a è indefinito poiché a ha valore NULL). Questo è un errore a run-time (lo si trova solo facendo girare il programma e fornendo in ingresso un valore di y minore di 10).

Sequenza 3: è corretta, e stampa 2 per x e 1 per y.

Esercizio 5.8

Parte 1Si considerino le seguenti dichiarazioni:

typedef int *PUNT;typedef PUNT *DOPPIOPUNT;



int x, y;PUNT P, Q;DOPPIOPUNT DP, DQ;

a) Ipotizzando che nessuna delle variabili dichiarate qui sopra sia ancora inizializzata, si scriva una sequenza di istruzioni C tale per cui alla fine della loro esecuzione la condizione **DP == 10 risulti vera.

b) Assumendo invece che tutte le variabili in gioco contengano un valore significativo (e in particolare che i puntatori non contengano il valore NULL), si dica, giustificando brevemente la risposta, se le seguenti affermazioni sono corrette o no:

Se P == Q allora *P == *QSe *P == *Q allora P == Q

Parte2 *IND*Con riferimento alla Parte 1, a) 1 si assuma che nella macchina di von Neumann le celle 101 e 102, 111 e 112, 121 e 122 corrispondano, rispettivamente alle variabili x e y, P e Q, DP e DQ. a) Si scriva una sequenza di istruzioni nel linguaggio della macchina che producano lo stesso

risultato delle istruzioni scritte in C per la Parte 1,a), ossia tali che il contenuto della cella il cui indirizzo è il contenuto della cella 121 sia 10.

b) Successivamente si scriva una sequenza di istruzioni nel linguaggio della macchina che, indipendentemente dal contenuto attuale delle varie celle, producano l’effetto che produrrebbe l’istruzione C **DP = **DP + 10 sulle corrispondenti variabili.

Si facciano le seguenti assunzioni:

1. Le istruzioni del linguaggio di von Neumann utilizzabili sono quelle della Tabella del Capitolo 2 con le tre modalità di indirizzamento.

2. Si possono usare celle temporanee a partire dalla 150.


Parte1

a)P = &x;DP = &Px = 10

/* oppure **DP = 10; si noti però che, in assenza delle due precedenti istruzioni, la sola **DP = 10 genererebbe un errore a run-time */

b)

La prima affermazione è corretta: se P e Q puntano alla stessa cella, il relativo contenuto non può che essere identico a se stesso; la seconda invece è sbagliata: P e Q possono puntare a celle diverse e quindi avere valori diversi ma il contenuto delle celle a cui puntano potrebbe coincidere.

Parte2

a)LoadA= 10StoreA 101 /* si inizializza x a 10 */LoadA= 101



StoreA 111 /* si inizializza P con il l’indirizzo di x*/LoadA = 111StoreA 121 /* si inizializza DP con il l’indirizzo di P*/

b)LoadA@ 121StoreA 150LoadA@ 150LoadB= 10SumABStoreA 150

Esercizio 5.9Si scriva un programma che:

Legge dallo StandardInput un intero positivo n e una sequenza di n + 1 interi relativi {a0, a1, … an}.

Legge successivamente un numero reale x.

Scrive sullo StandardOutput il valore del polinomio a0 + a1·x + … + an·xn.

Il programma non può far uso di funzioni di libreria a parte quelle standard di input-output (scanf e printf).

Soluzione dell’Esercizio 5.9 (traccia in pseudo-C)

#include <stdio.h>#define MAX_Grado 50

int main (){

int indici[MAX_Grado], n;double x, risultato = 0.;int i, k;printf ( [messaggio di richiesta di n]);scanf ("%d", &n);for (i = 0; i <= n; i++) {

printf ( [messaggio di richiesta di indici [i]]);scanf("%d", &indici [i]]);

}printf ( [messaggio di richiesta di x]);scanf ("%f", &x);for (i = 0; i <= n; i++){

monomio = 1; for (k = 0; k < i; k++){

monomio = monomio * x;}monomio = monomio * indici[i];risultato = risultato + monomio;

}printf ([messaggio di stampa del valore calcolato del polinomio]);

}




Legge dallo StandardInput un intero positivo m;

Verifica che m sia un quadrato perfetto: m = n2; in caso contrario interrompe l’esecuzione segnalando l’anomalia sullo StandardOutput

Legge successivamente m numeri reali e li stampa in n righe a n per riga separati tra loro da 4 spazi; si può assumere di sapere a priori che ogni riga abbia spazio sufficiente per contenere tutti gli n numeri così spaziati e che ogni numero occupi lo stesso spazio, in modo che la stampa finale risulti in una tabella quadrata n n.

È preferito un programma che non sfrutti funzioni di libreria a parte quelle standard di input-output (scanf e printf).

Soluzione dell’Esercizio 5.10 (traccia in pseudo-C)

#include <stdio.h>

int main (){ int m, n, i, j; double x; printf ([messaggio di richiesta di m]); scanf ("%d", &m);

/* verifica che m sia un quadrato perfetto; non si verifica, ma sarebbe ben farlo, che m sia positivo */

i = 1; while (i*i < m) i++; if (i*i == m) { n = i ; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { printf ([messaggio di richiesta del prossimo dato da scrivere, x]); scanf("%lf", &x); printf ("%f ", x);

/* stampa x in formato float seguito da 4 spazi*/ } printf ("\n"); } } else printf ([messaggio di segnalazione che n non è un quadrato perfetto]);}

Esercizio 5.11Si considerino le seguenti dichiarazioni nel linguaggio C:

typedef struct { float PrimoCampo; char SecondoCampo; int TerzoCampo;} struttura;

struttura x, r;int z;float w;

Scrivere una sequenza di istruzioni nel linguaggio di von Neumann che sia equivalente alle seguenti istruzioni C:



x = r;z = r.TerzoCampo;r.PrimoCampo = w;

Si possono fare le seguenti assunzioni:

1.Una variabile di tipo float occupa due celle di memoria, mentre variabili di tipo int e char ne occupano una.Le celle della macchina di von Neumann corrispondenti alle variabili C suddette sono, rispettivamente: x: Un numero adeguato di celle a partire dalla cella 101r: Un numero adeguato di celle a partire dalla cella 111z: Un numero adeguato di celle a partire dalla cella 121w: Un numero adeguato di celle a partire dalla cella 131I campi delle variabili di tipo struttura sono memorizzati in celle consecutive.

2.Le istruzioni del linguaggio di von Neumann utilizzabili sono quelle riportate nella Tabella del Capitolo 2

3.Le istruzioni del linguaggio di von Neumann che realizzano il codice C suddetto siano numerate a partire dal numero k


/* x = r, con x che parte dalla cella 101 ed occupa 4 celle, mentre r parte dalla cella 111 */

LoadA 111StoreA 101LoadA 112StoreA 102LoadA 113StoreA 103LoadA 114StoreA 104

/* z = r.TerzoCampo, con il terzo campo di r che corrisponde alla cella 114 */LoadA 114StoreA 121

/* r.PrimoCampo = w, con il primo campo di r che è lungo 2 celle */LoadA 131StoreA 111LoadA 132StoreA 112

Esercizio 5.12 *IND*Si considerino le seguenti dichiarazioni in linguaggio C:

int a[20][10] int x, i, j;

Assumendo che nella memoria della macchina di von Neumann l’indirizzo della cella destinata a contenere l’elemento a[0,0] sia 100, e che quelli delle celle di x, i e j siano rispettivamente 50,



60, 70 si indichi come possono essere disposte le 200 celle consecutive dell’array a nella memoria della macchina.

Indi si scriva una sequenza di istruzioni nel linguaggio della macchina di von Neumann equivalente alla seguente istruzione C:

x = a[i,j]


1. Una variabile di tipo int occupa esattamente una cella di memoria2. Possono essere utilizzate ulteriori celle di memoria temporanea.

Le istruzioni della macchina di Von Neumann utilizzabili sono quelle indicate nella Tabella relativa al Capitolo 2; si può fare uso delle 3 modalità di indirizzamento ivi specificate; inoltre si può aggiungere alle istruzioni della tabella un’ulteriore istruzione MultAB (codice binario 1000) che esegue il prodotto tra il contenuto del registro A e quello del registro B e lascia il risultato nel registro A.

Soluzione dell’Esercizio 5.12Due modi “naturali” (ma non gli unici) di memorizzare un array bidimensionale sono, rispettivamente “per righe” e “per colonne”. Nel nostro caso una memorizzazione per colonne consisterebbe nel memorizzare gli elementi a[0,0] ... a[19,0] dalla cella 100 alla 119, a[0,1] in 120 e così via.

L’istruzione C proposta nell’esercizio può quindi essere tradotta nel linguaggio della macchina di Von Neumann nel seguente modo (utilizzando le celle 80 e 90 come celle temporanee):

LoadA 70LoadB= 20MultABStoreA 80 /* TEMP1 = j*20 */LoadA= 100LoadB 80SumABLoadB 60SumABStoreA 90 /* TEMP2 = 100 + j*20 + i */LoadA@ 90StoreA 50

Esercizio 5.13 *IND*Si considerino le seguenti dichiarazioni nel linguaggio C

typedef struct EL { int i; struct EL *n;} myType;

myType *myVar;

Scrivere una sequenza di istruzioni nel linguaggio di von Neumann che sia equivalente alle seguenti istruzioni C:



while(myVar != NULL){ printf("%f", myVar->i); myVar = myVar->n;}


1.Una variabile di tipo int occupa una cella di memoria; una variabile di tipo puntatore occupa anch’essa una cella di memoria, indipendentemente dal tipo dell’oggetto puntato.La prima delle celle della macchina di von Neumann corrispondenti alla variabile myVar è la cella 101.I campi delle variabili di tipo struttura sono memorizzati in celle consecutive.Il valore NULL corrisponde al valore 0 (cioè all’indirizzo 0).

2.Le istruzioni del linguaggio di von Neumann utilizzabili sono quelle specificate nella Tabella del Capitolo 2 con le 3 modalità di indirizzamento, diretto, immediato, indiretto.

3.Le istruzioni del linguaggio di von Neumann che realizzano il codice C suddetto siano numerate a partire dal numero k


/* if myVar == NULL GOTO end */k. LoadA 101k+1. BEQA k+10

/* printf (myVar->i) */k+2. Write@ 101

/* myVar = (myVar->n) */k+3. LoadA 101k+4 LoadB= 1k+5. SumABk+6. StoreA 102k+7. LoadA@ 102k+8. StoreA 101k+9. BR k

Esercizio 5.14 *IND*Si considerino le seguenti dichiarazioni in linguaggio C:

int a[] = {0, 1, 2, 3, 4, 5}int s;int i;

Scrivere una sequenza di istruzioni nel linguaggio della macchina di Von Neumann equivalente alle seguenti istruzioni C:

for (i = 0; a[i] < 5; i++) {s = s + a[i];

}




1. Una variabile di tipo int occupa esattamente una cella di memoria2. Le variabili s ed i sono memorizzate nelle celle di memoria di indirizzo 100 e 101

rispettivamente3. L’array a è memorizzato a partire dalla cella di memoria 2004. Ulteriori celle di memoria temporanea possono essere utilizzate a partire dall’indirizzo

3005. Le istruzioni del linguaggio di von Neumann utilizzabili sono quelle specificate nella

Tabella del Capitolo 2 con le 3 modalità di indirizzamento, diretto, immediato, indiretto

Soluzione dell’Esercizio 5.14Le istruzioni C proposte possono essere tradotte nel linguaggio della macchina di von Neumann nel seguente modo (la cella di memoria 300 viene utilizzata come cella di reindirizzamento per i valori dell’array):

LoadA= 0StoreA 101 /* Inizializza i */

LOOP: LoadA 101LoadB= 200SumABStoreA 300 /* Calcola l’offset per il valore cercato nell’array a[] */LoadA@ 300 /* Carica il valore cercato dall’array a[] */LoadB= 6SubAB /* Sottrae 6 per il confronto */

/* Se minore di zero esce dal loop. NB a è un array di interi*/

BLAEXIT:LoadA@ 300LoadB 100SumABStoreA 100 /* Effettua l’addizione */Branch LOOP:

EXIT:

Esercizio 5.15

Parte aSi scriva in C la definizione di un tipo “conto corrente” che contenga almeno le seguenti informazioni:

Cognome e nome di uno o al massimo due intestatari;

Numero del conto;

Ammontare del conto;

Data di apertura del conto

Successivamente si definisca un tipo “persona” che contenga almeno le seguenti informazioni:

Cognome e nome della persona

Data e luogo di nascita

Codice fiscale

Riferimento a uno o due (al massimo) possibili conti correnti di cui la persona sia intestatario.



NB1: Per “riferimento” si intende un’informazione che permetta di risalire all’eventuale conto corrente di cui la persona è intestatario; ovviamente il conto corrente sarà una variabile C del tipo definito precedentemente.

NB2: Una persona potrebbe anche non essere intestatario di alcun conto corrente.

Parte b

Si dichiarino un array di persone e uno di conti correnti appartenenti ai tipi definiti nella parte a. Indi si scriva una sequenza di istruzioni (non un programma completo!) che scandisca l’array di persone e per ognuna di esse produca, sullo Standard Output:

Cognome e Nome seguito dal numero di conto (o dei conti) di cui è intestatario e da Cognome e Nome degli intestatari del conto, tra cui, per semplicità è possibile ripetere Cognome e Nome dell’intestatario originale.

Se una persona non è intestataria di alcun conto corrente non deve comparire nell’elenco.

Ad esempio, si supponga che:

Mario Rossi sia intestatario dei conti 1005 e 2007; il conto 1005 sia intestato anche a Cristina Rossi; il conto 2007 non sia intestato ad alcun altro;

Giuseppe Bianchi sia intestatario esclusivo dei conti 1456 e 3456;

Domenico Brambilla non sia intestatario di alcun conto;

Cristina Rossi sia intestatario del conto 1005.

L’output prodotto dovrebbe allora essere il seguente:

Mario Rossi è intestatario del conto N. 1005 intestato a Mario Rossi e Cristina Rossi e del conto N. 2007 intestato a Mario Rossi

Giuseppe Bianchi è intestatario del conto N. 1456 intestato a Giuseppe Bianchi e del conto N. 3456 intestato a Giuseppe Bianchi

Cristina Rossi è intestatario del conto N. 1005 intestato a Mario Rossi e Cristina Rossi

Facoltativamente la sequenza di istruzioni dovrebbe anche verificare eventuali situazioni scorrette (ad esempio: i dati di una persona fanno riferimento a un conto corrente che non risulta intestato a quella persona).


Parte a

La definizione del tipo “conto corrente” può essere data come segue:

#define STRING_MAX_LENGTH 80

typedef struct { unsigned int giorno; unsigned int mese; unsigned int anno;} data;

typedef struct { char primoIntestCognome[STRING_MAX_LENGTH]; char primoIntestNome[STRING_MAX_LENGTH]; char secondoIntestCognome[STRING_MAX_LENGTH];



char secondoIntestNome[STRING_MAX_LENGTH]; unsigned int numeroCC; float saldo; data dataApertura;} contoCorrente;

La definizione del tipo “persona” può invece essere data come:

typedef struct { char cognome[STRING_MAX_LENGTH]; char nome[STRING_MAX_LENGTH]; char codiceFiscale[16]; data dataNascita; char luogoNascita[STRING_MAX_LENGTH]; contoCorrente *CCintestati[2]; /* Array di puntatori al tipo conto corrente */} persona;

Parte b

Riferendosi ai tipi dati definiti nella Parte a, il problema posto può essere risolto dalla seguente sequenza di istruzioni:

contoCorrente conti[NUM_CONTI];persona persone[NUM_PERSONE];

/* Si assume che, nel caso in cui un conto corrente abbia un singolo intestatario, la stringa adibita a memorizzare nome e cognome del secondo intestatario sia semplicemente

costituita dal carattere nullo. Si assume inoltre che per segnalare l’assenza di un conto corrente intestato ad una determinata persona si sia posto a NULL il relativo

puntatore nella struct persona. */

int i; for (i = 0; i < NUM_PERSONE; i++){ contoCorrente *primoCC = persone[i].CCintestati[0]; contoCorrente *secondoCC = persone[i].CCintestati[1];

/* Controlla possibili co-intestatari del primo CC, se esiste */ if (primoCC != NULL){ printf("%s %s è intestatario del conto N.%u intestato a %s %s", persone[i].nome, persone[i].cognome,

primoCC->numeroCC, primoCC->primoIntestNome, primoCC->primoIntestCognome);

if (primoCC->secondoIntestCognome[0] != ‘\0’ || primoCC->secondoIntestNome[0] != ‘\0’) { printf ("e %s %s", primoCC->secondoIntestNome,

primoCC->secondoIntestCognome); } }

/* Controlla possibili co-intestatari del secondo CC, se esiste */ if (secondoCC != NULL){ printf("e del conto N.%u intestato a %s %s",

secondoCC->numeroCC, secondoCC->primoIntestNome, secondoCC->primoIntestCognome);

if (secondoCC->secondoIntestCognome[0] != ‘\0’ || secondoCC->secondoIntestNome[0] != ‘\0’) { printf ("e %s %s", secondoCC->secondoIntestNome,

secondoCC->secondoIntestCognome); } }}



La versione facoltativa richiede un ulteriore sforzo nel confronto delle stringhe che rappresentano nomi e cognomi. Una possibile soluzione è la seguente, che viene descritta qui di seguito basandosi sulle stesse assunzioni prima riportate e solo per quanto riguarda il primo conto corrente riferito ad una certa persona. Il caso del secondo conto corrente è del tutto analogo:

contoCorrente conti[NUM_CONTI];persona persone[NUM_PERSONE];int i,j;bool checkNome, checkCognome, checkOK = false; for (i = 0; i < NUM_PERSONE; i++){ contoCorrente *primoCC = persone[i].CCintestati[0]; contoCorrente *secondoCC = persone[i].CCintestati[1];

/* Controlla la correttezza del primo CC associato, se esiste */ if (primoCC != NULL) { checkNome = false;

/* Diventa true se il nome passa il controllo */ checkCognome = false;

/* Diventa true se il cognome passa il controllo */

/* Controlla se il nome della persona corrisponde al nome del primo intestario */

j = 0; while (persone[i].nome[j] == primoCC->primoIntestNome[j] && persone[i].nome[j] != ‘\0’ && primoCC->primoIntestNome[j] != ‘\0’) { j++; } if (j > 0 && persone[i].nome[j] == primoCC->primoIntestNome[j] && persone[i].nome[j] == ‘\0’){ checkNome = true; }

/* Controlla se il cognome della persona corrisponde al cognome del primo intestatario */

j = 0; while (persone[i].cognome[j] == primoCC->primoIntestCognome[j] && persone[i].cognome[j] != ‘\0’ && primoCC->primoIntestCognome[j] != ‘\0’) { j++; }

if (j > 0 && persone[i].cognome[j]==primoCC->primoIntestCognome[j] && persone[i].cognome[j]==‘\0’) { checkCognome = true; } if (checkNome&&checkCognome) { checkOK = true; } else {

/* In caso il controllo sia fallito sul primo intestatario, viene tentato sul secondo */

checkNome = false; checkCognome = false;

/* Idem come nel caso precedente per il primo intestatario */ … }



if (!checkOK) { printf("Errore: nei dati riguardanti la persona %s %s",

persone[i].nome, persone[i].cognome); } else {

… /* Come nel caso non-facoltativo */

… }

/* Da ripetere sul secondo CC eventualmente associato alla persona */

}}



Capitolo 6Strutture di controllo

Strutture di controllo: for, switch, do-while.

Esercizio 6.1Con riferimento all’Esercizio 5.1, si scriva un frammento di programma C che:Legga da tastiera, mediante opportuno dialogo con l’utente, il nome di un bambino e, se questo compare nell’elenco dei bambini, stampa l’elenco dei nomi dei giocattoli da lui posseduti.Nello scrivere il frammento di programma (ossia una sequenza di istruzioni che non costituisce necessariamente un programma completo) si assuma che l’elenco dei bambini e l’elenco dei giocattoli siano costituiti dalle variabili Bambini e Giocattoli già in memoria.Per semplicità si può assumere che l’utente non commetta errori durante il dialogo con la macchina (ad esempio non fornisca nomi troppo lunghi).Si facciano inoltre le seguenti assunzioni:

Ogni stringa di caratteri che costituisca un nome (di giocattolo o di bambino) sia terminata dal carattere “new line” (‘\n’) premendo il tasto <ENTER>

Se il bambino possiede solo k giocattoli, k < 10, gli ultimi 10 – k puntatori valgono NULL.

La variabile NumBambini, che pure si assume sia già in memoria, contiene il numero di bambini effettivamente presenti nell’elenco dei bambini.Un esempio di dialogo utente-programma è il seguente (NB dopo aver battuto i caratteri che compongono il nome del bambino l’utente batte il tasto <ENTER>):

Immetti il nome di un bambino:GiovanniI giocattoli posseduti da Giovanni sono:Trenino elettricoCavallo a dondolo


#include <stdio.h>#include <stdbool.h>

#define …

typedef …

int main (){

Giocattolo Giocattoli[MaxGiocattoli];Bambino Bambini[MaxBambini];string NomeBambino;bool trovato;int i, k, j, LunghNomeBamb, NumBambini;

/* NumBambini indica il numero di bambini presenti nell’elenco */…/* parte di programma omessa. Comprenderà, tra l’altro, il dialogo utente-macchina

per acquisire i dati e memorizzarli nelle variabili Giocattoli e Bambini*/printf ("Immetti il nome del bambino di cui vuoi conoscere i giocattoli:\n");i = 0;scanf("%c", &NomeBambino[i]); while (NomeBambino[i] != ‘\n’)



{i++;scanf("%c", &NomeBambino[i])

}LunghNomeBamb = i;

/* Si cerca nell’array Bambini il nome immesso */trovato = false;k = 0;while (! trovato && k < NumBambini){

/* Si incrementa i fintanto che la condizione rimane vera */for (i = 0; i <= LunghNomeBamb && Bambini[k].nome[i] == NomeBambino[i]; i++) ;

if (i > LunghNomeBamb)trovato = true;

else k++;

}if (! trovato)

printf (“Il bambino indicato non compare nell’elenco\n”);else{

printf (“I giocattoli posseduti dal bamino sono:\n”);i = 0; while (i < 10 && Bambini[k].GiocattoliPosseduti[i] != NULL){

for (j = 0; j < 30 && Bambini[k].GiocattoliPosseduti [i] -> nome[j] != ‘\r’; j++)

printf ("%c", Bambini[k].GiocattoliPosseduti [i] -> nome[j]);i++;printf ("\n"),

}} /*fine del frammento di programma*/…

}

Esercizio 6.3Realizzare un programma che legge da tastiera (e memorizza) una sequenza di caratteri alfabetici minuscoli (letti ad uno ad uno), terminata dal carattere ‘#’; se l’utente inserisce un carattere non valido (un carattere maiuscolo, un numero o un simbolo che non sia ‘#’), il carattere non va memorizzato; la sequenza può essere lunga al massimo 100 elementi (escluso lo ‘#’). Il programma riproduce sullo standard output la sequenza di caratteri, convertendone il contenuto secondo la cifratura ROT-13. Questa cifratura prevede che ad ogni carattere che rappresenta la lettera tra le 26 dell’alfabeto in posizione i si sostituisca la lettera in posizione i+13 (mod 26).Ad esempio, digitando la sequenza di caratteri testodiprova#, il programma deve stampare la stringa di caratteri grfgbqvcebin. Si noti come applicando un numero pari di volte la trasformazione si riottenga il testo di partenza.


#include <stdio.h>

#define MAX_NUM 100

int main (){

char dati[MAX_NUM], dato_corr, trasf;int i, j, n_dati;

n_dati = 0;do {

printf ("Inserisci carattere alfabetico "



"(# per terminare, massimo %d caratteri): ", MAX_NUM); scanf (" %c", &dato_corr);

if (dato_corr <= ‘z’ && dato_corr >= ‘a’) {

dati[n_dati] = dato_corr; n_dati++; }

} while (dato_corr != ‘#’ && n_dati < MAX_NUM);

printf("\nSequenza trasformata:\n"); for (i = 0 ; i < n_dati ; i++)

{ trasf = ‘a’ + (dati[i]+13 - ‘a’) % 26; printf("%c", trasf);

}printf("\n");

}

Esercizio 6.4Scrivere un programma che legge da tastiera delle righe di caratteri (di lunghezza massima 100 caratteri). Per ogni riga letta, il programma conta il numero di occorrenze di ogni vocale (sia che appaia in caratteri maiuscoli che in quelli minuscoli).Quando l’utente immette una riga vuota, il programma stampa un istogramma verticale (dall’alto al basso) con tanti asterischi quante sono le occorrenze di ogni vocale.Per esempio, se l’utente immette le seguenti righe:

NEL mezzo DEL cammin DI nostra vita <ENTER>mi RITROVAI per una SELVA oscura <ENTER>CHE la diritta via era SMARRITA <ENTER><ENTER>

Il programma stampa il seguente istogramma:

AEIOU**************************** ** ** ****


#include <stdio.h>

#define MAX_RIGA 100

int main (){

char riga[MAX_RIGA+1]; unsigned int counter[5]; int i;



/* Inizializza i contatori */ for (i = 0; i < 5; i++)

counter[i] = 0;/* Leggi la prima riga */

printf("Inserisci riga di caratteri (max %d elementi):\n", MAX_RIGA); i = 0;

scanf("%c", &riga[i]); while (riga[i] != ‘\n’) {

i++;scanf("%c", &riga[i]);

}/* Analizza la riga */

while(riga[0] != ‘\n’){

for(i=0; riga[i] != ‘\n’; i++) { if (riga[i] == ‘a’ || riga[i] == ‘A’)

counter[0] += 1; else if (riga[i] == ‘e’ || riga[i] == ‘E’)

counter[1] += 1; else if (riga[i] == ‘i’ || riga[i] == ‘I’)

counter[2] += 1; else if (riga[i] == ‘o’ || riga[i] == ‘O’)

counter[3] += 1; else if (riga[i] == ‘u’ || riga[i] == ‘U’)

counter[4] += 1; }

/* Leggi la riga successiva */printf("Inserisci riga di caratteri (max %d elementi):\n", MAX_RIGA);

i = 0;scanf("%c", &riga[i]); while (riga[i] != ‘\n’) {

i++;scanf("%c", &riga[i]);

}}

printf("\nAEIOU\n"); while (counter[0] > 0 || counter[1] > 0 || counter[2] > 0 || counter[3] > 0 || counter[4] > 0)

{ if (counter[0] > 0)

{ printf("*"); counter[0] -= 1; }

else{

printf(" "); }

if (counter[1] > 0){

printf("*"); counter[1] -= 1; }

else{

printf(" "); } if (counter[2] > 0)

{ printf("*"); counter[2] -= 1; }

else{




{ printf("*"); counter[3] -= 1; }

else{


{ printf("*");

counter[4] -= 1; }

else{

printf(" "); } printf("\n"); }}

Esercizio 6.5 Facendo riferimento all’Esercizio 5.5, si scriva un frammento di programma C che, per ogni quartetto senza pianoforte (cioè in cui nessuno strumentista suona il pianoforte) presente nell’elenco ElencoQuartetti, stampa a video il nome del quartetto. In seguito stampa a video il nome di tutti i quartetti con pianoforte.Nel realizzare il frammento di programma si supponga che la variabile ElencoQuartetti di cui al punto precedente sia già stata inizializzata (sia cioè già stata caricata di dati, che non devono essere riletti da tastiera), e si supponga inoltre che un’altra variabile numQuartetti, di tipo int (anch’essa già inizializzata) contenga il numero di quartetti effettivamente inseriti in ElencoQuartetti.


#include <stdio.h>

#define MAX_QUARTETTI 100

int main (){

TipoQuartetto ElencoQuartetti[MAX_QUARTETTI]; int numQuartetti[MAX_QUARTETTI];

/* inizializzazione delle variabili sopra dichiarate, da considerare già fatta */ TipoQuartetto QuartettiSenzaPiano[MAX_QUARTETTI]; TipoQuartetto QuartettiConPiano[MAX_QUARTETTI]; int numQuarSenzaPiano = 0, numQuarConPiano = 0, i, j, trovato;

for (i = 0; i < numQuartetti; i++){

j = 0; trovato = 0;

while (trovato == 0 && j<4){

if (ElencoQuartetti[i].musicisti[j].strumento == pianoforte){

trovato = 1; } j++; }



if (trovato == 0){

QuartettiSenzaPiano[numQuarSenzaPiano] = ElencoQuartetti[i]; numQuarSenzaPiano++; }

else{

QuartettiConPiano[numQuarConPiano] = ElencoQuartetti[i]; numQuarConPiano++; }

}printf("Quartetti senza piano:\n");

for (i = 0; i < numQuarSenzaPiano; i++){

printf("%s\n", QuartettiSenzaPiano[i].nome); } printf("Quartetti con piano:\n"); for (i=0; i < numQuarConPiano; i++)

{ printf("%s\n", QuartettiConPiano[i].nome); }}

Esercizio 6.6Scrivere un programma C che esegue le seguenti operazioni.Legge da tastiera una sequenza di esattamente 64 pacchetti di 4 bit ciascuno (si ricorda che un pacchetto di 4 bit altro non è che una sequenza di 4 interi che possono assumere solo i valori 0 o 1). Un pacchetto è ammissibile solo se contiene solo 0 e 1; pacchetti non ammissibili vanno reimmessi.Un pacchetto ammissibile è detto corretto se e solo se il numero di 1 in tutto il pacchetto è pari.Il programma, quindi, per ogni pacchetto ammissibile, verifica se il pacchetto è corretto, e, dopo avere letto tutti i pacchetti, stampa prima i pacchetti corretti, quindi quelli scorretti.



#define MAX_PACC 64

typedef int TipoPacchetto[4];

int main (){

TipoPacchetto corretti[MAX_PACC], non_corretti[MAX_PACC], corrente;int i, j, k, h, somma, n_corretti, n_non_corretti;bool ammissibile;

i = 0; j = 0; k = 0;while(i < MAX_PACC){

printf("Pacchetto numero %d (4 bit, separare i singoli bit con degli spazi): ", i+1);

scanf("%d %d %d %d", &corrente[0], &corrente[1], &corrente[2], &corrente[3]);ammissibile = true;somma = 0;for(h = 0 ; h < 4 ; h++){

if(corrente[h] > 1 || corrente[h] < 0) {

ammissibile = false;



}else{

somma += corrente[h];}

}if (ammissibile){

if (somma % 2 == 0){

for(h = 0; h < 4; h++) {

corretti[j][h] = corrente[h];}j++;

}else{

for(h = 0 ;h < 4; h++){

non_corretti[k][h] = corrente[h];}k++;

}i++;

}else{

printf("Pacchetto immesso non ammissibile, reimmetterlo!\n");}

}

n_corretti = j;n_non_corretti = k;printf("Pacchetti corretti:\n”);for(j = 0; j < n_corretti; j++){

for(h = 0; h < 4; h++){

printf("%d", corretti[j][h]);}printf("\n");

}

printf("Pacchetti NON corretti:\n");for(j = 0; j < n_non_corretti; j++){

for(h = 0; h < 4; h++){

printf("%d", non_corretti[j][h]);}printf("\n");

}}

Esercizio 6.7Con riferimento all’Esercizio 5.6, si scriva un main() che, senza curarsi di come viene inizializzata la variabile elencoCD (che supponiamo già caricata con i dati di interesse), esegue le seguenti operazioni:

- chiede all’utente di inserire un anno (compreso tra 1990 e 1999);- per ogni trimestre di quell’anno (Gen-Mar, Apr-Giu, Lug-Set, Ott-Dic) stampa a video il

numero di CD (contando anche le copie multiple dello stesso titolo) acquistati in quel periodo.




#include <stdio.h>

#define MAX_L_TITOLO 50#define MAX_L_AUTORE 60#define MAX_TIT_IN_MESE 50

typedef struct{

char titolo[MAX_L_TITOLO]; char autore[MAX_L_AUTORE]; int anno; int n_copie;} TipoDatiCD;

typedef struct{

TipoDatiCD cd[MAX_TIT_IN_MESE]; int n_titoli;} CDAcqInMese;

/* Le righe di ‘elencoCD’ corrispondono agli anni dal 1990 al 1999, le colonne ai 12 mesi di ciascun anno */

CDAcqInMese elencoCD[10][12];

int main () {

int anno; int i, j, k, totale_cd_trimestre;

do{

printf("Inserisci un anno compreso tra 1990 e 1999: "); scanf("%d", &anno); } while (anno < 1990 || anno > 1999);

/* tramuto l’anno interno nella riga corrspondente dell’array doppio ‘elencoCD’ */anno = anno - 1990;

/* il ciclo piu’ esterno conta i trimestri, quello piu’ interno i mesi del trimestre */

for(i = 0; I < 4; i++) {

totale_cd_trimestre = 0; for(j = 0; j < 3; j++)

{ /* conto il numero di CD acquistati nel mese i*3+j e li aggiungo

al totale del trimestre*/ for(k = 0; k < elencoCD[anno][i*3+j].n_titoli; k++)

{totale_cd_trimestre += elencoCD[anno][i*3+j].cd[k].n_copie;

} }

printf("Totale CD del trimestre n. %d dell’anno %d: %d\n", i+1, anno+1990, totale_cd_trimestre);

}}




Legge dallo StandardInput due stringhe di caratteri (lunghe al massimo 100 caratteri l’una) separate tra loro dal carattere speciale (non appartenente alle stringhe) ‘#’ e terminate dallo stesso carattere ‘#’ (si supponga pure che l’utente non immetta mai stringhe più lunghe di 100 caratteri).

Verifica che le lunghezze delle due stringhe (senza contare il carattere ‘#’) differiscano al massimo di un’unità. In caso contrario interrompa l’esecuzione scrivendo sullo StandardOutput un opportuno messaggio.

Scriva sullo StandardOutput una stringa ottenuta alternando i caratteri delle due stringhe di ingresso (un carattere di una stringa seguito da un carattere dell’altra mantenendo l’ordine originario tra i caratteri della stessa stringa) secondo la regola seguente:

o Se una delle due stringhe è più lunga dell’altra si deve cominciare con il primo carattere della stringa più lunga.

o Se le due stringhe sono di lunghezza uguale, si può cominciare con una qualsiasi delle due.

o Facoltativamente, se la stringa risultante è più lunga di 80 caratteri, ogni 80 caratteri scritti si deve andare a capo.


#include <stdio.h>

#define MAX_L 100

int main (){ char s1[MAX_L], s2[MAX_L], curr; int n_el1=0, n_el2=0; int i; do { scanf("%c", &curr); if (curr != ‘#’) { s1[n_el1] = curr; n_el1++; } } while(curr != ‘#’);

do { scanf("%c", &curr); if(curr != ‘#’) { s1[n_el2] = curr; n_el2++; } } while(curr != ‘#’); if(n_el1-n_el2 <= 1 && n_el1-n_el2 >= -1) {

/* caso in cui la stringa 1 è più lunga della stringa 2 */ if(n_el1 > n_el2) { for (i=0; i<n_el2; i++) { printf("%c%c", s1[i], s2[i]); if(((i+1)*2) % 80 == 0) printf ("\n"); } /* chiude il for */



printf("%c, s1[n_el1-1]) } /* chiude il ramo then dell’if interno*/ else { /*n_el2 >= n_el1*/ for (i=0; i<n_el1; i++) { printf("%c%c", s2[i], s1[i]); if(((i+1)*2) % 80 == 0) printf ("\n"); } /* chiude il for */

/*se le due stringhe sono di lunghezza diversa*/ if(n_el2 > n_el1) printf ("%c, s2[n_el2-1]) } /* chiude il ramo else dell’if precedente*/ } else { printf ("Le lunghezze delle stringhe differiscono tra loro di più di una unità"); }}

Esercizio 6.9Scrivere una sequenza di istruzioni nel linguaggio di von Neumann –utilizzando le istruzioni in versione simbolica definite dalla tabella del Capitolo 2– che sia equivalente alla seguente istruzione C:

do x = x – z;while (x > z)

Si assuma che le celle della macchina di von Neumann corrispondenti alle variabili C x, z siano, rispettivamente: 101, 102.


La sequenza di istruzion C proposta nell’esercizio può essere tradotta nel linguaggio della macchina di von Neumann nella seguente maniera:

k: LoadA 101k+1: LoadB 102k+2: SubABk+3: StoreA 101k+4: SubABk+5: BGA k:

Esercizio 6.10Scrivere un programma che legge da tastiera una sequenza di esattamente 10 numeri razionali, ognuno formato da numeratore e denominatore (sia numeratore che denominatore devono essere numeri interi) e:

c) verifica che tutti abbiano denominatore diverso da zero;

d) se tutti i numeri hanno denominatore diverso da zero stampa a video:

a. la media dei numeri che sono interi (cioè con numeratore multiplo del denominatore)

b. il prodotto di tutti i numeri





typedef struct { int num; int den;} TipoRazionale;

int main(){ TipoRazionale seq[10]; int i, int n_int = 0; double media = 0.0; TipoRazionale prod; bool flag = true;

for (i = 0; i < 10; i++) { printf("inserisci numero razionale nella forma <numeratore/denominatore>: "); scanf("%d/%d", &seq[i].num, &seq[i].den); if (seq[i].den == 0) flag = false; } if (flag) { for (i=0; i<10; i++) { if (seq[i].num%seq[i].den == 0) { n_int++; media += seq[i].num/seq[i].den; } prod.num = prod.num * seq[i].num; prod.den = prod.den * seq[i].den; } if (n_int > 0) media = media / n_int; printf("media numeri interi: %f\n", media); printf("prodotto numeri: %d/%d\n", prod.num, prod.den); }}



Capitolo 7Funzioni e procedure

Funzioni e procedure, parametri e valore di ritorno; stringhe.

Esercizio 7.1Si consideri la seguente dichiarazione di tipo:

typedef struct{

int campo1; int campo2;int campo3;int campo4;

} Struttura;

Parte 1. Si scriva una funzione che riceva un parametro di tipo Struttura e produca come risultato un valore dello stesso tipo in cui i campi risultino invertiti (il valore di campo4 si trovi in campo1 e quello di campo3 in campo2).

Parte 2. Si trasformi poi la funzione in una procedura che esegua la medesima operazione sulla variabile di tipo struttura che le è passata come parametro.


Parte 1.Struttura InvertiStruttura (Struttura param){

Struttura varloc;

varloc.campo1 = param.campo4;varloc.campo2 = param.campo3;varloc.campo3 = param.campo2;varloc.campo4 = param.campo1;return varloc;

}

Parte 2.void ProcInvertiStruttura (Struttura *param){

Struttura varloc;

varloc.campo1 = param->campo4;varloc.campo2 = param->campo3;varloc.campo3 = param->campo2;varloc.campo4 = param->campo1;param->campo4 = varloc.campo4;param->campo3 = varloc.campo3;param->campo2 = varloc.campo2;param->campo1 = varloc.campo1;

}

Esercizio 7.2Data la seguente funzione calcola():



int calcola (int *a, int b, int *c){

*a = *a * 2;b = b * 2;*c = *c - 2;

return *a + b + *c;}

Qual è l’output del seguente frammento di programma?

#include <stdio.h>int main (){

int z;int *y;int x;

y = &x;z = 1;*y = 2;x = 3;z = calcola(&z,x,y);printf("%d, %d",z,x);

}


Il frammento di programma stampa, nell’ordine, i valori 9 e 1. Infatti, prima della chiamata di calcola(), z ha valore 1, y contiene l’indirizzo di x, ed x vale 3 (quindi *y vale anch’esso 3).Durante l’esecuzione di calcola(), x passa da 3 ad 1 con l’istruzione *c = *c – 2.z viene anch’esso modificato (è passato per indirizzo), ma questa modifica viene poi annullata quando, al termine di calcola(), il valore ritornato dalla funzione è assegnato a z. Poichè calcola() ritorna 9 (la funzione era stata chiamata con z=1, x=3, *y=3), z alla fine vale 9.

Esercizio 7.3Data la seguente funzione calcola():

int calcola(int *a, int b, int *c){

*a = *a * b;b = b * 2;*c = *a - b;

return *a + b + *c;}

Ed il seguente programma:

int main (){

int z;int *y;

int x;

y = &x; z = -1; *y = 1; x = 2; z = calcola(y,x,&z);



}

Mostrare lo stato delle variabili x, y e z al termine dell’invocazione di calcola().


Alla fine del main(), la variabile x contiene il valore 4, la y punta a x, quindi *y a sua volta vale 4, mentre z vale 8. Infatti, prima della chiamata di calcola, z ha valore –1, y contiene l’indirizzo di x, ed x vale 2 (quindi *y vale anch’esso 2).Durante l’esecuzione di calcola(), x passa da 2 ad 4 con l’istruzione *a = *a * b.z viene anch’esso modificato (è passato per indirizzo), ma questa modifica viene poi annullata quando, al termine di calcola(), il valore ritornato dalla funzione è assegnato a z. Poichè calcola ritorna 8 (la funzione era stata chiamata con z=-1, x=2, *y=2), z alla fine vale 8.

Esercizio 7.4Si scriva un insieme di dichiarazioni di tipo per la rappresentazione dello stato di un apparecchio TV. Esso deve contenere una descrizione dello stato del televisore (acceso/spento, canale, posizione dei vari controlli: luminosità, volume, ecc.).Si scrivano poi i prototipi (non le definizioni complete) di alcune funzioni corrispondenti ai comandi. Ad esempio, una funzione cambiaCanale() potrebbe assegnare al televisore il canale impostato dall’utente; un’ulteriore funzione incrementaCanale(), innescata dalla pressione del tasto corrispondente, dovrebbe determinare il passaggio dal canale attuale al successivo; ecc.Successivamente si scrivano le definizioni di almeno due delle procedure suddette.



#define INCREMENTO 0.1

typedef struct{

bool acceso; unsigned int canale; float luminosita; /* Tra 0 e 1 */ float saturazione; /* Tra 0 e 1 */ float volume; /* Tra 0 e 1 */} Televisore;

/* Prototipi delle funzioni */void cambiaCanale (Televisore *stato, unsigned int nuovoCanale);void accendiSpegni (Televisore *stato);void incrementaCanale (Televisore *stato);void decrementaCanale (Televisore *stato);void incrementaVolume (Televisore *stato);void decrementaVolume (Televisore *stato);void incrementaSaturazione (Televisore *stato);void decrementaSaturazione (Televisore *stato);void incrementaLuminosita (Televisore *stato);void decrementaLuminosita (Televisore *stato); int main (){ Televisore stato;

/* Per esempio, accendiamo e spegniamo il televisore */ stato.acceso = false; printf ("%d", stato.acceso);



accendiSpegni (&stato); printf ("%d", stato.acceso); accendiSpegni (&stato); printf ("%d", stato.acceso);}

/* Definizione delle funzioni */void incrementaCanale (Televisore *stato){ if (stato->canale < 99) stato->canale = stato->canale + 1;}

void incrementaVolume (Televisore *stato){ if (stato->volume + INCREMENTO <= 1) stato->volume = stato->volume + INCREMENTO;}

void accendiSpegni (Televisore *stato){ stato->acceso = ! stato->acceso;}

/*… definizione delle funzioni rimanenti. */

Esercizio 7.5Si scriva un programma che: Legge dallo standard input una sequenza di coppie di numeri reali {<xi , yi>} (per comodità si

può assumere che tale sequenza non contenga più di KMAX elementi, essendo KMAX un valore costante noto a priori).

Per ogni coppia <xi , yi> calcola il valore zi della funzione f(xi,yi) = 20xi2 – yi

3. Stampare sullo standard output la sequenza di valori { zi } in ordine crescente.Ad esempio, in corrispondenza della sequenza di input {<0,5>, <2,4>, <1,3>} il programma deve stampare in uscita la sequenza {–125, –7, 16}.È particolarmente apprezzata la costruzione di un programma che sia facilmente modificabile in modo da risolvere lo stesso problema facendo però riferimento ad una diversa funzione f(xi,yi); ad esempio, f(xi,yi) = sin(xi) · cos3(yi).Se lo si ritiene opportuno è possibile fare uso di adeguati sottoprogrammi di servizio (ad esempio una procedura di ordinamento) senza codificarli ma limitandosi a dichiararne opportunamente l’interfaccia.


#include <stdio.h>

#define KMAX 10

typedef struct{

float x; float y;} Coppia;

/* Dichiarazione prototipi */float eleva (float base, unsigned int esp);float funzione (Coppia c);void ordina (float ris[], unsigned int n);

int main (){



float risultati[KMAX]; unsigned int nCoppie, i; Coppia c; printf ("Quante coppie (max %u): ", KMAX); scanf ("%u", &nCoppie); for (i = 0; i < nCoppie; i++) { printf ("x: "); scanf ("%f", &c.x); printf ("y: "); scanf ("%f", &c.y); risultati[i] = funzione(c); } ordina (risultati, nCoppie); for (i = 0; i < nCoppie; i++) printf ("risultato: %f\n", risultati[i]); }

/* Definizione delle funzioni *//* Si assume che la funzione ordina() sia fornita dall’esterno */

float eleva (float base, unsigned int esp){

unsigned int i; float tot = 1.0; for (i = 0; i < esp; i++) tot = tot * base; return tot;} float funzione (Coppia c){

return 20 * eleva (c.x, 2) - eleva (c.y, 3);}

Esercizio 7.6Si consideri una versione ridotta del C in cui non esista il costrutto “puntatore”. È noto che tale meccanismo è indispensabile in C per realizzare, tra l’altro il passaggio parametri “per indirizzo”. Come sarebbe possibile allora costruire sottoprogrammi il cui effetto sia di modificare in modo parametrico una variabile del chiamante (ad esempio inserendo un elemento in una tabella) essendo sprovvisti di puntatori?NB. Si possono adottare le seguenti ipotesi semplificative:

Il tipo dei parametri che si intende modificare è un tipo semplice I sottoprogrammi non possono essere ricorsivi.

Soluzione dell’Esercizio 7.6In mancanza del costrutto puntatore, per poter modificare in modo parametrico una variabile del chiamante si può procedere in vari modi.Una semplice soluzione consiste nel trasformare tutte le procedure che avrebbero fatto uso del passagio parametri per indirizzo in funzioni, e sfruttare il valore di ritorno per modificare una variabile qualsiasi del chiamante. Ad esempio:

void foo(int* item){

*item++;}

int main()



{int a;foo(&a);

}

diventa allora:

int foo(int item){

return item + 1;}

int main(){

int a;a = foo(a);

}

In questo modo però ogni procedura potrebbe modificare solo un parametro.Una soluzione alternativa –escludendo il caso di sottoprogrammi ricorsivi– è invece quella di associare a tutte le variabili che necessiterebbero di passaggio per indirizzo una variabile globale. In questo caso, ogni chiamata a procedura deve essere preceduta da un assegnamento alla variabile globale del valore del parametro attuale. La procedura tratterà la variabile globale come se fosse un parametro. Al ritorno dalla procedura il chiamante “preleverà” il valore dalla variabile globale riasssegnandolo al parametro attuale:


*item++;}

int main(){

int a,b;foo(&a); foo(&b);

}

diventa allora:

int parametrovoid foo(){

parametro++;}

int main(){

int a,b;parametro = a;

/* “simuliamo” il passaggio del parametro memorizzando il valore di ‘a’ nella variabile globale parametro */

foo();a = parametro; /* Recuperiamo il valore modificato */parametro = b;foo();b = parametro; /* Recuperiamo il valore modificato */

}

Se invece si volesse permettere l’uso della ricorsione si potrebbe associare ad ogni parametro da modificare una stack. Ad ogni chiamata, incluse quelle ricorsive, si dovrebbe incrementare il



valore dell’indice della stack –anch’esso usato come variabile globale– e memorizzarvi il valore del parametro attuale, operando in modo inverso al ritorno dal sottoprogramma:


*item++;} int main(){

int a,b;foo(&a); foo(&b);

}

diventa allora:

int indice = -1int stack[MaxRic];

/* MaxRic indica un massimo livello di ricorsione possibile, sarà opportuno operare una verifica ad ogni chiamata per evitare overflow */

void foo() {

stack[indice]++;} int main() {

int a,b;indice++; stack[indice] = a; /* controllare eventuale overflow */foo();a = stack[indice]; /* Recuperiamo il valore modificato */indice--;indice++; stack[indice] = b;foo();b = stack[indice]; /* Recuperiamo il valore modificato */indice--;

}

NB: un’eventuale chiamata ricorsiva all’interno di foo opererebbe alla stessa maniera

Esercizio 7.7Si consideri il seguente frammento di codice C (i puntini indicano parti omesse in quanto inessenziali ai fini dell’esercizio).

…int x = 10;int z = 5;…

int foo (int p) {

z = z + x + p;}

int main(){

int x = 8;foo(x);…

}



Quale valore assume z dopo l’esecuzione di foo(x) nel main?


Quando il main() chiama foo() gli passa il valore 8 della propria variabile locale x: di conseguenza il parametro formale p di foo() assume il valore 8. La variabile x cui foo() fa riferimento non è la variabile locale x del main() bensì la variabile globale che vale 10. Il valore di z diventa quindi, in seguito alla chiamata 5 + 10 + 8 = 23.



Capitolo 8Introduzione alla programmazione ricorsiva

La ricorsione.

Esercizio 8.1Sia data la funzione ricorsiva:

int elabora(int n1, int n2){

int a, b;

a = n1 + 1; b = n2 - 1;

if (b <= 0) return a; else return alabora(a,b);}

Descrivere l’esecuzione della funzione in seguito all’invocazione: elabora(4,3).


La sequenza di chiamate ricorsive della funzione elabora() è la seguente:

elabora(4,3)elabora(5,2)elabora(6,1)

Alla fine il valore ritornato dalla chiamata elabora(4,3) è 7.

Esercizio 8.2Sia data la funzione ricorsiva seguente:

void elabora (unsigned int i){

if (i <= 1)printf("%u\n", i);

else{

printf("%u", i % 2); elabora(i / 2); }}

Descrivere l’esecuzione della funzione in seguito all’invocazione elabora(10), specificando che cosa rimane visualizzato sullo schermo alla fine dell’esecuzione.


La sequenza di chiamate ricorsive della funzione elabora() è la seguente:



elabora(10)elabora(5)elabora(2)elabora(1)

Alla fine rimane visualizzata la seguente sequenza di valori: 0101. La funzione elabora() infatti calcola in maniera ricorsiva la rappresentazione binaria (scritta con la cifra meno significativa a sinistra) del numero passatole.

Esercizio 8.3Si consideri la seguente funzione, che calcola l’n-simo numero di Fibonacci in modo ricorsivo:

int fibonacci(unsigned int n){

if (n == 0)return 0;

else if (n == 1)return 1;

elsereturn fib(n – 1) + fib(n – 2);

}

Si descriva la computazione di fibonacci(4).


La sequenza di chiamate ricorsive della funzione fibonacci() è la seguente:

fibonacci(4)fibonacci(3) + fibonacci(2)fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)fibonacci(1) + fibonacci(0) + 1 + 1 + 01 + 0 + 1 + 1 + 03

Esercizio 8.4Data la seguente definizione ricorsiva:

f(x) = 0; per x = 0f(x) = 2 + f(f(x – 2) – 2); per x > 0

1. Si determini per quali valori interi di x è definita la funzione e quale è il suo valore.2. Si scriva una funzione ricorsiva che realizzi la funzione stessa. Il prototipo della funzione

sia il seguente:

int f1 (int x);

3. Si scriva una funzione che realizzi la funzione e restituisca come parametro il numero di chiamate ricorsive effettuate. Il prototipo della funzione sia il seguente:

int f2 (int x, int *numChiamate);



NB: si supponga che, al momento della prima chiamata, il valore di numChiamate sia correttamente inizializzato a 0.


Parte 1.

La funzione è definita solo per x = 0.

Parte 2.

int f1(int x){

if (x == 0) return 0; else if (x > 0) return 2 + f(f(x-2)-2); else { printf ("ERRORE x=%d\n", x); exit(-1); } }

Parte 3.

int f2(int x, int *numChiamate){

*numChiamate = *numChiamate + 1; if (x == 0) return 0; else if (x > 0) return 2 + f(f(x - 2, numChiamate) - 2, numChiamate);

else { printf ("ERRORE x=%d, nunChiamate=%d\n", x, *numChiamate);

exit(-1); } }

Esercizio 8.5Siano date le seguenti funzioni C.

int foo (int x){

if (x == 0) return 0;else boo(x - 1);

}

int boo(int y) {

if (y == 0) return -1;else foo(y - 1);

}

Quale valore viene ritornato dall’esecuzione di foo(3), di boo(1) e di foo(-1), rispettivamente?




L’esecuzione di foo(3) ritorna –1 (boo(0) alla base della ricorsione) , l’esecuzione di boo(1) ritorna 0 (foo(0) alla base della ricorsione), mentre l’esecuzione di foo(-1) genera un errore di overflow. Infatti, le due funzioni si alternano decrementando di 1 l’argomento con cui vengono chiamate finchè questo non risulta pari a zero. Se l’argomento iniziale è negativo in partenza tale procedura ha termine solo quando il calcolatore raggiunge il limite inferiore del tipo numerico considerato (int in questo caso), generando appunto un errore di overflow.

Esercizio 8.6Sia data la funzione ricorsiva seguente:

int Elabora(int *x, int y) {

if (*x == y) return y

else{

*x = *x -1;y++;return Elabora(x, y)

}

}

Si dica per quali valori dei parametri attuali (o delle variabili da essi puntati) l’esecuzione della funzione termina e che risultato produce.


Siano a e b i valori dei parametri attuali corrispondenti a x e y, rispettivamente. L’esecuzione di Elabora termina solo se *a – b è un valore non negativo e pari; in tal caso il risultato prodotto è:b + (*a – b)/2.

Esercizio 8.7Parte a

Sia data la funzione ricorsiva seguente:

float Elabora (float x, y){ if (y – x < 0)

return (x + y)/2 else Elabora(x+1, y-1);

}

Descrivere l’esecuzione della funzione e il risultato da essa prodotto in seguito alle invocazioni Elabora(1, 11), Elabora(11, 1), Elabora(3.3, 6.7), Elabora(2, 3), Elabora(-4, -6).

Parte b

Si ricodifichi la funzione Elabora() della parte a in modo tale che essa produca lo stesso risultato, senza però far uso della ricorsione.




Parte a

La funzione, ad ogni chiamata ricorsiva, incrementa x e decrementa y a meno che y non sia maggiore di x. Per esempio, per la chiamata Elabora(1, 11), le chiamate ricorsive successive sono:Elabora(1, 11), Elabora(2, 10), Elabora(3, 9), Elabora(4, 8), Elabora(5, 7), Elabora(6, 6), Elabora(7, 5)e alla fine ritorna la media dei due numeri, cioè 6.Quindi, i risultati delle varie chiamate sono:

Elabora(1, 11) = 6Elabora(11, 1) = 6Elabora(3.3, 6.7) = 5Elabora(2, 3) = 2.5Elabora(-4, -6) = -5

La funzione calcola la media di x e y.

Parte b

float ElaboraNonRic(x, y){ while(x < y){ x++; y--; } return (x+y)/2;}

In alternativa, avendo capito che la funzione altro non fa che calcolare la media di x ed y, si poteva implementare la funzione non ricorsiva in questa maniera:

float ElaboraNonRic(x, y){ return (x+y)/2;}



Capitolo 9Gestione dei file

I file di testo e i file binari.

Esercizio 9.1Con riferimento all’Esercizio 5.4 si scriva la funzione inserisciMedia() che legge un file binario contenente i dati di tutti gli studenti di un ateneo, privi della media dei voti riportati e lo aggiorna inserendo nell’apposito campo la media suddetta.

La funzione dovrà a sua volta far uso di un’ulteriore, appropriata, funzione che calcoli la media. È sufficiente fornire la dichiarazione di tale funzione ausiliaria, senza fornirne la definizione completa.



typedef struct{

unsigned short giorno;unsigned short mese;unsigned int anno;

} Tipo_data;

typedef struct{

char nome[40];char codice[6];unsigned short voto;bool lode;float crediti;

} Tipo_esame;

typedef struct{

char nome[50];unsigned int matricola;Tipo_data data_immatricolazione;Tipo_esame esami[29];unsigned short numero_esami;float media;

} Tipo_studente;

/* La funzione media() non viene implementata */float media (Tipo_esame esami[], unsigned short numEsami);void inserisciMedia(char nomeFIle[]);

int main (){

/* Il main del programma... */}

void inserisciMedia(char nomeFile[]){

FILE *fileDati; Tipo_studente studente;



fileDati = fopen(nomeFile, "r+"); fread (&studente, sizeof(studente), 1, fileDati); while (! feof(fileDati)) { studente.media = media (studente.esami, studente.numero_esami); fread (&studente, sizeof(studente), 1, fileDati);

/* Torna indietro per scrivere le modifche sullo stesso record */ fseek (fileDati, -sizeof(studente), SEEK_CUR); fwrite (&studente, sizeof(studente), 1, fileDati); } fclose (fileDati);}

Esercizio 9.2Con riferimento all’Esercizio 5.5 si definiscano i tipi TipoStrumentista e TipoQuartetto come nell’esercizio suddetto.Si definisca inoltre un tipo TipoConcerto costituito dal nome della località in cui il concerto si è tenuto (massimo 40 caratteri), dalla data in cui si è tenuto il concerto, e dal quartetto che ha tenuto il concerto.Si supponga poi di avere un file binario contenente un elenco di concerti. Si supponga inoltre che il file sia già stato aperto in modalità (binaria) lettura/scrittura.Si risolva a scelta una delle seguenti varianti.

Variante aDopo avere dichiarato eventuali variabili globali, definire una funzione CancellaConcertiDiQuartetto() che riceve in ingresso il nome di un quartetto, e crea un nuovo file (sempre binario), di nome “NuovaListaConcerti.dat”, contenente l’elenco di tutti i concerti esclusi quelli del quartetto il cui nome è stato passato alla funzione. La funzione ritorna 1 se l’operazione è andata a buon fine, 0 altrimenti. Il file originario con l’elenco dei concerti rimane immutato.

Variante b Dopo avere dichiarato eventuali variabili globali, definire una funzione CancellaConcertiDiQuartetto() che riceve in ingresso il nome di un quartetto, e cancella dal file con l’elenco dei concerti tutti i concerti tenuti dal quartetto il cui come è stato passato alla funzione. La funzione ritorna 1 se l’operazione è andata a buon fine, 0 altrimenti; essa modifica il file originario con l’elenco dei concerti.In questa variante è ammesso (anzi, è consigliato) aprire file temporanei, in aggiunta al file originario.

Variante c Dopo avere dichiarato eventuali variabili globali, definire una funzione CancellaConcertiDiQuartetto() che riceve in ingresso il nome di un quartetto, e cancella dal file con l’elenco dei concerti tutti i concerti tenuti dal quartetto il cui come è stato passato alla funzione. La funzione ritorna 1 se l’operazione è andata a buon fine, 0 altrimenti; essa modifica il file originario con l’elenco dei concerti.In questa variante non è ammesso aprire file temporanei aggiuntivi, si può lavorare solo sul file originario.

Suggerimento per le varianti b e c: per troncare un file f alla lunghezza data dalla posizione corrente nel file, l’istruzione da usare è: ftruncate(fileno(f), ftell(f));




Definizione dei tipi; parte comune a tutte le varianti.

#define L_NOME_MUS 40#define L_NOME_QUAR 30#define MAX_QUARTETTI 100#define L_NOME_CONC 40

typedef struct{

short giorno; short mese; int anno;} TipoData;

typedef enum {pianoforte, basso, batteria, sax, trombone, flauto, clarinetto, voce} TipoStrumento;

typedef struct{ char nome[L_NOME_MUS + 1]; TipoData data_nascita; TipoStrumento strumento;} TipoStrumentista;

typedef struct{ char nome[L_NOME_QUAR + 1]; TipoStrumentista musicisti[4];} TipoQuartetto;

typedef struct{

char nome_loc[L_NOME_CONC + 1]; TipoData data; TipoQuartetto quartetto;} TipoConcerto;

Variante a.

#include <string.h>#include <stdio.h>

FILE *f_concerti;

int CancellaConcertiDiQuartetto(char nome_quar[]){

TipoConcerto curr_conc;

FILE *nf = fopen("NuovaListaConcerti.dat", "wb"); if (nf == NULL)

return 0;rewind(f_concerti);

while (! feof(f_concerti)){

if (fread(&curr_conc, sizeof(TipoConcerto), 1, f_concerti) == 1){

if (strcmp(curr_conc.quartetto.nome, nome_quar) != 0){

if (fwrite(&curr_conc, sizeof(TipoConcerto), 1, nf) != 1){

fclose(nf);return 0;

} } }

else



{fclose(nf);return 0;

} } if (fclose(nf) == 0)

return 1; else

return 0;}

Variante b.


FILE *f_concerti;


TipoConcerto curr_conc;

FILE *tmp_f = fopen("_temp.dat", "wb+"); if (tmp_f == NULL)

return 0;rewind(f_concerti);

while (! feof(f_concerti)){



if (fwrite(&curr_conc, sizeof(TipoConcerto), 1, tmp_f) != 1){

fclose(tmp_f);return 0;

} } }

else{


} } rewind(f_concerti); rewind(tmp_f); while (!feof(tmp_f))

{ if (fread(&curr_conc, sizeof(TipoConcerto), 1, tmp_f) == 1)

{ if (fwrite(&curr_conc, sizeof(TipoConcerto), 1, f_concerti) != 1)

{fclose(tmp_f);return 0;

} }

else{


} }

/* tronco il file all’ultima posizione in cui ho scritto (il file riscritto è in generale più corto del file originario) */

ftruncate(fileno(f_concerti), ftell(f_concerti));



if (fclose(tmp_f) == 0)return 1;

elsereturn 0;

}

Variante c.


FILE *f_concerti;


TipoConcerto curr_conc; /* tengo due indici nel file: la prossima posizione in cui

devo scrivere (pos_next_write) e la prossima posizione da cui devo leggere (pos_next_read) */

long pos_next_write, pos_next_read;

rewind(f_concerti); pos_next_write = ftell(f_concerti);

while (!feof(f_concerti)){



/* se il concerto è da mantenere, lo riscrivo nel file f_concerti alla prossima posizione in cui devo scrivere. Prima di scrivere, però,

devo memorizzare la posizione corrente nel file perchè a questa posizione dovrò poi tornare per ricominciare a leggere. */

pos_next_read = ftell(f_concerti);

/* mi sposto nel file alla posizione in cui devo scrivere, e poi effettivamente scrivo. */

if (fseek(f_concerti, pos_next_write, SEEK_SET))return 0;

if (fwrite(&curr_conc, sizeof(TipoConcerto), 1, f_concerti) != 1)return 0;

/* memorizzo la posizione corrente, che è la prossima posizione in cui dovrò scrivere, e mi riporto nella posizione

che è la prossima da cui devo leggere */ pos_next_write = ftell(f_concerti); if (fseek(f_concerti, pos_next_read, SEEK_SET))

return 0; } }

elsereturn 0;

}

/* mi riporto sulla posizione che è la prossima in cui scrivere (cioè appena dopo l’ultimo concerto che va conservato, e tronco il

file (il file riscritto è in generale più corto del file originario */

if (fseek(f_concerti, pos_next_write, SEEK_SET))return 0;

ftruncate(fileno(f_concerti), ftell(f_concerti)); return 1;}



Esercizio 9.3Si abbia un file (binario) “FileFatture.dat” contenente fatture. Ogni fattura sia del tipo TipoFatture dichiarato qui sotto:

typedef struct{

unsigned int NumFattura;char Nome[30];char Cognome[40];float Importo;char PartitaIva [12];/*altri campi irrilevanti per l’esercizio*/

} TipoFatture;

Si scriva una procedura che aggiorna una (e una sola!) fattura del file cambiandone l’importo da Lire a Euro (si ricorda che un Euro vale 1936,27 Lire). La procedura riceve come parametro il numero d’ordine della fattura nel file (si assuma che il numero di fattura ,denotato dal campo NumFattura, sia anche la posizione assunta dalla fattura nel file, cioè che la fattura numero 1 sia la prima, quella numero 2 la seconda, ecc.).Prima di procedere alla codifica della procedura si dichiarino eventuali variabili globali da essa utilizzate.Si supponga che il file sia già aperto al momento della chiamata della procedura.


FILE *file_fatture;

void aggiorna(unsigned int num_ord){

TipoFatture fattura;long pos_corr;

pos_corr = ftell(file_fatture);fseek(file_fatture, sizeof(TipoFatture)*(num_ord-1), SEEK_SET);fread(&fattura, sizeof(TipoFattura), 1, file_fatture);fattura.Importo = fattura.Importo/1936.27;fseek(file_fatture, sizeof(TipoFatture)*(num_ord-1), SEEK_SET);fwrite(&fattura, sizeof(TipoFattura), 1, file_fatture);fseek(file_fatture, pos_corr, SEEK_SET);

/*anche se non esplicitamente richiesto, la procedura lascia inalterata la posizione corrente del file*/

}

Esercizio 9.4Si scriva un programma che legge un file di parole appartenenti al vocabolario italiano o al vocabolario inglese e le ristampa su due file separati, uno per le parole inglesi e uno per quelle italiane.Si assuma che il programma abbia accesso (in memoria o su file) ai vocabolari delle due lingue.NB1. Si ponga attenzione a casi particolari come il fatto che una parola del file originario non si trovi in nessuno dei due vocabolari o che si trovi in entrambi, ecc. NB2. Non è necessaria una codifica in tutti i dettagli del programma completo: si può invece far uso di opportune procedure limitandosi a definire con precisione il loro uso (la loro interfaccia) senza per questo codificarne l’implementazione.


#include <stdio.h>



#include <stdbool.h>

/* Le funzioni inVocabolarioItaliano() e inVocabolarioInglese() non sono implementate… */

bool inVocabolarioItaliano (char parola[]);bool inVocabolarioInglese (char parola[]);void separaParoleItaIng (char nomeFilePar[], char nomeFileParIta[], char nomeFileParIng[]);

int main (){ char nomeFileParole[100], nomeFileParoleIta[100], nomeFileParoleIng[100]; printf ("Nome file di parole: "); scanf ("%s", nomeFileParole); printf ("Nome file di parole italiane: "); scanf ("%s", nomeFileParoleIta); printf ("Nome file di parole inglesi: "); scanf ("%s", nomeFileParoleIng); separaParoleItaIng (nomeFileParole, nomeFileParoleIta, nomeFileParoleIng);}

/* Si assume che una parola non sia lunga più do 50 lettere. Se la parola esiste in entrambi i vocabolari, viene scritta in entrambi i file */void separaParoleItaIng (char nomeFilePar[], char nomeFileParIta[], char nomeFileParIng[]){

FILE *fileParole, *fileParoleIta, *fileParoleIng; char parola[50]; fileParole = fopen (nomeFilePar, "r"); fileParoleIta = fopen (nomeFileParIta, "w"); fileParoleIng = fopen (nomeFileParIng, "w"); fscanf (fileParole, "%s", parola); while (! feof (fileParole)) {

if (inVocabolarioItaliano (parola)) fprintf (fileParoleIta, "%s\n", parola); if (inVocabolarioInglese (parola)) fprintf (fileParoleIng, "%s\n", parola); fscanf (fileParole, "%s", parola); } fclose (fileParole); fclose (fileParoleIta); fclose (fileParoleIng);}

Esercizio 9.5Si scriva un programma che, non facendo uso di accesso diretto a file (ossia usando esclusivamente le funzioni di libreria fopen, fclose, fread, fwrite e rewind), dato un file di interi “InputInteri” produca un nuovo file “OutputInteri” contenente gli stessi elementi del file di ingresso ma scritti in ordine inverso. Si assuma che la memoria centrale non sia sufficientemente grande da contenere l’intero file ma possa contenerne circa i 2/3.

NB:

1. Tra le varie possibili soluzioni sono da preferire quelle più efficienti.

2. È auspicata una soluzione che faccia uso di opportuni sottoprogrammi. Alcuni di essi, eventualmente, potrebbero essere definiti anche solo parzialmente mediante pseudocodice, evitando una codifica completa.



3. Eventualmente si può assumere l’ipotesi semplificativa che la dimensione del file sia nota a priori e valga la costante K. In tal caso però la qualità della soluzione peggiora.


int main (){

/* elInFile calcola il numero di interi nel file binario f (supposto già aperto in sola lettura). */

long int elInFile(FILE *f);

/* readArrayFromFile prende in ingresso il descrittore di un file binario (supposto aperto lettura) ed un array di interi, e legge n_el interi dal file, memorizzandoli

nell’array (supposto grande a sufficienza per contenere i dati).*/ void readArrayFromFile(FILE *f, int *ar, long int n_el);

/* reverseArrayInFile prende in ingresso il descrittore di un file binario (supposto vuoto e aperto in sola scrittura) ed un array di interi di lunghezza n_el e

scrive il contenuto dell’array nel file, partendo dall’ultimo elemento dell’array fino al primo.*/

void reverseArrayInFile(FILE *f, int *ar, long int n_el);

/* appendFile prende in ingresso i descrittori di due file binari fromFile ed inFile, il primo aperto in lettura, il secondo in scrittura, e scrive gli elementi del primo

file in fondo al secondo, mantenendo l’ordine in cui essi compaiono nel primo. */ void appendFile(FILE *fromFile, FILE *inFile);

FILE *in, *out, *tempFile; int *tempAr; long int tot_n_el, n_el;

in = fopen("InputInteri", "rb"); out = fopen("OutputInteri", "wb"); tot_n_el = elInFile(in); n_el = tot_n_el/2 + 1; tempAr = malloc(sizeof(int)*n_el);

rewind(in); readArrayFromFile(in, tempAr, n_el); tempFile = fopen("_tf", "wb+"); reverseArrayInFile(tempFile, tempAr, n_el); n_el = tot_n_el - n_el; readArrayFromFile(in, tempAr, n_el); reverseArrayInFile(out, tempAr, n_el); appendFile(tempFile, out);

fclose(in); fclose(out); fclose(temp);}

long int elInFile(FILE *f){ int temp; long int res = 0; rewind(f); while(fread(&temp, sizeof(int), 1, f) == 1){ res++; } return res;}

void readArrayFromFile(FILE *f, int *ar, long int n_el){ long int i; for(i=0 ; i<n_el ; i++){ fread(&ar[i], sizeof(int), 1, f); }



/* oppure, in alternativa, si poteva risolvere tutto con una istruzione singola: fread(ar, sizeof(int), n_el, f); */

}

void reverseArrayInFile(FILE *f, int *ar, long int n_el){ long int i; for(i=n_el-1 ; i>=0 ; i--){ fwrite(&ar[i], sizeof(int), 1, f); }}

void appendFile(FILE *fromFile, FILE *inFile){ int temp; rewind(fromFile); while(fread(&temp, sizeof(int), 1, fromFile) == 1){ fwrite(&temp, sizeof(int), 1, inFile); }}

Esercizio 9.6Si supponga di dover implementare un modulo di libreria per la gestione di un archivio di dati relativi alla Coppa del Mondo di Calcio – Germania 2006. Ogni squadra partecipante è caratterizzata da un nome e da un insieme di 23 giocatori al massimo. Ogni giocatore è caratterizzato da nome, cognome, data di nascita, gol segnati e ruolo (portiere, difensore, centrocampista, attaccante).

1)Si descrivano le dichiarazioni di tutte le strutture dati ritenute necessarie per la manipolazione dei suddetti dati e i prototipi di almeno le seguenti operazioni:a) un’operazione per la creazione iniziale della struttura dati,b) un’operazione che permetta l’inserimento di una nuova squadra da parte di un utente,c) un’operazione che permetta di inserire un nuovo giocatore in una squadra, dato il nome

della squadra,d) un’operazione che restituisca tutti i giocatori di una squadra, dato il nome della squadra,e) un’operazione che restituisca i 10 migliori marcatori del torneo.

2)Supponendo che nell’archivio vi siano già presenti alcune squadre ed almeno un giocatore per ciascuna di queste squadre, si implementino le funzioni 1d e 1e, supponendo che la struttura dati sia interamente contenuta in memoria centrale.

3)Si implementi una funzione readDatiSquadra() che, dato in ingresso il nome di un file, legga da questo tutti i dati necessari ad inserire nell’archivio una nuova squadra con i suoi giocatori. Il formato dei dati sul file può essere scelto a piacere, a patto che sia descritto con la necessaria precisione prima di descrivere l’implementazione vera e propria di readDatiSquadra().


Punto 1)

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>

/* Definizioni di costanti */



#define STRING_SIZE 80#define MAX_GIOCATORI 23#define MIGLIORI_MARCATORI 10

/* Struttura dati per la data */typedef struct{ unsigned int giorno; unsigned int mese; unsigned int anno;} Data;

/* Il ruolo di un giocatore */typedef enum {PORTIERE, DIFENSORE, CENTROCAMPISTA, ATTACCANTE} Ruolo;

/* I dati di un giocatore */typedef struct{ char nome[STRING_SIZE]; char cognome[STRING_SIZE]; Data nascita; unsigned int goals; Ruolo ruolo;} Giocatore;

/* L’elenco delle squadre è rappresentato come una lista a puntatori */typedef struct el{ char nome[STRING_SIZE]; Giocatore giocatori[MAX_GIOCATORI]; int giocatori_presenti; struct el *next;} DatiSquadra;

/* Verifica se l’archivio è vuoto */bool isEmpty(DatiSquadra* archivio)

/* Crea l’archivio */DatiSquadra *creaArchivio();

/* Aggiunge una nuova squadra all’archivio */DatiSquadra *aggiungiSquadra(char *nome_squadra, DatiSquadra *archivio);

/* Aggiunge un giocatore ad una squadra dato il nomeDatiSquadra *aggiungiGiocatore(char *nome, char *cognome, Data data_nascita,

unsigned int goals, Ruolo ruolo, char *nome_squadra, DatiSquadra *archivio);

/* Ritorna l’array dei giocatori di una data squadra, n_giocatori rappresenta la lunghezza dell’array ritornato */

Giocatore *ritornaGiocatori(char *nome_squadra, DatiSquadra *archivio, int *n_giocatori);

/* Ritorna un array con i 10 migliori marcatori del torneo, n_marcatori rappresenta la lunghezza dell’array ritornato (potrebbe infatti essere inferiore a 10) */

Giocatore *ritornaMiglioriMarcatori(DatiSquadra *archivio, int *n_marcatori);

Punto 2)

Giocatore *ritornaGiocatori(char *nome_squadra, DatiSquadra *archivio, int *n_giocatori)

{ DatiSquadra *temp = archivio; if (!isEmpty(archivio)) {

/* Scorre tutta la lista delle squadre controllandone il nome */ while (temp->next!=NULL) { if (strcmp(temp->nome, nome_squadra) == 0) {

/* Nel caso la squadra sia trovata, ritorna i dati relativi */ *n_giocatori = temp->giocatori_presenti;



return temp->giocatori; } } printf("Squadra non trovata!\n"); return NULL; } printf ("Archivio vuoto!\n"); return NULL;}

Giocatore *ritornaMiglioriMarcatori(DatiSquadra *archivio, int *n_marcatori){

/* Utilizza un array temporaneo dimensionato per il caso peggiore */ Giocatore temp_giocatori[MIGLIORI_MARCATORI]; Giocatore *res; int giocatori_trovati = 0; DatiSquadra *temp_list = archivio; int i, position;

if (!isEmpty(archivio)) {

/* Scorre la lista delle squadre */ while (temp_list->next!=NULL) {

/* Scorre la lista dei giocatori di una squadra */ for (i=0; i<temp_list->giocatori_presenti; i++) {

/* Se c’è posto, inserisce subito il giocatore */ if (giocatori_trovati < MIGLIORI_MARCATORI) { temp_giocatori[giocatori_trovati] = temp_list->giocatori[i]; giocatori_trovati++; } else {

/* Se già 10 marcatori sono stati trovati, richiama trovaPosizione per capire se e dove inserire questo giocatore (vedi dopo) */

position = trovaPosizione (temp_giocatori, temp_list->giocatori[i].goals);

if (position != -1) { temp_giocatori[position] = temp_list->giocatori[i]; } } } }

/* Alloca un array sullo heap per contenere il risultato della procedura e vi copia il risultato finale. L’array è dimensionato sulla base

della cardinalità vera e propria del risultato. */ res = malloc (sizeof(Giocatore)*giocatori_trovati); for (i=0; i<giocatori_trovati; i++) { res[i] = temp_giocatori[i]; } *n_marcatori = giocatori_trovati; return res; } printf ("Archivio vuoto!\n"); return NULL;}

/* Funzione ausiliaria per ritornaMiglioriGiocatori. Dato un numero di goal, esamina il contenuto corrente dell’array temporaneo sul quale si sta operando e ritorna la

posizione in cui il giocatore andrebbe inserito. Ritorna -1 se il numero di goal dato come parametro è inferiore al numero di goal segnati dal peggiore fra i migliori

marcatori. */int trovaPosizione (Giocatore *marcatori, int goals)



{ int i; int min_position = 0; int min_goals; if (marcatori != NULL) { min_goals = marcatori[0].goals;

/* Trova il marcatore che nel set corrente ha segnato meno goal */ for (i = 0; i<MIGLIORI_MARCATORI; i++) { if (marcatori[i].goals < min_goals) { min_position = i; min_goals = marcatori[i].goals; } }

/* Se il peggiore marcatore nel set corrente ha segnato meno goal di quello passato come parametro, ritorna la sua posizione per la sostituzione. Altrimenti,

ritorna -1. */ if (min_goals < goals) { return min_position; } } return -1;}

Punto 3)

Si suppone che i dati richiesti siano memorizzati in formato carattere in un unico file con due diversi separatori a distinguere il nome di una squadra dai suoi giocatori (analogamente per gli altri campi delle strutture dati). Ad esempio:

Italia#Gigi Buffon …@FabioCannavaro…@…@

Dato tale formato nel file, la procedura readDatiSquadra() può essere così implementata:

void readDatiSquadra (char *nome_file){ char nome_squadra[STRING_SIZE+2]; char nome_giocatore[STRING_SIZE+2]; char cognome_giocatore[STRING_SIZE+2]; char separatore[STRING_SIZE+2]; FILE* dati_squadra;

DatiSquadra *archivio = creaArchivio();

dati_squadra = fopen (nome_file, "r"); if (dati_squadra == NULL) { printf("Errore nell’apertura del file...\n"); return; }



/* Legge il nome della squadra */ fgets(nome_squadra, STRING_SIZE+1, dati_squadra); aggiungiSquadra(nome_squadra, archivio); fgets(separatore, STRING_SIZE+1, dati_squadra);

/* Controlla il separatore */ if (strcmp(separatore, "#") != 0) { printf ("Formato file errato\n"); fclose(dati_squadra); return; }

/* Legge i giocatori */ while (!feof(dati_squadra)) { fgets (nome_giocatore, STRING_SIZE+1, dati_squadra); fgets (cognome_giocatore, STRING_SIZE+1, dati_squadra);

… /* Lettura di eventuali altri campi */ fgets(separatore, STRING_SIZE+1, dati_squadra);

/* Controlla il separatore */ if (strcmp(separatore, "@") != 0) { printf ("Formato file errato\n"); fclose(dati_squadra); return; } else { aggiungiGiocatore (nome_giocatore, cognome_giocatore, … ,

nome_squadra, archivio); } }}

Esercizio 9.7Parte a. Sidefiniscano dei tipi di dato per contenere informazioni relative a patenti e multe.Una patente è definita da un numero identificativo, dal nome del proprietario, dal suo codice fiscale, da una data di rilascio e una di scadenza, e da un numero di punti ancora disponibili sulla patente.Una multa è definita da un numero identificativo, dal numero identificativo della patente cui viene addebitata, dalla data in cui è stata emessa, dall’ammontare della multa (in euro), dal numero di punti da togliere alla patente a causa della multa.

Parte b.Si codifichi un sottoprogramma che prende in ingresso i descrittori fpat e fmul di 2 file (entrambi supposti aperti sia in lettura che in scrittura), uno contenente una serie di patenti, ed uno contenente una serie di multe, e ritorna il descrittore di un nuovo file.Il sottoprogramma deve realizzare quanto segue: per ogni multa presente nel file fmul, il sottoprogramma modifica i dati della patente corrispondente nel file fpat, togliendo i punti indicati nella multa.Se una patente, dopo avere sottratto i punti di una multa, ha un residuo di punti minore o uguale a zero, il sottoprogramma scrive in un terzo file (il cui descrittore verrà ritornato alla fine) la posizione nel file fpat della suddetta patente.Si assuma che nel file fpat le patenti siano elencate in ordine di data di scadenza, mentre nel file fmul le multe siano ordinate secondo l’identificatore della patente a cui si riferiscono.Si supponga pure che tutte le multe del file fmul si riferiscano a patenti effettivamente esistenti nel file fpat.

Versione semplificata



Si assuma che per ogni patente nel file fmul si trovi al massimo una multa.

Parte c. Si codifichi un sottoprogramma che riceva in ingresso il nome di un file contenente patenti, e restituisca una lista contenente le patenti con meno di 10 punti residui, ordinate in ordine crescente di punti residui (cioè mettendo prima quelle con meno punti residui).


Parte a.

typedef struct { unsigned long id; char nome[80]; char CF[16]; TipoData rilascio; TipoData scadenza; int punti;} TipoPatente;

/* la dichiarazione di TipoData viene data per scontata. */

typedef struct { unsigned long id; unsigned long id_pat; TipoData emessa; float somma; int punti;} TipoMulta;

Parte b.

Versione completa.

FILE *aggiornaPatenti(FILE *fpat, FILE *fmul){ TipoMulta m_cor, m_prec; unsigned long id_pat; int totPunti; long pos_pat; bool next_pat; FILE *fsottozero = fopen("invalide.txt", "wb"); rewind(fmul); while(!feof(fmul)) { next_pat = false; totPunti = 0; do { fread(&m_cor, sizeof(TipoMulta), 1, fmul); if(totPunti == 0) {

/* è la prima multa che leggo relativa alla prossima patente */ totPunti = m_cor.punti; m_prec = m_cor; } else if (m_cor.id_pat == m_prec.id_pat) {

/* la multa appena letta si riferisce alla stessa patente della multa precedente, mi, limito a sommare i punti da togliere */

totPunti += m_cor.punti; }



else {

/* devo passare alla prossima multa; come prima cosa, ritorno sulla multa precedente */

fseek(fmul, -sizeof(TipoMulta), SEEK_CUR); m_cor = m_prec; next_pat = true; } } while(!feof(fmul) && next_pat == false);

/* Vado a cercare la patente da modificare nel file di patenti, quindi faccio i cambiamenti necessari; */

rewind(fpat); do { fread(&p, sizeof(TipoPatente), 1, fpat); } while(p.id != m_cor.id_pat); fseek(fpat, -sizeof(TipoPatente), SEEK_CUR); p.punti -= totPunti; pos_pat = ftell(fpat); fwrite(&p, sizeof(TipoPatente), 1, fpat);

/* se la patente ha un numero di punti <= 0, la segnalo nel file apposito;

if (p.punti <= 0) { fwrite(&pos_pat, sizeof(long), 1, fsottozero); } } /* fine del while esterno */ return fsottozero;}

Versione semplificata.

FILE *aggiornaPatenti(FILE *fpat, FILE *fmul){ TipoMulta m_cor, m_prec; unsigned long id_pat; int totPunti; long pos_pat; bool next_pat; FILE *fsottozero = fopen("invalide.txt", "wb"); rewind(fmul); while(fread(&m_cor, sizeof(TipoMulta), 1, fmul) == 1) {

/* Vado a cercare la patente da modificare nel file di patenti, quindi faccio i cambiamenti necessari; */

rewind(fpat); do { fread(&p, sizeof(TipoPatente), 1, fpat); } while(p.id != m_cor.id_pat); fseek(fpat, -sizeof(TipoPatente), SEEK_CUR); p.punti -= m_cor.punti; pos_pat = ftell(fpat); fwrite(&p, sizeof(TipoPatente), 1, fpat);

/* se la patente ha un numero di punti <= 0, la segnalo nel file apposito;

if (p.punti <= 0) { fwrite(&pos_pat, sizeof(long), 1, fsottozero); } } /* fine del while esterno */ return fsottozero;}

Parte c.

typedef struct EL {



TipoPatente info; struct EL *next;} ElListaPatenti;typedef ElListaPatenti *ListaPatenti;

bool inser_per_punti(ListaPatenti *l, TipoPatente p) { ElListaPatenti *pt_new_el; if (l == NULL) { pt_new_el = malloc(sizeof(ElListaPatenti)); pt_new_el->info = p; pt_new_el->next = NULL; *l = pt_new_el; return true; } if((*l)->info.punti > p.punti) { pt_new_el = malloc(sizeof(ElListaPatenti)); pt_new_el->info = p; pt_new_el->next = *l; *l = pt_new_el; return true; } else { return inser_per_punti(&((*l)->next), p); }}

ListaPatenti menoDi10(char *nome_file){ FILE *f = fopen(nome_file, "rb"); ListaPatenti res = NULL; TipoPatente p; while(fread(&p, sizeof(TipoPatente), 1, f) == 1) { if (p.punti < 10) inser_per_punti(&res, p); } return res;}

Esercizio 9.8Si consideri un archivio universitario per memorizzare la carriera degli studenti: per ogni studente sono memorizzati: nome, cognome, numero di matricola, l’elenco degli esami sostenuti indicante per ogni esame titolo dell’insegnamento, voto in trentesimi, eventuale lode, numero di crediti associato all’esame, valutazione della prova finale, espressa come un intero (maggiore di –2 e minore o uguale a 7).Si scriva un programma completo che prelevi i dati degli studenti dall’archivio realizzato mediante un opportuno file e produca un nuovo file che per ogni studente indichi il voto di laurea; il voto di laurea è ottenuto sommando alla media pesata dei singoli esami (un esame da 10 crediti “pesa il doppio” di un esame da 5; l’eventuale Lode non incide sulla media) l’incremento determinato dall’esito della prova finale. Il programma deve anche verificare che il totale dei crediti sia maggiore o uguale a una soglia prefissata (ad esempio 165 se la prova finale valesse 15 crediti)..È auspicato un opportuno uso di sottoprogrammi.


#include <stdio.h>



#include <string.h>#include <stdbool.h>

#define MAX_NUMERO_ESAMI 25#define MAX_CARATTERI 50#define MIN_CREDITI 165

/* definizione strutture dati */typedef struct {

char titolo_insegnamento [MAX_CARATTERI];short int voto;bool lode;float crediti;

} datiEsameStudente;

typedef struct {

char nome [MAX_CARATTERI];char cognome [MAX_CARATTERI];int matricola;int numero_Esami;datiEsameStudente carriera_studente [MAX_NUMERO_ESAMI];short int valutazione_prova_finale;

} datiAnagraficaStudente;

typedef struct {

char nome [MAX_CARATTERI];char cognome [MAX_CARATTERI];int matricola;int voto_laurea;

} datiMediaStudente;

bool leggiDatiStudenteDaArchivio (FILE *dati_input_studenti, datiAnagraficaStudente *archivioStudente)

{if (fread (archivioStudente, sizeof (datiAnagraficaStudente),

1, dati_input_studenti) == 1){return true;

}else{return false;

}}

float calcolaMediaStudente (datiAnagraficaStudente archivioStudente){

int i; float totaleCrediti = 0;float Totale_Voti_Pesati = 0;for (i = 0; i < archivioStudente.numero_Esami; i++){

Totale_Voti_Pesati = Totale_Voti_Pesati + archivioStudente.carriera_studente[i].voto * archivioStudente.carriera_studente[i].crediti;

totaleCrediti = totaleCrediti + archivioStudente.carriera_studente[i].crediti;

}if (archivioStudente.carriera_studente[i].crediti < MIN_CREDITI){

printf("numero di crediti insufficiente"); return 0;

}



/* per semplicità si fornisce media 0 se i crediti non sono sufficienti*/

return Totale_Voti_Pesati / totaleCrediti;}

bool scriviDatiFinaliStudente (FILE *dati_output_studenti, datiMediaStudente votoStudente)

{if (fwrite (&votoStudente, sizeof (datiMediaStudente), 1,

dati_output_studenti) == 1){

return true;}else{

return false;}

}

int main (){

/* definizione variabili */FILE *dati_input_studenti, *dati_output_studenti;datiAnagraficaStudente archivioStudente;datiMediaStudente votoStudente;float media;

/* apertura dei file di lavoro */dati_input_studenti = fopen ("archivio_studenti.dat", "rb");if (dati_input_studenti == NULL)

printf ("Errore nell’apertura del file di input\n");else{

dati_output_studenti = fopen ("archivio_voti_studenti.dat", "wb");if (dati_output_studenti == NULL){

printf ("Errore nell’apertura del file di output\n");fclose (dati_input_studenti);

}else{

/* ciclo di lettura dei dati */while (leggiDatiStudenteDaArchivio (dati_input_studenti, &archivioStudente)){

printf ("Calcolo della media di %s %s...\n", archivioStudente.nome, archivioStudente.cognome);

/* calcolo della media */media = calcolaMediaStudente (archivioStudente);if (media < 66)

printf ("lo studente non può laurearsi"); else{

printf (" %f\n", media); /* scrittura dei dati elaborati */

strcpy (votoStudente.nome, archivioStudente.nome);strcpy (votoStudente.cognome, archivioStudente.cognome);votoStudente.matricola = archivioStudente.matricola;votoStudente.voto_laurea = media +

archivioStudente.valutazione_prova_finale;scriviDatiFinaliStudente (dati_output_studenti, votoStudente);

}}

/* chiusura dei file di lavoro */fclose (dati_input_studenti);fclose (dati_output_studenti);

}



}}

Esercizio 9.9Si assuma che un file Persone sia costituito da record contenenti i seguenti campi:

Nome (una stringa di 20 caratteri)Cognome (una stringa di 30 caratteri)IndirizzoPadre (il numero d’ordine del record del file in cui è memorizzato il padre della persona descritta nel record – una sorta di puntatore che far riferimento a una posizione nel file invece che a un indirizzo di memoria)IndirizzoMadre (il numero d’ordine del record del file in cui è memorizzata la madre della persona descritta nel record)

I record del file sono numerati a partire dallo 0; se uno dei due campi IndirizzoPadre, IndirizzoMadre ha il valore –1, ciò significa che il record corrispondente al padre (madre) della persona non si trova nel file.Si assuma anche che non vi siano omonimie nel file (relativamente alla coppia <nome, cognome>)

Si scriva una dichiarazione di tipo di dato adatto a memorizzare il record suddetto; indi si scriva un sottoprogramma che, assumendo il file già aperto, riceva come parametri una coppia <nome, cognome> e produca in output nome e cognome del padre e della madre della persona corrispondente, segnalando eventualmente se la persona cercata o uno dei suoi genitori non si trova nel file; si scriva anche un’opportuna istruzione di apertura del file da far precedere alla chiamata del sottoprogramma.È permesso e consigliato fare uso di sottoprogrammi della libreria standard del C.


typedef struct{

string nome, cognome;long int IndirizzoPadre, Indirizzo Madre

} Persona

FILE *Pers

if ((Pers = fopen ("Persone", "rb+")) == NULL){

…}

…

int CercaPersone (string nome, cognome)/* Cerca nel file riferito da Pers l’individuo con i dati nome e cognome; ritorna il numero d’ordine del record del file che ne contiene il record;

se l’individuo cercato non esiste ritorna il valore convenzionale -1 */

void StampaPadreMadre (string nome, cognome){

int dim, posizione;persona Individuo, Padre, Madre;

dim = sizeof (Persona);



posizione = (CercaPersone (nome, cognome) ;if (posizione == -1)

printf ("individuo cercato non esiste nel file");else{

fseek (Pers, dim, posizione, SEEK_SET); fread (&Individuo, dim, 1, Pers);fseek (Pers, dim, individuo.IndirizzoPadre, SEEK_SET);numeroByteLetti = fread (&Padre, dim, 1, Pers);if (!numeroByteLetti == dim) printf ("non esiste nel file il padre dell’individuo cercato");

else printf ("il padre dell’individuo cercato è %s, %s",

Padre.nome, Padre.Cognome);/* ….segue codice simile per la madre delll’individuo cercato … */

}

Esercizio 9.10Si definisca un tipo di dato ContoCorrente contenente, tra l’altro, almeno i seguenti campi:- Numero del CC- Nome dell’intestatario- Importo presente sul CCSi definisca poi un sottoprogramma che riceva come parametro un numero di CC e un aggiornamento opportunamente codificato (ad esempio, un numero relativo, oppure un qualificatore “deposito/prelievo” seguito da un valore assoluto) ed apporti l’aggiornamento richiesto ad un file, supposto già aperto ed il cui descrittore è contenuto in una variabile globale, di record di tipo ContoCorrente.Come può cambiare il sottoprogramma nell’ipotesi che nel file il numero di CC coincida con la posizione occupata dal record (record relativo al CC # 0 in posizione 0, ecc.)?

Parte facoltativa Si descriva sinteticamente, senza necessariamente codificare l’intero sottoprogramma, come si potrebbe modificare il sottoprogramma se i parametri di ingresso fossero numero di conto e nome dell’intestatario, ma uno dei due potesse mancare. Si considerino sia il caso in cui ogni persona possa essere intestatario al più di un solo CC sia il caso opposto. Sarebbe un sottoprogramma siffatto il modo migliore per affrontare il problema nella realtà quando l’utente si presenta allo sportello fornendo solo uno dei dati suddetti? In caso negativo che alternativa proporreste?


typedef struct{ int CC; char intestatario[50]; double importo;} ContoCorrente;

bool aggiorna(int n_CC, double variazione){ ContoCorrente curr; while(fread(&curr, sizeof(ContoCorrente), 1, file) == 1) { if (curr.CC == n_CC){ curr.importo += variazione; fseek(file, -sizeof(ContoCorrente), SEEK_CUR); if(fwrite(&curr, sizeof(ContoCorrente), 1, file) == 1) { return true;



} else { return false; } } } return false;}

Se il numero di conto corrente coincide con la posizione nel file, il programma va modificato come segue:

bool aggiorna(int n_CC, double variazione){ ContoCorrente curr; if(fseek(file, sizeof(ContoCorrente)*n_CC, SEEK_SET) != 0) { return false; }

if (fread(&curr, sizeof(ContoCorrente), 1, file) != 1) return false; curr.importo += variazione; fseek(file, -sizeof(ContoCorrente), SEEK_CUR); if(fwrite(&curr, sizeof(ContoCorrente), 1, file) == 1) { return true; } else { return false; }}

Parte facoltativa

L’intestazione del sottoprogramma andrebbe modificata come segue:

bool aggiorna(int *n_CC, char intestatario[], double variazione)

Il numero di conto corrente viene passato come puntatore adesso, per dare la possibilità di mettere NULL nel caso in cui non si voglia specificare alcun numero di conto corrente.Nel caso in cui sia il numero di conto che il nome del correntista vengono passati al sottoprogramma, nel ciclo while che va a trovare i dati del conto corrente da modificare occorre verificare se entrambi coincidono con i dati del conto appena letto. In caso positivo, si effettua la modifica, altrimenti, se non è possibile che una persona abbia intestati più conti correnti, viene segnalato un errore. Se invece una persona può avere intestati più conti correnti, si continua nella ricerca.Se invece uno solo tra numero di conto e nome dell’interstatario è specificato, la verifica viene fatta con quello che c’è e basta (e non è possibile fare la contro-verifica che i dati siano consistenti tra di loro). Se però è possibile che un correntista abbia più conti correnti e viene passato solo il nome dell’intestatario, occorre verificare se esistono più CC con lo stesso intestatario e, in tal caso, sollevare un errore; altrimenti si può procedere con l’aggiornamento.

Un sottoprogramma siffatto non sarebbe la soluzione migliore. La soluzione migliore sarebbe di avere tre sottoprogrammi separati, uno che prende in ingresso solo il numero di conto corrente, uno che accetta solo il nome dell’intestatario, ed uno che li accetta entrambi. Il main(), o un



sottoprogramma opportuno eventualmente interattivo, dovrebbe decidere quale dei sottoprogrammi è appropriato.

Esercizio 9.11Parte a.Definire dei tipi di dato per contenere informazioni relative ad un albero genealogico.Ogni persona è caratterizzata dai suoi dati anagrafici e dai suoi parenti più stretti.I dati anagrafici di una persona sono il suo codice fiscale (che è una stringa alfanumerica di esattamente 16 cifre), nome e cognome, il luogo e la data di nascita, il suo sesso e lo stato matrimoniale (single o sposato).Inoltre, ad ogni persona sono associati le seguenti informazioni: il codice fiscale dello sposo/sposa (naturalmente se la persona è sposata); i codici fiscali dei genitori; il codici fiscali dei figli (si assuma pure che una coppia non possa avere più di 10 figli). Se qualcuna di queste informazioni non è disponibile, il cofice fiscale corrispondente contiene solo ‘0’ (per esempio se la persona non è sposata, il codice fiscale associato allo sposo/a è 0000000000000000).

Parte b. Codificare un sottoprogramma che riceve in ingresso un codice fiscale e le informazioni di una persona (dati anagrafici e parenti più stretti), e ritorna true se la persona passata ha il codice fiscale corrispondente al primo parametro.

Parte c.Codificare un sottoprogramma che riceve in ingresso il descrittore di un file binario (supposto già aperto in sola lettura) contenente le informazioni di un insieme di persone, il quale stampa a video i nomi delle coppie di persone sposate, indicando prima il marito, e poi la moglie (deve cioè stampare, su ogni riga, i nomi di una coppia marito-moglie, indicando prima il marito).NB: Ogni coppia va stampata una volta sola. L’ordine con cui vengono stampate le coppie può essere qualunque. Il file in ingresso può anch’esso avere le persone in ordine qualunque.Il sottoprogramma deve essere side-effect-free, cioè quando termina esso deve lasciare il file in ingresso ESATTAMENTE nello stesso stato in cui questo era all’inizio del sottoprogramma.Eventuali sottoprogrammi di appoggio (che non facciano parte della standard library del C) devono essere codificati nella loro interezza.


Parte a.

typedef TipoCF char[16];

typedef TipoSesso enum{M, F};

typedef struct{ TipoCF cf; char nome[30]; char cognome[30]; char luogoNascita[30]; TipoData dataNascita; TipoSesso s; bool sposato;} TipoDatiAnagrafici

typedef struct



{ TipoDatiPersona anagrafica; TipoCF sposo; TipoCF padre; TipoCF madre; TipoCF figli[10]; int nfigli;} TipoDatiPersona

Con il seguente classico tipo:

typedef struct{ short giorno; short mese; int anno;} TipoData;

Parte b.

bool confrontaCF(TipoCF cf, TipoDatiPersona pers){ int i; for(i = 0; i < 16; i++){ if(cf[i] != pers.anagrafica.cf[i]) return false; } return true;}



Parte c.

#include <stdio.h>void stampaSposi(FILE *f){ bool trovaPersonaInFile(TipoCF cf, FILE *f, TipoDatiPersona *dpOut); long oldPos = ftell(f); TipoCF cfSposo; TipoDatiPersona dp, sposo; TipoDatiPersona *marito, *moglie;

rewind(f); while(!feof(f)) { fread(&dp, sizeof(TipoDati(Persona), 1, f); if(dp.anagrafica.sposato) { if(trovaPersonaInFile(marito.anagrafica.cf, f, &sposo,)) { if(dp.anagrafica.sesso == M) { marito = &dp; moglie = &sposo; } else { marito = &sposo; moglie = &dp; } printf("%s %s, %s %s\n", marito->anagrafica.nome, marito->anagrafica.cognome, moglie->anagrafica.nome, moglie->anagrafica.cognome); } } } fseek(f, posCorr, SEEK_SET);}

/* Funzione che prende in ingresso il codice fiscale di unapersona ed un file in cui cercarla, e ritorna true se lapersona esiste nella porzione di file seguente al punto

in cui si trova il puntatore nel file al momento della chiamata,altrimenti ritorna false (nel caso cioè in cui o la persona non

esiste, oppure, se esiste, si trova nel file in un punto precedente).Se la persona esiste, i suoi dati sono caricati nella variabile

dp passata per indirizzo.La funzione lascia il puntatore nel file nel punto in cui lo

aveva trovato all’inizio dell’esecuzione. */bool trovaPersonaInFile(TipoCF cf, FILE *f, TipoDatiPersona *dpOut){ long posCorr = ftell(f); TipoDatiPersona dp; while(!feof(f)) { fread(&dp, sizeof(TipoDati(Persona), 1, f); if(confrontaCF(cf, dp) == true) { *dpOut = dp; fseek(f, posCorr, SEEK_SET); return true; } } fseek(f, posCorr, SEEK_SET); return false;}



Esercizio 9.12Si fornisca una qualsiasi definizione del tipo Fattura, che comprenda tra l’altro, le seguenti voci:

c) Numero della fattura

d) Destinatario, a sua volta descritto da

1. Nome

2. Cognome

3. Codice fiscale

e) Importo al netto dell’IVA

f) IVA

g) Importo totale

h) Data di emissioneSi definisca poi un sottoprogramma che esegua, mediante opportuna interazione con l’operatore, il “data entry” di una fattura (ossia acquisisca la fattura dall’operatore attraverso lo standard input), inserendola poi in un file ordinato per numero di fattura e mantenendone l’ordinamento (non sono ammesse fatture con lo stesso numero nel file). Il sottoprogramma deve aprire il file e richiuderlo ad operazione terminata.È raccomandato l’uso sistematico e appropriato dei sottoprogrammi della libreria standard del C.

Versione semplificataL’inserimento avviene in fondo al file invece che mantenendo il file ordinato per numero di fattura; sono ammesse fatture con lo stesso numero nel file.


#include string.h #include stdio.h

typedef struct { int NumFattura;

struct { char Nome[LunghezzaNome]; char Cognome[LunghezzaCognome]; char CodiceFiscale[16] } Destinatario;double Importodouble IVAdouble ImportoLordo

struct { int Giorno, Mese, Anno} DataEmissione;} Fattura

typdef enum {Fallimento, Successo} Esito;

Esito AcquisisciFattura ( ){file AF, FileTemp; Fattura FattCorr, FattLetta;int DimFattura = sizeof(Fattura), Aliquota;if (AF = fopen (“ArchivioFatture”, “ab+”) ==NULL) return Fallimentoelse{if (FileTemp = fopen (“ArchivioTemporaneo”, “ab+” == NULL))

{fclose (AF); return Fallimento}else{ /*input dei dati*/printf “Inserire in numero della fattura”);scanf (“%d”, & FattLetta.NumFattura);



printf “Inserire il nome del destinatario”); gets(FattLetta.Destinatario.Nome, LunghezzaNome)printf “Inserire il cognome del destinatario”); gets(FattLetta.Destinatario.Cognome, LunghezzaCognome)printf “Inserire il codice fiscale del destinatario”); gets(FattLetta. CodiceFiscale, 16)printf “Inserire l’inporto al netto dell’IVA”);scanf (“%f”, & FattLetta.Importo);printf “Inserire l’aliquota IVA: 10 o 20 %”);scanf (“%d”, & Aliquota); if (Aliquota == 10) FattLetta.IVA = Importo*0.1 else FattLetta.IVA = Importo*0.2;FattLetta.ImportoLordo = FattLetta.Importo + FattLetta.IVA;printf “Inserire la data di emissione: nell’ordine, giorno,

mese e anno, come interi”);scanf (“%d, %d, %d”, & FattLetta.DataEmissione.Giorno,

& FattLetta.DataEmissione.Mese, & FattLetta.DataEmissione.Anno);

/*Fine input dati*/

fread(&FattCorr, DimFattura, 1, AF);while (feof(AF) == 0 && FattLetta.NumFattura > FattCorr.NumFattura) do

fread(&FattCorr, DimFattura, 1, AF);{if (feof(AF) != 0 && (! (FattLetta.NumFattura ==

FattCorr.NumFattura))){fwrite (&FattLetta, DimFattura, 1, AF); fclose (AF); fclose (FileTemp); return Successo};

if (FattLetta.NumFattura == FattCorr.NumFattura){printf (“Esiste già una fattura con lo stesso

numero nell’archivio”); fclose (AF); fclose( FileTemp); return Fallimento}

else /* La fattura va inserita nella posizione corrente del file*/{while (feof(AF) == 0)

{fwrite (&FattCorr, DimFattura, 1, FileTemp); fread(&FattCorr, DimFattura, 1, AF)};fwrite (&FattLetta, DimFattura, 1, AF);{while (feof(FileTemp) == 0)

{ fread(&FattCorr, DimFattura, 1, FileTemp); fwrite (&FattCorr, DimFattura, 1,AF);};

fclose (AF); fclose (FileTemp); return Successo;}

Esercizio 9.13Parte aSi definisca(no) i(l) tipi(o) di dato che serve(ono) per contenere le informazioni relative alla carriera dei calciatori militanti in serie A. Per ogni calciatore devono essere definiti:Nome, Cognome, Data di nascita, Elenco dei dati delle stagioni giocate in Serie A (per ogni stagione giocata in serie A deve essere definito: anno, squadra in cui si è giocato, numero di partite giocate, numero di gol segnati), Media dei gol segnati per anno.Si assuma pure che un giocatore, in una stagione, gioca per al massimo una squadra.

Parte b



Si scriva un sottoprogramma che prende in ingresso un file binario (supposto già aperto sia in letture che in scrittura) contenente i dati di tutti i calciatori di serie A, privi della media dei gol segnati per anno e lo aggiorna inserendo nell’apposito campo la media suddetta.


Parte a

typedef struct{ short giorno; short mese; unsigned int anno;} TipoData;

typedef struct { char nome[30]; char cognome[30]; TipoData data_nascita; TipoStagione stagioni[30]; int n_stagioni; float media_gol;} TipoGiocatore;

typedef struct { int anno; char squadra[20]; int n_partite; int n_gol;} TipoStagione;

Parte b

void clacolaMedie(FILE *f){ rewind(f); TipoGiocatore g; while(fread(&g, sizeof(TipoGiocatore), 1, f) == 1) { g.media_gol = clacolaMediaGol(g.stagioni, n_stagioni); fseek(biblio, -(sizeof(TipoGiocatore)), SEEK_CUR); fwrite(&g, sizeof(TipoGiocaotre), 1, f); }}

Laddove la funzione calcolaMediaGol è definita come segue:

float clacolaMediaGol(TipoStagione s[], int num_stag){ int i; float somma = 0; for(i = 0; i < num_stag; i++) somma += s[i].n_gol; if(num_stag > 0) return somma/n_stag else return 0;}



Capitolo 10Strutture dati dinamiche

Le liste.

Esercizio 10.1Parte a.Si considerino la tradizionale dichiarazione:

struct EL{

int Info;struct EL *Prox;

};typedef struct EL ElemLista;typedef ElemLista *ListaDiInteri;

E la seguente funzione:

int sconosciuta (ListaDiInteri Lista){

int x = 0;ListaDiInteri cursore;

cursore = Lista;while (cursore != NULL) {

if (cursore->Info > x)x = cursore->Info;

cursore = cursore->Prox;}return x;

}

Si dica qual è il risultato della funzione sconosciuta quando vengono eseguite le seguenti chiamate:

sconosciuta (L1)sconosciuta (L2)

L1 ed L2 essendo, rispettivamente le liste rappresentate nella figura seguente.



In generale, qual è il risultato prodotto dalla funzione per una generica lista di interi?

Parte b.Si ricodifichi la funzione sconosciuta in forma ricorsiva.


Parte a.La funzione produce come risultato 18, quando applicata alla lista L1 e 0 quando applicata a L2. In generale essa il valore massimo contenuto nella lista se essa contiene almeno un numero positivo; 0 in caso contrario (lista vuota o contenente solo numeri non positivi).

Parte b.Si definisca in primo luogo la funzione ausiliaria max():

int max(int p1, p2){

if (p1 > p2)return p1;

elsereturn p2;

}

Successivamente la funzione sconosciuta può essere ricodifcata come segue, in forma ricorsiva:

int sconosciuta (ListaDiInteri Lista)/*la funzione produce il valore massimo contenuto nel parametro Lista

se essa contiene almeno un numero positivo; 0 in caso contrario */{

if (Lista == NULL)return 0;

elsereturn (max(Lista->Info, sconosciuta(Lista->Prox));

}



Esercizio 10.2Si vuole realizzare una serie di funzioni per la manipolazione di un archivio di numeri di carte di credito. Ogni carta di credito è definita dai seguenti dati: nome del titolare della carta (massimo 80 caratteri), numero della carta di credito (un codice di esattamente 16 cifre), massimale di spesa mensile per la carta (in euro).Il programma deve essere sviluppato nei seguenti punti:

Punto a.Definire il tipo TipoCartaDiCredito, che contiene i dati di una singola carta. Definire quindi i tipi TipoElemListaCarte e TipoListaCarte (con l’ovvio significato degli identificatori), necessari per definire una lista di carte di credito realizzata mediante puntatori.Dichiarare i prototipi di tutte e sole le seguenti funzioni (senza darne ancora l’implementazione!):carica_lista_da_file(): riceve in ingresso il nome del file binario in cui è memorizzato l’archivio e ritorna una lista contente i dati dell’archivio; si assuma che il file binario contenga una sequenza di dati TipoCartaDiCredito; la lista ritornata dalla funzione non è ordinata secondo nessun criterio particolare; se non è possibile recuperare i dati da file, la funzione ritorna una lista vuota; scarica_lista_su_file(): riceve in ingresso una lista di carte di credito ed un nome di file, e

scrive la lista nel dato file; se il file già esiste, viene cancellato, altrimenti viene creato ex-novo; la funzione ritorna 1 se la scrittura avviene con successo, 0 altrimenti;

stampa_ListaCarte(): riceve in ingresso una lista di carte di credito, e la stampa a video; estrai_carte_da_lista(): riceve in ingresso una lista di carte di credito, e ne ritorna una

nuova, che contiene solo le carte di credito la cui ultima cifra è ‘7’.

Punto b.Implementare la funzione carica_lista_da_file() dichiarata al punto a). Eventuali librerie standard del C usate per implementare la funzione vanno dichiarate prima del corpo della funzione stessa, mediante l’apposita clausola include. Eventuali ulteriori sottoprogrammi ausiliari dovranno essere definiti completamente.

Punto c.Implementare la funzione estrai_carte_da_lista() dichiarata al Punto a. Eventuali librerie standard del C usate per implementare la funzione vanno dichiarate prima del corpo della funzione stessa, mediante l’apposita clausola #include. Eventuali ulteriori sottoprogrammi ausiliari dovranno essere definiti completamente.Si fornisca una duplice implementazione della funzione: una versione iterativa e una ricorsiva.




Punto a.

#define MAX_L_NOME 80

typedef struct{

char nome[MAX_L_NOME+1]; char numero[16]; float massimale;} TipoCartaDiCredito;

struct EL{

TipoCartaDiCredito info; struct EL *next;};

typedef struct EL TipoElemListaCarte;typedef TipoElemListaCarte *TipoListaCarte;

TipoListaCarte carica_lista_da_file (char *nome_file);int scarica_lista_su_file (char *nome_file, TipoListaCarte lista);void stampa_ListaCarte (TipoListaCarte lista);TipoListaCarte estrai_carte_da_lista (TipoListaCarte lista);

Punto b.

#include <stdlib.h>

TipoListaCarte carica_lista_da_file (char *nome_file){

FILE *f; TipoCartaDiCredito carta; TipoElemListaCarte *ptr_el; TipoListaCarte l = NULL;

f = fopen(nome_file, "rb+"); if(f == NULL)

return NULL;while (fread(&carta, sizeof(TipoCartaDiCredito), 1, f) == 1){

ptr_el = malloc(sizeof(TipoElemListaCarte)); ptr_el->info = carta; ptr_el->next = l; l = ptr_el; } return l;}

Punto c (versione iterativa).

#include <stdlib.h>

TipoListaCarte estrai_carte_da_lista (TipoListaCarte lista){

TipoListaCarte new_l = NULL;TipoElemListaCarte *curr = lista, *ptr_new_el;while (curr != NULL){

if (curr->info.numero[16] == ‘7’){

ptr_new_el = malloc(sizeof(TipoElemListaCarte)); ptr_new_el->info = curr->info; ptr_new_el->next = new_l; new_l = ptr_new_el;



} curr = curr->next; } return new_l;}

Punto c (versione ricorsiva).

#include <stdlib.h>

TipoListaCarte estrai_carte_da_lista (TipoListaCarte lista){

TipoElemListaCarte *ptr_new_el = NULL; if (lista == NULL)

return NULL;if (lista->info.numero[16] == ‘7’){

ptr_new_el = malloc(sizeof(TipoElemListaCarte)); ptr_new_el->info = lista->info; ptr_new_el->next = estrai_carte_da_lista(lista->next); return ptr_new_el; }

elsereturn estrai_carte_da_lista(lista->next);

}

Esercizio 10.3Si vuole realizzare un programma GestisciNomi che realizza le seguenti funzionalità: legge dal file “ElencoNomi” un elenco di nomi (ogni nome si trova su una riga separata); man mano che i nomi vengono letti, essi vengono inseriti in una lista, la quale viene

mantenuta ordinata secondo l’ordine alfabetico; quando non ci sono più nomi da leggere dal file, la lista viene stampata a video; viene creata una nuova lista, che contiene gli stessi elementi della precedente, ma in ordine

inverso rispetto all’originale (NB: la lista originale deve essere lasciata inalterata); la lista inversa viene stampata.Si precisa che il file da cui vengono letti i nomi è in formato carattere (non binario!), con ogni nome su una riga diversa; si presume che non ci siano righe vuote. Ogni riga è lunga al massimo 80 caratteri.Il programma deve essere sviluppato nei seguenti punti:

Punto a.Definire i tipi TipoElemListaNomi e TipoListaNomi (con l’ovvio significato degli identificatori), quindi dichiarare i prototipi di tutte e sole le seguenti funzioni (senza darne ancora l’implementazione!): init_ListaNomi(): inizializza una lista di nomi alla lista vuota; inserisci_nome(): riceve in ingresso un nome ed una lista di nomi, ed inserisce il nome nella

lista, in modo che la lista rimanga ordinata in ordine alfabetico; se l’inserimento avviene con successo ritorna true, altrimenti false;

stampa_ListaNomi(): riceve in ingresso una lista di nomi, e la stampa a video nome per nome, riga per riga;

inverti_ListaNomi(): riceve in ingresso una lista di nomi, e ne ritorna una nuova, in cui l’ordine degli elementi nella lista è invertito.

Punto b.



Scrivere un main che, utilizzando le funzioni dichiarati al punto precedente (e la libreria standard del C; le librerie che vengono usate devono essere indicate con l’apposita clausola #include prima del main), realizza il programma GestisciNomi delineato in precedenza.

Punto c.Implementare la funzione (e solo quella!) inverti_ListaNomi() dichiarata al Punto a. Eventuali librerie standard del C usate per implementare la funzione vanno dichiarate prima del corpo della funzione stessa, mediante l’apposita clausola #include. Eventuali ulteriori sottoprogrammi ausiliari dovranno essere definiti completamente.La funzione inverti_ListaNomi() deve essere implementata sia in versione iterativa che in versione ricorsiva. Soluzione dell’Esercizio 10.3

Punto a.

#define MAX_L_NOME 80

struct EL{

char info[MAX_L_NOME + 1]; struct EL *next;};

typedef struct EL TipoElemListaNomi;typedef TipoElemListaNomi *TipoListaNomi;void init_ListaNomi (TipoListaNomi *lista_I);bool inserisci_nome (char nome[], TipoListaNomi *lista_Ins);void stampa_ListaNomi (TipoListaNomi lista_S);TipoListaNomi inverti_ListaNomi(TipoListaNomi lista_Inv);

Punto b.

#include <stdio.h>

int main (){

TipoListaNomi lista_Att, inversa; char nome[MAX_L_NOME + 1]; FILE *f;

f = fopen("ElencoNomi", "r"); if(f == NULL) printf("Errore nell’apertura del file\n"); else

{ init_ListaNomi(&lista_Att); while (! feof(f))

{ fgets(nome, MAX_L_NOME + 1, f); inserisci_nome(nome, &lista_Att); } stampa_ListaNomi(lista_Att); inversa = inverti_ListaNomi(lista_Att) stampa_ListaNomi(inversa); }}

Punto c (versione iterativa).

#include <stdlib.h>#include <string.h>



TipoListaNomi inverti_ListaNomi (TipoListaNomi lista_Inv){

TipoListaNomi inversa; TipoElemListaNomi *cursor, *temp;

init_ListaNomi(&inversa); cursor = lista_Inv; while(cursor != NULL)

{ temp = malloc(sizeof(TipoElemListaNomi)); strcpy(temp->info, cursor->info); temp->next = inversa; inversa = temp; cursor = cursor->next; } return inversa;}

Punto c (versione ricorsiva).

#include <stdlib.h>#include <string.h>

void inserisci_in_coda(TipoListaNomi *lista, char nome[]){

TipoElemListaNomi *temp;

if (lista == NULL){

temp = malloc(sizeof(TipoElemListaNomi)); temp->next = NULL; strcpy(temp->info, (*lista)->info); *lista = temp; }

elseinserisci_in_coda(&((*lista)->next), nome);

}

TipoListaNomi inverti_ListaNomi (TipoListaNomi lista_Inv){

TipoElemListaNomi *inversa;

if(lista == NULL)return NULL;

else{

inversa = inverti_ListaNomi(lista_Inv->next); inserisci_in_coda(&inversa, lista_Inv->info); return inversa; }}

Esercizio 10.4Si considerino le seguenti dichiarazioni:

/* xxx denota una qualsiasi dichiarazione del tipo TipoElemento che qui non interessa Sull’insieme dei valori di TipoElemento è definita una relazione d’ordine totale

implementata dalla funzione precede() dichiarata in seguito*/typedef xxx TipoElemento; typedef enum {false, true} boolean;

/* precede() ritorna true o false a seconda che elem1 preceda o no elem2nella relazione d’ordine definita su TipoElemento*/

bool precede (TipoElemento elem1, TipoElemento elem2);



Parte a.Si definiscano i tipi TipoElementoLista e TipoLista per costruire liste di elementi di tipo TipoElemento basate su puntatori.

Parte b. Si scriva una funzione merge(), codificandola sia in modo ricorsivo che iterativo, che riceva come parametri due liste ordinate in ordine crescente rispetto alla relazione implementata dalla funzione precede (l’i-esimo elemento precede l’i+1-esimo) contenenti elementi del tipo TipoElemento e produce come risultato una nuova lista, pure ordinata, contenente tutti e soli gli elementi contenuti nelle due liste di ingresso. La funzione non deve alterare le liste di ingresso; perciò il loro contenuto dovrà essere copiato in nuovi elementi che comporranno la nuova lista.Per semplicità si può assumere che sia possibile assegnare direttamente variabili di tipo TipoElemento (cioè che si possa scrivere a=b, se a e b sono due variabili di tipo TipoElemento).Eventuali ulteriori sottoprogrammi ausiliari dovranno essere definiti completamente.La figura sottostante fornisce un esempio di come deve operare la funzione nel caso TipoElemento sia int.

Suggerimento per realizzare la versione non ricorsiva della funzioneSi definisca una funzione ausiliaria copia() che riceva come parametro una lista e ne copi il contenuto in un’altra lista.La funzione merge() si potrebbe comportare nel modo seguente:

- Se entrambe le liste passate alla funzione sono vuote, si ritorna ovviamente la lista vuota.



- Se una sola delle due liste è vuota si copia l’altra nella lista risultato e si ritorna quest’ultima.

- Altrimenti (entrambe le liste non sono vuote):o Si inizializza la lista risultato con il minore tra i primi elementi delle due liste.o Si inizializzano opportuni puntatori correnti sia delle liste di ingresso che della

lista risultato (il puntatore corrente alla lista risultato punta sempre all’ultimo elemento della lista).

o Indi, finché entrambe le liste di ingresso non sono state percorse completamente: Si aggiunge in fondo alla lista risultato (tramite il suo puntatore corrente)

l’elemento minore tra quelli puntati dai puntatori correnti delle liste di ingresso, avanzando di conseguenza i vari puntatori.

o Quando si è giunti in fondo a una delle due liste si copia la parte rimanente dell’altra lista in fondo alla lista risultato.

NB. Se si segue il suggerimento, non è indispensabile codificare la procedura ausiliaria copia(): all’occorrenza è sufficiente dichiararla. Funzioni ausiliare diverse da copia(), invece, vanno completamente definite.


Parte a.

struct EL{

TipoElemento info;struct EL *next;

};typedef struct EL TipoElementoLista;typedef TipoElementoLista *TipoLista;

Parte b (versione non ricorsiva).

TipoLista merge (TipoLista lista1, TipoLista lista2){

TipoLista curr1, curr2, curr, temp, lista_unione;

/*prototipo procedura ausiliaria che copia in lista2 il contenuto di lista1*/void copia(TipoLista lista1, TipoLista *lista2);

lista_unione = NULL;curr1 = lista1;curr2 = lista2;if (curr1 == NULL && curr2 == NULL)

return lista_unione;else if (curr1 == NULL)

copia(lista2, &lista_unione);else if (curr2 == NULL)

copia(lista1, &lista_unione);else{

lista_unione = malloc(sizeof(TipoElementoLista));lista_unione->next = NULL;curr = lista_unione;if (precede(curr1->info, curr2->info)){

lista_unione->info = curr1->info;curr1 = curr1->next;

}else{

lista_unione ->info = curr2->info;



curr2 = curr2->next};}while (curr1 != NULL && curr2 != NULL){

temp = malloc(sizeof(TipoElementoLista));temp->next = NULL;curr->next = temp;curr = temp;if (precede(curr1->info, curr2->info)){

temp->info = curr1->info;curr1 = curr1->next;

}else{

temp->info = curr2->info;curr2 = curr2->next;

}}if (curr1 == NULL)

copia(curr2, curr -> next);else

copia(curr1, curr -> next);return lista_unione;

}}

void copia(TipoLista lista1, TipoLista *lista2){

TipoLista temp, curr1, curr2;

*lista2 = NULL;curr1 = lista1;if (curr1 != NULL){

temp = malloc(sizeof(TipoElementoLista));temp->next = NULL;temp->info = curr1->info;*lista2 = temp; curr2 = temp; curr1 = curr1->next;

} while (curr1 != NULL){

temp = malloc(sizeof(TipoElementoLista));temp->next = NULL;temp->info = curr1->info;curr2->next = temp; curr2 = temp; curr1 = curr1->next;

}}

Punto b (versione ricorsiva).

TipoLista merge (TipoLista lista1, TipoLista lista2){

TipoLista lista_unione;

if (lista1 == NULL && lista2 == NULL)return NULL;

if (lista1 == NULL){

lista_unione = malloc(sizeof(TipoElementoLista));lista_unione -> info = lista2->info;lista_unione->next = merge(lista1, lista2->next);

}else if (lista2 == NULL){

lista_unione = malloc(sizeof(TipoElementoLista));lista_unione->info = lista1->info;



lista_unione->next = merge(lista1->next, lista2);}else{

lista_unione = malloc(sizeof(TipoElementoLista));if (precede(lista1->info, lista2->info)){

lista_unione->info = lista1->info;lista_unione->next = merge(lista1->next, lista2);

}else{

lista_unione -> info = lista2->info;lista_unione->next = merge(lista1, lista2->next);

}}return lista_unione;

}

Esercizio 10.5Punto a.Si consideri il seguente programma:

#include <stdio.h>#include <stdlib.h>

int main (){

int **P; int *Q;

Q = malloc(sizeof(int)); P = &Q; **P = 5; *Q = 4; printf("il valore finale di **P è %d \n", **P);}

Si dica, spiegandone brevemente le ragioni, quale sarà l’output del programma.

Punto b.Si risolva lo stesso esercizio per la seguente variazione del programma precedente:

#include <stdio.h>#include <stdlib.h>

typedef int *Pint;

int main (){

int **P; int *Q; int x;

x = 27;Q = malloc(sizeof(int));P = malloc(sizeof(Pint));*P = Q;**P = 4;Q = &x;P = &Q;*Q = 5;printf("il valore finale di **P è %d e quello di x è %d \n", **P, x);

}

Soluzione dell’Esercizo 10.5



Punto a.Dopo la malloc() e l’assegnazione P = &Q in memoria si crea una situazione come indicato in figura:

**P = 5 produce la situazione successiva seguente:

*Q = 4 però riscrive il valore 4 nella stessa cella dove era stato scritto 5. Perciò il risultato finale è l’output seguente:

il valore finale di **P è 4

Punto b.Dopo l’esecuzione delle istruzioni:

x = 27;Q = malloc(sizeof(int));P = malloc(sizeof(Pint));*P = Q;

si è creata la situazione seguente:

Assegnando a Q l’indirizzo di x e a P quello di Q, si ottiene l’effetto che l’assegnamento *Q = 5 sostituisce 5 a 27 in x. Ma x è anche puntata da **P. Quindi il risultato finale è l’output seguente:

il valore finale di **P è 5 e quello di x è 5


QP

QP

5

QP

x

27

100


Esercizio 10.6Si scriva un sottoprogramma che riceva come parametri

Un array rettangolare di interi Un intero indicante il numero di righe dell’array Un intero indicante il numero di colonne dell’array

e produca come risultato una lista –realizzata mediante puntatori– contenente, nell’ordine: Gli elementi della prima riga nello stesso ordine in cui compaiono nell’array; Gli elementi della seconda riga in ordine inverso rispetto a quello in cui compaiono

nell’array … e così via alternando le righe dispari con le righe pari.

Ad esempio l’array di figura

5 84

34 26

2 11

Dovrebbe essere trasformato nella lista5, 84, 26, 34, 2, 11(ovviamente i valori interi dovrebbero essere il contenuto del campo informativo di celle collegate tra loro mediante puntatori).NB1. È possibile fare uso di opportuni sottoprogrammi per la gestione di liste di interi senza necessariamente definirli tutti, purché si riportino tutte le dichiarazioni necessarie alla compilazione del sottoprogramma.NB2. Tra le diverse soluzioni possibili sono preferibili quelle più efficienti.

Soluzione dell’Esercizio 10.6 (i puntini indicano parti omesse in quanto inessenziali)

typedef int TipoElemento;

struct EL{

TipoElemento Info;struct EL *Prox;

};

typedef struct EL ElemLista;

typedef ElemLista *ListaDiElem;

…

bool pari (int i)bool dispari (int j)

void Inizializza (ListaDiElem *Lista)/* Lista è la variabile locale che punta alla "testa di lista". La funzione assegna alla "testa di lista" il valore NULL corrispondente al valore di lista vuota */void InsercisciInTesta (ListaDiElem *Lista, TipoElemento Elem)/* Modifica la lista passata "per indirizzo" inserendo, come suo primo elemento, il valore Elem */

ListaDiElem MatLista (int matrice[ ][ ], int NumRighe, int NumColonne);{

ListaDiElem ListaTemp; int i, j;



Inizializza (&ListaTemp);for (i = NumRighe - 1, i >= 0, i--)

if dispari(i) for (j = 0, j < NumColonne, j++) InsercisciInTesta (&ListaTemp, matrice [i, j];

else for (j = NumColonne - 1, j >= 0, j--) InsercisciInTesta (&ListaTemp, matrice [i, j];

return ListaTemp;}

NB. Una soluzione che faccia uso della procedura InserisciInCoda() sarebbe nettamente meno efficiente. Perché?

Esercizio 10.7Si scriva un main() che legga dal file “FileInteri” una sequenza di interi e li memorizzi, riga per riga, in un array di 10 righe e 20 colonne, verificando che il file contenga esattamente 200 elementi (in caso contrario stampi un’opportuna segnalazione di errore); indi lo trasformi in una lista definita come nell’Esercizio 10.6, facendo uso del sottoprogramma costruito nel medesimo esercizio; infine produca in output gli interi contenuti nella lista, nell’ordine in cui compaiono in essa, evitando però eventuali ripetizioni.NB1. È possibile fare uso di opportuni sottoprogrammi per la gestione di liste di interi senza necessariamente definirli tutti, purché si riportino tutte le dichiarazioni necessarie alla compilazione del sottoprogramma.NB2. Tra le diverse soluzioni possibili sono preferibili quelle che più facilmente possono essere modificate per essere applicate ad array e file di diverse dimensioni.

Soluzione dell’Esercizio 10.7 (i puntini indicano parti omesse in quanto inessenziali)

#include …#define NumeroRighe 10#define NumeroColonne 20#define LunghezzaFile NumeroRighe* NumeroColonne

typedef int TipoElemento;

…

struct EL{


};



…

void Inizializza (ListaDiElem *Lista)/* Lista è la variabile locale che punta alla "testa di lista". La funzione assegna alla "testa di lista" il valore NULL corrispondente al valore di lista vuota */void InsercisciInTesta (ListaDiElem *Lista, TipoElemento Elem)/* Modifica la lista passata "per indirizzo" inserendo, come suo primo elemento, il valore Elem */

bool Ricerca (ListaDiElem Lista, TipoElemento ElemCercato)ListaDiElem MatLista (int matrice[ ][ ], int NumRighe, int NumColonne);



int Mat [NumeroRighe][NumeroColonne];

int main (){

FILE *f;int i, j, temp;ListaDiElem ListaMain, Cursore;

if ((f = fopen ("FileInteri", "rb")) == NULL){

puts ("Non è stato possibile aprire il file FileInteri ");exit (-1);

}for (i = 0, i < NumeroRighe, i++)

for (j = 0, i < NumeroColonne, j++) if (!fread(&Mat[i,j], sizeof(int), 1, f) == 1) {

if feof(f){

puts ("Il file non contiene un numero corretto" "di elementi");exit(-1)

}}

fread (&temp, sizeof(int), 1, f)); if (!feof(f)) {

puts ("Il file non contiene un numero corretto di elementi"); exit(-1)

}ListaMain = MatLista (Mat, NumeroRighe, NumeroColonne);printf ("%d, \n" ListaMain-> Info); cursore = ListaMain-> Prox;while (! cursore = NULL) {

if (!Ricerca (ListaMain, cursore -> Info) printf ("%d, \n" ListaMain-> Info);

cursore = cursore–>Prox;}

}

Esercizio 10.8Si scriva un sottoprogramma che riceva come parametri due liste di interi ordinate in ordine crescente e produca come risultato una nuova lista, pure ordinata in ordine crescente, costituita dall’intersezione degli elementi contenuti nelle due liste fornite come parametri.NB:

1. Tra le varie possibili soluzioni sono da preferire quelle più efficienti e quelle formulate in maniera ricorsiva.

2. È possibile fare uso di sottoprogrammi già noti (ad esempio disponibili sul testo) senza bisogno di ricodificarli, purché siano chiaramente definiti.


struct EL{ int info; struct EL *next;}

typedef struct EL TipoElLista;typedef TipoElLista *TipoLista;



TipoLista intersezione(TipoLista l1, TipoLista l2){ if (l1 == NULL || l2 == NULL) { return NULL; } if(l1->info == l2->info) { res = intersezione(l1->next, l2->next); InserisciInTesta(&res, l1->info); return res; } else if (l1->info < l2->info) { return intersezione(l1->next, l2); } else { return intersezione(l1, l2->next); }}

/* il sottoprogramma InserisciInTesta è quello definito nel testo */

Esercizio 10.9Una lista bidirezionale è una lista in cui ogni elemento è collegato, mediante puntatori, all’elemento seguente e a quello precedente; alla lista è possibile accedere simmetricamente sia attraverso un puntatore al primo elemento che attraverso un puntatore all’ultimo elemento. La figura sottostante fornisce un’immagine grafica di una lista bidirezionale. Esempio di lista bidirezionale.

Parte 1Si fornisca una dichiarazione completa del “tipo astratto” ListaBidirezionale, ossia la dichiarazione del singolo elemento della lista e dei meccanismi di accesso alla lista tramite la sua testa e la sua coda. Si può assumere che il generico elemento della lista sia un valore intero, oppure lasciare il suo tipo non specificato. Si può comunque assumere –per la soluzione della parte 2- che tra valori del generico elemento sia definita non solo la relazione di uguaglianza ma anche la relazione d’ordine, espresse mediante i normali operatori, ==, <, >, <=, >=.

Parte2 (Per questa parte è preferibile una soluzione ricorsiva)Si definisca un sottoprogramma che riceva come parametri

una lista bidirezionale del tipo dichiarato nella parte 1, i cui valori dei vari elementi siano ordinati in ordine crescente e

un valore del tipo dei vari elementi (per semplicità si può anche assumere che si tratti di interi)

e inserisca il nuovo elemento, solo se non esiste già nella lista, in una posizione tale che la lista rimanga ordinata. È però importante che il sottoprogramma non “visiti” inutilmente un gran numero di elementi. Ad esempio, se la lista contenesse 1000 elementi e l’elemento da aggiungere dovesse essere inserito in posizione 950, si dovrebbe evitare di esaminare tutti i 949 elementi che lo precedono nell’ordine.




Parte1Nelle ipotesi date dall’esercizio, una dichiarazione basilare, ma completa del “tipo astratto” ListaBidirezionale, con i relativi meccanismi di accesso alla lista può essere:

#include <stdio.h>#include <stdlib.h>#incluse <stdbool.h>

typedef struct el{ int data; struct el *right; struct el *left;} ListItem; /* Rappresenta il singolo elemento della lista */

typedef struct{ int number_items; ListItem *head; ListItem *tail;} BidirectionalList; /* Rappresenta la lista */

BidirectionalList *createBList();bool isEmpty(BidirectionalList *b_list);bool isPresent(BidirectionalList *b_list, int data);bool insertItem(BidirectionalList *b_list, int data);bool modifyItem(BidirectionalList *b_list, int oldData, int newData);bool removeItem(BidirectionalList *b_list);void printList(BidirectionalList *b_list);

Il tipo di ritorno bool viene utilizzato per comunicare al chiamante la riuscita dell’operazione. Ad esempio, nel caso di insertItem(), un valore di ritorno false corrisponde a non aver inserito il nuovo elemento poiché la memoria è esaurita oppure l’elemento esiste già nella lista.

Parte 2La procedura di inserimento di un nuovo elemento nella lista può essere resa più efficiente, evitando un gran numero di confronti, se la lista viene percorsa parallelamente dalla testa verso la coda e viceversa. Una procedura iterativa che effettui questo tipo di inserimento può essere:

bool insertItem(BidirectionalList *b_list, int data) { bool inserted = false; ListItem *leftCursor = b_list->head; ListItem *rightCursor = b_list->tail; ListItem *toInsert; ListItem *temp;

/* Alloco memoria per il nuovo elemento */ toInsert = malloc (sizeof(ListItem)); if (toInsert == NULL) return false; /* L’allocazione della memoria non ha avuto successo */ toInsert->data = data; while (!inserted) {

if (isEmpty(b_list)) {

/* Primo elemento in lista */ toInsert->right = NULL; toInsert->left = NULL; b_list->head = toInsert; b_list->tail = toInsert;

/* Termino il loop */



inserted = true;

} else if (b_list->head->data > data) {

/* Caso particolare: inserimento in testa */ leftCursor->left = toInsert; toInsert->left = NULL; toInsert->right = leftCursor; b_list->head = toInsert;

/* Termino il loop */ inserted = true;

} else if (b_list->tail->data < data) { /* Caso particolare: inserimento in coda

(analogo all’inserimento in testa) */…

} else if (leftCursor->data == data || rightCursor->data == data) {

/* L’elemento esiste già nella lista */ free(toInsert); return false;

} else if (leftCursor->data < data && leftCursor->right->data > data) {

/* Imposto i puntatori verso la coda della lista */ temp = leftCursor->right; leftCursor->right = toInsert; toInsert->right = temp;

/* Imposto i puntatori verso la testa della lista */ temp->left = toInsert; toInsert->left = leftCursor;


} else if (rightCursor->data > data && rightCursor->left->data < data) {

/* Imposto i puntatori verso la testa della lista */ temp = rightCursor->left; rightCursor->left = toInsert; toInsert->left = temp;

/* Imposto i puntatori verso la coda della lista */ temp->right = toInsert; toInsert->right = rightCursor;


} else {

/* Facciamo scorrere i cursori */ leftCursor = leftCursor->right; rightCursor = rightCursor->left; } } b_list->number_items++;



return true;}

Una versione alternativa, che effettui l’inserimento in maniera ricorsiva, può essere:

bool insertItem(BidirectionalList *b_list, int data) { ListItem* toInsert;

/* Alloco memoria per il nuovo elemento */ toInsert = malloc(sizeof(ListItem)); if (toInsert == NULL) return false; /* L’allocazione della memoria non ha avuto successo */ toInsert->data = data;

if (isEmpty(b_list)) {

/* Primo elemento in lista */ toInsert->right = NULL; toInsert->left = NULL; b_list->head = toInsert; b_list->tail = toInsert; } else if (b_list->head->data > data) {

/* Caso particolare: inserimento in testa */ b_list->head->left = toInsert; toInsert->left = NULL; toInsert->right = b_list->head; b_list->head = toInsert; } else if (b_list->tail->data < data) {

/* Caso particolare: inserimento in coda (analogo all’inserimento in testa) */

… } else {

/* Prima chiamata ricorsiva */ if (!insertItemRecursive(b_list->head, b_list->tail, toInsert)) { free(toInsert); return false; } } b_list->number_items++; return true;}

bool insertItemRecursive(ListItem* leftCursor,ListItem* rightCursor,ListItem* toInsert) {

ListItem* temp; if (leftCursor->data == toInsert->data || rightCursor->data == toInsert->data) {

/* Caso base 1: l’elemento esiste già nella lista */ return false; } else if (leftCursor->data < toInsert->data && leftCursor->right->data > toInsert->data) {

/* Caso base 2: ho trovato la posizione in cui inserire venendo da sinistra */



/* Imposto i puntatori verso la coda della lista */

temp = leftCursor->right; leftCursor->right = toInsert; toInsert->right = temp;

/* Imposto i puntatori verso la testa della lista */ temp->left = toInsert; toInsert->left = leftCursor;

return true; } else if (rightCursor->data > toInsert->data

&& rightCursor->left->data < toInsert->data) {

/* Caso base 3: ho trovato la posizione in cui inserire venendo da destra */

/* Imposto i puntatori verso la testa della lista */ temp = rightCursor->left; rightCursor->left = toInsert; toInsert->left = temp;

/* Imposto i puntatori verso la coda della lista */ temp->right = toInsert; toInsert->right = rightCursor; return true; } else {

/* Chiamata ricorsiva */ return insertItemRecursive(leftCursor->right, rightCursor->left, toInsert); }}

Esercizio 10.10Una lista circolare è una lista in cui ogni elemento –se la lista non è vuota! – è collegato, mediante puntatori, all’elemento seguente e l’ultimo elemento punta al primo; alla lista è possibile accedere attraverso un puntatore al primo elemento. La figura sottostante fornisce un’immagine grafica di una lista circolare.


IngressoLista

E1

E2

E3

E4

Ex

En

108


Esempio di lista circolare.

Parte.1Si fornisca una dichiarazione completa del “tipo astratto” ListaCircString, in cui il contenuto dei

singoli elementi siano stringhe di caratteri, ossia

la dichiarazione del singolo elemento della lista;

la dichiarazione del meccanismo di accesso alla lista tramite il suo “ingresso”,

la dichiarazione (non la definizione!) di alcuni sottoprogrammi ritenuti utili per la gestione di una lista siffatta (non è necessario fornirne in numero elevato: basta che siano utilizzabili per le operazioni più naturali).

Parte.2 Si definisca un sottoprogramma che riceva come parametri

una lista circolare del tipo dichiarato nell’Esercizio 3.1, i cui valori dei vari elementi siano ordinati in ordine alfabetico crescente e

una stringa

e inserisca la stringa ricevuta in un nuovo elemento, solo se essa non esiste già nella lista, in una posizione tale che la lista rimanga ordinata.È possibile utilizzare all’uopo i sottoprogrammi per la gestione di stringhe disponibili nella libreria standard del C.




Parte.1Una possibile definizione per il tipo di dato astratto ListaCircolare può essere la seguente:

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdbool.h>

#define MAX_LENGTH 80

/* Singolo elemento della lista */typedef struct el { char data[MAX_LENGTH]; struct el *next;} ListItem;

/* Blocco di accesso */typedef struct lc { ListItem* enter; int number_items; } ListCirc;

bool removeItem(ListCirc* list, char data[]);bool isEmpty(ListCirc* list);void printList(ListCirc* list)ListCirc* createList()bool insertItem(ListCirc* list, char data[]);

Parte.2

La procedura che effettua l’inserimento in ordine alfabetico, che utilizza le funzioni di librearia per la manipolazione delle stringhe, può essere implementata come segue:

bool insertItem(ListCirc* list, char data[]){ ListItem* new; ListItem* temp; ListItem* prec; int i;

if (list == NULL) { /* La lista non è ancora stata creata */ return false;

} else if (isEmpty(list)) { /* La lista è creata, ma è vuota */ new = malloc (sizeof(ListItem)); strcpy (new->data, data); new->next = new; list->enter = new;

} else { /* Caso generale */ temp = list->enter; prec = list->enter;

/* Al termine del ciclo, prec punta all’ultimo elemento */ for (i = 0; i < list->number_items-1; i++) { if (strcmp(prec->data,data) == 0)



{ return false; /* L’elemento è già presente */

} prec = prec->next; }

/* Allocazione nuovo elemento */ new = malloc (sizeof(ListItem)); strcpy (new->data, data);

/* Cerco la posizione in cui inserire */ i = list->number_items; while (strcmp(temp->data, data)<0 && i>0) { prec = temp; temp = temp->next; i--; }

/* Inserimento dei link */ new->next = temp; prec->next = new;

/* Update del blocco di ingresso se necessario */ if (i==list->number_items) { list->enter = new; } }

list->number_items++; return true;}

Esercizio 10.11È noto che il sottoprogramma

void InsercisciInTesta (ListaDiElem *Lista, TipoElemento Elem)/* Modifica la lista passata "per indirizzo" inserendo,

come suo primo elemento, il valore Elem */

Deve passare il parametro Lista per indirizzo per ottenere l’effetto che la chiamata InsercisciInTesta (&Lista1, Elem1)produca l’effetto desiderato sul parametro attuale Lista1.Si definisca in sua vece un sottoprogramma InserimentoInTesta (ListaDiElem Lista, TipoElemento Elem)e si dica in che modo effettuare una sua chiamata per ottenerne lo stesso effetto della precedente chiamata InsercisciInTesta (&Lista1, Elem1)


Il sottoprogramma può essere trasformato in una funzione nel modo seguente:

ListaDiElem InserimentoInTesta (ListaDiElem Lista, TipoElemento Elem)/* Modifica la lista passata "per valore" inserendo, come suo primo elemento, il valore

Elem, ritorna come risultato il puntatore al nuovo elemento in testa alla lista */{

ElemLista *Punt;

/* Allocazione dello spazio necessario per la memorizzazione del nuovo elemento e inizializzazione del puntatore */



Punt = malloc (sizeof (ElemLista));Punt–>Info = Elem;Punt–>Prox = *Lista;return Punt;

}

A questo punto l’effetto della chiamata InsercisciInTesta (&Lista1, Elem1)si ottiene mediante l’istruzione Lista1 = InserimentoInTesta (Lista1, Elem1)

Esercizio 10.12Si scrivano le dichiarazioni di tipo necessarie per definire liste di elementi di un generico tipo TipoElemento (che non deve essere dichiarato), concatenati tra loro mediante puntatori.Si scriva poi un sottoprogramma che riceva come parametri due liste del tipo dichiarato in precedenza e cancelli dalla prima tutti gli elementi che compaiono nella seconda (si assuma che le liste possano contenere elementi ripetuti); il sottoprogramma deve poi produrre come risultato una nuova lista contenente tutti gli elementi della seconda lista scritti in ordine inverso.NB1. È permesso fare uso di sottoprogrammi ausiliari già definiti altrove (ad esempio nel libro di testo). In tal caso è sufficiente la dichiarazione di tali sottoprogrammi con un riferimento preciso alla loro definizione. Se però fosse necessario un sia pur lieve cambiamento di sottoprogrammi definiti altrove occorrerebbe spiegare con precisione i cambiamenti apportati, senza necessariamente codificarli in maniera completa.NB2. Si assuma anche che si possa usare l’operatore ‘==‘ per confrontare due elementi di tipo TipoElemento.

Eventuale suggerimento per facilitare la soluzione dell’esercizio

Si modifichi in modo adeguato la funzione Cancella() definita nel testo. Quindi si scorra la lista L2: per ogni elemento di L2 che esiste in L1 (anche in questo caso si può fare uso di funzioni predefinite) si usi la funzione Cancella() modificata per cancellare tutte le occorrenze dell’elemento di L2 corrente. Lo stesso elemento corrente viene poi aggiunto alla nuova lista da costruire (anche in questo caso si può fare uso di funzioni predefinite).


struct EL{ TipoElemento Info; struct EL *Prox;}

typedef struct EL ElemLista;typedef ElemLista *ListaDiElem;

void CancellaTutte(ListaDiElem *Lista, TipoElemento Elem){

/* Analoga alla Cancella del testo,ma con la chiamata ricorsiva a “CancellaTutte”

anche nel ramo if, non solo nell’else.*/}

ListaDiElem Cancella_e_Inverti(ListaDiElem *L1, ListaDiElem L2){ boolean Ricerca (ListaDiElem Lista, TipoElemento ElemCercato);

/* definita nel testo */ void InserisciInTesta(ListaDiElem *Lista, TipoElemento Elem)



/* definita nel testo */

ListaDiElem ris = NULL; ElemLista *cursor, temp;

cursor = L2; while(cursor != NULL) { if (Ricerca(*L1, cursor->Info)) { CancellaTutte(L1, cursor->Info); }

InserisciInTesta(&ris, L2->Info); cursor = cursor->Prox; } return ris;}

Esercizio 10.13Si scriva una funzione che riceva come parametro due liste ordinate non contenenti elementi ripetuti e produca come risultato una nuova lista, pure ordinata, ottenuta dalla fusione (merge) delle due liste anch’essa priva di ripetizioni.Ad esempio applicando la funzione alle due liste L1 e L2 di figura si deve ottenere la lista L3.

È necessario premettere al codice della funzione la dichiarazione delle strutture dati opportune.È ammesso, per semplicità, assumere che le liste contengano numeri interi, ma sarebbe preferibile che struttura dati e funzione fossero definite per liste di qualsiasi tipo di elementi, in modo tale che il codice della funzione non debba cambiare se, ad esempio, il tipo degli elementi fosse una


L1 10 15 20 30

L2 10 25 30

L3 10 15 20 25

30

113


fattura invece che un intero; in tal caso si può assumere l’esistenza di una funzione confronta() che, dati due valori del tipo degli elementi della lista stabilisce se il primo è minore del secondo o viceversa, o sono uguali: fornire la dichiarazione (non la definizione!) di tale funzione e farne uso nella funzione merge().Costituisce titolo preferenziale una versione ricorsiva della funzione richiesta.


struct EL{


}



typedef enum {maggiore, uguale , minore} Esito;

Esito Confronta (TipoElemento El1, TipoElemento El2);

ListaDiElem Merge (ListaDiElem L1, ListaDiElem L2){

ElemLista *Punt;if (ListaVuota(L1) && ListaVuota(L2))

return NULL;else if (ListaVuota(L1)) {

Punt = malloc(sizeof(ElemLista)); Punt->Info = TestLista (L2); Punt->Prox = Merge (L1, L2–>Prox); return Punt;

}else if (ListaVuota(L2)) {

Punt = malloc(sizeof(ElemLista)); Punt->Info = TestLista (L1); Punt->Prox = Merge (L2, L1–>Prox); return Punt;

}else if (Confronta (TestLista (L1), TestLista (L2)) == minore){

Punt = malloc(sizeof(ElemLista)); Punt->Info = TestLista (L1);Punt->Prox = Merge (L2, L1->Prox); return Punt;

}else if (Confronta (TestLista (L1), TestLista (L2)) == uguale){

Punt = malloc(sizeof(ElemLista)); Punt->Info = TestLista (L1);Punt->Prox = Merge (L2–>Prox, L1–>Prox); return Punt;

}else if (Confronta (TestLista (L1), TestLista (L2)) == maggiore){

Punt = malloc(sizeof(ElemLista)); Punt->Info = TestLista (L2);Punt->Prox = Merge (L2–>Prox, L1); return Punt;

}}



Capitolo 11Tipi di dato astratti, classi, e la programmazione a oggetti in Java

Esercizio 11.1Si realizzi una classe Java per rappresentare vettori bidimensionali


public class Vettore { private double vx; private double vy;

public Vettore(double vx, double vy) { this.vx = vx; this.vy = vy; }

public double getVx() { return vx; }

public double getVy() { return vy; }

public void aggiungi(Vettore v) { vx += v.vx; vy += v.vy; }

public void sottrai(Vettore v) { vx -= v.vx; vy -= v.vy; }

public void moltiplica(double d) { vx *= d; vy *= d; }

public double getModulo() { return Math.sqrt(vx*vx+vy*vy); }

}

Esercizio 11.2Si realizzi una classe Java per rappresentare matrici numeriche di dimensione qualsiasi




public class Matrice { public double cella[][];

public Matrice(int numRighe, int numColonne) { cella = new double[numRighe][numColonne]; }

public int getNumRighe() { return cella.length; }

public int getNumColonne() { return cella[0].length; }

public double getCella(int riga, int colonna) { return cella[riga][colonna]; }

public void setCella(int riga, int colonna, double val) { cella[riga][colonna] = val; }

public void moltiplica(double d) { for(int r = 0; r < getNumRighe(); r++) for(int c = 0; c < getNumColonne(); c++) cella[r][c] *= d; }

public void moltiplica(Matrice m) { double[][] ris = new double[this.getNumRighe()][m.getNumColonne()]; for(int r = 0; r<this.getNumRighe(); r++) for(int c = 0; c<m.getNumColonne(); c++) for(int i = 0; i<this.getNumColonne(); i++) ris[r][c] += cella[r][i]*m.cella[i][c]; cella = ris; }

public void stampa() { for(int r = 0; r<getNumRighe(); r++) { System.console().printf("|"); for(int c = 0; c<getNumColonne(); c++) System.console().printf("%8.2f ", cella[r][c]); System.console().printf("|\n"); } }

}



Esercizio 11.3Si realizzi una classe Java per contenere un insieme di numeri interi. Si supponga nota al momento della costruzione dell’insieme la sua capacità massima. Si mantenga l’insieme ordinato onde minimizzare il tempo di ricerca di un elemento nell’insieme.


public class InsiemeInt { private int[] dati; private int numElem; public InsiemeInt(int dimensione) { dati = new int[dimensione]; numElem = 0; } public void aggiungi(int elem) { int inizio=0, fine=numElem-1, idx; idx = cercaIndice(elem, 0, numElem-1); if(dati[idx]==elem) return; // elemento già presente if(elem>dati[idx]) idx++; if(idx==numElem) { dati[numElem] = elem; numElem++; } else { for(int i=numElem; i>=idx; i--) {

dati[i+1] = dati[i]; } dati[idx] = elem; numElem++; } } public void rimuovi(int elem) { int idx; idx = cercaIndice(elem, 0, numElem-1); if(dati[idx]!=elem) return; // elemento non presente for(int i=idx; i<numElem-1; i++) { dati[i] = dati[i+1]; } numElem--; } public boolean contiene(int elem) { int idx; idx = cercaIndice(elem, 0, numElem-1); return dati[idx]==elem; } public int numElementi() { return numElem;



} private int cercaIndice(int elem, int inizio, int fine) { int idx=0; while(inizio<=fine) { idx = (inizio+fine)/2; if(dati[idx]==elem) break; if(dati[idx]>elem) fine=idx-1; else inizio=idx+1; } return idx; }}

Esercizio 11.4Si realizzi in Java una classe Veicolo con marca, modello e colore. Si definiscano poi due sottoclassi: Auto e Bici. L’auto aggiunge gli attributi targa e cilindrata, mentre la bici aggiunge un attributo ad indicare il fatto che sia ammortizzata o meno. Entrambe le sottoclassi ridefiniscano appropriatamente il metodo stampaCaratteristiche che stampa a video le caratteristiche del veicolo.


public class Veicolo { protected String marca; protected String modello; protected String colore; public Veicolo(String marca, String modello, String colore) { this.marca = marca; this.modello = modello; this.colore = colore; } public String getMarca() { return marca; } public String getModello() { return modello; } public String getColore() { return colore; } public void stampaCaratteristiche() { System.out.println("Veicolo:"); System.out.println("\tmarca: "+marca); System.out.println("\tmodello: "+modello); System.out.println("\tcolore: "+colore); }}public class Auto extends Veicolo {



protected String targa; protected int cilindrata;

public Auto(String marca, String modello, String colore, String targa, int cilindrata) {

super(marca, modello, colore);this.targa = targa;this.cilindrata = cilindrata;

}

public String getTarga() {

return targa; }

public int getCilindrata() {

return cilindrata; }

public void stampaCaratteristiche() {

System.out.println("Autovettura:");System.out.println("\tmarca: "+marca);System.out.println("\tmodello: "+modello);System.out.println("\tcolore: "+colore);System.out.println("\ttarga: "+targa);System.out.println("\tcilindrata: "+cilindrata+"cc");

}}

public class Bici extends Veicolo{ protected boolean ammortizzata; public Bici(String marca, String modello, String colore, boolean ammortizzata) { super(marca, modello, colore); this.ammortizzata = ammortizzata; } public boolean isAmmortizzata() { return ammortizzata; } public void stampaCaratteristiche() { if(ammortizzata) System.out.println("Bici ammortizzata:"); else System.out.println("Bici:"); System.out.println("\tmarca: "+marca); System.out.println("\tmodello: "+modello); System.out.println("\tcolore: "+colore); }}

Esercizio 11.5Si realizzi in Java una struttura dati volta a contenere le informazioni relative ad una gara automobilistica. Per ogni pilota (massimo 20, caratterizzati da nome, cognome e nome scuderia) si vuole memorizzare il tempo di percorrenza dei diversi giri (massimo 50).


public class Gara



{ private Pilota piloti[]; private int numPiloti; public Gara() { piloti = new Pilota[20]; numPiloti = 0; } public void aggPilota(String nome, String cognome, String scuderia) { piloti[numPiloti] = new Pilota(nome, cognome, scuderia); numPiloti++; } public void setTempo(String nome, String cognome, int numGiro, double tempo) { int i=0; while(i<numPiloti) { if(piloti[i].getNome().equals(nome) && piloti[i].getCognome().equals(cognome)) break; i++; } if(i==numPiloti) return; // pilota non trovato piloti[i].setGiro(numGiro, tempo); } public double getTempo(String nome, String cognome, int numGiro) { int i=0; while(i<numPiloti) { if(piloti[i].getNome().equals(nome) && piloti[i].getCognome().equals(cognome)) break; i++; } if(i==numPiloti) return -1; // pilota non trovato else return piloti[i].getGiro(numGiro); }}

public class Pilota{ private String nome; private String cognome; private String scuderia; private double giro[]; public Pilota(String nome, String cognome, String scuderia) { this.nome = nome; this.cognome = cognome; this.scuderia = scuderia; giro = new double[50]; } public String getNome() { return nome; } public String getCognome() { return cognome;



} public String getScuderia() { return scuderia; } public void setGiro(int numGiro, double tempo) { giro[numGiro] = tempo; } public double getGiro(int numGiro) { return giro[numGiro]; }}

Esercizio 11.6Si realizzi in Java una struttura dati volta a contenere le informazioni relative al risultato di un compito in classe. Si suppone che il numero di studenti partecipanti sia noto al momento dell’istanziazione della struttura dati. Per ogni studente si vuole memorizzare il nome, il cognome, il numero di matricola e il voto. Si inseriscano opportuni metodi per conoscere il voto di uno studente (nota la sua matricola e/o il suo nome e cognome), per stampare la tabella dei risultati e per inserire il voto di uno studente nota la matricola.


public class RisultatiCompito { private Risultato[] ris; int numStud;

public RisultatiCompito(int numStud) { ris = new Risultato[numStud]; numStud = 0; }

public void aggStud(String nome, String cognome, String matricola,int voto) { ris[numStud] = new Risultato(new Studente(nome,cognome,matricola),voto); numStud++; }

public void aggStud(String nome, String cognome, String matricola) { ris[numStud] = new Risultato(new Studente(nome, cognome, matricola)); numStud++; }

public void setVoto(String matricola, int voto) { for(int i = 0; i < numStud; i++) { if(ris[i].getStud().getMatricola().equals(matricola)) ris[i].setVoto(voto); } }

public int getVoto(String matricola) { for(int i = 0; i < numStud; i++)



{ if(ris[i].getStud().getMatricola().equals(matricola)) return ris[i].getVoto(); } return -1; }

public int getVoto(String nome, String cognome) { for(int i = 0; i < numStud; i++) { if(ris[i].getStud().getNome().equals(nome) && ris[i].getStud().getCognome().equals(cognome)) return ris[i].getVoto(); } return -1; }

public void print() { for(int i=0; i<numStud; i++) { System.console().printf("%6s %20s %20s %2d\n", ris[i].getStud().getMatricola(), ris[i].getStud().getCognome(), ris[i].getStud().getNome(), ris[i].getVoto()); } }

}

class Studente { private String nome; private String cognome; private String matricola;

public Studente(String nome, String cognome, String matricola) { this.nome = nome; this.cognome = cognome; this.matricola = matricola; }

public String getNome() { return nome; }

public String getCognome() { return cognome; }

public String getMatricola() { return matricola; }

}

class Risultato { private Studente stud; private int voto;

public Risultato(Studente stud, int voto) { this.stud = stud; this.voto = voto;



}

public Risultato(Studente stud) { this.stud = stud; this.voto = -1; }

public int getVoto() { return voto; }

public void setVoto(int voto) { this.voto = voto; }

public Studente getStud() { return stud; }

}

Esercizio 11.71. Con riferimento all’esercizio precedente, si aggiunga un metodo alla classe

RisultatiCompito per normalizzare i voti degli studenti, facendo in modo che lo studente che ha preso il voto più alto prenda 30 e adeguando il voto di tutti gli altri studenti.

2. Si modifichi la struttura dati dell’esercizio precedente per memorizzare i dati relativi all’intera carriera universitaria degli studenti. Per ogni studente si vuole memorizzare gli esami sostenuti con il relativo voto.

Esercizio 11.8Si realizzi in Java una struttura dati per organizzare un archivio fotografico. Per ogni fotografia in archivio si vuole memorizzare il nome, la posizione del file all’interno del file system dell’utente, fino a cinque parole chiave e un indice di qualità (un valore do 0 a 10). Si forniscano gli opportuni metodi incluso quello per cercare tutte le fotografie identificate da una particolare parola chiave.



Soluzioni di esercizi del testoEsercizio testo 11.4Si riporta la soluzione per il caso dei numeri naturali su 32 bit, con rappresentazione interna del numero tramite long, lasciando allo studente la soluzione per il caso in cui si voglia utilizzare una diversa rappresentazione interna

public class NumBinario { private long valore;

public NumBinario(long valore) { this.valore = valore; }

public long getValore() { return valore; }

public void setValore(long valore) { this.valore = valore; }

public long getBit(int b) { return (valore & Math.round(Math.pow(2,b))) / Math.round(Math.pow(2,b)); }

public void setBit(int b) { valore = valore^Math.round(Math.pow(2, b)); }

public void somma(NumBinario n) { valore += n.valore; }

public void sottrai(NumBinario n) { valore -= n.valore; }

public void print() { for(int b = 32; b >= 0; b--) { System.console().printf("%1d", getBit(b)); } System.console().printf("\n"); }

}

Esercizio testo 11.8Utilizziamo la classe ListaDiInt definita nel testo come un buffer nel quale inserire gli elementi via via che l’utente li immette.



public class InvertiSequenza { public static void main(String[] args) { int numero; String numeroInCaratteri; ListaDiInt buffer = new ListaDiInt(); System.console().printf("Inserire una serie di numeri. End per finire."); while(true) { numeroInCaratteri = System.console().readLine(); if(numeroInCaratteri.equals("End")) break; numero = Integer.parseInt(numeroInCaratteri); buffer.inserisciInTesta(numero); } while(!buffer.vuota()) { System.console().printf("%d ", buffer.testa()); buffer = buffer.coda(); } }

}



Capitolo 12Estensioni dell’architettura di von Neumann

Memorie cache, architetture di calcolo parallele.

Esercizio 12.1Supponiamo di avere un calcolatore dotato di memoria cache di primo livello (cache L1). Il tempo t1 necessario per cercare un dato nella memoria cache è pari a 1 ns. Nel caso in cui il dato cercato non sia presente nella memoria cache, lo stesso dato deve essere prelevato dalla memoria tradizionale, richiedendo un tempo t2 di 80 ns. Un programma in esecuzione sul calcolatore ha un miss-rate m pari al 10%, ossia, nel 10% dei casi il processore non trova il dato che cerca nella cache di primo livello e deve quindi prelevare il dato dalla memoria di lavoro. Si chiede di calcolare, mediamente, quanto tempo impiega il processore per accedere ai dati in memoria.

Soluzione dell’Esercizio 12.1Per rendere più semplice capire come affrontare questo esercizio, ipotizziamo che il processore debba accedere a 100 dati in memoria.- Ad ogni accesso, per prima cosa il processore cercherà il dato nella memoria cache.

Indipendentemente dal fatto che il dato sia trovato o meno in cache, il tempo necessario per cercare il singolo dato è pari a t1 = 1 ns.

- Dato che il processore deve accedere a 100 dati, il tempo totale perso per cercare questi dati nella cache è pari a 100 × t1 = 100 ns.

- Nel 10% dei casi il processore non trova il dato in cache e lo deve andare a prelevare dalla memoria di lavoro. Il numero totale di accessi alla memoria di lavoro è pari a 100 × m = 10.

- Il tempo necessario per un accesso alla memoria di lavoro è pari a t2 = 80 ns.In totale quindi, il tempo necessario per accedere alla memoria di lavoro è pari a100 × m × t2 = 800 ns.

- In definitiva, sommando il tempo richiesto per accedere alla cache e quello richiesto per accedere alla memoria principale, otteniamo che il processore spende in totale 900 ns per accedere ai dati (100 × t1 + 100 × m × t2 = 900 ns).

- Mediamente, ciascun accesso ai dati richiede quindi un tempo pari a 900/100 ns, ossia t1 + m × t2 = 9 ns

Esercizio 12.2Supponiamo che lo stesso calcolatore dell’esercizio precedente esegua un programma caratterizzato da un miss-rate m pari al 99%, ossia, nel 99% dei casi il processore non trova il dato che cerca nella cache di primo livello e deve quindi prelevare il dato dalla memoria di lavoro. Anche in questo caso, si chiede di calcolare, mediamente, quanto tempo impiega il processore per accedere ai dati in memoria.

Soluzione dell’Esercizio 12.2Sfruttando il procedimento visto con l’esercizio precedente, sappiamo che il tempo medio perso dal processore per accedere ai dati è pari a

t1 + m × t2



dove t1 = 1 ns è il tempo di accesso alla memoria cache mentre t2 = 80 ns è il tempo di accesso alla memoria di lavoro.Nel caso di miss-rate m = 99% abbiamo che il tempo medio di accesso ai dati è pari a

1 ns + 0.99 × 80 ns = 80.4 nsIn altre parole, a causa dell’elevato miss-rate, il tempo medio di accesso ai dati dell’architettura con memoria cache è leggermente superiore rispetto al tempo di accesso che si avrebbe senza memoria cache.

Esercizio 12.3Generalizzando quanto appreso con i due esercizi precedenti, si chiede di calcolare il miss-rate m massimo oltre il quale una generica architettura con cache di primo livello non trae più beneficio nel tempo medio di accesso ai dati.

Soluzione dell’Esercizio 12.3Indichiamo con t1 il tempo necessario per cercare un dato nella memoria cache e con t2 il tempo necessario per prelevare un dato dalla memoria di lavoro, nel caso in cui il dato cercato non sia presente nella memoria cache. Il tempo medio di accesso ad un dato per un elaboratore senza memoria cache è pari a

t2

Il tempo medio di accesso ad un dato per un elaboratore con cache di primo livello è pari at1 + m × t2

Perché la memoria cache sia vantaggiosa deve esseret1 + m × t2 < t2

ossiam < 1 −

Esercizio 12.4Supponiamo di avere un calcolatore dotato di due livelli di memoria cache: una cache di primo livello (cache L1) e una cache di secondo livello (cache L2). Indichiamo con t1 il tempo necessario per cercare un dato nella cache di primo livello. Nel caso in cui il dato non sia presente nella cache L1, il processore cerca il dato nella cache di secondo livello, impiegando un tempo t2. Infine, se il dato non è presente nemmeno nella cache L2, il processore preleva il dato dalla memoria di lavoro, impiegando un tempo t3.Si chiede di calcolare il tempo medio di acceso ai dati nel conoscendo i miss-rate m1 e m2 dei due livelli di cache.

Soluzione dell’Esercizio 12.4L’esercizio può essere svolto generalizzando la soluzione dell’esercizio precedente. Il tempo medio impiegato dal processore per accedere ai dati è dato dalla somma di 3 componenti

- il tempo speso per cercare il dato nella cache di primo livello;- il tempo speso per cercare il dato nella cache di secondo livello;- il tempo speso per prelevare il dato dalla memoria principale.

Il primo termine è pari a t1 . Il secondo termine è pari a m1 × t2 , ossia è il prodotto tra la probabilità m1 di dover cercare il dato nella cache L2 e il tempo t2 di accesso alla cache L2.



Il terzo termine è pari a m1 × m2 × t3 , ossia è il prodotto tra la probabilità m1 × m2 di non trovare il dato in nessuno dei due livelli di cache e il tempo t3 necessario per accedere alla memoria di lavoro.La somma delle tre componenti ci permette di calcolare il tempo medio di accesso ai dati, che è pari a

t1 + m1 × t2 + m1 × m2 × t3 Ad esempio, nel caso in cui

t1 = 1 nst2 = 10 ns t3 = 100 ns m1 = 50%m2 = 20%

abbiamo1 + 0.5 × 10 + 0.5 × 0.2 × 100 = 1 + 5 + 10 = 16 ns

Esercizio 12.5Nel campo delle architetture multi-processore si utilizza spesso una grandezza chiamata frazione seriale fs per indicare la frazione del tempo di esecuzione di un programma che non trae beneficio dalla parallelizzazione. In altre parole, se indichiamo con T1 il tempo di esecuzione di un programma quando viene eseguito su un computer mono-processore e con Tn il tempo di esecuzione quando lo stesso programma viene eseguito su un computer con n processori, possiamo scrivere

Tn = T1 × Supponiamo di eseguire un programma su due computer dotati della stessa architettura ma con diverso numero di processori: il computer A è mono-processore, il computer B ha quattro processori. Il tempo di esecuzione del programma sui due computer è TA = 20 sec e TB = 6 sec. Calcolare la frazione seriale fs del programma.

Soluzione dell’Esercizio 12.5Il tempo di esecuzione del programma con un processore è pari a TA, ossia

T1 = TA = 20 sec.Il tempo TB è il tempo di esecuzione dello stesso programma ma con quattro processori, ossia

T4 = 13 sec.Possiamo quindi scrivere che

T4 = T1 × ossia

6 = 20 × Con alcuni passaggi ricaviamo che

6 = 20 × da cui si ottiene

fs = 1/15

Esercizio 12.6

Lo speed-up Sn misura di quanto si riduce il tempo di esecuzione di un programma quando viene eseguito su un computer con n processori rispetto al tempo di esecuzione su un computer mono-processore.



Sn = In altre parole, se un programma ha uno speed-up con 4 processori pari a 3.5, questo significa che, eseguendo quel programma su un sistema con 4 processori, il suo tempo di esecuzione si riduce di 3.5 volte rispetto a quando si esegue lo stesso programma su un sistema mono-processore.Utilizzando quanto visto nell’esercizio precedente, calcolare lo speed-up massimo di un programma con frazione seriale fs.

Soluzione dell’Esercizio 12.6Utilizzando la definizione di speed-up e servendosi della frazione seriale per calcolare il tempo di esecuzione di un programma su un computer con n processori, abbiamo che

Sn = Semplificando si ottiene

Sn = Questa è la curva di un’iperbole con un asintoto orizzontale, come rappresentato in figura. Lo speed-up massimo si ottiene con un numero infinito di processori ed è pari a 1 / fs .Si noti che, nel caso di frazione seriale nulla, la curva dello speed-up ha un andamento lineare.



Capitolo 14Archivi e basi di dati

Prestazioni dei dischi, esercizi SQL, Data Definition Language e Data Manipulation Language.

Esercizio 14.1Si chiede di calcolare il tempo medio necessario per un’operazione di ingresso/uscita di un disco magnetico con le seguenti caratteristiche

- velocità di rotazione: 15000 RPM (Revolutions Per Minute)- tempo di seek medio: 5 ms- transfer rate di un blocco di dati: 500 Mbit/s- dimensione di un blocco dati: 10 Kbit

Soluzione dell’Esercizio 14.1Il tempo medio necessario per un’operazione di ingresso/uscita è dato dalla somma di tre componenti:

tI/O = tSEEK + tLAT + tTRASF

Il primo di questi tre termini include il tempo necessario per lo spostamento meccanico del braccio che regge le testine. Lo spostamento della testina verso la traccia richiesta si chiama seek e l’attesa necessaria a realizzare questo spostamento si dice tempo di seek. È poi necessario attendere che il settore richiesto passi al di sotto della testina di lettura e scrittura; in media, questo tempo di latenza è pari alla metà del tempo di rotazione del dispositivo. Infine, è necessario attendere il tempo di trasferimento dei dati dal disco alla memoria o viceversa.

- Il tempo di seek tSEEK è un dato del problema.- Il tempo di latenza rotazionale è dato da

tLAT = × = 2 ms- Il tempo di trasferimento dei dati è dato da

tTRANSF = 1000 ms/sec × = 0.02 msIl tempo totale necessario per un’operazione di ingresso/uscita è dato dalla somma dei tre termini:

tI/O = 5 + 2 + 0.02 = 7.02 ms

Esercizio 14.2Si consideri il disco dell’esercizio precedente. Si chiede di calcolare il tempo medio necessario per un’operazione di ingresso/uscita nel caso in cui la frammentazione f dei blocchi è pari al 60%.

Soluzione dell’Esercizio 14.2In alcuni casi i blocchi di dati che devono essere letti o scritti dal disco possono essere fisicamente contigui, ossia possono trovarsi su una stessa traccia. In questo caso, per leggere un intera sequenza di blocchi, è necessario spostare la testina e attendere la rotazione del piatto una sola volta, dopodiché la sequenza di blocchi viene letta con una serie di operazioni di trasferimento.Più in generale, possiamo calcolare il tempo di ingresso/uscita come

tI/O = f × ( tSEEK + tLAT ) + tTRASF



dove f e la frammentazione dei dati su disco, ossia, la percentuale di blocchi di dati che non sono contigui.Con i dati del problema abbiamo

tI/O = 0.6 × (5 + 2) + 0.02 = 4.22 ms

Esercizio 14.3Siano date le seguenti relazioni:

persona (cod_fiscale, nome, eta, sesso)automobile (targa, proprietario, colore)

Definire lo schema relazionale tramite il DDL SQL.


CREATE TABLE persona(

cod_fiscale: char(9), PRIMARY KEY, NOT NULL,nome: char(20),eta: integer,sesso: char(1)

)

CREATE TABLE automobile(

targa(9), PRIMARY KEY, NOT NULL,proprietario: char(9),colore: char(10)

)

Esercizio 14.4Partendo dalle relazioni definite nell’esercizio precedente e riempite con i dati seguenti:

Relazione: persona Relazione: automobilenome cod_fiscale eta sesso proprietario targa colore

Rossi RSS123456 25 M RSS123456 AG125FA rossoBianchi BIA654321 29 M VER441611 FF111GG azzurroVerdi VER441611 26 F GRA741852 XX222FF rossoGrandi GRA741852 50 F RSS123456 FA143XX giallo

BIA654321 GA766AG rosso

Definire, usando il DML SQL, le seguenti interrogazioni:a. Estrarre il nome e l’età di tutte le persone di sesso femminile.b. Estrarre le targhe di tutte le automobili i cui proprietari hanno meno di 30 anni.c. Estrarre i nomi di tutte le persone di sesso maschile proprietarie di automobili rosse.

Per ognuna di esse si disegni inoltre la tabella contenente i risultati dell’interrogazione.




SELECT nome, etaFROM personaWHERE persona.sesso = ‘F’

nome etaVerdi 26Grandi 50

SELECT targaFROM persona, automobileWHERE persona.cod_fiscale = automobile.proprietario And persona.eta < 30

targaAG125FAFA143XXGA766AGFF111GG

SELECT nomeFROM persona, automobileWHERE persona.cod_fiscale = automobile.proprietario And persona.sesso=‘M’ And automobile.colore = ‘rosso’

nomeRossiBianchi



Capitolo 17Sicurezza dei calcolatori e delle reti

Crittografia.

Esercizio 17.1Scrivere una funzione in linguaggio C che permetta di decifrare un testo lungo N caratteri cifrato con il cifrario di Cesare sapendo che il testo in chiaro contiene sicuramente una particolare parola di M caratteri



/* Lunghezza delle stringhe da leggere */#define N 100#define M 100

/* Stringa che contiene il testo da “rompere” */char testo[N];

/* Stringa che contiene la parola presente nel testo da decifrare */char parola[M];

/* Codice ASCII della prima e dell’ultima lettera dell’alfabeto */int prima_lettera = ‘A’;int ultima_lettera = ‘Z’;

/* Numero di lettere dell’alfabeto */int num_lettere = ultima_lettera - prima_lettera;

int lun_testo, lun_parola;

int chiave;

bool fine = false;

int strlen(char a[]);int strcmp(char a[], char b[], int chiave, int n);

int main(){ int i;

printf("Testo cifrato :"); scanf("%s", testo);

printf("Parola nota :"); scanf("%s", parola); lun_testo = strlen(testo); lun_parola = strlen(parola);

/* Ciclo che prova diverse chiavi, tante quante le lettere dell’alfabeto */ for(chiave = 0; chiave < num_lettere; chiave++) {



/* Ciclo che cerca la parola nel testo cifrato */ for(i = 0; i < lun_testo-lun_parola+1; i++) { if(strcmp(testo+i,parola,chiave,lun_parola) == 0) { fine = true; break; } } if(fine) break; } if(fine) printf("La chiave e’ %d\n", chiave); }

int strlen(char a[]){ int i = 0; while (a[i] != 0) i++; return i; }

/* Confronta i caratteri uno ad uno, spostando “avanti” di “chiave” posizioni le lettere della stringa “a” */ int strcmp(char a[], char b[], int chiave, int n){ int i; for(i = 0; i < n; i++) if(((a[i]+chiave-prima_lettera) % num_lettere)+prima_lettera != b[i]) return 1; return 0; }



Capitolo 18La visione dei sistemi informatici da parte dell’utente finale

Esercizi EXCEL.

Esercizio 18.1Si costruisca un archivio, usando un qualsiasi foglio elettronico, contenente informazioni relative a un insieme di dipendenti di un’azienda. Tali informazioni devono contenere, tra l’altro:

- Nome e cognome della persona- Data di nascita- Data di assunzione- Retribuzione annua lorda

Altre informazioni possono essere inserite a discrezione dello studente.Un ulteriore campo, il cui valore deve essere opportunamente calcolato sulla base delle informazioni precedenti, deve indicare l’ammontare annuo della pensione cui il soggetto ha eventualmente diritto, sulla base della seguente definizione:Se il soggetto ha maturato un’anzianità di servizio ≥ 35 anni (per semplicità si può calcolare tale anzianità assumendo che l’anzianità di servizio sia il periodo di tempo intercorso dalla data di assunzione alla data attuale) e < 45 anni la pensione cui ha diritto è il 60% della retribuzione annua lorda. Se il soggetto ha maturato un’anzianità di servizio ≥ 45 anni la pensione cui ha diritto è il 90% della retribuzione annua lorda (la pensione non spetta a chi ha un’anzianità inferiore a 35 anni).

Soluzione dell’Esercizio 18.1Un foglio Excel contenente una possibile soluzione è fornito nel file:“SpShCap18\18.1.xls”.Per la sua costruzione si è fatto uso

della funzione Now per indicare la data attuale; delle funzioni logiche IF e AND per distinguere in vari casi possibili; della funzione differenza per calcolare la differenza tra la data attuale e la data di

assunzione: tale differenza è prodotta in giorni ed è stata quindi divisa per 360 secondo la convenzione commerciale che considera un anno costituito da 12 mesi di 30 giorni l’uno.

Esercizio 18.2Si risolva l’esercizio 7.5 utilizzando un foglio elettronico. In tal caso i dati di ingresso e di uscita devono trovarsi in apposite posizioni del foglio elettronico.

Soluzione dell’Esercizio 18.2Un foglio Excel contenente una possibile soluzione è fornito nel file:“SpShCap18\18.2.xls”.A mo’ di esempio una colonna contiene il calcolo della prima funzione richiesta e un’altra il calcolo della seconda.

Esercizio 18.3Si costruisca un archivio per la gestione (semplificata) di un registro IVA:



- nella prima colonna si trova il numero progressivo attribuito al documento di spesa;- nella seconda colonna si trovano gli estremi del fornitore;- nella terza l’imponibile ad aliquota 10%;- nella quarta l’imposta relativa all’imponibile indicato in precedenza (cioè il 10% di quanto

indicato nella terza colonna);- nella quarta e quinta rispettivamente si trovano imponibile e imposta relativi all’aliquota

20%;- nella sesta colonna si trova il totale dell’operazione (si noti che alcune fatture possono

avere imponibili e imposte per entrambe le aliquote).La riga in fondo al foglio contiene i totali come suggerito dalla figura sottostante.

Registro IVANumero progressivo

Dati del cliente

Imponibile al 10%

Imposta al 10%

Imponibile al 20%

Imposta al 20%

Totale

1 Telecom, ... 10.000 1.000 234.560 46.912 292.4722 AEM, ... 200.000 20.000 220.0003 Officina

Pinco 1.000.000

200.000 1.200.000

...

Totali xxx yyyy Zzz vvvv tttt

Un foglio Excel contenente una possibile soluzione è fornito nel file:“SpShCap18/18.3.xls”.

Esercizio 18.4Il signor Rossi vuole tenere sotto controllo i propri conti mensilmente. All’uopo egli desidera registrare ogni mese entrate e uscite, divise in opportune categorie, in modo da sapere se e quanto ha guadagnato o perso; inoltre egli desidera tenere sotto controllo anche il proprio conto corrente bancario, tenendo traccia di tutte le operazioni di prelievo-deposito effettuate in modo da poter sapere in ogni momento di quanto denaro egli dispone.Si costruisca mediante Framework uno strumento che soddisfi le esigenze del signor Rossi.

Parte FacoltativaSi osservi che solitamente pagamenti (e incassi) possono avvenire sia in contanti che mediante operazioni bancarie (bonifici, assegni, ...). Ad esempio: lo stipendio potrebbe essere accreditato automaticamente dal datore di lavoro sul cc del signor Rossi. Alcune spese egli potrebbe effettuarle pagando in assegni, ma altre usando contante che egli preleva ogni tanto dalla banca. In questo modo le operazioni sul cc non coincidono necessariamente con le operazioni di entrata-uscita.Si organizzi allora lo strumento in modo che incassi e pagamenti effettuati tramite operazioni bancarie possano essere registrati dal signor Rossi una sola volta (ad esempio se egli paga un elettrodomestico mediante un assegno egli segna questa spesa una sola volte mediante il suo strumento che provvede automaticamente ad aggiornare sia il conto ricavi-spese che lo stato del cc bancario). Le operazioni effettuate in contante invece devono essere trattate separatamente: ad esempio se il giorno 10 il signor Rossi preleva L. 500,000 questa operazione comporta un



aggiornamento del cc.ma nessuna spesa nel conto entrate-uscite; successivamente egli spende L. 250,000 al ristorante e L. 250,000 in abbigliamento pagando entrambe le volte in contanti: entrambe le operazioni vanno allora registrate come uscite nel registro entrate-uscite, ma non comportano alcun aggiornamento sul cc; chiaramente alla fine del mese I conti devono “tornare”, cioè la variazione dell’ammontare dell cc (più la variazione dell’ammontare del contante disponibile in cassa) deve uguagliare il netto del conto entrate-uscite.

Soluzione dell’Esercizio 18.4Una possibile soluzione della versione facoltativa è impostata nei fogli Excel forniti nel file: “SpShCap18\18.4.xls”.Si noti che sono stati usati due fogli nello stesso file: uno per gestire il conto entrate-uscite, chiamto ContoEc, l’altro, Banca, per gestire il conto corrente bancario. Alcune celle del foglio Banca sono calcolate automaticamente sulla base delle operazioni registrate nel ContoEc: queste sono suddivise, per ogni voce, in operazioni in contanti e operazioni effettuate tramite banca. Queste ultime sono automaticamente riportate nel foglio Banca. L’utente deve invece riportare sul foglio Banca tutte le operazioni di prelievo-deposito contanti. Si noti che, se a fine di un periodo il signor Rossi ha nel portafoglio (ammontare complessivo dei contanti) la stessa cifra che aveva all’inizio del periodo, il margine complessivo del periodo risultante nel ContoEc eguaglia la differenza tra fine-periodo e inizio-periodo del foglio Banca.NB. Per semplicità i fogli del file sono stati riempiti solo relativamente al mese di gennaio.

Esercizio 18.5Si vuole ripartire la spesa di costruzione di una strada a fondo chiuso sulla quale insistono quattro condomini di nome Primula, Violetta, Fiordaliso e Gelsomino, composti rispettivamente da 8, 6, 12 e 4 appartamenti e che distano dall’inizio della strada rispettivamente 10, 100, 250 e 300 metri. La spesa, di complessive L 50.000.000, va ripartita in base al numero di appartamenti di ogni condominio, pesato con la sua distanza dall’inizio della strada. Si costruisca un foglio elettronico che, tramite l’introduzione dei dati del problema, permetta di ottenere una ripartizione della spesa in modo analogo a quanto mostrato nella seguente tabella.

Condominio D=distanza N=no.app.ti Quote Q = N x D Ripartizione = Q x C

Primula 10 8 80 819672Violetta 100 6 600 6147541Fiordaliso 250 12 3000 30737705Gelsomino 300 4 1200 12295082

Totali 4880 50000000

Costo quota C = Costo complessivo/no. quote =

10245,90164

Soluzione omessa in quanto derivabile immediatamente dalla figura esplicativa.



Capitolo 19La produzione industriale del software

Esercizio 19.1Discutere la classificazione della modificabilità come qualità interna o esterna del prodotto o del processo di produzione.

Soluzione dell’Esercizio 19.1Nell’ambito dei prodotti software tradizionali, sviluppati da una azienda per un utente finale e rilasciati sotto forma di eseguibili, la modificabilità deve essere classificata come una qualità interna essendo percepita dal progettista/sviluppatore e non dall’utente finale. D’altra parte, nel caso di un prodotto software rilasciato in forma di sorgente (ad esempio una libreria open-source), l’utente finale è a sua volta uno sviluppatore che quindi può essere interessato alla modificabilità del prodotto. In questo caso è corretto classificare la modificabilità come una qualità esterna. Per quel che riguarda il caso del processo software piuttosto che del prodotto, la modificabilità è una qualità interna che indica la facilità con la quale è possibile modificare il processo per tenere conto di mutate condizioni esterne.

Esercizio 19.2Si usi un diagramma delle classi per modellare un distributore automatico di bevande. Si mettano in evidenza i diversi componenti e le principali azioni effettuabili.


Esercizio 19.3Con riferimento all’esercizio precedente si tracci un diagramma delle sequenze che mostri il funzionamento del distributore automatico e come le diverse parti interagiscano.




Ci concentriamo sullo scenario di scelta della bevanda, lasciando allo studente il compito di elaborare, in maniera analoga, lo scenario di inserimento della moneta.

Esercizio 19.4Si tracci un diagramma delle macchine a stati per il distributore automatico di bevande di cui agli esercizi precedenti.

Soluzione dell’Esercizio 19.4Come richiesto dal testo creiamo un diagramma delle macchine a stati per l’intero distributore, mantenendoci quindi ad un elevato livello di astrazione e trascurando i singoli componenti.

Esercizio 19.5Si modelli tramite UML il software di gestione di una agenzia di viaggi. L’agenzia vende pacchetti viaggio caratterizzati da una destinazione, una sede di partenza, una data di partenza, una data di ritorno, dalla categoria alberghiera ed dal costo. I tour operator possono collegarsi al sistema informativo dell’agenzia di viaggio per aggiungere nuove offerte. I clienti dell’agenzia possono accedere all’elenco delle offerte (per destinazione, sede di partenza, costo massimo e/o periodo di interesse) e, se ne trovano una di loro interesse, prenotare il viaggio. Il proprietario dell’agenzia, a fine giornata, può stampare l’elenco delle prenotazioni effettuate nel giorno. Periodicamente (ad esempio a inizio settimana), il proprietario può anche stampare l’elenco delle prenotazioni per viaggi con partenza in un determinato intervallo temporale (ad esempio la settimana successiva).



Si realizzi almeno un diagramma dei casi d’uso e un diagramma delle classi per l’intera applicazione, più un diagramma delle sequenze per lo scenario di prenotazione da parte di un cliente.

Esercizio 19.6Si modelli tramite UML il software di gestione di una agenzia immobiliare. L’agenzia vende e affitta appartamenti. Per ogni appartamento si memorizza l’indirizzo, il piano, il tipo dello stabile (1, 2 o 3), il numero di stanze, se la cucina sia abitabile o meno, la metratura, la presenza di cantina o solai annessi, i principali dati del proprietario (nome, cognome, indirizzo di residenza, num. Telefono), la cifra richiesta per la vendita o per l’affito mensile. Per i soli immobili in vendita si memorizza anche la data in cui l’appartamento sarà libero, mentre per i soli immobili in affitto si memorizza l’importo di eventuali spese accessorie (condominio, riscaldamento, etc). Per ogni cliente a cui sia stato mostrato un appartamento il sistema memorizza i principali dati anagrafici. In caso un cliente effettui un’offerta si memorizza la cifra offerta e se sia stata accettata o meno. Nel primo caso si memorizza la data del rogito/contratto di affitto.Il sistema viene utilizzato dal proprietario dell’agenzia o dai venditori per aggiungere nuovi appartamenti e/o informazioni su nuovi clienti a cui sia stato mostrato un appartamento. Il sistema offre anche un’interfaccia web alla quale chiunque può accedere per visionare l’elenco degli appartementi offerti.Si realizzi almeno uno diagramma dei casi d’uso e un diagramma delle classi per l’intera applicazione, più un diagramma delle sequenze per lo scenario in cui un cliente già presente in elenco venga a vedere un nuovo appartamento, nonché un diagramma delle macchine a stati per la classe che si ritiene più significativa.

Esercizio 19.7Si modelli tramite UML il software di gestione utilizzato nel sistema di cronometraggio di una gara automobilistica. Il software memorizza i dati relativi ai piloti in pista e, per ogni giro, il tempo dei diversi piloti. Il sistema fornisce la possibilità di calcolare la classifica finale della gara (sulla base del tenpo totale di percorrenza) oltre alla classifica dei migliori tempi sul giro. Il sistema permette infine di visualizzare tali dati oltre a calcolare e visualizzare il tempo più veloce in gara (con il nominativo del pilota che lo ha fatto).Si realizzi almeno un diagramma dei casi d’uso e un diagramma delle classi per l’intera applicazione, più un diagramma delle sequenze per lo scenario ritenuto più significativo.

Soluzioni di esercizi del testo



Esercizio testo 19.3





Esercizio testo 19.7Implementiamo in C le stesse classi implementate in Java nel testo, lasciando al lettore il compito di completare l’implementazione, se ritenuto utile:

#define MAX_CONTATTI 1000

typedef struct Rubrica {

Contatto contatti[MAX_CONTATTI];int numContatti;

} Rubrica;

void initRubrica(Rubrica *r){

r->numContatti = 0;}

void aggiungi(Rubrica *r, Contatto c){

if (r->numContatti < MAX_CONTATTI) {

r->contatti[r->numContatti] = c;r->numContatti++;

}}

void rimuovi(Rubrica *r, Contatto c){

int i, j;for (i = 0; i < r->numContatti; i++){

if (r->contatti[i]==c){

r->numContatti--;for (j = i; j < r->numContatti; j++)

r->contatti[j] = r->contatti[j+1];}

}



}

Contatto *cerca(Rubrica *r, char *s){

int i, j, numTrovati = 0;Contatto *ris;for (i = 0; i < r->numContatti; i++){

if (strstr(getNomeContatto(&(r->contatti[i]), s) != NULL || strstr(getCognomeContatto(&(r->contatti[i]), s) != NULL)

numTrovati++;}ris = (Contatto *) malloc(sizeof(Contatto)*numTrovati);j = 0;for (i = 0; i < numContatti; i++){

if (strstr(getNomeContatto(&(r->contatti[i]), s) != NULL || strstr(getCognomeContatto(&(r->contatti[i]), s) != NULL) {

ris[j] = r->contatti[i];j++;

}}return ris;

}

typedef struct Impegno{

TipoImpegno tipo;Data inizio;Data fine;char descrizione[256];char luogo[256];char note[256];

} Impegno;

void initImpegno(Impegno *imp, Data inizio, Data fine, char *descrizione){

imp->tipo = PRIVATO;imp->inizio = inizioimp->fine = fine;strcpy(imp->descrizione, descrizione);memset(imp->luogo,0,256);memset(imp->note,0,256);

}

void setTipoImpegno(Impegno *imp, TipoImpegno t) { imp->tipo = t; }

TipoImpegno getTipoImpegno(Impegno *imp) { return imp->tipo; }

void setInizioImpegno(Impegno *imp, Data d) { imp->inizio = d; }

Data getInizioImpegno(Impegno *imp) { return imp->inizio; }

void setFineImpegno(Impegno *imp, Data d) { imp->fine = d; }

Data getFineImpegno(Impegno *imp) { return imp->fine; }

#define MAX_PARTECIPANTI 10

typedef struct Appuntamento{

Impegno imp;Contatto partecipanti[MAX_PARTECIPANTI];int numPartecipanti;

}

void initAppuntamento(Appuntamento *app, Data inizio, Data fine, char *descrizione)



{initImpegno(& app->imp, inizio, fine, descrizione);app->numpartecipanti=0;

}

void aggPartec(Appuntamento *app, Contatto c){

if (app->numPartecipanti<MAX_PARTECIPANTI) {

app->partecipanti[app->numPartecipanti] = c;app->numPartecipanti++;

}}


Esercizio testo 19.10Operando in maniera analoga a quanto fatto nell’Esercizio 19.9 (la cui soluzione è stata data nell’Appendice F del testo), è facile giungere alla conclusione che la macchina a stati risultante avrebbe 90 stati.Più in generale, la macchina a stati finiti ottenuta dalla composizione di due o più macchine a stati finiti ha uno spazio di stato che è il prodotto cartesiano degli spazi di stato della macchine componenti. Di conseguenza la cardinalità dello spazio di stato di una macchina che descriva la composizione di h processi, ognuno con ki stati, è pari a: k1 · k2 · … · kh




Esercizio testo 19.13public class Contatto{

private String nome, cognome, mailPrim, mailSec, note;private Indirizzo indirizzo;private static final int MAX = 10;private RecapitoTelefonico tel[];private int numTel;

public Contatto(String nome, String cognome, String mail){

this.nome = nome;this.cognome = cognome;this.mailPrim = mail;tel = new RecapitoTelefonico[MAX];numTel = 0;

}

public void aggTel(String tipo, String numero){

if(numTel < MAX){

tel[numTel] = new RecapitoTelefonico(tipo, numero);numTel++;

}}

public RecapitoTelefonico[] getTel(){

return tel;}

public void setIndirizzo(Indirizzo ind){



indirizzo = ind;}

public Indirizzo getIndirizzo(){

return indirizzo;}

}


Date post:	08-Aug-2021
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Esercizi su web per il testo Informatica: Arte e mestiere, II...

Documents