.dsy:it. - Progetto Febbraio

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > Progetto Febbraio

Pages (8): « First ... « 4 5 6 7 [8]

Last Thread Next Thread

Author

Thread Expand all | Contract all

CowBoy

.arcimaestro.

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

25-02-2011 12:03

Click here to Send CowBoy a Private Message

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

Last edited by CowBoy on 25-02-2011 at 12:58

25-02-2011 12:20

Magio

.novellino.

User info:

Registered: Oct 2008
Posts: 4 (0.00 al dì)
Location: Milan
Corso: Info
Anno: 1
Time Online: 6:40:22 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

25-02-2011 22:09

Click here to Send Magio a Private Message

darkman13

.arcimaestro.

User info:

Registered: Feb 2004
Posts: 272 (0.03 al dì)
Location:
Corso:
Anno:
Time Online: 3 Days, 14:00:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Ciao, qualcuno potrebbe postare il progetto risolto, grazie!

16-03-2011 19:44

Click here to Send darkman13 a Private Message

picchio

.primate.

User info:

Registered: Dec 2007
Posts: 67 (0.01 al dì)
Location:
Corso: informatica
Anno:
Time Online: 15:46:09: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ?!

20-05-2011 13:10