matteo.pata
24-01-2011, 21:16
Buonasera a tutti ragazzi,
sono alle prese con il mio progetto di algoritmi per l'università.
E' il terzo che cerco di fare i primi due non sono andati nel senso che non sono mai riuscito a consegnare purtroppo.
Le mie conoscenze del C sono molto basse e in più non sono molto ferrato lo ammetto senza nessun problema.
Sono qui a chiedervi una mano a tutti per poter consegnare con il vostro aiuto il progetto.
Vi posto le specifiche con la speranza che voi con la vostra capacità di programmatori riusciate a portarmi sulla strada giusta per utilizzare la miglior struttura dati e che non sia troppo complicata.;) :help:
SPECIFICHE:
Bisogna scrivere un programma che legga da un le una sequenza di eventi, come l'introduzione di una
nuova persona nel gruppo delle cene, l'estromissione dallo stesso gruppo di elementi caduti in disgrazia, o
l'indizione di una cena nella villa del presidente. Per alcuni eventi, il programma deve produrre in output
alcuni dati statistici (vedi sotto).
Nel seguito compare una descrizione dei tre tipi di evento, compreso il modo in cui vengono codi cati nel file di input.
1.1 Evento: introduzione di una persona
http://img820.imageshack.us/img820/654/cattura3h.jpg (http://img820.imageshack.us/i/cattura3h.jpg/)
Il campo presenze è una stringa, costruita sull'alfabeto fL,M,E,G,V,S,Dg, che descrive i giorni della
settimana nei quali il nuovo arrivato o la nuova arrivata è disponibile per le cene (ogni settimana). I giorni della settimana da Lunedì a Domenica sono rappresentati rispettivamente dalle lettere maiuscole
L,M,E,G,V,S,D (mErcoledì dalla lettera E).
Se il nuovo arrivato è un uomo, allora si tratta di un membro del governo o di altra persona entrata
nelle simpatie del presidente. In questo caso, il dato denaro rappresenta la somma massima che questa
persona può corrispondere a una persona che bene cia della sua disinteressata generosità (in una singola
operazione di donazione), mentre i campi da età a costituzione non si riferiscono ai suoi tratti sici ma
rappresentano i tratti che tendono a stimolare in lui istinti lantropici. Ad esempio, se età vale 17,
signi ca che il membro dell'entourage presidenziale in questione si prende particolarmente a cuore i casi
dei cittadini di 17 anni di età.
Se il nuovo arrivato è di sesso femminile, allora è una giovane (o giovanissima) donna che è stata indivi-
duata tramite appositi meccanismi come bisognosa ed è ammessa a partecipare alle cene. In questo caso,
il campo denaro rappresenta l'entità monetaria del bisogno, e i campi da età a costituzione rappresentano
gli e ettivi tratti sici della persona.
1.2 Evento: estromissione di una persona
http://img248.imageshack.us/img248/3087/catturajr.jpg (http://img248.imageshack.us/i/catturajr.jpg/)
La persona che esce dal giro può essere un uomo o una donna. Non parteciperà più a nessuna cena del
presidente (gli uomini, perchè caduti in disgrazia - ad es. per tradimento; le donne, di solito, per perdita
dei requisiti).
1.3 Evento: cena sociale
http://img256.imageshack.us/img256/7715/cattura1s.jpg (http://img256.imageshack.us/i/cattura1s.jpg/)
Dopo la cena svoltasi nel giorno speci cato, vengono scambiate fra i partecipanti <n> somme di denaro:
per <n> volte, si trova la coppia più affine di sesso opposto (che ancora non abbia interagito in questo bun-
gabunga) i cui membri siano entrambe presenti il giorno speci cato. L'uomo scelto aiuta economicamente
la ragazza scelta.
Come si può facilmente immaginare, la lantropia richiede di solito una certa privacy e quindi benefattore e bene ciata si appartano, ma non necessariamente a coppie. Infatti, secondo la regola descritta,
può benissimo succedere che un uomo (particolarmente generoso) bene ci più di un concittadino, o che
un concittadino (particolarmente in difficoltà) si faccia aiutare da più di un benefattore. Quello che
succede è che la comitiva si divide nel massimo numero di gruppetti, in modo che tutte le coppie bene-
fattore/bene ciato si trovino insieme. Ad esempio, se bungabunga G 7 calcola l'insieme delle 7 coppie
più affini presenti di giovedì, poniamo {(u1; d1); (u1; d3); (u2; d3); (u4; d2); (u4; d5); (u3; d4); (u5; d4)}, i tre
gruppetti {u1; u2; d1; d3}, {u4; d2; d5} e {u3; u5; d4} si apparteranno in tre stanze separate.
In risposta a questo evento, il programma dovràstampare in output una riga con tre numeri: il numero
di gruppi che vengono a formarsi e il numero di benefattori (uomini) e bene ciate (donne) presenti nel
gruppo piu' numeroso (in caso di parita', quello con piu' uomini), nell'esempio in questione, (3; 2; 2).
Nota: ci saranno di solito anche partecipanti alla cena di entrambi i sessi che non partecipano a nessuno
scambio di denaro; queste persone, durante il bungabunga in oggetto, rimangono a tavola e non vanno
conteggiate in nessun gruppo.
1.3.1 Determinare l'affinità di una coppia
Il grado di affinità di una coppia è quanti cabile con un numero reale che dipende dalla somiglianza, fra
i due, dei valori dei campi da denaro a costituzione (compresi). Speci catamente, sarà un valore dato
dalla somma pesata delle di erenze in modulo fra i rispettivi campi (il peso è il fattore di importanza del
rispettivo campo):
http://img146.imageshack.us/img146/9201/cattura2f.jpg (http://img146.imageshack.us/i/cattura2f.jpg/)
Gli eventuali casi di parità fra i gradi di affinità di due coppie si possono dirimere in maniera arbitraria.
2 Il progetto da consegnare
2.1 Input e Output
Il programma deve prendere dalla riga di comando il nome del le di input (un le di testo contente
un comando per riga). Deve scrivere in risposta, nello standard output, una riga per ogni evento di
bungabunga, come descritto sopra.
2.2 Altri vincoli
La correttezza delle soluzioni è un requisito necessario. Un progetto sarà considerato più o meno valido
rispetto all'efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti.
La s da consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze più complesse
possibili.
2.3 Dimensioni delle tipiche istanze del problema
La classe politica della Repubblica di Bananas (nella lingua locale: la \cricca") si sta velocemente espan-
dendo, per poter sempre meglio servire i propri cittadini. Si prevede che la pratica del bungabunga andrà
consolidandosi del pari, arrivando a coinvolgere un numero sempre maggiore di persone. Per il 2020, non
saranno forse infrequenti giri di migliaia di persone ospitate settimanalmente o forse anche più.
Ringrazio tutti in anticipo per l'aiuto che sono sicuro riuscirete a darmi...:help: :help: :help:
sono alle prese con il mio progetto di algoritmi per l'università.
E' il terzo che cerco di fare i primi due non sono andati nel senso che non sono mai riuscito a consegnare purtroppo.
Le mie conoscenze del C sono molto basse e in più non sono molto ferrato lo ammetto senza nessun problema.
Sono qui a chiedervi una mano a tutti per poter consegnare con il vostro aiuto il progetto.
Vi posto le specifiche con la speranza che voi con la vostra capacità di programmatori riusciate a portarmi sulla strada giusta per utilizzare la miglior struttura dati e che non sia troppo complicata.;) :help:
SPECIFICHE:
Bisogna scrivere un programma che legga da un le una sequenza di eventi, come l'introduzione di una
nuova persona nel gruppo delle cene, l'estromissione dallo stesso gruppo di elementi caduti in disgrazia, o
l'indizione di una cena nella villa del presidente. Per alcuni eventi, il programma deve produrre in output
alcuni dati statistici (vedi sotto).
Nel seguito compare una descrizione dei tre tipi di evento, compreso il modo in cui vengono codi cati nel file di input.
1.1 Evento: introduzione di una persona
http://img820.imageshack.us/img820/654/cattura3h.jpg (http://img820.imageshack.us/i/cattura3h.jpg/)
Il campo presenze è una stringa, costruita sull'alfabeto fL,M,E,G,V,S,Dg, che descrive i giorni della
settimana nei quali il nuovo arrivato o la nuova arrivata è disponibile per le cene (ogni settimana). I giorni della settimana da Lunedì a Domenica sono rappresentati rispettivamente dalle lettere maiuscole
L,M,E,G,V,S,D (mErcoledì dalla lettera E).
Se il nuovo arrivato è un uomo, allora si tratta di un membro del governo o di altra persona entrata
nelle simpatie del presidente. In questo caso, il dato denaro rappresenta la somma massima che questa
persona può corrispondere a una persona che bene cia della sua disinteressata generosità (in una singola
operazione di donazione), mentre i campi da età a costituzione non si riferiscono ai suoi tratti sici ma
rappresentano i tratti che tendono a stimolare in lui istinti lantropici. Ad esempio, se età vale 17,
signi ca che il membro dell'entourage presidenziale in questione si prende particolarmente a cuore i casi
dei cittadini di 17 anni di età.
Se il nuovo arrivato è di sesso femminile, allora è una giovane (o giovanissima) donna che è stata indivi-
duata tramite appositi meccanismi come bisognosa ed è ammessa a partecipare alle cene. In questo caso,
il campo denaro rappresenta l'entità monetaria del bisogno, e i campi da età a costituzione rappresentano
gli e ettivi tratti sici della persona.
1.2 Evento: estromissione di una persona
http://img248.imageshack.us/img248/3087/catturajr.jpg (http://img248.imageshack.us/i/catturajr.jpg/)
La persona che esce dal giro può essere un uomo o una donna. Non parteciperà più a nessuna cena del
presidente (gli uomini, perchè caduti in disgrazia - ad es. per tradimento; le donne, di solito, per perdita
dei requisiti).
1.3 Evento: cena sociale
http://img256.imageshack.us/img256/7715/cattura1s.jpg (http://img256.imageshack.us/i/cattura1s.jpg/)
Dopo la cena svoltasi nel giorno speci cato, vengono scambiate fra i partecipanti <n> somme di denaro:
per <n> volte, si trova la coppia più affine di sesso opposto (che ancora non abbia interagito in questo bun-
gabunga) i cui membri siano entrambe presenti il giorno speci cato. L'uomo scelto aiuta economicamente
la ragazza scelta.
Come si può facilmente immaginare, la lantropia richiede di solito una certa privacy e quindi benefattore e bene ciata si appartano, ma non necessariamente a coppie. Infatti, secondo la regola descritta,
può benissimo succedere che un uomo (particolarmente generoso) bene ci più di un concittadino, o che
un concittadino (particolarmente in difficoltà) si faccia aiutare da più di un benefattore. Quello che
succede è che la comitiva si divide nel massimo numero di gruppetti, in modo che tutte le coppie bene-
fattore/bene ciato si trovino insieme. Ad esempio, se bungabunga G 7 calcola l'insieme delle 7 coppie
più affini presenti di giovedì, poniamo {(u1; d1); (u1; d3); (u2; d3); (u4; d2); (u4; d5); (u3; d4); (u5; d4)}, i tre
gruppetti {u1; u2; d1; d3}, {u4; d2; d5} e {u3; u5; d4} si apparteranno in tre stanze separate.
In risposta a questo evento, il programma dovràstampare in output una riga con tre numeri: il numero
di gruppi che vengono a formarsi e il numero di benefattori (uomini) e bene ciate (donne) presenti nel
gruppo piu' numeroso (in caso di parita', quello con piu' uomini), nell'esempio in questione, (3; 2; 2).
Nota: ci saranno di solito anche partecipanti alla cena di entrambi i sessi che non partecipano a nessuno
scambio di denaro; queste persone, durante il bungabunga in oggetto, rimangono a tavola e non vanno
conteggiate in nessun gruppo.
1.3.1 Determinare l'affinità di una coppia
Il grado di affinità di una coppia è quanti cabile con un numero reale che dipende dalla somiglianza, fra
i due, dei valori dei campi da denaro a costituzione (compresi). Speci catamente, sarà un valore dato
dalla somma pesata delle di erenze in modulo fra i rispettivi campi (il peso è il fattore di importanza del
rispettivo campo):
http://img146.imageshack.us/img146/9201/cattura2f.jpg (http://img146.imageshack.us/i/cattura2f.jpg/)
Gli eventuali casi di parità fra i gradi di affinità di due coppie si possono dirimere in maniera arbitraria.
2 Il progetto da consegnare
2.1 Input e Output
Il programma deve prendere dalla riga di comando il nome del le di input (un le di testo contente
un comando per riga). Deve scrivere in risposta, nello standard output, una riga per ogni evento di
bungabunga, come descritto sopra.
2.2 Altri vincoli
La correttezza delle soluzioni è un requisito necessario. Un progetto sarà considerato più o meno valido
rispetto all'efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti.
La s da consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze più complesse
possibili.
2.3 Dimensioni delle tipiche istanze del problema
La classe politica della Repubblica di Bananas (nella lingua locale: la \cricca") si sta velocemente espan-
dendo, per poter sempre meglio servire i propri cittadini. Si prevede che la pratica del bungabunga andrà
consolidandosi del pari, arrivando a coinvolgere un numero sempre maggiore di persone. Per il 2020, non
saranno forse infrequenti giri di migliaia di persone ospitate settimanalmente o forse anche più.
Ringrazio tutti in anticipo per l'aiuto che sono sicuro riuscirete a darmi...:help: :help: :help: