• Non ci sono risultati.

Esercizio 1 (13 punti)

N/A
N/A
Protected

Academic year: 2021

Condividi "Esercizio 1 (13 punti)"

Copied!
2
0
0

Testo completo

(1)

Prova scritta del 19 luglio 2018 di Fondamenti di Informatica I (prof. Montessoro) + Fondamenti di Informatica II (prof. Di Gaspero)

Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 3 ORE

A pena di annullamento immediato della prova:

1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.

2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula

Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.

Esercizio 1 (13 punti)

Nel gioco della morra cinese ad ogni giocata due giocatori scelgono e dichiarano con un gesto della mano uno tra gli oggetti

“carta”, “forbici” e “ sasso”. Il sasso vince sulla forbice, la forbice sulla carta e la carta sul sasso.

In una gara internazionale sono state registrate le giocate di due giocatori in un file che contiene, per ogni riga, l’oggetto scelto dal giocatore 1 e quello scelto dal giocatore 2. Il problema è che, a causa delle numerose nazionalità presenti, la registrazione è avvenuta in modo un po’ confuso e i nomi degli oggetti sono stati scritti in lingue diverse, come nell’esempio a destra.

Il vettore char* dizionario[50][3] contiene la forma

delle tre parole in tutte le lingue utilizzate (che sono al massimo 50, il numero di lingue effettivamente presenti è contenuto nella variabile int n_lingue), nell’ordine “carta”,

“forbici” e “sasso”. Si veda l’esempio a sinistra. Si osservi che le parole non contengono mai spazi.

Si scriva una funzione in linguaggio C che riceva come argomenti il nome di un file contenente le giocate come sopra descritto, il vettore char* dizionario[50][3]e la variabile intera int n_lingue e stampi il punteggio dei due giocatori e il vincitore (oppure l’indicazione che la partita è terminata alla pari).

Nell’esempio precedente il programma dovrà stampare:

punteggio giocatore 1: 2 punteggio giocatore 2: 1 vince il giocatore 1

NOTA: è obbligatorio scrivere e utilizzare una funzione che riceva come ingresso due codici numerici che rappresentano gli oggetti dichiarati in una giocata (0 = carta, 1 = forbice, 2 = sasso) e restituisce 1 se vince il primo giocatore e 2 se vince il secondo.

Esercizio 2 (12 punti)

Un modo per rappresentare gli insiemi di valori interi (nel senso matematico di ”collezioni” di valori prive di duplicazioni) è attraverso un vettore dinamico che contiene i valori rappresentati nell’insieme. In particolare, qualora il vettore venga

mantenuto ordinato, le operazioni di verifica dell’appartenenza di un elemento ad un insieme possono essere realizzate in modo efficiente.

Vogliamo definire l’implementazione del tipo di dato astratto insieme che gestisca questa struttura dati attraverso la sua rappresentazione per mezzo di vettori dinamici ordinati.

Le operazioni possibili sugli insiemi sono le seguenti:

• insieme crea_insieme(): crea un nuovo insieme vuoto.

• struct info_rango rango(insieme i, int x): restituisce due informazioni organizzate nella seguente struct:

struct info_rango { int rango;

bool presente;

}

scissors carta stone ciseaux forbici pierre carta paper paper papier carta forbici sasso

paper scissors stone

papier ciseaux pierre

(2)

Il campo rango conterrà il rango del valore x nell’insieme i, ovvero il numero di elementi minori di x (alternativamente, la posizione di x nella sequenza ordinata), mentre il campo presente avrà valore true qualora l’elemento x sia presente nell’insieme e false in caso contrario.

* insieme aggiungi(insieme* i, int a): restituisce il descrittore del nuovo insieme ottenuto aggiungendo il valore a (allocando, se necessario, opportunamente la memoria); se tale valore è già presente nell’insieme la funzione non farà alcuna modifica

* void elimina_insieme(insieme* i): elimina l’insieme i liberando la memoria eventualmente allocata dinamicamente.

1. Si definisca un possibile descrittore per il tipo di dato insieme (in altre parole la typedef struct {}

insieme) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.

2. Si implementino in linguaggio C le operazioni di manipolazione degli insiemi descritte in precedenza. Qualora fosse necessario si assuma l’esistenza delle funzioni di manipolazione delle strutture dati utilizzate nel descrittore, scelte fra quelle studiate durante il corso. In particolare, si richiede che l’implementazione della funzione rango() abbia complessità O(log n) , con n numero di valori contenuti nell’insieme.

Nota: il rango di un determinato valore x è calcolabile sia nel caso esso sia presente nell’insieme che in caso contrario. Ad esempio, per l’insieme { 1, 5, 8, 14, 18 }, il valore 4 ha rango 2 (ovvero apparirebbe in seconda posizione nella sequenza ordinata), mentre il valore 14 ha rango 4.

Suggerimento: la funzione rango() può essere utilizzata per implementare la funzione aggiungi() in modo più efficiente.

Esercizio 3 (5 punti)

Si consideri uno heap-tree in cui a ciascun nodo n sia associato un valore intero n.dato. Scrivere un algoritmo (ricorsivo) in linguaggio C che, dato in input il descrittore di un albero siffatto, due valori estremi a e b e una pila p, riempia la pila con il valore di tutti i nodi i cui campi dato sono compresi fra a e b(estremi inclusi).

A titolo d’esempio, si considerino le seguenti due esecuzioni in un dato heap-tree con valori diversi per a e b. I nodi grigi sono quelli che dovranno essere memorizzati nella pila.

20

11

7

1

8

5 6

18

13 a = 4 b = 10

15

20

11

7

1

8

5 6

18

13 a = 12 b = 16

15

Riferimenti

Documenti correlati

Si trovino gli intervalli massimali su cui f

Di seguito sono esposte due possibili risoluzioni di due esercizi dati durante il corso, al solo scopo di mostrare il livello di motivazione dei passaggi al quale ten- dere

COMPITO DI MATEMATICA DISCRETA Modulo I 22 Giugno

2, si ricava che il termine generale della serie non `e infinitesimo, quindi la serie non converge (ovvero, in questo caseo, diverge)... Pertanto, F risulta

[r]

Soluzione degli esercizi del primo esonero di Calcolo Differenziale ed Integrale I e

Sia X uno spazio

Essendo B aperto in R, ne consegue che A sarà un sottoinsieme proprio di B, ricordando il legame tra chiusura e completezza di uno spazio metrico (stiamo già implicitamente pensando