.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] Samegame3 (http://www.dsy.it/forum/showthread.php?threadid=33907)

[Progetto] Samegame3

Ma da dove è spuntato fuori? Sul SIFA non risultano appelli di Algoritmi per marzo...

Qualcuno sa qualcosa?

__________________
Come potrebbe "l'istruzione" farmi sentire più intelligente?! Ogni volta che imparo qualcosa di nuovo, questa spinge le cose vecchie fuori dal mio cervello... (Homer J Simpson)

Re: [Progetto] Samegame3

Originally posted by alexn1
Ma da dove è spuntato fuori? Sul SIFA non risultano appelli di Algoritmi per marzo...

Qualcuno sa qualcosa?

__________________
Khelidan

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

__________________
Come potrebbe "l'istruzione" farmi sentire più intelligente?! Ogni volta che imparo qualcosa di nuovo, questa spinge le cose vecchie fuori dal mio cervello... (Homer J Simpson)

infatti questo è quello di febbraio,i due precedenti erano di gennaio,uno all'inizio e uno alla fine

__________________
Khelidan

Ok, grazie ora mi è chiaro...

__________________
Come potrebbe "l'istruzione" farmi sentire più intelligente?! Ogni volta che imparo qualcosa di nuovo, questa spinge le cose vecchie fuori dal mio cervello... (Homer J Simpson)

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?

qualcuno ha intenzione di fare questo progetto?

perchè io mi sa che inizierò a guardarlo perchè voglio passarlo!

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

io devo assolutamente passarlo,ultimo esame....

__________________
Khelidan

dai che ce la facciamo allora!

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?

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

__________________
by Ð@rk§h@ÐØw

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?

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?

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

credo di si,ormai tutti i progetti son da fare con i grafi,alla fine è cio che si presta meglio ad implementare delle adiacenze

__________________
Khelidan

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 ?

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

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

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

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

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

puoi indicarmi dove richiede l'implementazione della scacchiera?

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?

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?

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

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

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

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

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

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

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

qualcuno ha capito la reale utilità della formula: k*c+(h+1)???
dovrebbe indicare la posizione relativa all'input...

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;

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

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

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?

l'insieme delle biglie potrebbe essere rappresentato con un albero binario di ricerca...che ne pensate???

Originally posted by gicagi
l'insieme delle biglie potrebbe essere rappresentato con un albero binario di ricerca...che ne pensate???

__________________
by Ð@rk§h@ÐØw

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

chi di voi utilizza un albero RB lo fa per la gestione delle biglie???

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

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

ma per implementare le biglie hai usato un grafo?

__________________
Khelidan

come avete risolto il problema della relazione d'ordine dei colori??

__________________
by Ð@rk§h@ÐØw

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.

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

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?

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

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

__________________
by Ð@rk§h@ÐØw

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

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

giusto...la penso come te...

domani cmq dovrei andare da aguzzoli al ricevimento e già che c sn chiedo conferma di sta cosa e farò sapere

a me non tornano i numeri di blocchi di cui parlate(14 e 9), i primi due del test...

EDIT: trovato errore....

qualche suggerimento sulla fz minore???

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

Scusate, nessuno ha avuto problemi per il calcolo delle colonne da cancellare nella riduzione? Io ci sto sbattendo la testa da 2 gg...

__________________
Come potrebbe "l'istruzione" farmi sentire più intelligente?! Ogni volta che imparo qualcosa di nuovo, questa spinge le cose vecchie fuori dal mio cervello... (Homer J Simpson)

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

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

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

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

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

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

si lo dice nel testo che non sono da considerarsi come prototipi di funzione

__________________
Khelidan

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

io non ho usato una struttura leggo scompongo e passo direttamente alle funzioni che devo lanciare poi rileggo ecc...

:-S

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

la penso come larios

quindi voi non salvate le biglie???

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

__________________
Khelidan

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

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

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?

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)

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

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.

__________________
by Ð@rk§h@ÐØw

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

si la colonna "piu a sinistra" del blocco è il limite massimo di spostamento per quelle che rimangono.

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?

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?

