[C]Progetto algoritmi "Bunga-Bunga"

[matteo.pata]

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.

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




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 eettivi tratti sici della persona.


1.2 Evento: estromissione di una persona





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




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 dierenze in modulo fra i rispettivi campi (il peso è il fattore di importanza del
rispettivo campo):




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...

[dojolab]

Se studi all'Insubria e questo è un progetto del Prof. di ALgoritmi e Strutture dati (per privacy non faccio il nome) lo sto stimando troppo!

[gugoXX]

L'aiuto si puo' dare a chi deve correggere deglio errori o chiede cose specifiche.
Quindi non so quanto aiuto troverai qui.

Detto questo, chi ha inventato il testo e' davvero spiritoso.

[Tommo]

Chi è il genio della sottigliezza che ha creato questo testo

Cmq non si fanno compiti, too bad

[matteo.pata]

Ragazzi non vhiedo la soluzione (anche se sarebbe comoda)...chiedo solo unp o' di aiuto nel scegliere la struttura dati da utilizzare tutto qua....

Si faccio l'università a Varese...

[dojolab]

Originariamente inviato da matteo.pata

Si faccio l'università a Varese...

Sto stimando il Docente. .
Avessi avuto io questo compito ci avrei messo 100 volte l'impegno

[matteo.pata]

up

[bobbytre]

Originariamente inviato da matteo.pata

up

se non posti prima una tua soluzione , indicando dove non riesci ad andare avanti nessuno ti potrà dare una mano...

[matteo.pata]

VA bene ragazzi io ho provato a mettere giù qualcosa su carta. Ho pensato ad alberi per ogni ogni giorno della settimana e in più avevo pensato di fare due alberi uno per gli uomini e uno per le donne quindi in totale 14 alberi.
Il mio problema sta nel fatto di come inserire gli uomini e le donne negli alberi.
Nel senso....quale chiave uso per ordinarli?
La mia idea sta in piedi oppure per niente.
L'idea di avere alberi per ogni giorno della settimana è interessante oppure sono fuori strada?

Grazie per le risposte..

[matteo.pata]

up....dai ragazzi qualche anima pia che mi da una mano per favore

[matteo.pata]

UP

[matteo.pata]

UP ragazzi nessuno riesce a darmi una mano...

[radeon_snorky]

scusa la domanda... ma l'affinità M-F deve essere perfetta?
cioè il bungabunga avviene solo tra M-F perfettamente affini?
il bungabunga avviene sempre?
più volte in una cena?
un M dona solo una volta a cena?
una F si "dona" solo una volta a cena?
se tra M-F c'è affinità di caratteri ma la richiesta di F è minore si concretizza il bungabunga?

da meditare...

propenderei un approccio fuzzy.... o meglio fucky!

[xura]

ciao, voi come fareste per la parte delle coppie, tipo, se ho 7 coppie:
{ (u1, d1); (u1, d3); (u2,d3); (u4,d2); (u4,d5); (u3, d4); (u5,d4) }

come faccio a dividerle nel massimo numero di gruppetti, in modo che tutte le coppie si trovino insieme ???

ottenendo quindi 3 gruppetti:

{ u1; u2; d1; d3 }, { u4; d2 ; d5 } e { u3; u5; d4 }

grazie dell'aiuto !!

[goldorak]

Originariamente inviato da xura

ciao, voi come fareste per la parte delle coppie, tipo, se ho 7 coppie:
{ (u1, d1); (u1, d3); (u2,d3); (u4,d2); (u4,d5); (u3, d4); (u5,d4) }

come faccio a dividerle nel massimo numero di gruppetti, in modo che tutte le coppie si trovino insieme ???

ottenendo quindi 3 gruppetti:

{ u1; u2; d1; d3 }, { u4; d2 ; d5 } e { u3; u5; d4 }

grazie dell'aiuto !!

Usa un classico algoritmo di union-find.

[xura]

non avendo fatto nessun algo union find - ne fuzzy l'unica cosa che mi viene in mente sarebbe di utilizzare i grafi e calcolare le componenti connesse... ma forse è troppo...
grazie di eventuali suggerimenti !

[goldorak]

Originariamente inviato da xura

non avendo fatto nessun algo union find - ne fuzzy l'unica cosa che mi viene in mente sarebbe di utilizzare i grafi e calcolare le componenti connesse... ma forse è troppo...
grazie di eventuali suggerimenti !

Union Find : http://en.wikipedia.org/wiki/Union_find

Come punto di partenza puo' andare. Poi qualsiasi libro di algoritmi ha un capitolo dedicato agli algoritmi di union find.

E qui grazie a un po' di google-fu ha una pagina in italiano con tanti riferimenti agli algoritmi di union find.

http://www.google.it/search?hl=it&so...i=g10&aql=&oq=

Per risolvere il tuo problema non servono tecniche fuzzy o fare affidamento a grafi. Basta un semplice, e ripeto semplice algoritmo union find.

[matteo.pata]

qualche altra soluzione oltre all'algoritmo union find per raggruppare le coppie??
come sarebbe meglio gestirli le persone??

[Darecon]

Originariamente inviato da matteo.pata

qualche altra soluzione oltre all'algoritmo union find per raggruppare le coppie??
come sarebbe meglio gestirli le persone??

Perche' non va bene union find? Massazza l'ha sempre spiegato, quindi se la tua finalità e' passare l'esame non vedo perche' non usarlo.. Puo' anche essere usato con un solo array e/o con la compressione dei cammini..

[matteo.pata]

Originariamente inviato da Darecon

Perche' non va bene union find? Massazza l'ha sempre spiegato, quindi se la tua finalità e' passare l'esame non vedo perche' non usarlo.. Puo' anche essere usato con un solo array e/o con la compressione dei cammini..

Dicevo che va bene l'union find però volevo capire dove e come memorizzare le persone che struttura dati utilizzare.