 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
progetto csi
Clicca QUI per vedere il messaggio nel forum |
| gionavisi |
| qualcuno ha idea come risolvere la funzione sul massimo? |
| pintu |
| dipende da come hai implementato il tutto e da qali strutture dati hai usato! |
| gionavisi |
| ho usato un grafo e un albero. |
| pintu |
| Ora non ho il testo davanti..ma se usi le liste di adiacenza potrebbe bastarti trovare la lista più lunga! |
| gionavisi |
| ma devo trovare il massimo di persone presenti sulla scena contemporaneamente |
| zack1988 |
| Se hai usato un grafo dove come vertici hai le persone e nelle liste di adiacenza le persone che incontri allora, il massimo sarà la persona con la lista di adiacenza più grande. |
| _X_clear |
| anch'io non so come fare questa funzione.... zack1988 la tua risposta è sbagliata perche se A ha la lista di adiacenza piu lunga e incontra B C D non è detto che però B e D si siano incontrati, quindi non si trovano contemporaneamente sulla scena del crimine. A puo avere la lista di adiacenza piu lunga, ma se B non incontra nè C nè D, C non incontra nè B nè D e D non incontra nè B nè C allora ci sono al massimo due presenze sulla scena del crimine. Se ci fossero E F G con E che incontra F e G, F incontra E e G, e G incontra E e F, questi tre elementi hanno la lista di adiacenza piu corta di quella di A ma si incontrano tutti e tre quindi la funzione massimo restituirà 3. |
| fra85 |
| io sto implementando il codice per l'appello di febbraio,e ho usato un grafo in cui inserisco le precedenze. Anche io non sto riuscendo a trovare la soluzione per il massimo... |
| bramar |
Originally posted by fra85
io sto implementando il codice per l'appello di febbraio,e ho usato un grafo in cui inserisco le precedenze. Anche io non sto riuscendo a trovare la soluzione per il massimo...
per la soluzione del massimo non basta vedere quante stanze al massimo vengono utilizzate? |
| _X_clear |
Originally posted by bramar
per la soluzione del massimo non basta vedere quante stanze al massimo vengono utilizzate?
Mi sembra di no... guarda il mio esempio sopra... le stanze che puoi fare sono A E, B F, C G, D.... che sono 4 stanze... mentre massimo deve restituire 3... se c'è un metodo di far le stanze in modo che siano 3 come la funzione massimo, fammi un esempio x favore, perchè magari la tua idea può essere giusta!!! |
| _X_clear |
Originally posted by _X_clear
Mi sembra di no... guarda il mio esempio sopra... le stanze che puoi fare sono A E, B F, C G, D.... che sono 4 stanze... mentre massimo deve restituire 3... se c'è un metodo di far le stanze in modo che siano 3 come la funzione massimo, fammi un esempio x favore, perchè magari la tua idea può essere giusta!!!
però ora che ci penso le stanze possono essere A E, B D F, C G... quindi 3... come la funzione massimo... la tua idea potrebbe essere giusta... bisogna provare altri testimoni per vedere se funziona in tutti i casi!!!! |
| bramar |
Originally posted by _X_clear
però ora che ci penso le stanze possono essere A E, B D F, C G... quindi 3... come la funzione massimo... la tua idea potrebbe essere giusta... bisogna provare altri testimoni per vedere se funziona in tutti i casi!!!!
esatto bisogna capire se ci sono casi che non abbiamo valutato...
io sto facendo i test su carta ed fogli di calcolo e non mi viene altra soluzione che quella... :( |
| _X_clear |
| entro lunedi provo a eseminare altri casi... speriamo che sia la soluzione giusta perchè altrimenti non so più dove sbattere la testa!!! se la soluzione è esatta, basta solo capire in che modo comporre le camere!!! |
| pintu |
Potrebbe essere giusto... Io ho fatto questo esempio...
nodi | lista di adiacenza
A | B - C - D - E - F
B | A - D
C | A
D | A - B
E | A
F | A
G | H - I - L
H | G - I - L
I | G - H - L
L | G - H - I
Il massimo in questo esempio è 4 (G-H-I-L è la sequenza più lunga di presenze contemporanee). Se proviamo a dividere in stanze una soluzione possibile è questa..
1 2 3 4
AG , EFCDH , BI , L
Quindi 4 come il massimo. Se poi guardiamo questi 4 sottoinsiemi si può notare che..
Almeno un elemento dell'insieme 1 si è incontrato con uno dell'insieme 2. Almeno un elemento dell'insieme 2 si è incontrato con uno dell'insieme 3. E cosi via..Si crea quindi una sequenza di presenze contemporanee..Ho provato altri esempi e sembra funzionare sempre! Quindi penso che hai avuto l'intuizione giusta bramar! L'unica cosa che non mi è chiara...perchè fare due funzioni che alla fine fanno quasi la stessa cosa? Boooo |
| panzone |
Originally posted by _X_clear
però ora che ci penso le stanze possono essere A E, B D F, C G... quindi 3... come la funzione massimo... la tua idea potrebbe essere giusta... bisogna provare altri testimoni per vedere se funziona in tutti i casi!!!!
Deve funzionare per tutti i casi, ed è facilmente dimostrabile.
interrogatori afferma che bisogna suddividerli nel minor numero di stanze possibili affinchè le persone di una stanza non abbiano incontrato gli altri. Se supponiamo un massimo di 3, significa che al massimo 3 persone si son incontrate contemporaneamente, ergo devo avere almeno 3 stanze diverse per l' interrogatorio.
Visto che abbiamo bisogno del numero MINIMO di stanze, questo valore è dunque 3. Come massimo. |
| bramar |
Originally posted by panzone
Deve funzionare per tutti i casi, ed è facilmente dimostrabile.
interrogatori afferma che bisogna suddividerli nel minor numero di stanze possibili affinchè le persone di una stanza non abbiano incontrato gli altri. Se supponiamo un massimo di 3, significa che al massimo 3 persone si son incontrate contemporaneamente, ergo devo avere almeno 3 stanze diverse per l' interrogatorio.
Visto che abbiamo bisogno del numero MINIMO di stanze, questo valore è dunque 3. Come massimo.
ok quindi la mia intuizione va bene ma come va implementata per me è ancora un punto interrogativo... |
| _X_clear |
| invece idee sull'implementazione di tempo_deserta qualche idea? |
| yeats84 |
| io son sempre bloccat su interrogatori..anche a me era venuta l'idea della funzione massimo, però bho..qualche idea?! |
| _X_clear |
| bisogna usare un algoritmo di greedy... |
| miccio.87 |
ciao a tutti, ma per implementare il grafo come avete fatto?
io non riesco a trovare molto a riguardo... |
| yeats84 |
Originally posted by _X_clear
bisogna usare un algoritmo di greedy...
si fin li c'ero, è che nn riesco a capire come stampare le persone nn incontrate da quelle divise nelle stanze..è un doppio greedy inverso? |
| _X_clear |
| quelle che non stampi le salvi su una struttura d'appoggio... poi ripete il procedimento che hai usato per stampare la prima stanza |
| yeats84 |
Originally posted by _X_clear
quelle che non stampi le salvi su una struttura d'appoggio... poi ripete il procedimento che hai usato per stampare la prima stanza
puoi spiegarmi meglio? anche in pvt se vuoi uff, nn ne vengo a capo |
| _X_clear |
| guarda praticamente io l ho fatta cosi. fai la funzione lunghezza, poi ti salvi quelli che non stampi in una struttura d'appoggio, poi riesegui la funzione lunghezza sui testimoni rimanenti, fino a quando non li hai stampati tutti... però ho dei problemi anche io su questa funzione e non vorrei che non fosse corretta, la mia è solo un idea!!! |
| pisto890 |
| la consegna del progetto è alla mezzanotte di oggi, 23 gennaio , o di domani? grazie a chiunque per la risp!! :) |
| _X_clear |
è domani!!!
io ho un dubbio sull'output!!
se come comandi di input do:
L f1.txt
t
m
l
l'output deve essere:
11:25
3
elena henry iole francesca giorgio davide
oppure:
11:25
3
elena henry iole francesca giorgio davide
ovvero ci deve essere un riga bianca tra un output e l altro o basta andare a capo?? |
| AleOver |
Originally posted by _X_clear
guarda praticamente io l ho fatta cosi. fai la funzione lunghezza, poi ti salvi quelli che non stampi in una struttura d'appoggio, poi riesegui la funzione lunghezza sui testimoni rimanenti, fino a quando non li hai stampati tutti... però ho dei problemi anche io su questa funzione e non vorrei che non fosse corretta, la mia è solo un idea!!!
cosa intendi per funzione lunghezza? e per quelli che non stampi? anche io sono in alto mare, xchè sia tempo_deserta che interrogatori nn riesco a capire.. |
| asvi |
qualcuno invece ha delle dritte su come fare banda() ?
Io non riesco a venirne a capo... :( |
| pintu |
| Devi fare una visita in profondità del grafo. |
| asvi |
| Intendi del grafo delle precedenze o di un altro grafo creato a supporto, ad esempio contenente gli incontri? |
| pintu |
Il grafo che contiene i testimoni e le rispettive liste di adiacenza. Visiti un nodo.
Se non è già stato marcato, marcalo.
Ripeti la visita sul figlio sinistro.
Ripeti la visita sul figlio destro. |
| panzone |
Originally posted by asvi
Intendi del grafo delle precedenze o di un altro grafo creato a supporto, ad esempio contenente gli incontri?
Io l' ho implementato tramite un grafo non orientato basato sugli incontri. Poi si tratta semplicemente di ricavare l' eventuale sottografo ( parti dal primo, esplori i suoi nodi ed esplori i loro figli ( evitando ovviamente ripetizioni ) e cosi via.
Originally posted by pintu
Il grafo che contiene i testimoni e le rispettive liste di adiacenza. Visiti un nodo.
Se non è già stato marcato, marcalo.
Ripeti la visita sul figlio sinistro.
Ripeti la visita sul figlio destro.
Questo però da per scontato che un nodo ha al massimo 2 archi, non per forza vero. |
| pintu |
Scusa ho sbagliato. La visita va ripetuta su ogni nodo della lista di adiacenza non sui figli destro e sinistro!
Visito un nodo.
Se non è stato marcato, lo marco.
For x appartenente alla lista di adiacenza del nodo:
se il nodo non è marcato marcalo.
ripeti visita su x. |
| asvi |
Ok dubbio chiarito, grazie.
In sostanza, tramite una visita sul grafo degli incontri si determina la componente connessa di cui fa parte y, e quella è la sua banda.
Many thanks |
| pintu |
| Qualcuno sa dov'è l'aula 4 in comelico? |
| asvi |
Ciao a tutti ;)
Mancano 13 ore al termine di consegna del progetto e come volevasi dimostrare devo ancora finirlo... :shock:
Mi manca solo massimo(), ma gli algoritmi che trovo per calcolare il massimo determinando la cricca massima del grafo incontri sono assurdamente difficili, mi ci vorrebbero dei giorni per implementarli...
Qualcuno ha trovato un modo per risolvere il problema più facilmente? |
|
|
|
|
