Corsi di Laurea in Ingegneria Aerospaziale, Chimica, Elettrica,
dei Materiali, Meccanica e Nucleare
Corso di Fondamenti di Informatica - A.A. 1999/2000
Elenco degli esercizi per lo svolgimento dei progetti
Estratti da D. Calvanese, P. Liberatore, F. Massacci, R. Rosati.
Complementi ed esercizi di programmazione in PASCAL.
Esculapio Progetto Leonardo, seconda edizione, 1999
Esercizio 4.1
Scrivere una procedura di scrittura di matrice su file.

Esercizio 4.2
La funzione che determina se una matrice è un quadrato magico non è
ottimizzata, dal momento che vengono eseguite tutte le somme delle righe,
delle colonne e delle diagonali anche se per esempio la somma delle prime due
righe è differente. L'efficienza del programma può venire migliorata in
due modi:
- 1.
- Alla fine del ciclo sulle righe, se mag=FALSE allora non si esegue
tutto il resto. Lo stesso alla fine del ciclo sulle colonne e della
verifica della diagonale principale.
- 2.
- All'interno di ogni ciclo, si può uscire appena mag=FALSE.
Questo può venire realizzato sostituendo le istruzioni for con
istruzioni while, come già visto in precedenza.
Implementare le due ottimizzazioni della funzione che determina se una
matrice è un quadrato magico.

Esercizio 4.3
Scrivere una funzione che calcoli la somma di tutti gli elementi di una
matrice a valori interi.

Esercizio 4.4
Scrivere una funzione che determini quale è la riga di una matrice la cui
somma degli elementi è massima.

Esercizio 4.5
Scrivere una funzione che determini se due matrici sono uguali.

Esercizio 4.6
Scrivere una funzione che determini se una matrice coincide con un'altra
ruotata di

.

Esercizio 4.7
La funzione di verifica degli elementi nulli su una riga data nella sezione
precedente è corretta, ma non ottimizzata. Infatti, se si trova un elemento
non nullo non è necessario continuare la scansione. Fornire una versione
ottimizzata di tale procedura.

Esercizio 4.8
Una matrice quadrata si dice simmetrica se per ogni coppia di indici
i e
j l'elemento

è uguale all'elemento

.
Scrivere una
funzione che verifichi se una matrice quadrata è simmetrica.

Esercizio 4.9
Una matrice quadrata si dice triangolare superiore se tutti gli elementi

con
i minore di
j (cioè che stanno ``sotto'' alla diagonale
principale) hanno valore nullo. Scrivere una funzione che verifichi se una
matrice quadrata è triangolare superiore.

Esercizio 4.10
Una matrice quadrata si dice triangolare inferiore se tutti gli elementi

con
i maggiore di
j (cioè che stanno ``sopra'' alla
diagonale principale) hanno valore nullo. Scrivere una funzione che
verifichi se una matrice quadrata è triangolare inferiore.

Esercizio 4.11
Scrivere una funzione che restituisca il vettore delle somme delle righe di
una matrice, cioè un vettore che per ogni riga della matrice ha un elemento
il cui valore è pari alla somma degli elementi della riga.

Esercizio 4.12
Scrivere una procedura che restituisca il vettore delle somme delle colonne
di una matrice.

Esercizio 4.13
La trasposta di una matrice
N x
M è una matrice
M x
N tale che
per ogni coppia di indici
i e
j il valore dell'elemento

della
trasposta è pari al valore dell'elemento

della matrice.
Scrivere una procedura che restituisca la trasposta di una matrice.

Esercizio 5.1
Si forniscano due implementazione della procedura
CancellaElementoLista
utilizzando la tecnica del record generatore, e rispettivamente 1 puntatore e
2 puntatori per la scansione della lista in ingresso.

Esercizio 5.2
Si implementi una procedura
ConcatenaListe, che prenda in ingresso due
liste e restituisca la lista ottenuta per concatenazione delle due liste.
- 1.
- Si implementi ConcatenaListe con condivisione di memoria ed in
modo distruttivo sulla prima lista utilizzando l'intestazione
procedure ConcatenaListe (var lis1: TipoLista;
lis2: TipoLista);
``Con condivisione di memoria ed in modo distruttivo sulla prima lista''
significa che lis2 va attaccata in coda a lis1.
- 2.
- Si implementi ConcatenaListe con condivisione di memoria (rispetto
alla seconda lista) ed in modo non distruttivo utilizzando l'intestazione
procedure ConcatenaListe (lis1, lis2: TipoLista;
var lis3: TipoLista);
``Con condivisione di memoria (rispetto alla seconda lista) ed in modo non
distruttivo'' significa che lis1 va prima copiata in lis3 e poi
lis2 va attaccata in coda a lis3.
- 3.
- Si implementi ConcatenaListe senza condivisione di memoria ed in
modo non distruttivo utilizzando l'intestazione
procedure ConcatenaListe (lis1, lis2: TipoLista;
var lis3: TipoLista);
``Senza condivisione di memoria ed in modo non distruttivo'' significa che
che lis1 va prima copiata in lis3 e poi una copia di lis2 va
attaccata in coda a lis3.
Per ognuno dei casi si fornisca un'implementazione iterativa, una ricorsiva
ed una utilizzando le procedure e funzioni (anche non primitive) già
sviluppate.