non sbagli Kira82 è proprio cosi.

__________________
by Ð@rk§h@ÐØw

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

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.

__________________
by Ð@rk§h@ÐØw

Come si fa un grafo orientato in c? almeno la definizione della struttura.

Grazie in anticipo

__________________
@~@~@~@~@~@~@~@~@~@

TIMEO DANAOS ET DONA FERENTES

@~@~@~@~@~@~@~@~@~@

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?

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

@Gioe :
quando costruisci gli archi del grafo poni le relazioni solo da un nodo verso un'altro e non in entrambi i versi

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

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)

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

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

qualcuno può dare qualche informazione su come ha implementato la funzione "minore"??????

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

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

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

rimane il calcolo delle conbinazioni .. ma rischiano di diventare veramente reoppe per valori attorno alle 15 colonne
n!/(k!*(n-k)!)

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

Originally posted by gicagi
qualcuno può dare qualche informazione su come ha implementato la funzione "minore"??????

nella struttura dell'albero rb che campi avete inserito? usate solo i puntatori? e dite che bastano solo i puntatori *left, *right e *up o bisogna aggiungerne uno *down?

help!

ma già con i puntatori left e right discendi l'albero...a sx o dx..
io personalmente non ho aggiunto altri puntatori

quindi la struttura di ogni nodo sarebbe una biglia con le coordinate, il valore e il colore?

perchè non mi è chiaro come usare gli alberi per spostarmi all'interno della scacchiera..

esatto le informazioni che ti servono all'interno di ogni biglia sono coordinate, colore, valore

ok, però ad esempio se il nodo A contiene la biglia in posizione (x,y), i suoi figli conterranno le biglie in quale posizione?

non sono molto ferrato con gli alberi!

edit: avevo pensato a fare in modo che i figli a sinistra di un nodo fossero quelli adiacenti per le ascisse, mentre quelli a destra fossero adiacenti per le ordinate, ma mi escono dei doppioni.

allora se crei un albero di biglie non puoi pretendere che i figli siano le celle adiacenti (anche perchè le biglie adicenti sono 4, mentre tu hai solo 3 puntatori: padre e i 2 figli).
se vuoi una struttura in cui memorizzare una biglia e tenere traccia delle biglie adiacenti devi costruirti un grafo tramite liste di adiacenza.

con un albero le "figlie" di una biglia dipendono da quando inserisci le biglie...
ad esempio...supponi aver una albero lessicografico in cui memorizzi dei colori...
se io inserisco nell'ordine "ocra", "arancione", "marrone"
avro un albero con radice ocra, figlio sx arancione, figlio dx marrone...
ma se inserisco nell'ordine arancione, ocra, marrone avrò un albero con radice arancione che avrà un figlio dx ocra che a sua volta avrà un figlio sx marrone...

quindi con il primo insieme di inserimenti ho un albero con 2 livelli (radice e i due figli)
con secondo insieme di inserimenti ho un albero con 3 livelli (radice [arancione], figlio dx della radice [ocra], figlio sx di ocra [marrone])

cmq se vuoi implementare dei grafi tramite liste di adiacenza puoi guardare alcuni vecchi progetti come "daltonismo"

ragazzi ma voi usate tutti gcc come compilatore? io ne uso un altro e va tutto ok, oggi ho provato gcc perchè il prof dice di usare quello e il programma non funziona più...

che problemi ti da??

cmq ho sempre usato gcc.

__________________
by Ð@rk§h@ÐØw

mi da qualche warning e se compilo con -ansi anche qualche errore... inoltre quando lancio il programma mi si blocca subito durante l'inserimento dei dati, mentre con l'altro compilatore funziona perfettamente...

forze usi gets o roba simile per le stringhe

__________________
by Ð@rk§h@ÐØw

Originally posted by imperator
con un albero le "figlie" di una biglia dipendono da quando inserisci le biglie...
ad esempio...supponi aver una albero lessicografico in cui memorizzi dei colori...
se io inserisco nell'ordine "ocra", "arancione", "marrone"
avro un albero con radice ocra, figlio sx arancione, figlio dx marrone...
ma se inserisco nell'ordine arancione, ocra, marrone avrò un albero con radice arancione che avrà un figlio dx ocra che a sua volta avrà un figlio sx marrone...

