Corsi di laurea in Ingegnera Elettronica e Ingegneria Gestionale Fondamenti di Programmazione / Fondamenti di Informatica I
Prova scritta del 16 giugno 2017
Esercizio 1 (15 punti)
Il noto gioco MasterMind consiste nell’indovinare un numero segreto di quattro cifre per tentativi. Ad ogni tentativo al giocatore viene comunicato il numero di cifre indovinate in valore e in posizione e il numero di cifre indovinate in valore ma nella posizione sbagliata. Il numero di cifre indovinate in valore e posizione è convenzionalmente indicato come “nere” e quello delle cifre indovinate solo in valore come “bianche”.
Per esempio, se il numero da indovinare è 7545, i seguenti tentativi riceveranno le rispettive risposte:
6703 nere 0, bianche 1; 7451 nere 1, bianche 2; 7455 nere 2, bianche 2; 7545 nere 4, bianche 0 (numero indovinato).
Scopo dell’esercizio è scrivere un programma per giocare a MasterMind. Ai fini dell’esercizio (e per permettere un’agevole verifica del corretto fuzionamento) il programma dovrà ricevere sulla riga di comando il numero segreto da indovinare, e poi leggerà da tastiera i tentativi del giocatore comunicandone di volta in volta l’esito secondo le regole sopra descritte. Il programma terminerà quando il numero viene indovinato. Inoltre, in alternativa all’inserimento di un numero, il giocatore potrà inserire la parola QUIT, a seguito della quale il programma terminerà comunicando qual era il numero segreto. Si assuma che gli inserimenti avvengano sempre in formato corretto.
SUGGERIMENTO: si memorizzino il numero segreto e i tentativi in stringhe di caratteri, non in variabili intere.
Per generare le risposte si suggerisce di utilizzare il seguente algoritmo.
Si definiscano due vettori di 4 flag ciascuno, uno per le cifre del numero segreto e uno per le cifre del tentativo.
In una prima fase si scorrono entrambi i numeri e, se si trova corrispondenza tra una cifra del numero segreto e la cifra nella stessa posizione del tentativo, si marcano a
“utilizzate” settando i corrispondenti flag in entrambi i vettori e si incrementa il contatore delle cifre nere.
Successivamente, per ogni cifra del tentativo non ancora utilizzata si cerca lo stesso valore tra le cifre non ancora utilizzate del numero segreto e, se lo si trova, si marcano utilizzate le due cifre settando i corrispondenti flag (che non saranno nella stessa posizione), e si incrementa il contatore delle cifre bianche.
Si vedano nel riquadro a lato due esempi di esecuzione del programma.
Esercizio 2 (15 punti)
Si vuole comprimere un file di testo (per semplicità lo si assuma contenente solo parole composte da caratteri alfabetici minuscoli e separate solo da spazi) mediante una semplice tecnica a dizionario. Si tratta di copiare nel file compresso ogni parola solo la prima volta che compare, e sostituirla, le volte successive, con l’indice con cui tale parola è stata inserita nel dizionario (cioè il numero d’ordine della prima occorrenza della parola nel file senza contare le eventuali ripetizioni di altre parole). Inoltre, se si trova nel file originale una parola che è l’inverso di un’altra già nel dizionario, la si sostituisce anch’essa con l’indice di quest’ultima, ma negativo (cioè, se nel dizionario è presente “la” all’indice 7, la parola “al” sarà sostituita da -7).
Per ragioni statistiche il programma dovrà, al termine, anche stampare a video il dizionario riportando quante volte è stata riutilizzata ciascuna parola.
Se, per esempio, il file di ingresso contiene il seguente testo:
questo file serve per provare questo programma e la rispondenza al testo e per provare se i programmatori evitarono soluzioni ornative anche se non per questo non da provare
il programma dovrà generare un file di uscita contenente il seguente testo compresso:
questo file serve per provare 0 programma e la rispondenza -7 testo 6 3 4 se i programmatori evitarono soluzioni ornative anche 10 non 3 0 17 da 4
e visualizzare il numero di riutilizzo delle parole come riportato nel riquadro a lato.
Si scriva in linguaggio C la funzione void comprimi (FILE *fpin, FILE *fpout) che riceva come argomenti i puntatori a due file, il primo di ingresso e il secondo di uscita già aperti rispettivamente in lettura e scrittura, e scriva nel secondo la versione compressa del primo, utilizzando la tecnica sopra descritta. Si assuma che il numero massimo di parole da inserire nel dizionario sia pari a 500. Inoltre, si assuma già disponible la funzione void reverse (char t[], char s[]) che copia nella stringa t la stringa s invertita.
C:\programmi>mastermind 3466 inserire numero: 1234
nere: 0, bianche: 2 inserire numero: 3456 nere: 3, bianche: 0 inserire numero: 3455 nere: 2, bianche: 0 inserire numero: QUIT Il numero era 3466
C:\programmi>mastermind 3466 inserire numero: 3456
nere: 3, bianche: 0 inserire numero: 3466 nere: 4, bianche: 0 Indovinato!
[0] questo 2 [1] file 0 [2] serve 0 [3] per 2 [4] provare 2 [5] programma 0 [6] e 1
[7] la 1
[8] rispondenza 0 [9] testo 0 [10] se 1 [11] i 0
[12] programmatori 0 [13] evitarono 0 [14] soluzioni 0 [15] ornative 0 [16] anche 0 [17] non 1 [18] da 0