Esercizio 5.3
Si implementi una funzione
EsisteInListaOrdinata, che prenda in ingresso
una lista con gli elementi in ordine crescente ed un elemento e restituisca
TRUE se l'lemento compare nella lista e
FALSE altrimenti. Rispetto alla
funzione
EsisteInLista si sfrutti il fatto che la lista è ordinata per
interrompere la scansione della lista quando si arriva ad un elemento
maggiore di quello da cercare. In questo caso l'elemento non può
sicuramente comparire nel resto della lista.

Esercizio 5.4
Si implementi una procedura
CancellaElementoListaOrdinata, che prenda in
ingresso una lista con gli elementi in ordine crescente ed un elemento e
restituisca la lista modificata avendo cancellato la prima occorrenza
dell'elemento. Si sfrutti anche in questo caso il fatto che la lista è
ordinata.

Esercizio 5.5
Si implementino procedure o funzioni P
ASCAL che realizzano le seguenti
funzionalità su liste rappresentate tramite record e puntatori. Si
utilizzi per ogni procedura o funzione una intestazione opportuna e si
forniscano diverse implementazioni (iterative, ricorsive ed utilizzando le
funzioni elementari e/o non elementari) adottando le tecniche di
programmazione mostrate nel presente capitolo:
- 1.
- somma e/o media degli elementi di una lista di interi;
- 2.
- conteggio del numero di volte che un dato elemento compare in una
lista;
- 3.
- lunghezza della massima sequenza di elementi uguali ad un dato
elemento;
- 4.
- lunghezza della massima sequenza di elementi consecutivi uguali;
- 5.
- inserimento di un elemento dopo un elemento dato;
- 6.
- cancellazione di tutti gli elementi pari da una lista di interi;
- 7.
- cancellazione dell'ultimo elemento di una lista;
- 8.
- cancellazione dell'ultima occorrenza di un dato elemento da una lista;
- 9.
- cancellazione di tutti gli elementi di ordine pari da una lista (cioè
del secondo, del quarto, etc.);
- 10.
- cancellazione di tutti gli elementi di ordine dispari da una lista
(cioè del primo, del terzo, etc.);
- 11.
- cancellazione di tutte le occorrenze successive alla prima di un dato
elemento;
- 12.
- cancellazione di tutte le occorrenze successive alla prima di tutti gli
elementi;
- 13.
- creazione di una lista che contenga gli stessi elementi di una lista
passata come parametro, ma in ordine inverso;
- 14.
- [Difficile] inversione di una lista, realizzata attraverso
l'inversione dei puntatori senza allocare o deallocare nuovi record.

Esercizio 5.7
Si forniscano diverse implementazioni in P
ASCAL (iterative, ricorsive ed
utilizzando le funzioni elementari e/o non elementari) di procedure che
effettuano l'ordinamento di una lista. Si utilizzino gli algoritmi di
ordinamento su vettori presentati nel capitolo 9
Si forniscano:
- 1.
- [Difficile] implementazioni che effettuano scambi tra i campi
info dei record contenenti gli elementi della lista, senza modificare
i puntatori della lista;
- 2.
- [Molto difficile] implementazioni che effettuano scambi tra i
puntatori dei record contenenti gli elementi della lista, senza modificare
i campi info della lista;

Esercizio 10.1
Modificare la procedura richiesta al punto (2) in modo tale che restituisca
il valore vero se in
T esistono
k posti liberi,
non necessariamente
adiacenti, su una riga con costo unitario

.

Esercizio 10.2
Modificare la procedura richiesta al punto (2) in modo tale che restituisca
il valore vero se in
T esistono
k posti liberi,
non necessariamente
adiacenti e non necessariamente sulla stessa riga, con costo unitario

.

Esercizio 10.3
Modificare la procedura richiesta al punto (2) in modo tale che restituisca
il valore vero se in
T esistono
k posti liberi adiacenti con costo
unitario

,
dove per adiacenti si intendono, oltre a due posti
successivi sulla stessa riga, anche l'ultimo posto (colonna
m) di una riga
ed il primo posto (colonna 1) della riga successiva.

Esercizio 10.4
Modificare la procedura richiesta al punto (2) in modo che stampi la lettera
(o le lettere) che compare il maggior numero di volte nelle copie degli
elementi di stampa a disposizione.

Esercizio 10.5
Modificare la procedura richiesta al punto (3) in modo che funzioni anche con
parole composte da un numero dispari di caratteri. Per questo tipo di parole,
la stampa dell'ultimo carattere può avvenire utilizzando una qualsiasi
coppia che ha come primo carattere l'ultimo carattere della parola.

Esercizio 10.6
Modificare la procedura proposta al punto (1) in modo tale che esca dal ciclo
di scansione non appena:
- a)
- si è trovato un elemento dominante;
- b)
- non si può più trovare un elemento dominante perché si è
già scandita più di metà della matrice.