quindi con il primo insieme di inserimenti ho un albero con 2 livelli (radice e i due figli)
con secondo insieme di inserimenti ho un albero con 3 livelli (radice [arancione], figlio dx della radice [ocra], figlio sx di ocra [marrone])

Originally posted by GiKappa

quello che non mi è chiaro è il tuo esempio sui colori. sono due modi di procedere per inserire le biglie?

ok! perfetto! era questo che non capivo! grazie!

in fase di esplorazione quale dei due è migliore? quello bilanciato o quello che prosegue con figlio dx-figlio sx?

attenzione...ho detto che si tratta di un semplice albero binario di ricerca (lessicografica)...non ho detto che questo era bilanciato.
il fatto che un albero sia bilanciato non dipende dagli inserimenti...ma proprio dal tipo di albero;
ad esempio albero RB è bilanciato...ma un generale albero di ricerca non è detto che sia bilanciato...
ad esempio supponi di avere un albaro binario di ricerca i cui nodi contengono degli interi e supponi di inserire nell'ordine 1, 2, 3, 4, 5.
bene questo albero di ricerca degenera sostanzialmente in un lista monodirezionale (1 ha figlio dx 2 che a sua volta a figlio dx 3 che a sua volta a figlio dx 4 etc..)
se usi però un albero RB invece l'albero è bilanciato, grazie alle rotazioni e ai colori dei nodi

Originally posted by 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...

anche io vorrei sapere che struttura utilizzare per la funzione minore, io pensavo a una lista, ma ancora nn ho guardato bene!

ho anche una domanda poco tecnica...se si consegna un progetto che nn implementa tutte le funzioni correttamente il prof te lo boccia o ti viene incontro???

compilando con -Ansi mi da il seguente:

<command line>:4:4: missing '(' after predicate

ma non riesco a capire cosa voglia dire....

