Prove d'esame 2020/21 Algoritmi e strutture dati

A T I I T

P R O G R A M M A Z I O N E

S R T A

O H A S H T A B L E M

R F R S M A I N

T I P O L I S T A C

Q E S T A C K

Si vogliono risolvere in C i seguenti problemi:

• Definire una opportuna struttura dati in grado di rappresentare lo schema di

gioco, utilizzabile per risolvere i problemi che seguono

• Verificare che uno schema già completato sia compatibile con un dato elenco

di parole.

• Dato uno schema libero e un elenco di parole, trovare (se esiste) un possibile

completamento dello schema mediante la selezione di un sottoinsieme delle

parole.

1.2.2 Struttura dati e formato file

Tra i vari formati possibili per rappresentare uno schema, si è scelto quello di elencare

in modo esplicito collocazione e lunghezza delle parole orizzontali e verticali. Date

queste, le caselle nere, se necessario, possono essere determinate in modo univoco.

Lo schema è rappresentato in un file che contiene:

• Prima riga, due interi e che rappresentano le dimensioni ed un intero che

R C N

rappresenta il numero di parole 5

Algoritmi e Strutture Dati Temi d’esame - Programmazione

• La collocazione delle parole orizzontali e verticali nello schema, una per ri-

ga, nel formato dove è

<lunghezza> <r> <c> <direzione>, <lunghezza>

la lunghezza della parola, e sono gli indici della casella di inizio

<r> <c>

e è uno tra i caratteri (per orizzontale) oppure (per

<direzione> ‘O’ ‘V’

verticale).

Esempio

15 9 18 // Schema 15x9 con 18 punti di inizio per le parole

8 0 0 V // Parola verticale iniziante in posizione [0,0] di lunghezza 8 caratteri

4 0 2 V

4 0 6 V

...

5 7 5 O // Parola orizzontale iniziante in posizione [7,5] di lunghezza 5 caratteri

2 7 2 V

5 8 10 O

Per completare lo schema, è fornito un insieme di parole. Le parole sono riportate

in un secondo file con il seguente formato:

• Sulla prima riga appare il numero di parole

P

• Seguono righe riportanti una parola ognuna.

P

Esempio

50

ALGORITMI

PROGRAMMAZIONE

DIJKSTRA

BST

UNIONFIND

...

Le parole hanno lunghezza massima 20 caratteri e non si ripetono nel file. Si

definiscano due strutture dati:

• una (con wrapper in grado si gestire lo schema, cioè le col-

struct schema)

locazioni (per le parole) nella griglia, sia orizzontali che verticali, ognuna

caratterizzata da casella di inizio e da lunghezza.

• una (con wrapper adatta a immagazzinare gli elenchi delle

struct parole)

parole ammesse, organizzate per lunghezza, in modo tale da poter accedere

con costo O(1) all’elenco delle parole di una data lunghezza

Si scrivano le funzioni, per l’acquisizione di tali strutture dati dai file.

6

Algoritmi e Strutture Dati Temi d’esame - Programmazione

1.2.3 Funzione di verifica

Si scriva una funzione che, ricevuti come parametri uno schema, un elenco di parole

e una matrice di caratteri (di dimensione compatibile con lo schema) contenente uno

schema di cruciverba completato (il contenuto delle caselle nere è trascurabile, in

quanto vanno solo controllate le parole), verifichi se le parole orizzontali e verticali

presenti nello schema sono compatibili con l’elenco delle parole. Il prototipo della

funzione sia:

int verificaSchema(schema *s, parole *p, char **m);

1.2.4 Problema di ricerca

Scopo del gioco è di posizionare opportunamente un sottoinsieme delle parole nella

griglia completandola. Le parole non possono comparire più di una volta nella

griglia. È sufficiente individuare la prima soluzione valida trovata, ammesso che

esista. Individuata la prima soluzione, la funzione termina.

• Si dica a quale schema di funzione ricorsiva si fa riferimento e perché

• Si definisca la struttura dati usata per rappresentare la soluzione struct solu-

zione

• Si scriva la funzione wrapper di invocazione della funzione ricorsiva di ricerca

void solve(schema *s, parole *p);

• Si scriva la funzione ricorsiva di ricerca che trova (se esiste) un elenco di parole

in grado di completare lo schema

void solve_r(schema *s, parole *p, soluzione *sol, int pos, ..., int

*trovato);

• Si scriva una funzione che data una soluzione, verifichi se questa rispetta i

vincoli (ad esempio, una parola verticale e una orizzontale devono avere lo

stesso carattere al loro incrocio) oppure no. Una soluzione è data dalle parole

selezionate per completare lo schema; si può trattare di soluzione parziale o

completa, a seconda che si richiami la funzione a scopo di pruning oppure in

un caso terminale della ricorsione. Completare opportunamente il seguente

prototipo e l’implementazione della funzione sulla base della scelta di utilizzo

effettuata.

int checkSol(schema *s, soluzione *sol, ...);

7

Algoritmi e Strutture Dati Temi d’esame - Programmazione

2 03/09/2020

2.1 Traccia da 12 punti

2.1.1 2pt

La funzione riceve in input due matrici quadrate di interi (di dimensione

mySum A

× ×

e (di dimensione Considerando per ciascuna matrice le righe

nA nA) B nB nB).

e le colonne, sono possibili le seguenti coppie dove il primo elemento della coppia

appartiene ad e il secondo a (riga A, riga B), (riga A, col B), (col A, riga B),

A B: i j i t k j

≤ ≤ ≤ ≤

(col A, col B) dove 0 i < nA, 0 k < nA, 0 j < nB, 0 t < nB. Si

k t