Esercizio 10.7
Modificare la procedura proposta al punto (1) in modo tale che i due cicli
for più interni vengano eseguiti solo se l'elemento corrente dei cicli
più esterni (
m[i,j]) è un carattere che
non era già stato
considerato in precedenza. Si utilizzi a tale scopo una matrice di valori
booleani, per tenere traccia degli elementi già considerati.

Esercizio 11.1
Modificare la procedura sviluppata al punto (2) in modo da riutilizzare la
memoria occupata dagli insiemi in ingresso per la creazione dell'insieme
unione. Le liste in ingresso vanno perdute, e la memoria occupata da
eventuali elementi non utilizzati deve essere di nuovo resa disponibile.

Esercizio 11.2
Si scriva una procedura P
ASCAL che, ricevendo in due parametri di ingresso
due insiemi rappresentati mediante liste semplici, fornisca in un parametro
di uscita l'intersezione degli insiemi dati, nella stessa rappresentazione,
creando una nuova lista senza modificare gli insiemi dati.

Esercizio 11.3
Si scriva una procedura P
ASCAL che, ricevendo in un parametro di ingresso
un insieme rappresentato tramite vettore caratteristico, fornisca in un
parametro di uscita lo stesso insieme rappresentato mediante lista semplice.

Esercizio 11.4
Scrivere una procedura P
ASCAL che, ricevendo come parametri di input un
numero di inventario e un numero di utente, aggiorni la lista dei prestiti
dell'utente, eliminando (se esiste) il record con il numero di inventario in
input nella lista dei prestiti dell'utente il cui numero è ricevuto in
input dalla procedura.

Esercizio 11.5
Scrivere una procedura P
ASCAL che, ricevendo come parametro di input
l'immagine in forma compatta prodotta dalla procedura richiesta al punto (2),
crei una rappresentazione compatta dell'immagine ottenuta invertendo ogni
riga. Ad esempio, se la riga
i-esima è
B B B B B V V V V V V G G G B B .....
la riga
i-esima invertita è
..... B B G G G V V V V V V B B B B B

Esercizio 11.6
Fornire una implementazione iterativa della procedura richiesta al punto (3).

Esercizio 11.7
Modificare la procedura richiesta al punto (3) in modo tale che restituisca
come parametro di uscita la lista ottenuta dalla lista di ingresso

eliminando tutti i record con quantità di pioggia maggiore o uguale a

.

Esercizio 11.8
Modificare la procedura richiesta al punto (3), nell'ipotesi che la lista di
input
non sia ordinata per quantità di pioggia
decrescenti.

Esercizio 11.9
Si modifichi la procedura sviluppata al punto (3) in modo che, ricevendo per
parametri le liste

e

,
crei la lista delle località
che soddisfano
entrambe le condizioni (a) e (b) e la restituisca in
un parametro di uscita. Tale lista deve essere ordinata in base alla
distanza crescente dal giacimento conosciuto e ciascuna località deve
occorrere una sola volta. La procedura deve anche stampare su standard
output le località in

la cui distanza dal giacimento conosciuto
risulti inferiore a 100 chilometri.

Esercizio 11.10
Si modifichi la procedura sviluppata al punto (3) in modo che effettui
l'eliminazione delle rimanenze rispetto ad una soglia

per tutti i
generi di prodotti presenti in

.

Esercizio 11.11
Estendere la funzione proposta come soluzione al punto (2) in modo che valuti
correttamente un'espressione banale nella quale l'operatore `
-'
può comparire più volte consecutivamente.

Esercizio 11.12
Estendere la funzione proposta come soluzione al punto (2) in modo che stampi
un messaggio di errore e restituisca il valore 0 nel caso in cui la lista
passata come parametro non rappresenti un'espressione banale corretta.

Esercizio 11.13
Implementare una funzione ricorsiva che valuti un'espressione banale
applicando le operazioni da destra a sinistra. Si utilizzi l'algoritmo
ricorsivo fornito come soluzione errata alla funzione richiesta al punto (2).

Esercizio 11.14
[Difficile]
Scrivere una funzione ricorsiva per la valutazione di un'espressione banale
come richiesto al punto (2), cioè applicando le operazioni da sinistra a
destra.

Esercizio 11.15
[Molto difficile]
Scrivere una funzione (ricorsiva o iterativa) per la valutazione di
un'espressione banale, tenendo conto della precedenza dell'operatore
`
*' sull'operatore `
+'.

Esercizio 11.16
[Difficile]
Si modifichino le procedure sviluppate ai punti (2) e (3) in modo che le
righe vengano spezzate solo in prossimità degli spazi bianchi. Si ammette
quindi che una riga possa contenere meno di

caratteri.

Esercizio 11.17
[Difficile]
Si modifichino le procedure sviluppate ai punti (2) e (3) in modo che le
righe vengano spezzate solo in prossimità degli spazi bianchi. Le righe
che sono state spezzate devono essere portate tutte a lunghezza

,
eventualmente spaziando le parole in modo uniforme attraverso l'inserimento
di spazi bianchi.

1999-05-21