Algoritmi e Programmazione Avanzata
Compito di programmazione – 19 settembre 2007
Tempo: 90 minuti, è possibile consultare libri o appunti.
A un incontro di speed-dating partecipano N persone di sesso maschile e altrettante persone di sesso femminile. Dopo essersi incontrati gli uni con gli altri, ognuno (maschi e femmine) esprime le proprie preferenze specificando un ordinamento delle persone del sesso opposto. In ciascun ordinamento, la persona che appare in una posizione è da preferire a quelli che si trovano in posizioni successive. I partecipanti desiderano quindi essere abbinati al meglio delle loro preferenze in modo cioè che l'abbinamento tra le N coppie sia perfetto, ovvero abbini tutti i partecipanti, e stabile rispetto agli ordinamenti delle preferenze.
Un abbinamento è stabile se non esistono due coppie, (a,b) e (c,d), le cui preferenze si incrociano: il cliente a preferisce la cliente d a b, mentre la cliente d preferisce il cliente a a c. In tale caso è molto probabile che a e c si separino da b e d, rispettivamente, per abbinarsi tra loro.
In altri termini un abbinamento (a, b) non è stabile se
– esiste una donna d che l'uomo a preferisce alla sua attuale consorte b e
– la stessa donna d preferisce tale uomo a al proprio marito c. (viceversa per l'altro sesso)
Si scriva un programma in linguaggio C per risolvere tale problema tenendo conto che le preferenze sono espresse in un file per gli uomini “uomini.txt” ed in un altro file per le donne “donne.txt”. Il contenuto dei file è così definito:
– la prima riga indica il numero N di uomini/donne le cui preferenze sono espresse nel file;
– ogni riga successiva inizia con il nome dell'uomo/donna associato a tale riga;
– i nomi di donna/uomo riportati di seguito, e separati da spazi, corrispondono all'ordine delle preferenze.
NOTE:
Si richiede l'utilizzo dell'allocazione dinamica della memoria perché il numero N di uomini/donne clienti dell'agenzia è noto solo durante l'esecuzione del programma.
Il programma deve saper riconoscere il caso in cui non esiste nessuna soluzione, se invece esiste la soluzione, deve stamparla a video indicando per ogni riga l'accoppiamento uomo+donna.
Esempio:
“uomini.txt”
3
Antonio Barbara Cristina Monica Carlo Monica Barbara Cristina Giuseppe Monica Cristina Barbara
“donne.txt”
3
Cristina Antonio Carlo Giuseppe Monica Giuseppe Carlo Antonio Barbara Carlo Giuseppe Antonio
Accoppiando Antonio con Barbara e Carlo con Monica, risulta che Giuseppe e Cristina non è un accoppiamento stabile. L'accoppiamento corretto è invece Antonio con Cristina, Carlo con Barbara e Monica con Giuseppe.
N.B. Allo studente è richiesto di consegnare una copia dell’elaborato scritto al termine della presente prova d’esame.
Affinché lo scritto venga valutato lo studente dovrà realizzare su PC il programma funzionante ed inviare al docente (servetti@polito.it) [ ENTRO il 03.10.2007 ]:
– il codice prodotto in aula e trascritto al computer in un file .c
– una relazione con il codice sorgente del programma funzionante correttamente su cui vengono evidenziate le differenze rispetto alla versione redatta in classe (es. in rosso il codice aggiunto, barrato il codice cancellato, in blu il codice modificato) corredato da una breve descrizione della struttura del programma e dalle motivazioni per le modifiche apportate.
Nella mail specificare come oggetto la sigla del corso ed il proprio numero di matricola, nella forma: [APA-TO + matricola]. La data ed il luogo per la registrazione del voto verrà comunicata via email.
