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

grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.

Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!!

grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.

Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!!

grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.

Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!!

Originally posted by aghito
cosa vi viene a voi con questo input?

c 5 2 6
c 25 3 5
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4

i 5 5
i 5 6
i 5 7
i 6 5
b
e 0 0
e 1 1
e 2 0
R 1

i 1 2
i 1 2
i 1 3
i 2 4

e 0 0

p 1 0
a 1 0
b
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4

i 5 5
i 5 6
i 5 7
i 6 5
e 0 0
f


a me

b:1
p:0
a:0
b:1

__________________
"Che ne sai di un ragazzo che ti amava
che parlava e niente sapeva
eppur quel che diceva chissà perchè‚ chissà adesso è verità."

Originally posted by aghito
cosa vi viene a voi con questo input?

c 5 2 6
c 25 3 5
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4

i 5 5
i 5 6
i 5 7
i 6 5
b
e 0 0
e 1 1
e 2 0
R 1

i 1 2
i 1 2
i 1 3
i 2 4

e 0 0

p 1 0
a 1 0
b
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4

i 5 5
i 5 6
i 5 7
i 6 5
e 0 0
f


a me

b:1
p:0
a:0
b:1

__________________
"Che ne sai di un ragazzo che ti amava
che parlava e niente sapeva
eppur quel che diceva chissà perchè‚ chissà adesso è verità."

grazie aghito per il test...ho trovato un buggino nel mio programmino....cmq ora che ho risolto i risultati mi vengono come i tuoi

__________________
"Che ne sai di un ragazzo che ti amava
che parlava e niente sapeva
eppur quel che diceva chissà perchè‚ chissà adesso è verità."

l'ho postato apposta perchè immaginavo di non essere il solo a trovare quel bug

__________________
alessandro colombini

ragazzi una domanda:
ma l'output del prof a voi viene giusto??

Perchè a me la k-cella (5; 2,0) non la elimina perchè è occupata da tre celle e il parametro di riempimento è 4. Dove sbaglio???



Ormai non penso di finirlo, quindi esco a divertirmi e domani a pranzo sono fuori.
Aguzzoli ci vediamo a gennaio

Chao
Roby

Originally posted by fasa
nn credo tu possa far...devi reimpostare il flag elemento per elemento....cmq tutti sto flag usate....ma si può sapere a cosa vi serve?io nn ne uso neanche uno!la mia struttura è semplicissima...2 variabili di tipo int x le coordinate e un puntatore per puntare all'elemento successivo della lista e questo mi basta per implementare tutte le richieste del programma!!!!

Originally posted by fasa
nn credo tu possa far...devi reimpostare il flag elemento per elemento....cmq tutti sto flag usate....ma si può sapere a cosa vi serve?io nn ne uso neanche uno!la mia struttura è semplicissima...2 variabili di tipo int x le coordinate e un puntatore per puntare all'elemento successivo della lista e questo mi basta per implementare tutte le richieste del programma!!!!

Documentazione...

Terminato il progetto, ora mi son bloccato sulla documentazione:

in pratica ho utilizzato 2 tabelle di hash, una per le 1-celle e una per le k-celle. I tempi di inserimento e rimozione sono oltremodo efficienti. Il calcolo dell'area, peso e blocchi avviene sulla tabella di k-celle. Supposto che vi siano di norma più inserzioni/cancellazioni/modifiche che non richiame ad area,pesi e blocchi, alla chiamata di queste ultime operazioni eseguo la ricerca "al volo" delle k-celle adiacenti per ogni k-cella, controllando per ogni k-cella nell'intorno delle 8 adiacenti (se esistono); ogni cella così trovata, se non ancora visitata, viene posta in una coda ausiliaria; vengono così "espanse" le celle trovate per prime. Se la coda si svuota, vuol dire che non abbiamo più k-celle adiacenti. Ogni elemento rimosso dalla coda è marcato come "visited" nella k-tabella hash, per cui viene escluso da ulteriori ricerche.
La cosa funge (i test sono ok); per i k-blocchi basta iterare sulla k-tabella finchè ci sono k-celle piene e non ancora visitate.
Il prolema che mi si pone è il calcolo del tempo di esecuzione: a "manina" infatti risulterebbe quadratico (credo che incida la ricerca al volo delle celle adiacenti). Purtroppo 'sto tempo sembra dipendere da parecchi fattori: in primis la risoluzione impostata, poi la distribuzione dei blocchi, nonchè (la +ostica) la continua espansione/contrazione della coda...
Su quache riferimento ho trovato un algoritmo simile, di tempo O(d^2 * N^2), dove d è una costante (nel mio caso, 1/k, la risoluzione...). Ovviamente per d piccolo (= k grande) e N grande, l'algo viene praticamente considerato lineare... Ma io come diavolo lo recupero e lo scrivo il presunto tempo di esecuzione?? Gia' non ci ho dormito tutta notte, se qualcuno ha suggerimenti...

Grazie e buona domenica a tutti

Gabriele

Caro ghily siamo in 2...

anche a me gli output del prof nn risultano più dopo r (25 4)... e le mie funzioni area e peso sono giuste... le ho provate con altri input... mah...

ci rinuncio e ripasso a gennaio... (che avrò anche reti e basi) ma è la quarta volta che ci provo... e se nn lo passo a gennaio devo rifare lo scritto........ ma siamo matti?

__________________
Sometimes you hurt the ones who love you most and sometimes you hold the ones who leave you lost,
and sometimes you learn
but its too late, it's too late. EI

anche a me dava l'errore di Dante. l'ho risolto mettendo in una variabile di tipo double il risultato di k * k * r (r è p/q)
perchè altrimente con alcuni valori ,25 4 ad esempio con k = 5,si mangiava can la variabile di tipo int il resto della virgola trasformando per esempio un 2,9 in 2.

Eh, ma cmq nn si deve arrotondare per difetto?

__________________
Sometimes you hurt the ones who love you most and sometimes you hold the ones who leave you lost,
and sometimes you learn
but its too late, it's too late. EI

Originally posted by Dante
Eh, ma cmq nn si deve arrotondare per difetto?