 | |
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] Samegame3
Clicca QUI per vedere il messaggio nel forum |
| alexn1 |
:? Ma da dove è spuntato fuori? Sul SIFA non risultano appelli di Algoritmi per marzo...
Qualcuno sa qualcosa? |
| khelidan |
Originally posted by alexn1
:? Ma da dove è spuntato fuori? Sul SIFA non risultano appelli di Algoritmi per marzo...
Qualcuno sa qualcosa?
ci credo le iscrizioni sono chiuse da un pezzo |
| alexn1 |
| Beh è confortante visto che nel calendario degli appelli che c'è sul sito dell'uni il primo appello successivo a quello di febbraio è quello di giugno... |
| khelidan |
| infatti questo è quello di febbraio,i due precedenti erano di gennaio,uno all'inizio e uno alla fine |
| alexn1 |
| Ok, grazie ora mi è chiaro... |
| pirlo21 |
chiedo qua così magari qualcuno mi sa rispondere...
una volta che uno ha passato lo scritto, come funziona? si fa il progettino, lo si invia e il giorno dell'orale si fa la correzione o il progettino viene corretto prima dell'orale? in genere l'orale verte sulle domande del compito? quanto dura? |
| GiKappa |
qualcuno ha intenzione di fare questo progetto?
perchè io mi sa che inizierò a guardarlo perchè voglio passarlo! |
| Larios |
| io ho intenzione di farlo, sto cominciando a vedere cosa chiede, anche perchè se non ho capito male se non lo si passa o fa, tocca rifare lo scritto... |
| khelidan |
| io devo assolutamente passarlo,ultimo esame.... |
| GiKappa |
| dai che ce la facciamo allora!:asd: |
| pirlo21 |
| ci sono anche io... l'ho già riletto un po' di volte e il primo dubbio che ho è quello dei colori...all'inizio dice che le biglie possono essere verdi blu o rosse, poi invece quando parla della mossa fusione e minore, inserisce azzurro, giallo, nero ecc ecc... voi avete capito? |
| darkshadow |
| scusate ma se il voto del progetto non e' sufficiente, si deve rifare tutto da capo (cioè scritto e nuovo progetto + orale) o si rifa solo il progetto?? |
| GiKappa |
Originally posted by pirlo21
ci sono anche io... l'ho già riletto un po' di volte e il primo dubbio che ho è quello dei colori...all'inizio dice che le biglie possono essere verdi blu o rosse, poi invece quando parla della mossa fusione e minore, inserisce azzurro, giallo, nero ecc ecc... voi avete capito?
da quello che ho capito io le biglie possono essere di un qualsiasi colore che corrisponde a una stringa |
| greensheep |
si le biglie possono essere di qualsiasi colore!!!
ragazzi ke struttura usate per il progetto??
e per le relazioni tra i colori? dove li salvate? |
| GiaXVI |
leggendo i post di chi ha fatto i progetti samegame di gennaio ho visto che andava x la maggiore usare 2 grafi come strutture dati, uno x le caselle, e uno x le biglie...
voi che dite??? |
| khelidan |
| credo di si,ormai tutti i progetti son da fare con i grafi,alla fine è cio che si presta meglio ad implementare delle adiacenze |
| Larios |
a mio parere credo non ci sia molta differenza nell'usare 2 o 1 grafo a livello di efficenza... per il resto mi sembra fattibile come progetto :)
una cosa che non mi è chiara...sul testo parla di scacchiera di dimentsione r per c quindi come si fa a sapere da che coordinate cominciare a costruirla visto che poi sui file di input di esempio ci sono coordinate negative ?
|
| pirlo21 |
ma infatti secondo me non ha senso costruire la scacchiera...
bisogna trovare una struttura dati per memorizzare le biglie che possa contenere sia la posizione, sia il colore e sia il valore |
| Larios |
Originally posted by pirlo21
ma infatti secondo me non ha senso costruire la scacchiera...
bisogna trovare una struttura dati per memorizzare le biglie che possa contenere sia la posizione, sia il colore e sia il valore
hai ragione, complica soltanto le cose costruire una scacchiera vuota all'inizio e non ha senso... :) |
| greensheep |
non credo bisogni costruire la scacchiera..
per la posizione il colore e il valore andrebbe bene un grafo magari rb
ma per le relazioni fra i colori?? |
| pirlo21 |
| ma il problema non è tanto come implementarli, ma come valutare poi le relazioni tra i colori... perchè se si può inserire un colore qualsiasi, bisogna poi essere in grado di relazionarlo a tutti gli altri colori, creando quindi una specie di elenco ordinato dal colore minore a quello maggiore |
| GiaXVI |
la scacchiera serve, lo dice espressamente il prof nel testo del progetto...
cmq considerando che ci sono delle coordinate negative nn so nemmeno io da dove far partire la scacchiera...è un bel casino |
| pirlo21 |
| puoi indicarmi dove richiede l'implementazione della scacchiera? |
| GiaXVI |
cit. "si tenga presente che la minima porzione rettangolare di piano contenente tutte le biglie puo essere molto grande rispetto al numero delle biglie presenti nel piano, quindi non è sicuramente efficiente rappresentare l'insieme delle biglie mediante un'unica matrice"
ragazzi ma qualcuno che ha consegnato uno dei progetti samegame di gennaio potrebbe postare qualcosa? |
| imperator |
X giaXVI
scusa ma il prof nn si limita a sconsigliare l'uso di una martice per la rappresentazione del piano?
o per scacchiera intendi le biglie? |
| pirlo21 |
| ma infatti il prof parla di insieme di biglie, non di scacchiera...infatti il prof dice che la scacchiera può essere molto più grande dell'insieme delle biglie e non ha senso implementare una struttura dati che resterà per lo più inutilizzata |
| GiaXVI |
| x come lo intendo io il prof consiglia di usare una struttura x il piano(scacchiera) e una per le biglie... io sto cercando di capire come fare...e che strutture usare |
| Larios |
Originally posted by pirlo21
ma infatti il prof parla di insieme di biglie, non di scacchiera...infatti il prof dice che la scacchiera può essere molto più grande dell'insieme delle biglie e non ha senso implementare una struttura dati che resterà per lo più inutilizzata
infatti...
GiaXVI non perderti col cercare di fare la scacchiera altrimenti non ne esci piu, pensavo anche io di farla all'inizio ma non ha senso... tieni conto delle biglie e se per caso alle coordinate x y non trovi nessuna biglia allora vuol dire che ce una casella vuota... ma non c'è bisogno di fare una struttura per per mantenerle.
Almeno questo è quello che credo sia meglio fare :/ |
| gicagi |
| per come l'ho inteso io:la scacchiera e le biglie sono due strutture ben separate...infatti,ad ogni input corrisponde una TABELLA di biglie diverse...che poi vanno inserite nelle corrispondenti (x+h,y+k) caselle della scacchiera...che ne pensate??? |
| pirlo21 |
| io la penso come larios...cmq sarebbe interessante magari andare avanti su due strade separate e poi quando si sviluppano le prime funzioni, confrontare le differenze per capire quale strada rende meglio |
| greensheep |
| io conosco chi ha fatto same game1 e mi ha espressamente detto che non bisogna implementare nessuna scacchiera perchè è totalmente inutili.. quindi concentriamoci sul tipo di albero da utilizzare |
| imperator |
qualcuno è già riuscito a fare la funzione riduzione?
teoricamente si dovrebbero calcolare i totali di tutte le possibili combinazioni di colonne, per poi cancellare le celle delle colonne della combinazione che da il maggior punteggio...
oppure c'è un'altra strada più facile? la programmazione dinamica non credo possa essere usata come anche gli algoritmi greedy...
ogni consiglio/osservazione è ben accetta...
infine credo anch'io che basti un albero rb...magari per determinate funzioni bisogna aggiungere qualche altra struttura dati temporanea |
| gicagi |
qualcuno ha capito la reale utilità della formula: k*c+(h+1)???
dovrebbe indicare la posizione relativa all'input... |
| imperator |
ti indica le coordinate della biglia da inserire:
esempio del prof:
la stringa blu si trova nella posizione 1, quindi per k=h=0 (k*c+(h+1)=1 per k=0 e h=0);
le coordinate della biglia blu saranno (x+h, y+k)=(4+0, 5+0):
quindi (4, 5)=blu;
la stringa rosso si trova nella posizione 2, quindi per k=0 e h = 1 (k*c+(h+1)=2 per k=0 e h=1);
le coordinate della biglia rosso saranno (x+h, y+k)=(4+1, 5+0):
quindi (5, 5)=rosso; |
| carla86 |
qualcuno ha risolto il problema ke in input si ha una stringa blu,3? come separo la stringa dall'intero?
che struttura usate per mantenere i blocchi?? |
| GiaXVI |
io mi sono convinto a usare un albero rb x le biglie senza fare quello x la scacchiera!
x il problema di come separare la stringa blu,3 aspetto notizie anche io....
si puo usare una getc() che riconosce la virgola???? |
| GiKappa |
spiegatemi un paio di cose:
la riduzione di un blocco (cioè di caselle adiacenti fra loro) consiste nel cancellare colonne non vicine in modo da ottenere il più alto punteggio possibile?
e una volta cancellate queste colonne, da cosa deriva lo spostamento delle restanti? |
| gicagi |
| l'insieme delle biglie potrebbe essere rappresentato con un albero binario di ricerca...che ne pensate??? |
| darkshadow |
Originally posted by gicagi
l'insieme delle biglie potrebbe essere rappresentato con un albero binario di ricerca...che ne pensate???
e' una possibilità ma ci sono altre strutture + adatte. Infatti non è detto che l'albero binario di ricerca rimanga sempre bilanciato man mano che inserite altre biglie. Una struttura + adatta puo' essere per esempio un Albero RB, il quale mantiene sempre bilanciato la struttura. Cmq negli altri progetti ho visto che oltre a gli alberi rb molti hanno usato una tabella HASH.
PS: Voi cosa ci scriveresti nella relazione del progetto?? |
| gicagi |
| nella relazione devi scrivere un pò di tutto...le funzioni che hai implementato e la relativa complessità...il perchè hai utilizzato una struttura dati piuttosto che un'altra... |
| gicagi |
| chi di voi utilizza un albero RB lo fa per la gestione delle biglie??? |
| imperator |
una domanda...
affinchè due blocchi B1 e B2 siano adiacenti basta che si verifichi la seguente condizione giusto?
-una cella di B1 adiacente a una cella di B2 |
| kalbiz |
rieccomi sempre sul solito giochino ....
per eliminare la virgola ho usato la funzione strtok in modo da ottenere due token separati uno prima della virgola ,con il colore della biglia ed il sucessivo con il valore della stessa ... non so se è valido ma funziona ....
in compenso sono fermo sulla scelta delle colonne da eliminare, cioè come scegliere la sommatoria massima ????
la combinazione di tutte le colonne ???
una matrice ??
voi che strada avete seguito ??? |
| khelidan |
| ma per implementare le biglie hai usato un grafo? |
| darkshadow |
| come avete risolto il problema della relazione d'ordine dei colori?? |
| carla86 |
siccome nn ti viene garantito ke tutti i colori siano in relazione tra loro, nn posso creare una lista di semplici colori in ordine di relazione.
allora ho creato una lista di relazioni di colori.
cioè una struct che memorizza tutti e due i colori e punta alla relazione successiva. |
| pirlo21 |
| io alla fine ho implementato una lista di liste... con grafi o alberi, visto che in laboratorio non li abbiamo mai provati, non saprei proprio come muovermi |
| imperator |
anch'io ho risolto come pirlo21 + o -...
tornando sulla funzione riduzione...dite che il backtracking può essere utile per calcolare i totali di tutte le possibili combinazioni delle colonne? |
| pirlo21 |
io ho un altro stupido problema...ho usato come suggerito la strtok, però come faccio a rendere il secondo token un intero?
già risolto...funzione atoi |
| darkshadow |
Originally posted by pirlo21
io ho un altro stupido problema...ho usato come suggerito la strtok, però come faccio a rendere il secondo token un intero?
già risolto...funzione atoi
con la funzione int atoi (char *c) |
| lackno |
domanda sull'inserimento iniziale.
quando ho vari inserimenti come nell'esempio del prof:
i 6 3 0 0 f1.txt
i 4 5 -4 -2 f2.txt
[...]
se nel secondo inserimento vado a finire su una cella gia' contenente una biglia, devo modificarla col colore/numero nuovi (ovvero del secondo inserimento) o lasciare quella gia' scritta al primo inserimento?
mi sorge questo dubbio perche' svolgendo l'esercizio a mano (disegnando una scacchiera e inserimendo i dati) dopo le prime due stampe di blocconumeri nel file del prof vengono segnati i numeri 14 e 9, mentre a mano, sovrascrivendo le biglie con quelle nuove a me esce 15 e 10, mentre se non sovrascrivo e lascio sempre le biglie piu' vecchie (ovviamente nell'inserimento biglia singola sovrascrivo come indicato) esce giustamente 14 e 9.
Nelle specifiche del file, se non sono del tutto rincretinito, non e' scritto nulla a riguardo se non un generico "modificare contenuto cella". |
| imperator |
io ho capito che se esiste già la biglia modifico semplicemente il contenuto della biglia...
se ho una biglia di coordinate xy, colore c, valore v, ed eseguo
biglia(xy, v1, c1)
allora cambio semplicemente v in v1 e c in c1...
questo è quello che penso e che ho capito |
| gicagi |
| giusto...la penso come te... |
| imperator |
| domani cmq dovrei andare da aguzzoli al ricevimento e già che c sn chiedo conferma di sta cosa e farò sapere |
| Larios |
a me non tornano i numeri di blocchi di cui parlate(14 e 9), i primi due del test...
EDIT: trovato errore....:oops: |
| gicagi |
| qualche suggerimento sulla fz minore??? |
| Larios |
ho bisogno di una mano qualcuno puo postare le sue coordinate dei passaggi sotto, o gentilmente dirmi dove sbaglio? a me i blocchi vengono 9 e 8 non 14 e 9... :(
un blocco per essere tale deve essere composto da almeno due biglie connesse, giusto?
eseguendo:
i 6 3 0 0 f1.txt
i 4 5 -4 -2 f2.txt
i 6 3 0 -6 f1.txt
ottengo queste coordinate:
**************************
0 0 blu v:7
1 0 blu v:3
1 1 blu v:1
2 1 giallo v:4
1 2 giallo v:6
2 2 giallo v:1
0 3 giallo v:6
1 3 rosso v:1
2 3 giallo v:2
1 4 rosso v:2
1 5 blu v:2
2 5 blu v:8
**************************
-4 -2 giallo v:3
-3 -2 giallo v:2
-2 -2 giallo v:1
-1 -2 blu v:2
0 -2 rosso v:2
-3 -1 rosso v:4
-2 -1 rosso v:7
-1 -1 blu v:6
-2 0 rosso v:1
0 0 rosso v:9
-4 1 giallo v:1
-2 1 giallo v:3
0 1 blu v:1
**************************
0 -6 blu v:7
1 -6 blu v:3
1 -5 blu v:1
2 -5 giallo v:4
1 -4 giallo v:6
2 -4 giallo v:1
0 -3 giallo v:6
1 -3 rosso v:1
2 -3 giallo v:2
1 -2 rosso v:2
1 -1 blu v:2
2 -1 blu v:8 |
| alexn1 |
| Scusate, nessuno ha avuto problemi per il calcolo delle colonne da cancellare nella riduzione? Io ci sto sbattendo la testa da 2 gg... :( |
| Larios |
Originally posted by alexn1
Scusate, nessuno ha avuto problemi per il calcolo delle colonne da cancellare nella riduzione? Io ci sto sbattendo la testa da 2 gg... :(
io mi sono creato una struttura dove inserisco le biglie di divise per colonna(la uso solo durante la riduzione), una volta fatta è facile cancellare le biglie giuste
Qualcuno puo darmi info riguardo alle coordinate del mio post sopra pls :) |
| alexn1 |
Originally posted by Larios
io mi sono creato una struttura dove inserisco le biglie di divise per colonna(la uso solo durante la riduzione), una volta fatta è facile cancellare le biglie giuste
Io ho creato un struttura che mi memorizza il totale per ogni colonna, l'unica cosa è che non riesco a trovare un modo efficiente per calcolare la somma massima ottenibile... |
| kalbiz |
ciao ecco la lista che genero dopo l'inserimento delle prime istruzioni ...
ho confrontato un paio di numeri e sembrano uguali se non fosse per la 0,0 blu v7 che io ho v9
(2,-1):blu - valore:8
(1,-1):blu - valore:2
(1,-2):rosso - valore:2
(2,-3):giallo - valore:2
(1,-3):rosso - valore:1
(0,-3):giallo - valore:6
(2,-4):giallo - valore:1
(1,-4):giallo - valore:6
(2,-5):giallo - valore:4
(1,-5):blu - valore:1
(1,-6):blu - valore:3
(0,-6):blu - valore:7
(0,1):blu - valore:1
(-2,1):giallo - valore:3
(-4,1):giallo - valore:1
(-2,0):rosso - valore:1
(-1,-1):blu - valore:6
(-2,-1):rosso - valore:7
(-3,-1):rosso - valore:4
(0,-2):rosso - valore:2
(-1,-2):blu - valore:2
(-2,-2):giallo - valore:1
(-3,-2):giallo - valore:2
(-4,-2):giallo - valore:3
(2,5):blu - valore:8
(1,5):blu - valore:2
(1,4):rosso - valore:2
(2,3):giallo - valore:2
(1,3):rosso - valore:1
(0,3):giallo - valore:6
(2,2):giallo - valore:1
(1,2):giallo - valore:6
(2,1):giallo - valore:4
(1,1):blu - valore:1
(1,0):blu - valore:3
(0,0):rosso - valore:9 |
| pirlo21 |
| una domanda...ma la struttura che memorizza le biglie, si può dichiarare come variabile globale? perchè nel prototipo delle funzioni del prof non c'è nessun puntatore alla struttura dati, ma nel testo del progettino dice che le variabili globali vanno usate solo per informazioni di tipo globale |
| pirlo21 |
| mi sono bloccato...la funzione insert mi sta diventando una cosa infinita e complicata, piena di controlli.. voi che struttura avete usato? non vorrei essermi complicato la situazione usando una lista di liste |
| Larios |
| per le funzioni che dice di scrivere c'è scritto che sono anche implementabili liberamente, quindi puoi aggiungerci i parametri che ti servono, chi ha capito come me dia conferma pls |
| khelidan |
| si lo dice nel testo che non sono da considerarsi come prototipi di funzione |
| pirlo21 |
aiutoooooooo
la funzione insert legge da file, quindi a meno che non siamo masochisti, la lettura è sequenziale e quindi anche l'inserimento deve essere sequenziale.. ma voi come avete implementato questa funzione e la struttura per contenere i dati??
io uso questa
struct elemento{
int x,
int y,
int valore,
char * colore,
struct elemento* nextx
struct elemento* next y
}
e mi sono bloccato perchè non riesco a effettuare tutti i collegamenti dei puntatori, senza contare che passando da una riga all'altra si salta anche una riga del file da dove si legge e quindi la cosa diventa impossibile |
| Larios |
| io non ho usato una struttura leggo scompongo e passo direttamente alle funzioni che devo lanciare poi rileggo ecc... |
| imperator |
Originally posted by imperator
io ho capito che se esiste già la biglia modifico semplicemente il contenuto della biglia...
se ho una biglia di coordinate xy, colore c, valore v, ed eseguo
biglia(xy, v1, c1)
allora cambio semplicemente v in v1 e c in c1...
questo è quello che penso e che ho capito
oggi ho chiesto ad aguzzoli, e mi ha confermato quanto detto sopra... |
| gicagi |
| la penso come larios |
| pirlo21 |
| quindi voi non salvate le biglie??? |
| khelidan |
Originally posted by pirlo21
aiutoooooooo
la funzione insert legge da file, quindi a meno che non siamo masochisti, la lettura è sequenziale e quindi anche l'inserimento deve essere sequenziale.. ma voi come avete implementato questa funzione e la struttura per contenere i dati??
io uso questa
struct elemento{
int x,
int y,
int valore,
char * colore,
struct elemento* nextx
struct elemento* next y
}
e mi sono bloccato perchè non riesco a effettuare tutti i collegamenti dei puntatori, senza contare che passando da una riga all'altra si salta anche una riga del file da dove si legge e quindi la cosa diventa impossibile
Vuoi fare un grafo no?In che senso non riesci a sistemare i puntatori?Io ti consiglio di prendere spunto dal progetto daltonismo che è molto simile a questo |
| Larios |
giusto per essere sicuri mi confermate che 1 biglia equivale ad blocco? perchè fino a poco fa pensavo che un blocco avesse dovuto avere almeno 2 biglie connesse dello stesso colore :| |
| imperator |
un blocco è un insieme di biglie adiacenti dello stesso colore: ad esempio supponi di avere le seguenti biglie...
(3,4)=blu
(3,5)=blu
(2,4)=blu
(4,4)=blu
allora hai un blocco di colore blu composto da 4 biglie |
| Larios |
quindi se avessi (1,3)=B(1,2)=B-->questo è un blocco (5,5)-->questa non sarebbe un blocco....
allora credo che i risultati di output del file di test sul pdf siano sbagliati in quanto 14 e 9 vengono solo se si considerano come blocchi anche le biglie singole...qualcuno ci ha fatto caso? |
| imperator |
hai ragione scusa... sn stato impreciso o cmq nn chiaro... anche un insieme composto da una biglia di un colore è un blocco
esempio:
(3,5)=B
(3,6)=R
(7,8)=B
ho tre blocchi (3, 5), (3,6), (7,8) |
| kalbiz |
qualcuno si è buttato sulla riduzione ?
a parte il gran casino, almeno personalmente è un gran casino, come fate la somma per colonna del blocco da ridurre ?????
cioè usate una matrice e due indici for
oppure con una bfs, anche se non mi è chiaro come arrivare a dire che su x la somma è tot su x+1 è tot eccetera ..... |
| darkshadow |
| l'algoritmo per trovare le colonne da eliminare che danno il punteggio massimo l'ho trovato. Il problema pero è implementarlo infatti come dice Kalbiz diventa difficile fare la somma delle colonne in un albero. Cmq anchio ci stavo provando a crearmi una matrice con solo le colonne interessate ma non ho ancora arrivato a niente di concreto. |
| kalbiz |
| tentavo la stessa strada, anche se per ora mi è oscuro l'algoritmo... io ho un grafo ed è difficile uguale... se incaselli le biglie del blocco in una matrice, quando poi la riduci , cioè muovi le biglie dove esiste lo spazio, in x-1, come fai a decidere quale è la tua base di riduzione ??? se la prima colonna del blocco è diciamo x = 3 , una biglia si sposta solo fino a x=3 corretto ??? |
| Larios |
| si la colonna "piu a sinistra" del blocco è il limite massimo di spostamento per quelle che rimangono. |
| Larios |
c'è una cosa che non capisco come risolvere...
quendo eseguo operazioni del tipo B devo aprire un foglio, leggere le informazioni compreso il colore che non si sa che lunghezza possa essere(nel testo parla di non mettererestrizioni nella lunghezza dei colori se non ricordo male).
Quindi prendendolo carattere per carattere esapando la mia stringa puntatore di volta in volta e quando ha finito associo alla funzione di creazione della biglia.
la seconda voltache richiamo l'operazione di tipo B e leggo un nuovo colore anche il colore della mia biglia precedente storata cambia...e prende l'ultimo inserito.
qualcuno mi sadire come posso evitare questa cosa? |
| Kira82 |
| Scusate ma mi è venuto un dubbio, voi avete creato celle e biglie o avete fatto in modo che siano la stessa cosa? cioè io ho fatto in modo che le celle mi vengano create nel momento in cui faccio un input e se nell'input ho 0.0 allora la cella non contiene biglie, altrimenti si crea la cella e automaticamente la colora e gli assegna un valore(quindi contiene una biglia).Voi avete fatto così oppure io sto sbagliando nella comprensione del progetto? |
| darkshadow |
| non sbagli Kira82 è proprio cosi. |
| Kira82 |
grazie darkshadow, ne approfitto per farti un'ulteriore domanda riguardo alle strutture..io ho usato per ora (sono ancora alle funzioni base) un grafo per le biglie, secondo te (che sicuramente sei più avanti) usando il grafo mi trovo poi in difficoltà nelle funzioni più complesse e sarebbe meglio usare un albero rb?
Te lo chiedo così se mi conviene di più usare un albero non vado avanti con il grafo.. |
| darkshadow |
guarda che un albero rb è un grafo.
la struttura è del tipo...
struct albero_biglie{
struct albero_biglie *left, *rigt, *up;
int campo;
}
ovviamente la mia è un po' diversa ma il concetto è quello.
per quanto riguarda la complessità come detto precedentemente c'e' il problema di eliminare le colonne.
PS: Come avete risolto la funzione minore??
Ho provato con liste di liste ma ogni volta mi andava a sovvrascivere quello che ho messo precedentemente.
Adesso sto provando con un albero ma niente ancora di concreto. |
| Gioe |
Come si fa un grafo orientato in c? almeno la definizione della struttura.
Grazie in anticipo |
| Kira82 |
| si so che un albero rb è un grafo ma l'implementazione è leggermente diversa..bisogna creare una radice e anche le operazioni (es. ricerca ed inserimento) non sono uguali..era per questo che distinguevo grafo da albero..ho forse sbagliato a capire qualcosa? |
| kalbiz |
| bloccato ... ho usato un grafo per le biglie ... il problema che si propone è, una volta determinato un blocco, sommare i valori delle biglie sulle rispettive colonne... come sopra ... con un rb non saprei magari viene meglio l'algoritmo per la scelte dell xn da eliminare... |
| kalbiz |
@Gioe :
quando costruisci gli archi del grafo poni le relazioni solo da un nodo verso un'altro e non in entrambi i versi |
| imperator |
qualcuno è riuscito a fare la funzione riduzione? se si dove ha trovato informazioni utili per trovare i totali di tutte le possibili combinazioni delle colonne?
thanks |
| Larios |
se in intendi come trovare il massimo punteggio realizzabile, basta ordinare i totali, esempio:
colonne -1(totale=8) 0(totale=7) 1(totale=6) 2(totale=8)
ordinando i totali ottengo: 6 7 8 8
scorro la lista in questo modo 8->8->7->6 controllando ad ogni passo se ci sono colonne vicine gia cancellate...
alla fine ottengo 16 (cancello colonne -1 e 2) |
| imperator |
ah!!! bastava usare il semplice trucco di ordinare le colonne... e io che m stavo tirando scemo cercando calcolare tutte le combinazioni.... vabbè meglio così...
grazie dell'aiuto |
| imperator |
scusa larios ma sono un po' dubbioso sulla tua tecnica...
ad esempio se la combinazione di colonne che ha il totale + alto nn comprende la colonna con il valore + alto in assoluto sono fregato...ad esempio:
col1 tot = 5;
col2 tot = 10;
col3 tot = 6;
con la tua tecnica cancellerei solo la col2 che ha totale 10;
mentre invece devo cancellare la col1 e col3 con il totale di 11...
quindi forse l'unica soluzione è calcolare il tot della combinazione che fa il maggior punteggio usando la porgrammazione dinamica, che mi consente di riciclare i risultati di sottoproblemi memorizzandoli da qualche parte senza star a dover ricalcolarli qualora gli stessi sotto-problemi si ripresentassero... |
| gicagi |
| qualcuno può dare qualche informazione su come ha implementato la funzione "minore"?????? |
| Larios |
Originally posted by imperator
scusa larios ma sono un po' dubbioso sulla tua tecnica...
ad esempio se la combinazione di colonne che ha il totale + alto nn comprende la colonna con il valore + alto in assoluto sono fregato...ad esempio:
col1 tot = 5;
col2 tot = 10;
col3 tot = 6;
con la tua tecnica cancellerei solo la col2 che ha totale 10;
mentre invece devo cancellare la col1 e col3 con il totale di 11...
quindi forse l'unica soluzione è calcolare il tot della combinazione che fa il maggior punteggio usando la porgrammazione dinamica, che mi consente di riciclare i risultati di sottoproblemi memorizzandoli da qualche parte senza star a dover ricalcolarli qualora gli stessi sotto-problemi si ripresentassero...
vero :(
rincontrollato e fatto qualche test, se mi verifico prima i totali ricavati dalle colonne pari e quelle dispari e confronto con totale ottenuto come descritto prima risolvo il problema... cosa ne dici? |
| kalbiz |
avevo provato un po di soluzioni simili, dividendo in sottoproblemi di ordine 2 tipo
(2,40)(50,20)(1,5)(100)
provando a tenere il maggiore per ogni insieme dopo un confronto sulle adiacenze ... ma non ha funzionato..
sono molto orientato a sviluppare con la programmazione dinamica, salvandomi i risultati volta a volta come diceva imperator |
| imperator |
e ma tu ad esempio in una soluzione puoi avere:
(supposto che il blocco abbia 10 colonne, numerate da 1 a 10)
sia la soluzione ottima composta dalle colonne 1, 4, 7,9.
ad esempio qui hai dei salti irregolari...
credo tu stia cercando di trovare la soluzione ottima direttamente, cercando attraverso determinati stratagemmi di scartare determinate colonne a prescindere, cercando così di costruire un'unica soluzione, quella ottima...
però qua devi per forza (credo) calcolarti tutte le possibili combinazioni... non ci sono algoritmi che ti consentono di prendere direttamente le colonne della combinazione migliore, la combinazione con il punteggio + alto... |
| kalbiz |
rimane il calcolo delle conbinazioni .. ma rischiano di diventare veramente reoppe per valori attorno alle 15 colonne
n!/(k!*(n-k)!) |
| imperator |
| tieni presente che non sono delle vere e proprie combinazioni matematiche... hai la regola che se cancelli la colonna x non puoi cancellare la colonna x-1 e x+1... |
| Larios |
Originally posted by gicagi
qualcuno può dare qualche informazione su come ha implementato la funzione "minore"??????
non riesco a capire come farla...l'idea sarebbe di associare dei numeri ai colori quando li inserisci nella'albero, ma non mi convince molto....
dall'altra parte se non hai una chiave associata al colore a questo punto non ha molto senso avere un albero bilanciato perchè non sapresti cmq se muoverti a destra o sinistra scendendo per trovare il colore....:?
altree idee? |
|
|
|
|
