.dsy:it. - Progetto Febbraio

Pages (8): « First ... « 4 5 6 7 [8]
Show 150 posts per page

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

Posted by CowBoy on 25-02-2011 12:03:

NUOVO AVVISO: http://lonati.dsi.unimi.it/algo/1011/?page=avvisi

25 febbraio 2011
A proposito della operazione "coppie_separate", nella traccia si richiede di individuare un'insieme massimale di coppie e si specifica, nel caso in cui esista più di un insieme massimale, di scegliere quello con discrepanza complessiva minore. Ci siamo accorti che quest ultimo vincolo (introdotto per rendere la soluzione unica) rende in realtà il problema molto più complesso! Pertanto correggiamo la specifica: non si deve considerare il vincolo sulla disparità, ovvero basta trovare uno qualsiasi degli insiemi massimali di coppie. Nell'esempio 4, quindi, sono accettabili entrambi gli insiemi citati.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by CowBoy on 25-02-2011 12:20:

Originally posted by Magio
per le stanze si usa un dfs, ma per coppie separate voi cosa volete/pensate du usare?

Ci sono alcuni casi dove DFS non ti da risultati oppure te ne da troppi rispetto alla soluzione globale, fate attenzione ai grafi non connessi.

Il problema delle coppie assomiglia un po al problema della sotto stringa massima. Se volete provate a ragionarci su, dando alle popolate il simbolo del benefattore collegato, creando così due vettori("benefattori" e "popolane con benefattore") di records o di puntatori a intero...

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by Magio on 25-02-2011 22:09:

Piu che un lcs che non credo funzioni molto cè il problema del matrimonio stabile che credo opportunamente modificato sia più utile ma nemmeno qui sò se sia una buona idea

Posted by darkman13 on 16-03-2011 19:44:

Ciao, qualcuno potrebbe postare il progetto risolto, grazie!

Posted by picchio on 20-05-2011 13:10:

Alcune dritte sul progetto Febbraio

Originally posted by Chobeat
io adesso sono riuscito a fare tutto con gli alberi rb, l'unico problema è che non si porta dietro le info del nodo ma solo la key. sarà qualche problema di puntatori.

Parlando col Prof. sembra che la scelta dell' albero RB come str. dati di base per contenere i vari invitati sia quella più giusta, anche se dice che in generale andavano bene anche le tab. HASH. Per quanto riguarda invece l' ordinamento, anzichè convertire la stringa in un numero con la funz. che Cowboy suggerisce (che peraltro funziona alla grande!) si poteva secondo il Prof. semplicemente usare la funz. di libreria "strcmp". Dice che essa introduce un ordinamento di tipo lessicografico, sufficiente per avere un albero RB ...Non so voi, ma io non ci sarei mai arrivato ... Per quanto riguarda invece l' ultimo quesito "coppie" ebbene la migliore str. dati era il grafo bipartito, poichè il testo chiede la "coppia" che massimizza ... Sul Cormen (ed1) ho visto che c'è proprio un paragrafo che tratta dell' argomento 27.3 "Abbinamento massimo in un grafo bipartito". Anche su questo non ci sarei mai arrivato...del resto non so se Torelli abbia mai spiegato i grafi bipartiti ?!

All times are GMT. The time now is 21:28.

Pages (8): « First ... « 4 5 6 7 [8]
Show all 110 posts from this thread on one page