.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Progetto Febbraio (http://www.dsy.it/forum/showthread.php?threadid=41482)

Non riesco a trovarlo...posteresti il link?

Ciao a tutti, ho una domanda da fare in merito alla funzione Festa. Il dubbio è su come vengono formati i gruppi: secondo quale calcolo/criterio un senatore riesce a soddisfare due o più donne? Oppure come può una donna essere soddisfatta da più uomini?

Perché tutto sarebbe lineare e chiaro se ogni uomo sceglie una SOLA donna.

quella è la funzione per il 28 febbraio.

In realtà è molto più facile così se ragioni come abbiamo fatto noi. L'idea è di avere le n triple (uomo, donna, affinità) con l'affinità migliore e da queste costruire un grafo. Fatto questo, fai un algoritmo che si gira tutti i gruppetti del grafo e vede come stanno raggruppati.

scusami non mi è ancora chiaro ... la funzione festa (giorno, n) fa parte delle funzioni da implementare x entrambi gli appelli.
Nel testo si legge testualmente:

"La filantropia talvolta puo richiedere una certa privacy e quindi benefattore e beneciata si appartano,
ma non necessariamente a coppie. Infatti, secondo la regola descritta, puo benissimo succedere che un
senatore (particolarmente generoso) aiuti piu di una popolana, o che una popolana (particolarmente in
dicolta) si faccia aiutare da piu di un benefattore."

Dunque quel che ho capito io è questo: io devo trovare per ogni senatore qual'è la donna più affine a lui. Da questa cosa risulterebbe che ogni uomo sceglie solo una donna ma può capitare che due uomini scelgano la stessa donna (in quanto è la più affine per entrambi). Fin qui mi sembra ok. Il problema nasce dall'esempio che riporta la prof nel testo. Infatti si vede che Tarquinio è in coppia sia con Tullia che con Messalina!! Come può essere possibile?

perché un uomo si sceglie tutte le donne che vuole ("puo benissimo succedere che un
senatore (particolarmente generoso) aiuti piu di una popolana"

però a questo punto se un senatore si sceglie tutte le donne che vuole si avrebbe che io in modo arbitrario dico che il senatore1 si sceglie 3 donne, il senatore2 ne sceglie 4 ecc... Così facendo avrei un output che non coinciderebbe più con quello fornito dalla prof. Infatti nel progetto non c'è nessuna funzione che definisca quante donne vengono scelte da ciascun senatore. Non so se mi sono spiegato bene ...

Sto leggendo l'implementazione dell'RB-tree dall'algoteam, e mi sono inbattuto in questo prototipo:

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))

che parametro sarebbe "void (*op)(rbnode *)"??? è la prima volta che leggo una cosa del genere

puntatore a funzione,e quella funzione punta a void .... ha "spiegato" ste robe l'ultimo giorno di lezione....
scusa se non ti scrivo di più ma non è molto chiaro nemmeno a me...

allora avevo ragione...

Modifico la domanda...
Per fare festa vi scorrete tutto l'albero tenendo già conto del giorno e salvate le affinità migliori?
Grazie.

io salvo tutte le affinità in un albero binario(quindi ordinato) e poi prendo le N migliori con cui costruisco il grafo.

Si idem, però una volta che hai le affinità migliori per festa non basta? Poi si fanno dei calcoli per stanze etc, no? Il grafo è per festa?

Originally posted by figo1987
salve qualcuno ha pensato alla complessità della funzione festa? io non riesco a scendere sotto a O(n^2)...

si pero' non funziona ancora bene... forse c'è un errore se poi funziona vi dico...

E come hai fatto a scendere sotto O(n^2)? la lista di uscita del bfs dove l'hai memorizzata?