.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Progetto per appello del 3 settembre (http://www.dsy.it/forum/showthread.php?threadid=40811)

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

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?

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

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

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

ma infatti anche io volevo procedere così, ma come hai detto tu, è incasinatissimo e ben poco elegante.

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

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

cioe metti ogni gruppo di componenti del prospetto in una lista e poi fai unna lista enorme che li raggruppa tutti????

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

prova con fgets!

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

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

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.

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.