Larios

User info:

Registered: Oct 2007
Posts: 114 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 20:21:35 [...]
Status: Offline

Post actions:

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

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

Last edited by imperator on 29-02-2008 at 12:54

gicagi

User info:

Registered: Jul 2006
Posts: 126 (0.02 al dì)
Location:
Corso: Informatica
Anno: II
Time Online: 2 Days, 22:18:38 [...]
Status: Offline

Post actions:

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

Larios

User info:

Registered: Oct 2007
Posts: 114 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 20:21:35 [...]
Status: Offline

Post actions:

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?

Last edited by Larios on 29-02-2008 at 13:35

kalbiz

User info:

Registered: Oct 2002
Posts: 72 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 2 Days, 16:48:32 [...]
Status: Offline

Post actions:

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

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

Last edited by imperator on 29-02-2008 at 16:14

kalbiz

User info:

Registered: Oct 2002
Posts: 72 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno:
Time Online: 2 Days, 16:48:32 [...]
Status: Offline

Post actions:

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

imperator

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

User info:

Registered: Oct 2007
Posts: 114 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 20:21:35 [...]
Status: Offline

Post actions:

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?

GiKappa

User info:

Registered: Oct 2004
Posts: 1800 (0.23 al dì)
Location: Brescia
Corso: Informatica
Anno: Laureato Triennale
Time Online: 9 Days, 22:40:44 [...]
Status: Offline

Post actions:

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!

imperator

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

GiKappa

User info:

Registered: Oct 2004
Posts: 1800 (0.23 al dì)
Location: Brescia
Corso: Informatica
Anno: Laureato Triennale
Time Online: 9 Days, 22:40:44 [...]
Status: Offline

Post actions:

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

Last edited by GiKappa on 29-02-2008 at 17:34

imperator

User info:

Registered: Apr 2004
Posts: 146 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 5 Days, 6:58:26 [...]
Status: Offline

Post actions:

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

GiKappa

User info:

Registered: Oct 2004
Posts: 1800 (0.23 al dì)
Location: Brescia
Corso: Informatica
Anno: Laureato Triennale
Time Online: 9 Days, 22:40:44 [...]
Status: Offline

Post actions:

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.

Last edited by GiKappa on 29-02-2008 at 17:44