 | |
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 per appello del 3 settembre
Clicca QUI per vedere il messaggio nel forum |
| johnnyd |
| Quando dovrebbe uscire? |
| Guepe |
| In teoria oggi, visto ke di solito da 2 settimane di tempo... |
| plafo |
Originally posted by Guepe
In teoria oggi, visto ke di solito da 2 settimane di tempo...
credo che il 3 settembre sia la data in cui esce il progetto, poi si hanno due settimane per farlo e consegnarlo |
| Guepe |
Originally posted by plafo
credo che il 3 settembre sia la data in cui esce il progetto, poi si hanno due settimane per farlo e consegnarlo
guardando gli appelli di settembre degli anni passati faceva uscire il progetto il giorno dell'appello al contrario degli altri appelli durante l'anno in cui anticipava di due settimane!meglio così! |
| plafo |
Originally posted by Guepe
guardando gli appelli di settembre degli anni passati faceva uscire il progetto il giorno dell'appello al contrario degli altri appelli durante l'anno in cui anticipava di due settimane!meglio così!
basta che il progetto non sia troppo complicato :) |
| ferra03 |
| ha messo un'avviso sul suo sito, il progetto verrà pubblicato il 30 agosto e dovrà essere consegnato entro il 20 settembre |
| gianni.malvasi |
| ma scusa dove hai letto l'avviso? |
| plafo |
Originally posted by gianni.malvasi
ma scusa dove hai letto l'avviso?
ho controllato anch'io il sito di aguzzoli ma non ho trovato niente :?
ferra03 puoi postare il link con l'avviso di cui parli?
grazie |
| johnnyd |
| regalo abbonamento di 2 anni a playboy a chi mi fa il progetto lol! |
| plafo |
| io continuo a non vedere nessun avviso ne sul sito di aguzzoli ne su quello di torelli... |
| plafo |
Originally posted by radyo
Ciao,
l'avviso è presente sul sito del corso della dott.sa Lonati:
http://lonati.dsi.unimi.it/algo/0910/?page=avvisi
solitamente il progetto è preparato da entrambi i docenti di lab.
ok grazie per la dritta!
certo che potevano scrivere un avviso anche per noi del serale.... |
| gianni.malvasi |
| ma ci sono problemi x aprire il sito del prof.....voi ci riuscite???? |
| plafo |
Originally posted by gianni.malvasi
ma ci sono problemi x aprire il sito del prof.....voi ci riuscite????
ciao a tutti,
qualcuno mi sa dire se è uscito veramente oggi il progetto?
purtroppo da qua non riesco ad accedere al sito del corso...
grazie! |
| gianni.malvasi |
ma dov'è???????????????????????????????
nn c'è sul sito!!!!!!!!!!!!!!! |
| lSical |
ciao, qualcuno mi potrebbe aiutare a capire come calcolare i seguenti valori?
pag. 2 es.1 B(D1)=28+20=48
- come calcola il 28?
-20 perchè calcola solo il perimetro del quadrato 5*4=20?, non considerando la componente c6 perchè sovrapposta?
pag 3 es.2 C(D1)=(....)+(4+2+3+5)=40
-non somma il costo della famiglia di c2 perchè dato che dopo non c'è un'altra componente allora non c'è costo di trasferimento?
C(D2)=(...)+(0+3)=18
-(0+3) lo ricava in questo modo?
delta(c1,c2)=0 perchè F(c1)=F(c2)
delta(c2,c3) = delta(F(c2)) = 3 perchè F(c2)!=F(c3)
poi dato che dopo c3 non c'è un'altra componente allora non c'è costo di trasferimento??
grazie dei chiarimenti! |
| gianni.malvasi |
anch'io non riesco a capire i conti.... allora...
vedendo lo scorso progetto che si parla di aree e a noi di perimetro i conti mi vengono considerando le parti sovrapposte ma sul progetto nuovo no...
cn le aree viene--> 25 + 2 + 12 + 10 = 49
cn il perimetro viene-> 20 + 6 + 14 + 14 = 54
dovrebbe venire-->20 + 28 = 48
qualcuno ci aiuta????? |
| lSical |
forse contano solo le componenti sovrapposte, quindi hai 20 di c6 e c5
mentre per le altre 3 forse non considera il segmento 2,3 3,3 (parte della componente c4) perchè non sovrapposta.?
i costi invece? |
| iron |
Per quanto riguarda il perimetro credo di aver capito, dalla figura 1 si evince che F(D) non è connessa e che è quindi formata dalle 2 sottofigure rispettivamente:
(c1,c4,c2) e (c6,c5)
in entrambi i casi le sottofigure hanno dei componenti sovrapposti pertanto nel caso di (c6,c5) notiamo che c6 è più piccolo di c5 ed è "contenuto" all'interno del perimento di c5 che è 5+5+5+5 cioè 20.
Nel caso di (c1,c4,c2) la figura che viene fuori dalla sovrapposizione è molto più irregolare e per calcolare il perimetro bisogna sommare tutti i vari lati che compongono il perimetro nel nostro caso abbiamo:
11 (base) + 1 + 2 + 2 + 4 +1 + 5 +2 = 28
vi convince? |
| SanJuanWolf89 |
| il problema è: come far fare il calcolo al computer che non "vede" la figura??? |
| gianni.malvasi |
allora...
per l'esempio1 :
D(D1)= 28 + 20 = 48
il 20 è il perimetro del componente c5 cioè--> 5+5+5+5=20
per il 28 considerate le altre figure ma attenti a contare bn cn le sovrapposizioni. Vedete le figure come un'unica figura--> per la base basta contare dal componente c4 alla fine del componente c2 quindi è 11. ovviamente è 11 + 11 che è la parte di sopra poi...il lato di sx e quello di dx è 3 visto che si sovrappongono ed è il + grande (vedi c1) alla fine...11 + 11 + 3 + 3 = 28
Esempio2:
C(D1)=(c6+c5+c1+c4+c2) + (delta) = 40
facciamo la prima c6...vedo nella tabella colonna F riga c6 ed è 7
adesso nella tabella dell'esempio 2 a 7 corrisponde delta 4...
fate gli altri e torna...l'ultimo nn lo consideriamo xkè nn ci sn + componenti dopo
C(D2)=(c1+c2+c3)+(delta)= 18
allora se vedete nella tabella c1 e c2 appartengono alla stessa famiglia quindi costo 0
mentre c3 ha costo 3 perchè nn essendoci altri componenti si vede la famiglia precedente quindi F = 3 e delta = 3
spero di essere stato chiaro... |
| Guepe |
Originally posted by iron
Per quanto riguarda il perimetro credo di aver capito, dalla figura 1 si evince che F(D) non è connessa e che è quindi formata dalle 2 sottofigure rispettivamente:
(c1,c4,c2) e (c6,c5)
in entrambi i casi le sottofigure hanno dei componenti sovrapposti pertanto nel caso di (c6,c5) notiamo che c6 è più piccolo di c5 ed è "contenuto" all'interno del perimento di c5 che è 5+5+5+5 cioè 20.
Nel caso di (c1,c4,c2) la figura che viene fuori dalla sovrapposizione è molto più irregolare e per calcolare il perimetro bisogna sommare tutti i vari lati che compongono il perimetro nel nostro caso abbiamo:
11 (base) + 1 + 2 + 2 + 4 +1 + 5 +2 = 28
vi convince?
si, è esattamente cosi, anke facendo le prove dell'input vengono i risultati! :D |
| iron |
| il problema è, come dice SanJuanWolf89, come si gestisce questa sovrapposizione...... :-/ |
| SanJuanWolf89 |
| Un altro problemino: le consegne dell'esempio 1 si ottengono facilmente con le liste... quelle successive non so ancora. Voi che strutture dati pensate di usare? |
| fxxstefano |
Qualcuno sa dirmi se l'orale del Prof. Torelli è realmente il 3 settembre o lo fa in concomitanza con quello del progetto?
Grazie in anticipo |
| zack1988 |
Originally posted by fxxstefano
Qualcuno sa dirmi se l'orale del Prof. Torelli è realmente il 3 settembre o lo fa in concomitanza con quello del progetto?
Grazie in anticipo
http://homes.dsi.unimi.it/~aguzzoli/algo.htm
l'ultimo giorno per la consegna del progetto è il 20 settembre, quindi presubilmente durante quella settimana ci saranno gli orali.
Ricordo che l'orale è diviso in due parti : esposizione del progetto con domande del Prof Aguzzoli e poi domande teoriche del Prof Torelli.
Ciao |
| gianni.malvasi |
qualcuno ha iniziato a scrivere qualcosa per il progetto???
se conoscete qualcuno che ha fatto lo scorso è molto simile...
cerchiamo di farlo o meglio di scambiarci alcune idee
io ho pensato ad alberi rb x i vari componenti voi che dite???? |
| johnnyd |
| Per questo progetto si può usare la base del vecchio componenti? |
| gianni.malvasi |
| ma le funzioni base si...tranne che nel vecchio era l'area e nel nuovo c'è il perimetro... |
| Chobeat |
voi che struttura dati state usando per la lista delle componenti?
Io per ora sono su una semplice lista linkata ma sicuramente dovrò implementare qualcosa di più complesso. Ho qualche idea ma volevo prima vedere cosa stavate facendo voi, prima di buttarmi a capofitto in roba troppo e inutilmente ottimizzata. |
| gianni.malvasi |
Io ho usato gli alberi rb per i componenti...
nn riesco a capire quando si parla di trasferimento...allora l'esempio 2 l'ho capito...ma quando vado a leggere l'output che dobbiamo inserire non capisco + nulla o meglio...
t 1 6
t 2 5
che cosa vogliono dire??
1 e 2 sono la famiglia e 6 e 5???
xkè nell'esempio si vede c1 c2 c3 ecc ma quando sono tt c???? |
| Chobeat |
Originally posted by gianni.malvasi
Io ho usato gli alberi rb per i componenti...
nn riesco a capire quando si parla di trasferimento...allora l'esempio 2 l'ho capito...ma quando vado a leggere l'output che dobbiamo inserire non capisco + nulla o meglio...
t 1 6
t 2 5
che cosa vogliono dire??
1 e 2 sono la famiglia e 6 e 5???
xkè nell'esempio si vede c1 c2 c3 ecc ma quando sono tt c????
beh se guardassi la sintassi del comando è chiaro. t f x
t è il comando
f è la famiglia
x è il costo del trasferimento.
per la seconda domanda, non ho capito.
sono tutti c perchè c è il comando.
sopratutto, se non hai capito la sintassi dei comandi, come hai fatto a tirar fuori gli alberi rb? a me non risulta vengano fatti a lezione anche se anche io li avevo presi in considerazione. |
| gianni.malvasi |
| se faccio i conti vedendo solo i vari componenti senza le varie t mi viene 27 che è il numero che deve uscire in output...quindi a che servono t 1 6 ecc ecc???? |
| gianni.malvasi |
| scusate ho sbagliato i conti....non mi viene |
| SanJuanWolf89 |
| qlkn è arrivato alla funzione prospetto??? |
| gianni.malvasi |
| prima di implementare la funzione prospetto...non capisco il costo minimo...nell'esempio 3 come faccio a dire se appartiene o meno al prospetto??? e poi quando dice che il dispositivo c2,2..c7,3..c6,1 non è realizzabile per P in quanto ecc ecc come mai viene così?? |
| SanJuanWolf89 |
| eh tu nn devi mica importare un file in cui ci sn tti i dati???..se prima nn s riesce a importare x bene i dati (parentesi escluse e stabilendo che sono la fine di ogni gruppetto) non s puo fare niente...una volta fatto poi s calcola il costominimo...e x altro i valori definiti nel file prospetto devono in qlk modo essere ricollegati a quelli gia inseriti (ad es x qnt riguarda il costo)...e quello e un casino... |
| gianni.malvasi |
| si ok hai ragione...ma prima di scriverlo in C voglio capire prima bn gli esempi del prof che nn ho capito...sia il costo minimo che il prospetto dell'esempio 3 |
| gianni.malvasi |
scusate vi pongo questa domanda...
nella funzione traferimento non riesco ad associare il valore x alla famiglia di riferimento...ho creato un albero rb per i componenti e quindi vorrei estrarre dall'albero il puntatore alla famiglia ed associargli il valore di x
aiutooooo |
| Chobeat |
Originally posted by gianni.malvasi
scusate vi pongo questa domanda...
nella funzione traferimento non riesco ad associare il valore x alla famiglia di riferimento...ho creato un albero rb per i componenti e quindi vorrei estrarre dall'albero il puntatore alla famiglia ed associargli il valore di x
aiutooooo
scelta stupida che ho fatto e cestinato per inutili complicazioni=fai una matrice bidimensionale che associa la famiglia al costo.
scelta furba che mi appresto ad implementare anche io= sfrutti sempre il codice dell'albero rb e costruisci un albero con la famiglia come chiave e il costo come valore.
quando dovrai leggero, userai sempre la funzione di ricerca ma sull'albero dedicato ai costi.
questo progetto non è difficile e ste cose mi sembrano cazzate al confronto di una cosa che non riesco a gestire: l'input.
sarò scemo io, sarà che non ho mai programmato in C ma non riesco a gestire bene i menù.
ho chiesto su qualsiasi chat, helpdesking vari, forum ma nessuno sa dirmi nè come gestire il stampa(f) nè tantomeno l' "o int1 int 2 intx"
ho appena buttato 80 righe di codice che tra while vari, gets(),fscanf() e pastrocchi vari, non riuscivano a gestirmi la chiamata alla funzione ordina().
Voi come state facendo? cioè è veramente complicato o sono io che mi son perso qualche cazzata? Praticamente la giornata oggi l'ho persa su quello. |
| gianni.malvasi |
sto impazzendo per creare la funzione trasferimento...
sto provando a fare la matrice ma non riesco e sn bloccato...
se qualcuno l'ha già fatta la posterebbe qui...
per la funzione stampa()...ho costruito un albero di ricerca per avere i componenti ordinati per costo in modo che li possa stampare con una semplice visita in ordine simmetrico |
| Chobeat |
Originally posted by gianni.malvasi
sto impazzendo per creare la funzione trasferimento...
sto provando a fare la matrice ma non riesco e sn bloccato...
se qualcuno l'ha già fatta la posterebbe qui...
per la funzione stampa()...ho costruito un albero di ricerca per avere i componenti ordinati per costo in modo che li possa stampare con una semplice visita in ordine simmetrico non capisco dove sia il problema. è un lavoro da 10 minuti se già hai le funzioni dell'albero rb. |
| gianni.malvasi |
| il problema che nn sono molto pratico del c e ho delle difficoltà... |
| Chobeat |
ma nemmeno io, ma se sei riuscito a fare l'albero rb, il trasferimento è una cazzata.
fai un albero con chiave un int che è la famiglia e come valore un int che è il costo. bon, finito lì |
| iron |
| Qualcuno ha scritto la funzione che calcola il perimetro? |
| Chobeat |
Originally posted by iron
Qualcuno ha scritto la funzione che calcola il perimetro?
Io mi sto accingendo giusto ora. Ho seri dubbi sulla struttura dati da utilizzare, infatti per oggi mi limito ad una versione con una lista contenente h, l, pos e codice.
Costruisco la lista e la ordino per posizione, così quando andrò a leggerla, sarà già apposto.
Quindi inizio dalla pos del primo nodo della lista e faccio i calcoli. Tengo alcune condizioni, leggo il secondo e con un po' di differenze, valuto i vari casi.
Mentre ci ragionavo, mi è venuta in mente una soluzione che in pratica calcola il perimetro con solo due casi, utilizzando il valore assoluto ma non sono sicuro possa funzionare. |
| iron |
Io ho messo i dati in una lista come dici tu, mettendo la posizione più bassa in testa, in modo da avere la lista ordinata per posizione.
come pensi di gestire le sottofigure non connesse? |
| Chobeat |
si può fare giocando un po' con le posizioni iniziali e le lunghezze.
ammettiamo di essere nel blocco A composto da 3 figure che si connettono e/o sovrappongono.
diciamo di avere un int che segna la posizione fin dove sono arrivato a calcolare.
quando questo puntatore va avanti, aggiungo e tolgo le figure "attive", ovvero che hanno il puntatore nell'intervallo [pos,pos+ lung].
Diciamo che siamo alla posizione 10. Se alla posizione 10 non ho figure attive, passo a guardare quella dopo. inizia a 10? si, allora son due figure affiancate e van considerate come un blocco unico. inizia dopo 10? vuol dire che c'è un buco. |
| SanJuanWolf89 |
| qlkn ha implementato la funzione prospetto e ha capito come cacchio si leggono le parentesi cm fine carattere...e una cavolata ma proprio nn m viene.. |
| iron |
| In che struttura dati metterai il prospetto? |
| SanJuanWolf89 |
allora io ho implementato un albero rb x la funzione c
e poi x qnt riguarda il prospetto pensavo a una lista ordinata...il problema xo e cm inserire i dati dal file:S |
| Jaio |
Ciao a tutti!! Per quanto riguarda la funzione b, qualcuno sa se i componenti sovrapposti sono sempre uno in fila all'altro fino ad arrivare ai componenti che formano una figura scollegata, oppure possono anche essere in posizioni casuali? Che io, per adesso, sono riuscito a implementare b solo per calcolare il perimetro di componenti sovrapposti con if else innestati che valutano i tre casi possibili dei componenti... Ma questo funziona solo se i componenti che formano una figura sono uno in fila all'altro:sad:
P.S. scusate l'italiano ma sono sul progetto dalle 10 di stamattina e connetto moooooolto poco:D |
| Chobeat |
Originally posted by Jaio
Ciao a tutti!! Per quanto riguarda la funzione b, qualcuno sa se i componenti sovrapposti sono sempre uno in fila all'altro fino ad arrivare ai componenti che formano una figura scollegata, oppure possono anche essere in posizioni casuali? Che io, per adesso, sono riuscito a implementare b solo per calcolare il perimetro di componenti sovrapposti con if else innestati che valutano i tre casi possibili dei componenti... Ma questo funziona solo se i componenti che formano una figura sono uno in fila all'altro:sad:
P.S. scusate l'italiano ma sono sul progetto dalle 10 di stamattina e connetto moooooolto poco:D
mi sa che non basta. le componenti probabilmente verranno testate con un generatore random e possono essere ovunque con qualsiasi altezza e larghezza. sennò è troppo facile XD.
io comunque sto elaborando un sistema ricorsivo, qualsiasi altra soluzione mi sembra insensata o non funzionante.
io per il prospetto ho usato una lista di liste. ho fatto un po' di test farlocchi perchè finchè non finisco bordo() non posso passare a costominimo che deve leggerci sopra. in teoria va abbastanza sciolto.
@Jaio e Iron, che sembrate due apposto, mi aggiungete su msn o organizziamo una wave per scambiarci un po' di pareri sulle scelte? io sono molto dubbioso su alcune cose e volevo vedere come avevate proceduto voi. |
| Jaio |
| Ok bordo sta diventando veramente una funzione immensa.... Oggi ci stavo pensando su nel farla diventare ricorsiva e mi è venuto in mente che un componente aggiunto dopo può far diventare sovrapposto un componente che prima non lo era mandando a ramengo tutto lo sbattimento che ho fatto... |
| Jaio |
Annunciazione annunciazione dopo 2 giorni di bestemmie, incazzature, insulti a persone non meglio identificate, una lista ordinata per posizione, 4 cicli while, una procedura ricorsiva con 6 if else innestati e una miriade di controlli che non so manco più cosa fanno la procedura bordo funziona in tutti i casi dello scibile umano!!!!!!!!!
Edit: sto leggendo or ora le specifiche di prospetto... Qualcuno sa dirmi che struttura dati usa?? Io sto pensando a un grafo ordinato e pesato su cui applicare un algoritmo greedy ma credo che sia una strada impraticabile soprattutto per il fatto che non mi pare che esistano algoritmi greedy per grafi ordinati... |
| iron |
| Anche io sto cercando di capire come calcolare il costominimo di un prospetto, credo che si debba costruire un grafo con gli opportuni accorgimenti del caso e poi usare dijkstra per calcolare il "cammino" (leggasi costo) minimo. |
| Jaio |
| Il problema del grafo e che poi ti calcolerebbe il raggiungimento a tutti i nodi mentre a noi interessa solo un nodo per gruppo di quelli inseriti... Tra l'altro una volta trovata la struttura dati adatta poi le tre funzioni si fanno da se... |
| iron |
Esatto, ma come puoi vedere nel file del prospetto, si sa da subito di quanti gruppi è formato un prospetto.
Quindi se si crea un grafo orientato e pesato ciclando dijkstra per ogni componente del primo gruppo di partenza e si ottengono tanti cammini minimi quanti sono i componenti del primo gruppo, il più "minimo" è quello che ci interessa.
Che te ne pare? |
| Jaio |
| ma così dovresti salvare n alberi = agli elementi del primo gruppo per tenere il prospetto visto che p inserisce solo i dati ed é poi compito di m e b lavorarci sopra... e poi non sono sicuro che dijkstra funzioni sui grafi orientati... o almeno in classe han sempre fatto vedere grafi non orientati come esempi... |
| Chobeat |
Originally posted by Jaio
ma così dovresti salvare n alberi = agli elementi del primo gruppo per tenere il prospetto visto che p inserisce solo i dati ed é poi compito di m e b lavorarci sopra... e poi non sono sicuro che dijkstra funzioni sui grafi orientati... o almeno in classe han sempre fatto vedere grafi non orientati come esempi...
un grafo orientato è un grafo non orientato con qualcosa in più. imho funzionerebbe lo stesso. in ogni caso non vedo alternative.
io al momento per bordo sono ancora al secondo if else con 2 cicli while però volevo fare lo sbrofa e calcolare prima tutti i blocchi distinti di figure, su cui poi richiamare una funzione più semplice (per non ridurmi alla follia di codice che probabilmente hai scritto tu).
edit: or ora mi sovviene una follia maggiore: se riesco a sapere il punto di inizio e fine del blocco, se riesco a eliminare tutte le figure contenute interamente, se so il numero di figure, posso calcolare molto più facilmente il tutto calcolando una volta da sinistra e una volta da destra, fino ad incontrarsi alla/e figura/e centrale, dove farò un calcolo diverso e ritornerò il perimetro. |
| Jaio |
Bhe in pratica il mio codice consiste in una lista ordinata per posizione dei componenti poi pian piano li passo tutti aggiornando i valori di altezza lunghezza e posizione minima e salvo in una lista temporanea i nodi che non si collegano poi per calcolare il perimetro faccio i conti e ci sommo la funzione richiamata con la lista temporanea per sommare il perimetro delle altre figure che si formano... solo che vengono cicli while a dismisura solo per tirar fuori i codici identificativi e le posizioni dal comando -__-
In effetti un grafo orientato ci può stare se solo non ci volessero n grafi per i vari componenti nella prima posizione... Anche se sto pensando ad un albero con un nodo radice vuoto fittizio che punta ai primi elementi solo che il tutto esce mooolto sbilanciato soprattutto perchè tutti i nodi di un livello devono puntare a tutti i nodi del secondo livello e non sappiamo quanti questi possano essere... |
| Chobeat |
| ma infatti anche io volevo procedere così, ma come hai detto tu, è incasinatissimo e ben poco elegante. |
| Jaio |
| Io sto pure ponderando di fare una lista di liste per salvare il prospetto per poi creare una lista semplice per il dispositivo a costo minimo... Solo che per grossi input diventa inefficiente anche quello... ma soprattutto se esistono 2 o più dispositivi di costo minimo poi dobbiamo stamparli tutti oppure uno a caso? che nelle specifice m e b dicono che stampano il costo e il perimetro di un dispositivo minimo del prospetto caricato, ma al contempo fa presente che i dispositivi possono essere più di uno... |
| Chobeat |
Originally posted by Jaio
Io sto pure ponderando di fare una lista di liste per salvare il prospetto per poi creare una lista semplice per il dispositivo a costo minimo... Solo che per grossi input diventa inefficiente anche quello... ma soprattutto se esistono 2 o più dispositivi di costo minimo poi dobbiamo stamparli tutti oppure uno a caso? che nelle specifice m e b dicono che stampano il costo e il perimetro di un dispositivo minimo del prospetto caricato, ma al contempo fa presente che i dispositivi possono essere più di uno...
Io ho fatto la lista di liste infatti... |
| SanJuanWolf89 |
| cioe metti ogni gruppo di componenti del prospetto in una lista e poi fai unna lista enorme che li raggruppa tutti???? |
| Jaio |
Io l'ho pensata più a una lista composta da n elementi pari al numero di gruppi che c'è nel prospetto che sarebbe il primo numero che leggi nel file, ogni elemento poi punta a una lista contenente i nodi e le posizioni specificate nel gruppo... C'è un po' da smandruppare con le funzioni per operare sui file ma è l'unico modo che ho trovato per non costruire n-mila alberi...
Edit: sembrerò un coglione ma non riesco a tirar fuori un ciclo che funzioni per tirar fuori tutti gli elementi del prospetto... cioè non posso usare fscanf perché per non so che motivo non mi riconosce EOF ma se uso fgetc non ne esco più visto che devo fare mille controlli per parentesi e \n... Qualcuno ha idee???
Edit2: Mi sembro scemo è tutto il giorno che cerco di far andare fscanf almeno per leggere il primo numero del file ma niente fopen trova il file ma morisse se riesco a leggerci dentro... neanche con fgetc va meglio... |
| Jaio |
| Dopo anni di bestemmie ho compreso l'errore fatale... il file non iniziava con uno spazio... adesso va benissimo con un paio di eleganti while e fscanf |
| SanJuanWolf89 |
| ma quindi di fatto quello k vuioi fare tu e una lista di successori...o meglio un grafo...xk io ho pensato la stessa identica cosa xo con le funzioni e uin bel casino |
| Chobeat |
ragazzi però non ho capito come applicare l'algoritmo di ricerca, perchè non so bene bene come fare le adiacenze
http://img830.imageshack.us/img830/5601/grafo.jpg
Questa è una situazione tipo.
mettiamo che il percorso minimo calcolato dal mio algoritmo sia 1 5 7 10 perchè il costo tra 1 5 è il più basso. però magari il percorso da 6 a 7 è minore di quello di 5 7. se quindi 1 5 7 costasse di più di 1 6 7, come farei a individuarlo, non essendo 5 e 6 connessi?
se 5 e 6 fossero connessi, il loro costo sarebbe ipoteticamente 0 e si risolverebbe facilmente, ma verrebbero rispettate le specifiche? mi sa di no.
devo capire come sistemare sta cosa. |
| Chobeat |
ragazzi però non ho capito come applicare l'algoritmo di ricerca, perchè non so bene bene come fare le adiacenze
http://img830.imageshack.us/img830/5601/grafo.jpg
Questa è una situazione tipo.
mettiamo che il percorso minimo calcolato dal mio algoritmo sia 1 5 7 10 perchè il costo tra 1 5 è il più basso. però magari il percorso da 6 a 7 è minore di quello di 5 7. se quindi 1 5 7 costasse di più di 1 6 7, come farei a individuarlo, non essendo 5 e 6 connessi?
se 5 e 6 fossero connessi, il loro costo sarebbe ipoteticamente 0 e si risolverebbe facilmente, ma verrebbero rispettate le specifiche? mi sa di no.
devo capire come sistemare sta cosa. |
| Jaio |
| Forse ha più senso ragionare al contrario... Prendendo gli elementi dell'ultimo gruppo e salendo a ritroso fino al primo così avrò sempre pesature che tengono conto di ciò che ho davanti... |
| Chobeat |
eh ma quindi devi fare un for che cerchi per tutto l'ultimo gruppo. vabbè si può fare.
io ho scaricato l'implementazione dell'algoteam e volevo vedere un po' cosa faceva ma non riesco a capire come formattare il file di input (volevo capire bene cosa facesse con dei test, prima di provare ad adattarlo al mio progetto).
Qualcuno sa come fare o ha un'altra implementazione carina? |
| Jaio |
Bhe quello che che sto pensando io è di fare un while sull'ultimo gruppo che prende ogni volta un nodo diverso sopra quel nodo chiama una procedura ricorsiva che crea un dispositivo minimo per quel nodo poi nel while confronta i dispositivi che creo mano a mano e salva nella struttura definitiva quello migliore...
Suona effettivamente un po' incasinato ma secondo me con un po' di pazienza la tiro fuori... poi una volta fatta questa bordominimo è solo una formalità |
| Chobeat |
Originally posted by Jaio
Bhe quello che che sto pensando io è di fare un while sull'ultimo gruppo che prende ogni volta un nodo diverso sopra quel nodo chiama una procedura ricorsiva che crea un dispositivo minimo per quel nodo poi nel while confronta i dispositivi che creo mano a mano e salva nella struttura definitiva quello migliore...
Suona effettivamente un po' incasinato ma secondo me con un po' di pazienza la tiro fuori... poi una volta fatta questa bordominimo è solo una formalità ma allora non ho capito cosa ti serve djikstra... è potente perchè funziona sempre. in ogni caso è solo questione di costruire adeguatamente l'albero (come in figura), per il resto funziona perfettamente l'algoritmo. |
| Jaio |
| Il fatto è che ho abbandonato djikstra anche perché l'idea che ho in mente io dovrebbe funzionare perfettamente sulla lista di liste che ho implementato mentre djikstra dovrei ancora trovare su cosa piazzarlo |
| Chobeat |
io sono ad un passo.
sto usando l'implementazione dell'algoteam e l'unica struttura dati è
Graph_IL che contiene 3 array long: first, adjacent,cost ma non c'è uno straccio di spiegazione su cosa sono questi array e come dovrei usarli.
cioè son 3 array che posso tenere allineati ma non capisco come dovrebbe essere strutturata l'informazione da portarsi dietro... |
| Jaio |
| Sto guardando Djikstra ma i grafi su cui lavora sono cose totalmente oscure alla mia mente... Ma soprattutto a costruirli ci vorrebbe un sacco di lavoro preliminare sui dati dei nostri file perché non abbiamo né i numeri dei vertici né quello dei bordi finché non leggiamo tutto il file e soprattutto non abbiamo tutti i dati scritti che cerca scritti nel file... Inoltre sto pensando al fatto che se dopo aver caricato il prospetto il prof manda in esecuzione un paio di chiamate t, il valore dei pesi del grafo cambiano di conseguenza portando t a lavorare sul grafo... Seconde me diventa molto più inefficiente così... |
| Chobeat |
| io son riuscito ad adattarli a quello che chiedeva l'algoteam, peccato che poi non desse segni di vita. |
| iron |
| C'è qualcuno che ha completato? |
| AngelMiller |
| si infatti qualcuno è riuscito a implementare dijkstra?la prof mi aveva detto di usarlo ma io non ci riesco! |
| Chobeat |
| io vista la nostra struttura, pensavo di fare una versione artigianale di dijkstra con chiamate ricorsive sulla mia lista di liste, che si portasse dietro il cammino minimo trovato e tornando indietro dalla ricorsione, verificasse per ogni altro cammino se ce n'è uno minimo tra quelli non visitati. |
| lux87 |
ragazzi un suggerimento: nel main come posso distinguere i due comandi b con e senza parametri (cioè bordo e bordocostominimo)???
grazie |
| SanJuanWolf89 |
Originally posted by Chobeat
io vista la nostra struttura, pensavo di fare una versione artigianale di dijkstra con chiamate ricorsive sulla mia lista di liste, che si portasse dietro il cammino minimo trovato e tornando indietro dalla ricorsione, verificasse per ogni altro cammino se ce n'è uno minimo tra quelli non visitati.
ma tu hai implementato una lista di liste o un array di liste??in cui ovviamente la grandezza dell array e il primo numero del file prospetto...xk io ho il tuo stesso problema.. |
| Chobeat |
lista di liste.
comunque qualcuno ha provato il secondo input per b dell'esempio?
b 155 12 131 8 152 8 8 6 19 0 17 20 11 22
a me anche disegnato su carta da 76, mentre l'output atteso è 80. il programma lo disegna giusto, lo calcola giusta e su carta è 76. chi ha ragione?
edit:lunghi attimi di panico.
Semplicemente io pensavo che il quarto numero fosse l'altezza e il quinto la lunghezza, invece era ovviamente il contrario. |
| Jaio |
Quindo chobeat deduco che tu sia riuscito a fare finalmente tutto?
Io ormai sono incastrato su m e chissà quando ne risucirò ad uscire...
Tra l'altro sto notando che il mio albero con gli imput del prof esce strasblilanciato quindi dovrò reimplementarlo... Qualcuno mi dice che funzioni dell'rbtree dell'AlgoTEAM ha importato nel suo progetto? |
| Chobeat |
| nono per carità. costominimo non l'ho ancora fatto. oggi ricomincio la nuova versione. è possibile che se funzioni ( e sulla carta funziona), lo riesca a finire tra oggi e domani, ma ancora non è detto. |
| Sbirilindo |
Sarà che sono da 6 ore davanti al pc, ma non ho capito che tipo di informazioni devono esserci nel prospetto.
OT: Chobeat lo dai con Torelli o Goldwurm? |
| Chobeat |
| goldwurm, come i veri uomini. |
| Sbirilindo |
Ho staccato 30 min e ho capito, cosa viene richiesto nella parte relativa al prospetto :).
Anche secondo me è logico, data la natura del problema, utilizzare un algortimo come quello di Dijkstra. Solo che non riesco a capire come si comporta la versione utlizzata su sito dell'algoteam.
Qualcuno ha usato quella, o mi tocca rifarla da 0? |
| Chobeat |
| no quella è il male assoluto. io la sto risolvendo molto più facilmente implementando una versione povera adattata alla nostra struttura ( o almeno alla mia). |
| Sbirilindo |
| Si, infatti pensavo anche io ad un algortimo casereccio, da osteria di periferia insomma, solo che essendo un esame di algoritmi mi prende abbastanza male. |
| Chobeat |
Originally posted by Sbirilindo
Si, infatti pensavo anche io ad un algortimo casereccio, da osteria di periferia insomma, solo che essendo un esame di algoritmi mi prende abbastanza male. beh non è detto che un djikstra con IL sia più ottimizzato di una cosa ad hoc. Nel nostro problema, secondo me, tra il tempo che ci metti a fare l'IL, il tempo che ci metti a fare l'algoritmo e il tempo che ci metti a riconvertire tutto nelle nostre componenti, secondo me non conviene, anche perchè dijkstra tradizionale fa la cosa che serve a noi ma dobbiamo costruire un grafo molto più semplice, per cui soluzioni che normalmente sarebbero meno efficaci, per la forma del nostro grafo, hanno le stesse prestazioni di dijkstra. |
| Jaio |
Non ci posso credere ma finalmente ho finito la funzione m e ora manca solo di modificare leggermente la funzione b e questo progetto da incubo sarà finalmente finito!!!!
Ora però ho letto che oltre a mandarlo per email devo pure farmi lo sbattimento di perdere due ore della mia vita per venire fino a Milano a consegnarlo anche in copia cartacea... Qualcuno sa se il dipartimento di Comelico è aperto anche Sabato? Perché la relazione penso proprio che la farò domani e inoltre non ho modo di arrivare in stazione a prendere il treno...
Altrimenti si può comunque consegnare anche Lunedì vero? |
| Guepe |
| Come da sito la consegna è da effettuarsi entro il giorno 20 compreso, quindi fino alle 19.30 (orario di chiusura comelico) si può consegnare il formato cartaceo o se preferite anche martedi 21 però prima che il professore ritiri la posta e l'email entro la mezzanotte del giorno 20. |
| Sbirilindo |
Originally posted by Chobeat
beh non è detto che un djikstra con IL sia più ottimizzato di una cosa ad hoc. Nel nostro problema, secondo me, tra il tempo che ci metti a fare l'IL, il tempo che ci metti a fare l'algoritmo e il tempo che ci metti a riconvertire tutto nelle nostre componenti, secondo me non conviene, anche perchè dijkstra tradizionale fa la cosa che serve a noi ma dobbiamo costruire un grafo molto più semplice, per cui soluzioni che normalmente sarebbero meno efficaci, per la forma del nostro grafo, hanno le stesse prestazioni di dijkstra.
Ok, ma se non erro, non usando un algoritmo simil-Dijkstra, bisognerebbe usare qualcosa di combinatorio per arrivare ad una soluzione...
Il che, forse input di piccole dimensioni, potrebbe andare bene, ma per input più corposi, potrebbe metterci di più..! |
|
|
|
|