dovrebbe essere che alla riga 4 hai dimenitcato una (

qualcuno è riuscito a fare la funzione riduzione?
se si dove ha preso ispirazione?

che algoritmo bisogna usare secondo voi x vedere quali sono le colonne col valore + alto nelle funzione riduzione???

qualcuno è riuscito a farla????

purtroppo no, ho tentato diverse strade, ma nulla.
anche la funzione per avere i totali per riga, ho usato due indici for in matrice... abbastanza una schifezza ... ma non ho trovato alternative.
voi già per la funzione di calcolo sulle somme righe, cosa avete utilizzato ?

nessumo mi può ispirare dicendomi almeno che struttura ha usato per la funzione minore?

Ragazzi io sono rimasta bloccata sulla funzione minore e sulla funzione riduzione...c'è qualcuno che è riuscito a farle e mi può dare qualche suggerimento??

Attenzione

qualcuno è riuscito a trovare un algoritmo efficiente per il conteggio del punteggio massimo? io ne ho trovato uno ma non è per nulla efficiente...

per le relazioni tra i colori ho invece usato semplicemente un grafo orientato, ad esempio se giallo è minore di blu, nel grafo giallo è adiacente a blu... sembra funzionare bene...

nella funzione Fusione come avete fatto a controllare se i 2 blocchi delle biglie date in input sono adiacenti?????

Originally posted by Fredx
qualcuno è riuscito a trovare un algoritmo efficiente per il conteggio del punteggio massimo? io ne ho trovato uno ma non è per nulla efficiente...

per le relazioni tra i colori ho invece usato semplicemente un grafo orientato, ad esempio se giallo è minore di blu, nel grafo giallo è adiacente a blu... sembra funzionare bene...

Aiutoooo...ho un problema ( a parte che mi manca da fare ancora la funzione riduzione..si accettano suggerimenti!!)..quando provo il programma funziona, ma se inserisco l'input del prof mi dà problemi. Esattamente il punto è
...
s 0 1
F 0 0 0 1
s 0 1
...
e il problema è che non mi effettua la fusione, ma se tolgo il primo s 0 1 allora la fusione funziona..funziona anche se inserisco un'altra funzione tra s 0 1 e F 0 0 0 1.....???????
qualcuno riesce a spiegarmi perchè?????

Spiegare il perchè è difficile senza avere il codice sottomano.
La cosa migliore che puoi fare, secondo me, è di giocare al calcolatore.
Armati di carta, matita, gomma, logica e un fottio di pazienza e debuggati il codice, oppure usa un debugger se ti trovi meglio.
Io personalmente uso il primo metodo, e sebbene a volte ci metti ORE a trovare il bug, se ti impegni lo trovi.

La pazienza è la virtù dei forti e la caratteristica che più odio del C è che i bug tendono a nascondersi in parti del codice lontane anni luce da quella in cui si presentano (perlomeno nel mio codice :p )

Ma non so se il debugger può essere utile perchè non è che mi restituisce un errore, solo che non fa quello che dovrebbe, ovvero la fusione.
Ho notato che è un problema delle due funzioni, cioè se le metto in successione la seconda non fa il 'suo dovere' ma se sono separate anche da una sola altra funzione tutto è ok.
Secondo voi ho sbagliato qualcosa con i puntatori? O come dice Vid devo debuggare?

Cmq qualcuno mi può dire la logica per trovare le colonne da cancellare nella riduzione..io sono riuscita a scrivere la funzione che somma i valori delle celle di un blocco in una colonna, ma poi come faccio a trovare le colonne che sommate danno il punteggio max??

per trovare l'errore fai eseguire tutta la sequenza di codice che ti da problemi, aggiungendo dei return per esempio che ti fanno terminare il programma dopo poche operazioni...poi ne fai eseguire altre in piu se quelle funzionano e cosi via... con un po di pazienza troverai il punto esatto che ti da l'errore... usa anche printf per verificare i dati che entrano sulle funzioni che testi.

Ho trovato il punto, sembra che dopo l'input di 's' oppure 'F' non entri nel case successivo.
Cioè ho provato a creare un case 'w' che esegue un printf, se metto
s 0 1
w 0 0
F 0 0 0 1
il programma esegue correttamente la 's' e la 'F' ma salta la 'w'; viene la stessa cosa con i case dopo 'F' cioè con
F 0 0 0 1
w 0 0
s 0 1
Non capisco perchè non mi entra nei case se li metto in input dopo la 's' o la 'F'.........aiutoooooooooooooooo!


Risolto..ho trovato l'errore!

raga come faccio a testare se il progetto funziona con gcc?
ho scaricato lo zip e ora?

lo apri, vai su dos, vai nella cartella dove l'hai aperto (non devi installare niente da li mi sembra) e poi esegui gocs
dopo usi il solito gcc -blabla prog.c

Scusate ma che logica avete usato per calcolare la somma massima delle colonne..come faccio a fare tutte le somme possibili?

io lo sto impostando in questo modo...anche se non è per niente facile questa parte devo dire :/

per trovare tutte le combinazioni di somme generiche...

esempio 1 2 3

trovo tutte le combinazioni di somme partendo da 1

fai 1 + 2 parte la ricorsione sul 2
2 + 3

3 non ha combinazioni e ritorna il suo valore... quindi 2+3=5 ritorni questo valore e 1+2 = 6

poi fai 1 3= 4

fine combinazioni partendo da 1....

e poi vai avanti col numero successivo il 2 che avra solo 2 3 e quindi 5.

e poi il 3 che fa 3...

da qui ti fai tutti confronti di volta in volta e tiri fuori il punteggio piu alto, devi anche salvarti le posizioni(gli indici delle colonne) man mano perchè poi devi sapere che colonne hanno formato il totale migliore e saranno da cancellare.

adesso sto testando il programma e fino ad un certo punto tutto va bene poi i risultati che ci sono nel nesto non coincidono più con i miei.

l'input è:

i 6 3 0 0 f1.txt
i 4 5 -4 -2 f2.txt
i 6 3 0 -6 f1.txt
b 0 -1 6 blu
n
i 1 5 -4 2 f3.txt
i 1 5 -5 -3 f3.txt
b 0 -4 2 giallo
n
s 0 1
r 0 1
< rosso bianco
< bianco blu
< blu rosso
s 0 1
F 0 0 0 1
s 0 1
r 0 1
b 0 -1 8 blu
F 0 -1 0 -2
F 1 -3 -3 -1
r 0 -1
n
r 0 2
< giallo azzurro
< azzurro bianco
F -2 -1 -2 -2
n
b 1 -2 12 blu
b -4 -4 3 blu
r -3 0             // da questo punto alcuni risultati non coincidono più
i 1 5 -6 1 f3.txt
F -1 1 -6 1
F 1 3 2 5
r 1 3
r 1 3
n
r -1 1
r -6 -3
r -6 -3
r -6 1
r -6 1
r -6 1
n
f

ho fatto tutti i grafici a mano per vedere se era il programma che non andava o se c'e' qualche errore nel testo.

facendo i conti mi ritrovo che il totale di ciascuna colonna è:

colonna x = -5   totale = 1
colonna x = -4   totale = 7
colonna x = -3   totale = 10
colonna x = -2   totale = 8
colonna x = -1   totale = 3
colonna x = 0    totale = 15
colonna x = 1    totale = 23
colonna x = 2    totale = 7

nel testo dice che il punteggio massimo è : 38
ma invece il punteggio massimo che si può ottenere è 37.
Tale risultato si ottiene eliminando le colonne: x = -4, x = -2, x = 0 e x = 2

qualcuno di voi può confermare???

__________________
by Ð@rk§h@ÐØw

se prendi le colonne -4, -2 e 1 il totale è 38

azz hai ragione!!

devo rivedere il codice della riduzione.

il resto sembra andare bene.

Speriamo!!!

Forza raga che ci siamo quasi.

__________________
by Ð@rk§h@ÐØw

Originally posted by darkshadow
facendo i conti mi ritrovo che il totale di ciascuna colonna è:

colonna x = -5   totale = 1
colonna x = -4   totale = 7
colonna x = -3   totale = 10
colonna x = -2   totale = 8
colonna x = -1   totale = 3
colonna x = 0    totale = 15
colonna x = 1    totale = 23
colonna x = 2    totale = 7

nel testo dice che il punteggio massimo è : 38
ma invece il punteggio massimo che si può ottenere è 37.
Tale risultato si ottiene eliminando le colonne: x = -4, x = -2, x = 0 e x = 2

qualcuno di voi può confermare??? [/B]

oramai a titolo informativo .... questo output dopo il primo comando s 0 1 (è uguale al testo)

(blu
0,1 valore : 1
1,1 valore : 1
1,0 valore : 3
1,-1 valore : 2
2,-1 valore : 8
0,-1 valore : 6
-1,-1 valore : 6
-1,-2 valore : 2
)

mi spiegate come è possibile che le colonne di valore massimo diano giustamente 16, dovrei eliminare, tutte le biglie che stanno quindi sulla colonna x= -1 e x = 2 (la cui somma è 16)
quindi eliminerei
(-1,-1)
(-1,-2)
(2,-1)
ok se elimino solo queste biglie, come è possibile che dopo la prima riduzione alla seconda richiesta di s 0 1
vengano stampate solo due biglie ????
quando riduco e stabilizzo le biglie si dovrebbero ricompattare e riformare il blocco ...

ok ho trovato l'errore ... la riduzione non spostava le biglie correttamente in x-1

sbaglio o il calendario x gli eventuali orali tarda ad uscire???

Originally posted by GiaXVI
sbaglio o il calendario x gli eventuali orali tarda ad uscire???

__________________
Come potrebbe "l'istruzione" farmi sentire più intelligente?! Ogni volta che imparo qualcosa di nuovo, questa spinge le cose vecchie fuori dal mio cervello... (Homer J Simpson)

perchè io non li trovo?

__________________
io Sofort e te che sei? un pupazzo?

Originally posted by Java
perchè io non li trovo?

vero vero....

il pc del lavoro qua è un rottame

__________________
io Sofort e te che sei? un pupazzo?