Fondamenti di Informatica 1 - Compito A

Prof. Marco Gavanelli

13 Marzo 2007

Esercizio (16 punti)

Un programma in linguaggio C deve verificare se una cartina politica è colorata correttamente. Una cartina è colorata correttamente se due stati confinanti hanno colore diverso. A disposizione ci sono 4 colori, indicati con i numeri da 1 a 4.

I confini fra gli stati sono indicati in un file binario  confini.bin che contiene le seguenti informazioni

• nomestato1 (stringa di 20 caratteri, incluso il terminatore)
• nomestato2 (stringa di 20 caratteri, incluso il terminatore).

La colorazione è invece indicata in un file binario  nazioni.bin che contiene

• nomestato (stringa di 20 caratteri, incluso il terminatore)
• colore (int)

Il programma deve visualizzare quanti conflitti ci sono, cioè quante coppie di stati confinanti hanno lo stesso colore. Si usi il seguente algoritmo:

1. Leggere il file confini.bin, portarlo in un array e stampare il suo contenuto.
2. Leggere il file nazioni.bin e portarne il contenuto in un array. Visualizzare tramite una procedura l'array.
3. Si scriva un funzione (che verrà invocata al punto 4) che, presi in ingresso come parametri:
   • l'array creato al punto 2
   • il nome di una nazione
   ed eventualmente altri parametri, fornisca in uscita il colore associato alla nazione.
4. Si scriva una funzione che, presi in ingresso (come parametri) i due array (ed eventualmente altri parametri), restituisce il numero di conflitti. Per fare questo,
   • si scorrano gli elementi dell'array creato al punto 1;
   • per ciascun elemento dell'array (cioè per ciascuna coppia di stati confinanti), si controlli se i due stati hanno lo stesso colore. Per fare questo, si utilizzi la funzione definita al punto 3.
5. Infine, si stampi il numero di conflitti.

Facoltativo (Punti 3)

Si cerchi di ridurre il numero di conflitti, eseguendo 1000 volte il seguente ciclo:

• si seleziona una coppia di valori che è in conflitto
• si assegni ad una delle due variabili (a scelta dello studente) un numero a caso compreso fra 1 e 4. Si usi la formula
  C = rand()*4/RAND_MAX+1

( rand() e RAND_MAX sono definiti in stdlib.h, si veda l'help di Visual Studio).

Infine, si mostri il numero di conflitti minimo trovato nelle 1000 iterazioni.