DOCUMENTO DI PROGETTO Algoritmo matching stabile Consegna di: Stefano Ghio - S3043460 I.Descrizione Generale II.Strutture Dati III.Note IV.Funzioni in breve I.Descrizione Generale -Utilizzo del programma: Il programma si lancia da riga di comando con la sintassi: [nome_programma] [numero coppie (massimo 9)] -Funzionamento del programma: Si richiede di immettere prima i nomi delle donne e degli uomini partecipanti, quindi le loro preferenze verso ciascun altro considerando che, se il programma accetta N coppie, una preferenza N verso qualcuno significa massimo amore, una preferenza 1 significa indifferenza. Non è possibile immettere preferenze duplicate. Al termine si puo' decidere di iniziare a calcolare le coppie dando priorita' alle preferenze espresse dalle donne o dagli uomini, oppure di terminare il programma. Ovviamente questa scelta puo' portare a risultati differenti. In qualsiasi altro momento, l'unico modo di terminare il programma e' premere CTRL+C. -Funzionamento dell'algoritmo di matching: L'algoritmo puo' essere suddiviso in tre semplici passi: 1- Crea coppie casuali, nel caso la donna numero 0 con l'uomo numero 0, e così via sino alla fine. 2- Prende una donna ed un uomo (od un uomo ed una donna, a seconda di a chi si è scelto dare priorita') e controlla se preferirebbero stare assieme piuttosto che con l'attuale partner. Se si', scambia le coppie. 3-Cicla finche' almeno uno scambio e' stato fatto. Nel momento in cui non sono avvenuti piu' scambi, ossia quando e' stata raggiunta la stabilits' delle coppie, termina. II.Strutture Dati Le strutture dati utilizzate sono principalmente matrici allocate dinamicamente successivamente all'immissione iniziale del numero di coppie partecipanti. Il numero di coppie viene salvato in una variabile globale int n. Nel dettaglio si ha: char** wnames; /*nomi donne*/ char** mnames; /*nomi uomini*/ ossia vettori di stringhe, ognuna delle quali viene creata disposta ad ospitare massimo 32 caratteri, spazi inclusi. Ogni riga corrisponde ad un/a uomo/donna distinto/a. int** wpref; /*preferenze donne verso uomini*/ int** mpref; /*preferenze uomini verso donne*/ ossia matrici di preferenze numeriche, ogni riga ed ogni colonna corrispondono rispettivamente ad un uomo ed una donna distinti. La donna/uomo in posizione n e' la stessa/o in posizione n nel vettore dei nomi. In totale la matrice e' grande NxN. int** result; ossia una matrice Nx2 che ospitera' le coppie finali generate dall'algoritmo. In posizione [][0], la donna ed in posizione [][1], l'uomo. III.Note 1- Si e' scelto di limitare il numero di coppie potenzialmente partecipanti a 9 per due motivi, uno funzionale, legato all'implementazione di un controllo di input, ed uno pratico. -Motivazione funzionale: Per controllare se la preferenza immessa dall'utente sia effettivamente un numero, si utilizza la macro: #define isdigit(x) ((x) >= '0' && (x) <= '9') /*controlla se x è un numero tra 0 e 9*/ Che controlla se il carattere passato è un numero o no ritornando 1 se lo e', 0 altrimenti. Questo e' legato alla non possibilita' di bloccare l'accettazione di input da tastiera dopo la richiesta di immissione della preferenza, difatti dato che tutto l'input viene salvato in un buffer a parte, l'accettazione di piu' coppie oltre la nona, comporterebbe il controllo carattere per carattere per decidere se sia un numero o meno. E complicherebbe la successiva conversione a valore numerico da "stringa di caratteri". Questo comporta quindi che input del tipo 1, 12345, 1aaa, vengano riconosciuti come validi ed equivalenti, in questo caso, ad 1. Sostanzialmente, se il primo carattere e' un numero tra 0 e 9, va bene, tutto il resto dell'input viene scartato senza informare l'utente il quale, se al passo successivo dovesse immettere semplicemente 1 o 143 o 1bb, si vedrebbe informare della non possibilita' di immettere valori duplicati, poiche' il primo carattere effettivamente era gia' stato immesso, sempre nell'ambito del nostro esempio. -Motivazione pratica: Immettere 9x2 nomi e 9x9x2 preferenze e' lungo e frustrante. 2- I nomi sono limitati a 32 caratteri ma permettono di inserire spazi. Eventuali caratteri successivi al 32esimo vengono scartati prima del successivo input. Nel caso per aumentare la lunghezza, basta modificare #define MNL 32 /*MAX_NAME_LENGTH*/ con il valore desiderato. 3- Le preferenze sono limitate a numeri compresi tra 1 e 9, non si possono - ovviamente - inserire duplicati, ne' preferenze fuori range, ne' caratteri non numerici. 4- L'algoritmo della creazione delle coppie e' lo stesso sia che si decida di dare priorita' alle donne o agli uomini, ma ovviamente a parti invertite. Esecuzioni differenti con input identici, ma priorita' finali differenti, possono quindi portare a risultati differenti. 5- Si e' scelto di non inserire sequenze di quit prima dell'ultimo passo semplicemente perche': -Durante l'immissione di nomi qualsiasi carattere/sequenza di caratteri, anche la piu' strana, deve essere accettata. -Il programma gira da riga di comando, il quit e' quindi CTRL+C. 6- I campi di input non sono manipolabili, ed accettano sequenze potenzialmente infinite di char, quello che sta sullo schermo potrebbe non corrispondere a quello che effettivamente viene salvato dal programma, eventuali caratteri in eccesso/non validi vengono difatti scartati senza feedback - inutile - per l'utente. Inserire quindi un nome lungo piu' di MNL char, ne comporta il troncamento dopo l'MNLesimo carattere. I restanti sono buttati. IV.Funzioni in breve -void error(int ); error handler. void flushInput(void ); svuota buffer di input da stdin. void name2numw(int ); associa univocamente, nell'ambito delle donne, un numero ad ogni donna, partendo da 0, permettendo da questo di risalire al suo nome e facilitando cosi' la gestione delle donne all'interno del programma, dato che vengono rappresentate come numeri. void name2numm(int ); come sopra, ma in ambito degli uomini. char* num2name(int , char** ); permette, dato un numero ed un vettore di nomi, di risalire all'utente corrispondente al numero. void getWpref(int ); raccoglie le preferenze di ogni donna verso ogni uomo. void getMpref(int ); come sopra ma per gli uomini verso le donne. void chooseMatch(int ); consente di scegliere a chi dare la priorita' nel calcolo delle coppie, o di terminare il programma ed uscire. void matchw(int ); esegue il matching dando priorita' alle donne. void matchm(int ); come sopra ma dando priorita' agli uomini. void print(int ); mostra le coppie generate. int getVal(int , int , int** ) dati due indici (i,j) e la matrice delle coppie in elaborazione (result), permette di estrarne un valore, che corrisponde sostanzialmente alla persona j appartenente alla coppia i