scriva un programma che identifica la coppia in cui la somma di tutti i valori del

primo e del secondo elemento (siano essi righe o colonne) sia la più vicina possibile

a zero. La scelta per ogni matrice sia espressa come stringa, nella forma R<indice>

(C<indice>) per indicare un indice di riga (colonna). Gli indici partono da zero.

Esempio  

1 2 3

2 0

−3

3 2

A = B =

  7 1

−6

11 12 − −

La coppia identificata dall’algoritmo è (col A, riga B) per cui vale (3 3 6) +

2 1

(7 + 1) = 2. L’output è quindi Si completi adeguatamente il codice della

C2 R1.

funzione, dato il prototipo:

coppia mySum(int **A, int nA, int **B, int nB)

e la definizione:

typedef struct coppia_ {char *scelta_A; char *scelta_B;} coppia;

Si riporti esplicitamente l’invocazione della funzione fatta dal main chiamante.

mySum

2.1.2 4pt

Si definisca una struttura dati adatta a rappresentare una lista linkata circolare. In

una lista circolare il puntatore al successore dell’elemento in coda punta all’elemento

di testa della lista stessa. I nodi della lista siano caratterizzati da un valore intero e

da un contatore di occorrenze. Si definisca la lista come ADT di I classe e il tipo nodo

come quasi ADT. Indicare esplicitamente in quale modulo/file appare la definizione

dei tipi proposti. Non è ammesso l’uso di funzioni di libreria. Si implementi

la seguente funzione di inserimento nella lista definita in precedenza: se l’elemento è

8

Algoritmi e Strutture Dati Temi d’esame - Programmazione

già presente, si incrementa il contatore. Se non è presente va inserito nella posizione

indicata dal secondo parametro. La testa ha posizione 0 per convenzione. Non è

ammesso l’uso di funzioni di libreria.

void LISTinsert(list_t L, int posizione, ...)

2.1.3 6pt

Un locale ha a disposizione un insieme di sale. La capienza di ogni sala è registrata

nS

in un vettore Il locale riceve, per un certo giorno, prenotazioni da gruppi. La

S. nP

cardinalità di ciascun gruppo è registrata in un vettore P.

Esempio

4 sale di capacità, rispettivamente 4, 9, 11 e 5 persone:

nS = 4

{4,

S = 9, 11, 5}

Prenotazione da parte di 9 gruppi con le rispettive cardinalità:

nP = 9

{2,

P = 2, 3, 2, 6, 2, 4, 4, 3}

Si scriva un algoritmo ricorsivo in grado di determinare, se esiste, un’assegnazio-

ne delle prenotazioni ricevute nelle sale del locale, tale per cui il numero di sale

occupate sia minimo. Si assuma non sia possibile spezzare una prenotazione su

due/più sale. Il prototipo della funzione invocata sia nella forma:

void solve(int *S, int nS, int *P, int nP, ...);

Tale funzione può rappresentare un wrapper per l’effettiva funzione ricorsiva. Giu-

stificare la scelta del modello combinatorio adottato. Giustificare la scelta del/dei

criteri di pruning adottati, o il motivo della loro assenza.

2.2 Traccia da 18 punti

2.2.1 Breve introduzione e definizioni

×

Una matrice rettangolare di dimensione rappresenta una griglia di gioco, le

R V

cui celle o sono vuote o contengono una cifra tra 1 e 9. La griglia di gioco è riportata

su un file testuale (griglia.txt) con il seguente formato:

9

Algoritmi e Strutture Dati Temi d’esame - Programmazione

• sulla prima riga appare una coppia di interi e a rappresentare le

<R> <C>

dimensioni della griglia

• seguono righe di caratteri (tra 1 e 9 per le celle piene oppure 0 per quelle

R C

vuote).

Esempio

3 3

1 5 0

0 0 0

0 0 0

Lo scopo del gioco è completare la griglia riempiendo le celle vuote con valori tra 1

e 9 tali da creare regioni contigue di dimensione pari alle cifre in esse contenute. Si

ricordi che:

• si considerano adiacenti due celle che condividono un lato verticale o orizzonta-

le. Non sono adiacenti le celle in diagonale. La nozione di adiacenza permette

quindi di considerare la mappa come un grafo (implicito) nel quale le celle libe-

re rappresentano i vertici, mentre le adiacenze (al massimo 4 per ogni vertice)

rappresentano gli archi.

• insiemi di celle adiacenti a 2 a 2 e contenenti lo stesso valore definiscono una

regione contigua

• la dimensione di una regione contigua è il numero di celle che la compongono.

Alcuni dei completamenti validi per la griglia parziale precedente sono, ad esempio:

       

1 5 1 1 5 3 1 5 1 1 5 5

5 5 5 5 5 3 5 5 5 3 5 5

       

5 2 2 5 5 3 1 5 1 3 3 5

Si scriva un programma in C che:

• definisca una opportuna struttura dati in grado di rappresentare lo schema di

gioco, utilizzabile

• per risolvere i problemi che seguono

• verifichi che una griglia già completata contenuta in un file testuale rispetti

le regole del gioco dato uno schema parziale, trovi (se esiste) una soluzione

ottima per il problema. 10

Algoritmi e Strutture Dati Temi d’esame - Programmazione

2.2.2 Struttura dati

Si definiscano una struttura dati adatta a rappresentare lo schema di gioco e si

definisca la funzione di acquisizione della griglia. Il prototipo della funzione sia:

int** leggiMappa(FILE *fin, int *R, int *C);

2.2.3 Problema di verifica

Si scriva una funzione che, data una griglia di gioco già completata, verifichi se

questa rispetta la regola di comple