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

[LAB. ALGORITMI] Progetto FILTRI

Ragazzi è uscito il progetto di algoritmi avete già visto qualcosa?

secondo voi è lecito utilizzare un RB albero(dei vari punti) con un collegamanto ad una lista dove sono inseriti i filtri in quel punto?

Aiuto!!!

sì, l'ho visto... devo ancora pensarci... ma perchè un rb?
ciao

Ah, nel testo del progetto si dice: "il segnale fuoriuscente è definito come la differenza binaria troncata a 0"; cosa significa differenza binaria troncata a 0?

ciao!

__________________
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

significa che siamo solo nella parte positiva di piano, penso.
Infatti subito dopo dice che p(x,y)=max(0,o-(T1+...+Tk)).

__________________
Chi pianta datteri non mangia datteri.

gli alberi rb garantiscono una complessita O(lgn) anche nel caso peggiore

ciao a tutti!
io x il progetto stavo pensando di usare un'albero(rb o no) in cui ogni nodo contiene,oltre ai vari dati quali coordinate e distorsione,un puntatore ad una lista la quale conterra' i nodi inclusi propiamente a quel nodo.Ma il problema si pone quando ad esempio inserisco un filtro ke è il piu' grande di tutti.......nn ho piu' un'albero ma una un'unica lista di liste......ke dite il mio ragionamento è MOLTO sbagliato?

grazie cmq

ciaoooooo

ma la somma e la sottrazione binaria come le fate? Con l'usuale metodo di inserire un bit di segno e aggiungere la quantita' negativa al termine da cui sottrarre...!

Originally posted by vinnie
ma la somma e la sottrazione binaria come le fate? Con l'usuale metodo di inserire un bit di segno e aggiungere la quantita' negativa al termine da cui sottrarre...!

E quindi???

Originally posted by vinnie
E quindi???

Il problema è che le specifiche del progetto lasciano a desiderare secondo me, cioè non si capisce bene cosa richiede nell'implementazione: la funzione segnale ad esempio... devo per forza passargli come parametro una stringa binaria? Se fosse così sarei costretto a rappresentare il segnale come una stringa, con pesanti conseguenze sul codice...

Intendi dire la sottrazione bit a bit?
Il problema del "resto negativo" e' eliminato dal fatto che al "minimo" puo' essere 0?

Non sono sicuro di come vada fatto pero', anche in questo caso...

Originally posted by vinnie
Intendi dire la sottrazione bit a bit?
Il problema del "resto negativo" e' eliminato dal fatto che al "minimo" puo' essere 0?

Non sono sicuro di come vada fatto pero', anche in questo caso...

Potresti risolvere portando tutto in base 10 per controllare se il minuendo è inferiore rispetto al sottraendo, di conseguenza sai che il segnale essendo negativo, è nullo.

Ciao!
scusate ma voi ke strutture dati usate?

"... devo per forza passargli come parametro una stringa binaria? Se fosse così sarei costretto a rappresentare il segnale come una stringa, con pesanti conseguenze sul codice..."

Un array di char? IMHO, molto più comodo anche per le operazioni sulle stringhe binarie.

Originally posted by Gusher
Potresti risolvere portando tutto in base 10 per controllare se il minuendo è inferiore rispetto al sottraendo, di conseguenza sai che il segnale essendo negativo, è nullo.

Estedi il tipo di dato tramite una struttura dati e il gioco è fatto :-)

Originally posted by Gusher
Estedi il tipo di dato tramite una struttura dati e il gioco è fatto :-)

io vi consiglierei una lista di adiacenza...ciao a tutti

__________________
Welcome to the real world....

io direi di usare una lista concatenata doppia

E che ci mettereste dentro la lista? Un char e il prossimo puntatore?

cmq secondo me il problema piu' impellente è in ke modo inserire i nodi......le altre funzioni sn tutte conseguenze.cioè in ke modo gestire la possibilità ke venga inserito un nodo ke includa propriamente tutti gli altri.........un bel macellino

secondo voi qual'è la struttura dati più corretta per risolvere il progetto?vi prego aiuto

struttura dati

mi sento un po' scemo nel pensare a una semplice lista likata lineare.....ma non riesco a capire e forse non la so e basta quali vantaggi avrei a fare un rb albero....
Nel senso che non trovo un motivo per giustificare un preciso ordine in cui salvo i miei bei filtrini... tanto per la questione dell'annidamento pensavo che immettendo un nuovo filtro questo debba confrontarsi direttamente con tutti i filtri già in lista .


Per la questione della sottrazione binaria ci devo ancora pensare...ma visto l'andazzo mi sa che bisognera vedere come funziona (cosa che mi son dimenticato ) e implementare la giusta funzione.

Mi sembra di aver realizzato che il problema delle operazioni binarie sia ridimensionato, infatti a pag. 3 del progetto (nelle specifiche) si dice che i fltri vadano immessi come DECIMALI. Inoltre tutta la gestione dell'imput mi sembra assai simile al modo in cui lui ha trattato le liste dinamiche (PDF13 e relativi sorgenti).
Che ne dite?

Si anke a me è caduto l'okkio sul quel pdf del prof........anke se il problema dei controlli,secondo me,riamane con ogni struttura dati......ke dite?

Ho detto una cazzata! Ho letto male. Tutto uguale. Forse pero' i sorgenti delle liste dinamiche possono (in parte) riciclarsi...

Originally posted by vinnie
Mi sembra di aver realizzato che il problema delle operazioni binarie sia ridimensionato, infatti a pag. 3 del progetto (nelle specifiche) si dice che i fltri vadano immessi come DECIMALI. Inoltre tutta la gestione dell'imput mi sembra assai simile al modo in cui lui ha trattato le liste dinamiche (PDF13 e relativi sorgenti).
Che ne dite?

[...]dove a,b,c,d sono numeri naturali, e sigma è una stringa binaria[...]

Si. Ho visto (vedi sopra).
Pero' quello che dici tu sullo spreco mi sembra inevitabile. perche' devi comunque inserire una stringa che e' fatta di char (con la loro dimensione)...
Bah! che depressione... che dite quindi di quei sorgenti suoi?

Originally posted by vinnie
Si. Ho visto (vedi sopra).
Pero' quello che dici tu sullo spreco mi sembra inevitabile. perche' devi comunque inserire una stringa che e' fatta di char (con la loro dimensione)...
Bah! che depressione... che dite quindi di quei sorgenti suoi?

Piuttosto ma due filtri che si sovrappongono solo in parte influenzano in qualche modo il loro grado di annidamento?

no,basta sommare i loro disturbi

Originally posted by drakend
Piuttosto ma due filtri che si sovrappongono solo in parte influenzano in qualche modo il loro grado di annidamento?

una funzione search su una lista lineare è O(n) mentre in un RB albero (O)Logn e già questo dovrebbe farti riflettere se poi iniziamo a mettere in mezzo la funzione per beccare il livello non finisci più diventa un funzione in O(n!)

dalla discussione mi sembra di aver capito che è meglio usare un albero (RB o no),i nodi sono strutture che contengono le coordinate abcd.Resta da capire con quale criterio ordino i nodi nell'albero per poi risalire al grado di annidamento.
Se qualcuno ha qualche idea (magari prendendo come riferimento l'immagine dei rettangoli sul testo del progetto) lo faccia sapere.GRAZIE!

Il maggiore problema resta proprio il criterio di ordinamento per il resto penso anche io che la struttura adatta sia un rb albero!

__________________
http://www.voglioscendere.ilcannocchiale.it/

Governare gli italiani non è impossibile, è inutile. (G.Giolitti)

I punti che stanno esattamente sui bordi dei filtri appartengon ai filtri? Penso di sì, però... meglio chiedere!

Drakend ovvio che valgono anche i punti del perimetro altrimenti con due filtri affiancati nei punti di incrocio dovrebbe risultare nessun filtro?

Originally posted by PuNk-MaD
Drakend ovvio che valgono anche i punti del perimetro altrimenti con due filtri affiancati nei punti di incrocio dovrebbe risultare nessun filtro?

bah.......allora sono brava anch'io! =P

Sembrava ovvio anche a me!

__________________
"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 pincopallino
bah.......allora sono brava anch'io! =P

Sembrava ovvio anche a me!

Off-Topic:

Non perdi mai occasione di menartela vero?
Fai pure, l'importante è essere convinti.

uff

Che casino mi sta fondendo il cervello a pensare alle procedure per gestire l'inserimento dei filtri nel modo appropriato

gran casino ste procedure per gestire gli annidamenti

una spiegazione rapida di questo thread?

__________________
www.alterazione.com www.andreaforzani.com
www.myspace.com/alterazione
www.myspace.com/festaincravilla

Concordo pienamente!

scusate, prima i thread erano separati adesso gli hanno uniti penso, scusate ankora!

__________________
www.alterazione.com www.andreaforzani.com
www.myspace.com/alterazione
www.myspace.com/festaincravilla

Implementazione del Piano

Ciao Ragazzi.Per implementare i filtri penso anch'io ch egli alberi Rg siano la struttura ideale,anzi con una loro estensione credo si possa fare meglio.Ma per l'implementazione del piano che struttura dati pensate di usare?.Io pensavo ad una lista che ha un puntatore all'albero Rb, che contiene il filtro in un punto del piano,predendo in considerazione l'ascissa.
In bocca al lupo
Ciao Ciao tom80

io avevo pensato ad una struct molto semplice in cui il punto ha int x e int y,
e per quanto riguarda i rettangoli farli identificare dai due angoli in basso a sx e in alto a dx.
cmq è ancora tutto da vedersi

Struct per il piano

ma praticamente verrebbe furoi comunque o una lista o un albero.Come pensi di unire le varie struct?.Per cercare un elemento nella sturct quanto mi costa?.Forse si potrebbe implementare l'asse delle x del piano con un albero il cui tempo di ricerca è O(nln).Che ne pensi/pensate?

Struct per l'implementazione del piano nel progetto Filtri

ma praticamente verrebbe furoi comunque o una lista o un albero.Come pensi di unire le varie struct?.Per cercare un elemento nella sturct quanto mi costa?.Forse si potrebbe implementare l'asse delle x del piano con un albero il cui tempo di ricerca è O(nln).Che ne pensi/pensate?

Ciao a tutti!
la mia sara' anke una idea folle ma io ho pensato(e sto implementando) un albero rb ke contiene tutti i filtri inseriti,e ogni nodo ha a sua volta contiene un albero rb ke rappresenta i filtri pieamente inclusi......sara' anke folle ma a questo punto invece di usare le liste uso solo alberi rb!kissa'.......

ciauz

Originally posted by Drake83
Ciao a tutti!
la mia sara' anke una idea folle ma io ho pensato(e sto implementando) un albero rb ke contiene tutti i filtri inseriti,e ogni nodo ha a sua volta contiene un albero rb ke rappresenta i filtri pieamente inclusi......sara' anke folle ma a questo punto invece di usare le liste uso solo alberi rb!kissa'.......

ciauz

vedendo il filtro come nodo di un albero è possibile che il filtro compaia due volte....se per esempio il filtro N è annidato in 2 filtri A e anche in B ma che tra loro non si annidano

Root--- A---B---X---Y....etc etc
| |
N N--W

non guardate lo schemino che ho provato a fare perchè gli allineamenti erano diversi....in pratica sotto A c'era N e sotto b anche

Originally posted by drakend
Che chiave univoca usi per ordinare l'albero di ricerca?

Originally posted by Skanky
non guardate lo schemino che ho provato a fare perchè gli allineamenti erano diversi....in pratica sotto A c'era N e sotto b anche

scusate ho una domanda: se inserisco 2 filtri cn stesse coordinate
ma con distorisioni diverse,come gestisto il tutto?lo inserisco lo stesso al posto di quell'altro oppure no?

scusate ma quando elimino un filtro R(a.b.c.d) e questo ne ha un altro annidato dentro tolgo pure lui?

__________________
http://www.voglioscendere.ilcannocchiale.it/

Governare gli italiani non è impossibile, è inutile. (G.Giolitti)

no

bella grazie gusher

__________________
http://www.voglioscendere.ilcannocchiale.it/

Governare gli italiani non è impossibile, è inutile. (G.Giolitti)

Però se due filtri sono uguali e uno sull'altro non vengono aggiunti sul grado del filtro

es A=B

e su A e B c'è C

A ha grado 1 e B grado 1

se due filtri sono uguali,basta sommare le distorsioni e tenere un filtro solo,lo si deduce dalle specifiche ("cancella TUTTI i filtri di forma a,b,c,d)

Se utilizzo un albero bilanciato e metto: nella radice il primo filtro, poi procedo così, a sx i filtri inclusi propriamente e a destra i filtri non inclusi o inclusi impropriamente, dovrebbe funzionare, no? A questo punto perchè dovrei utilizzare un albero rb?

Originally posted by Dante
Se utilizzo un albero bilanciato e metto: nella radice il primo filtro, poi procedo così, a sx i filtri inclusi propriamente e a destra i filtri non inclusi o inclusi impropriamente, dovrebbe funzionare, no? A questo punto perchè dovrei utilizzare un albero rb?

__________________
I really love your peaches,
wanna shake your tree...

The Joker - Steve Miller Band

Ciao io sono ancora un passo indietro di voi, pertanto ma volevo chiedervi gentilmente: ma come avete fatto a creare la stringa binaria? sto pensando di creare una lista di struttture caratteri per poi riconvertirele in un array; e mi rendo conto che è un'idea da deviato mentale...ma non riesco a trovare una soluzine migliore

__________________
Io sono la fata verde. Sono la rovina e il rimpianto, la vergogna e il disonore. Io sono la morte, io sono l'assenzio...

spero di essere stato poco chiaro, perchè se non fosse così vuol dire che non va bene la mia soluzione... :-( cmq tra un paio d'ore mando un msg con una spiegazione migliore della mia teoria... ora devo uscire... a dopo!!!

__________________
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

L'inserimento dei primi quattro quadrati dell' imput-esempio contenuto nella specifica diventa:

il primo filtro ha coppie di coordinate (2,2) e (11,10) e lo metto nella radice del mio albero bilanciato;

il secondo filtro è: (4,4) e (9,9):

confronto (2,2) con (4,4) e vedo se la prima coppia è minore-uguale alla seconda; confronto (11,10) e (9,9) e vedo se la prima coppia è maggiore-uguale alla seconda; se entrambi i confronti sono positivi allora deduco che il secondo filtro è incluso propriamente nel primo.

Cosa me ne faccio del secondo filtro quindi? Lo inserisco nell'albero come figlio sinistro della radice. Se non fosse risultato incluso propriamente lo avrei inserito come figlio destro della radice.

Stessa cosa col terzo filtro di vertici (4,6) e (8,8) incluso propriamente nel secondo (e quindi figlio sinistro del secondo filtro)

Il quarto nodo è (8,3) (10,5): risulta incluso propriamente nel primo filtro (la radice del mio albero) ma non risulta incluso propriamente nel secondo filtro (figlio sinistro della radice); lo inserisco come figlio destro del figlio sinistro della radice:


1° filtro(radice)
(2,2) (11,10)
/
/
2°filtro (nodo)
(4,4) (9,9)
/ \
/ \
3°filtro(nodo) 4°filtro(nodo)
(4,6) (8,8) (8,3) (10,5)

A questo punto la ricerca del grado di annidamento di un filtro funziona così: grado di annidamento del filtro (=nodo )A = quanti nodi incontro partendo dal nodo a scendendo verso figli sinistri fino al nodo foglia.

L'operazione punto (x,y) funzionerebbe così: confronto le coordinate di p(x,y) con le coordinate dei filtri partendo da quello nella radice, se sono comprese controllo in tutto il sottoalbero sx della radice se sono comprese anche in altri filtri... ecc...

secondo voi?
Ciao!

Ciao,

anch'io sto procedendo con un albero binario (trasformato da un albero a più vie).

Sono alquanto perplesso riguardo all'efficienza della struttura dati poiché non c'è alcun ordinamento tra i nodi sulle diramazioni dx (cioè tra i nodi non-inclusi propriamente) e pertanto per cercare un rettangolo potrebbe essere necessario scorrere molti nodi.

Inoltre, non so cosa fare se un rettangolo è incluso propriamente in DUE altri rettangoli. In questo caso la struttura non mi pare adatta (ma è solo una sensazione, per il momento!). Infatti mi pare che ad ogni inserimento occorra scorrere sempre tutto l'albero per accertarsi che il rettangolo sia inserito come figlio di tutti i nodi che lo includono propriamente.

Un'altra possibilità che sto valutando è dividere il piano in quattro settori o quadranti (ne, nw, sw, se) ognuno dei quali può essere successivamente diviso in altri quattro settori e rappresentare il tutto con un albero con quattro figli per nodo interno. Questo apparentemente ottimizzerebbe le ricerche e gli inserimenti. Ma cosa fare se un rettangolo interseca più settori?

Qualcuno ha avuto altre idee?

Ciao,

Marco

filtri-struttura dati

io sto usando un albero binario per ordinare i rettangoli.i nodi sono una struttutra (a,b,c,d,distorsione) che mi rapresenta il rett.Li ho ordinati per ascissa "a".quando voglio sapere il grado del rett mi basta guardare i nodi precedenti(i rett alla sx) e controllare se sono inclusi.

ciao

Originally posted by marco.pozzi
Un'altra possibilità che sto valutando è dividere il piano in quattro settori o quadranti (ne, nw, sw, se) ognuno dei quali può essere successivamente diviso in altri quattro settori e rappresentare il tutto con un albero con quattro figli per nodo interno. Questo apparentemente ottimizzerebbe le ricerche e gli inserimenti. Ma cosa fare se un rettangolo interseca più settori?

Ho notato mentre progettavo che nelle specifiche mancano alcune informazioni importanti.
Per esempio la quantita di quadrati che mediamente dovrebbero essere inseriti o la possibilità di sovrapposizioni intendo rettangoli con le stesse coordinate ma con filtri diversi o addirittura uguali.

Anche voi avete avuto dei dubbi del genere o sono io fuori strada.

mah x il fatto dell'inserimento di 2 rettangoli kon coordinate uguali ma con distorsioni diverse si ha un "effetto cumulativo" come dicono le pagine del progetto,x la quantita' media di filtri da inserire io nn mi pongo il problema dato ke uso alberi rb.
ciao

Non ti interessa sapere quanti rettangoli potresti potenzialmente avere, visto che lo scopo è quello di utilizzare una struttura dati dinamica (struttura ad albero in primis)

Ciao ragazzi.Qualcuno mi sa dire se in c esistono funzioni ch egestisconoi i bit.Per farmi capire li sommano li sottraggono?
Grazie mille!!!!
A presto!!!
Ziao Tom80

No devi gestirli tu con una struttura dati appropriata.

Originally posted by tom80
Ciao ragazzi.Qualcuno mi sa dire se in c esistono funzioni ch egestisconoi i bit.Per farmi capire li sommano li sottraggono?
Grazie mille!!!!
A presto!!!
Ziao Tom80

che intendi per "tipi matematici"?
(ehm... ho saltato le ultime lezioni)
io ho usato una lista concatenata doppia con sentinella. All'inizio avevo pensato agli array con l'allocazione dinamica della memoria, poi ho visto che usciva un casino trovare la corretta posizione, quindi ho cambiato idea

__________________
I don't care if you're black, white, straight, bisexual, gay, lesbian, short, tall, fat, skinny, rich or poor. If you're nice to me, I'll be nice to you. Simple as that.

intendo che io creerei un metodo sommabinaria e sottrazione binaria, in cui andrei a definire due array di caratteri in cui mettere le stringhe di caratteri 1 e 0 da usare; poi con strlenght recupero la lunghezza delle stringhe e con un for parto dall'ultima cifra dell'array (cioè in binario dalla cifra meno significativa) e faccio dei confronti: se la cifra dell'addendo a è 1 e quella dell'addendo b è 1 allora risultato è..., altrimenti se è ...e via così per definire la funzione.

dite pure che sia prestorico ma funziona.....

Avete considerato questo caso?

A è incluso propriamente in B;
A è incluso propriamente in C;
B non è incluso propriamente in C;
C non è incluso propriamente in B;

In pratica B e C includono A ma non esiste una relazione di inclusione tra loro.

si: in pratica facendolo con le liste si avrà A linkato sia a C che B, una ripetizione in pratica.

volendo sviluppare una struttura sottoforma di lista, essa dovrà avere n puntatori quanti sono i filri propriamente contenuti in esso.
Non posso decidere a priori il numero di puntatori "uscenti "di ogni nodo della lista giusto?
Grazie

Grazie mille Fabio.Infatti ho visto anche ioin n manuale di c che esistono gli operatori and e or per sommare o sottrarre i bit.
Grazie milel
Buon progetto.
Speriamo che vada!!!!.

Ciao ciao Tom80

Quanto incide sul voto finale la "bontà" del progetto? Un buon progetto con un orale quasi sufficiente permette di passare l'esame con Torelli? Oppure è meglio un progetto quasi sufficiente ed un orale sufficiente?

ciao a tutti!
svolgendo le linee di input della pagina 3 del progetto mi sn accorto di una cosa strana:
quando kiede il grado del filtro 4 4 9 9 lui stampa 1 ma invece è zero,xkè altrimenti il grado del filtro 2 2 11 10 sareebbe 3,nn 2 nn vi pare?
cmq ora mandero' una mail al prof.

ciau

Ave, avevo pensato di implementare la struttura dati con albero, aggiungendo un figlio
sx se il rettangolo in analisi è incluso nella radice, dx altrimenti. Tuttavia se come
radice ho R1(4,4,6,6), ne risulta che R2(1,2,7,8) diventa giustamente un figlio dx, ma
dell'inclusione di R1 in R2 non so come tenerne traccia. Altro casino di questa soluzione
è determinare la distorsione in un punto, infatti i rettangoli contenenti un punto
possono essere sia sx che a dx della radice principale. Stavo forse pensando di passare
alle liste, o direttamente al prossimo progetto...Quelli che hanno usato alberi rb come
hanno fatto?

Byez

__________________
Think indifferent!

Nella non troppo testata soluzione che sto cercando di realizzare, ho inserito una funzione che scambia adhoc padre e figlio se si presenta la situazione che hai indicato.

ma sono l'unico ad aver usato le liste??

Magari sei tu l'unico che passa l'esame... io sinceramente sono molto indietro, non ho testato un granché e non so una mazza per l'orale.

beh io l'orale non lo devo fare perchè ho passato i compitini..... però filtro l'ho fatto...la struttura l'ho fatta ma sto avendo qualche piiiiiiccoolo problema con la somma e sottrazione binaria...

Originally posted by fabio
beh io l'orale non lo devo fare perchè ho passato i compitini..... però filtro l'ho fatto...la struttura l'ho fatta ma sto avendo qualche piiiiiiccoolo problema con la somma e sottrazione binaria...

__________________
http://www.voglioscendere.ilcannocchiale.it/

Governare gli italiani non è impossibile, è inutile. (G.Giolitti)

no ora invece funzionaaaa!!!!!!!

olèè


il problema di convertire ad intero è grosso... nel senso che nelle specifiche del progetto dice che le stringhe possono essere molto grosse e quindi se devi convertire ad intero 11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
111111111111111111111111111111111 (esempio) sicuramente ti sballa perchè in intero è un numero non rappresentabile

ti conviene trattare carattere per carattere con confronti, palloso ma funziona (giuro, ho provato a sommare e sottrarre stringhe aventi 200 cifre e funziona!)


..chiaramente ho fatto la prova con la calcolatrice di windows per ricavare il risultato...a mano risultava un po' dura...


a proposito: ora che leggo alcuni vostri post, avete controllato la complessità di calcolo in una struttura albero RB che divide a sinistra gli inclusi e a destra i non inclusi? perchè è molto facile che l'albero debba essere ribilanciato ad ogni passaggio e che quindi la complessità si avvicini al caso peggiore quasi sempre...

fabio
ma come fai a farlo con le liste?

immaginati una struttura con 2 puntatori
un puntatore che punta alla destra del nodo (per i rettangoli che sono nello stesso 'livello' di inclusione)
uno che punta al livello sottostante (per i rettangoli inclusi)

più altri 2 puntatori per gestire l'eliminazione quando un filtro è incluso in più di un nodo.

in realtà è finita qui... la cosa si complica solo un attimo di più per l'inserimento (intendo rispetto ad un albero), ma tutto il resto risulta estremamente più semplice (per la mia mente chiaro!)

ho capito...
io infatti sto tentando l'albero, ma sono impantanato nel capire come memorizzare le varie righe dell'imput... infatti, non dovendo porre limiti di lunghezza del segnale, non posso usare array, ma devo usare un lista, in cui ogni nodo contiene un bit del segnale cioè se il segnale è 1101, la lista è 1-->1-->0-->1, ma mi risulta incasinata... tra getchar, conversione in int... mi sto incasinando... poi cerco di stampare la lista e non mi stampa una mazza...

ellamadonna no c'è da impazzire!!! o se riesci tanto meglio per te perchè l'albero poi ti fa quasi da solo grado, grado piano ed elimina però come struttura diventa un macello!!

no io memorizzo 4 interi (le coordinate) ed un array di caratteri per la distorsione

stanotte mi lancio nel meraviglioso mondo di elimina e di punto e poi sono a posto (o quanto meno lo spero....)

ghghghgh

si confermo ke con l'albero è meglio......+ complicato da gestire ma è meglio anke se calcolare il grado di annidamento nn è cosi' immediato(io ad esempio faccio una scansione di una scansione della'lbero)...

Originally posted by fabio
ellamadonna no c'è da impazzire!!! o se riesci tanto meglio per te perchè l'albero poi ti fa quasi da solo grado, grado piano ed elimina però come struttura diventa un macello!!

no io memorizzo 4 interi (le coordinate) ed un array di caratteri per la distorsione

stanotte mi lancio nel meraviglioso mondo di elimina e di punto e poi sono a posto (o quanto meno lo spero....)

ghghghgh

no un momento: io dichiaro l'array molto lungo e basta.
per esempio l'ho dichiarato di 1000 caratteri. chiaro che se lui con l'input va oltre genera errore (che è del resto il tipo di errore che si sfrutta con il buffer overflow, presente ancora nel 70% dei programmi commerciali), direi quindi che ci possiamo accontentare tanto lui di sicuro la prova la fa e all'orale chiede....


io risponderò "scelta implementativa" e tanti saluti

o del resto mica voglio prendere 37, voglio solo passarlo sto maledetto esame....

a me si manifesta il problema solo con la sottrazione, per il resto aver eliminato totalmente gli array non ho problemi di overflow (a meno di avere millllllle segnali...) e l'addizione alla fine funzia
il casino poi è la complessità: mi esce per forza O(n)..... a voi?

la complessità della struttura dati O(n)

<quote>

no un momento: io dichiaro l'array molto lungo e basta.
per esempio l'ho dichiarato di 1000 caratteri. chiaro che se lui con l'input va oltre genera errore (che è del resto il tipo di errore che si sfrutta con il buffer overflow, presente ancora nel 70% dei programmi commerciali), direi quindi che ci possiamo accontentare tanto lui di sicuro la prova la fa e all'orale chiede....

</quote>



Scusa, ma perchè non allochi inizialmente tot byte tramite malloc?
così ti allochi per esempio 40 byte (con i quali rappresenti 10 int)
o addiritura potresti usare anche short int (2 byte) visto che devi rappresentare solo 1 e 0 e poi quando superi il "tetto" di allocazione, fai una realloc. Cmq. occhio, perchè anche se allochi un puntatore a una zona di memoria 10 byte, dall'11 in poi puoi anche scriverli..gcc non si lamenta, ma stai potenzialmente sovrascrivendo zone di memoria magari allocate dal compilatore per fare "altro".. di conseguenza fai danni allucinanti.
ciauz

no ma infatti io non me lo sogno nemmeno di allocare/deallocare memoria per la semplice gestione di un array di caratteri.... sapevo che gcc faceva casino nel controllo.... preferisco sprecare spazio (e sicuramente anche rallentare un pochino) ma non avere problemi di nessun genere....

Forse non mi sono spiegato, ma i problemi seri li puoi avere dal 101 in poi.. tutto qui :-)

si ok ma così invece dichiaro l'array di 900 caratteri e sono DAVVERO a posto......

eheheeheh
quando lo inivii ad aguzzoli, fai un pacco postale e mandagli pure un banco di RAM aggiuntivo per *runnarlo*

ridi ridi
l'importante è passarlo sto esame
come non mi importa
te lo assicuro

Guardando in rete ho visto che esistono strutture dati usate soprattutto in grafica che lavorano proprio su problemi "spaziali" tipo (inclusione di un punto in un poligono o intersezione di più poligoni) ad esempio BSP Tree e R Tree. Il problema è trovare una documentazione completa.

@fabio
se la prima lista contiene tutti i nodi e poi per ogni nodo c'è una lista di nodi inclusi in quello hai praticamente creato un grafo usando la relazione "include". A questo punto per calcolare la distorsione rispetto a un punto e il grado ti converrebbe forse fare una DFS (anche se forse ha un peso eccessivo O(V+E)).

Originally posted by Dante
ho capito...
io infatti sto tentando l'albero, ma sono impantanato nel capire come memorizzare le varie righe dell'imput... infatti, non dovendo porre limiti di lunghezza del segnale, non posso usare array, ma devo usare un lista, in cui ogni nodo contiene un bit del segnale cioè se il segnale è 1101, la lista è 1-->1-->0-->1, ma mi risulta incasinata... tra getchar, conversione in int... mi sto incasinando... poi cerco di stampare la lista e non mi stampa una mazza...

Bloody, per la conversione da char a intero, c'è la funzione standard atoi(char *puntatore)
ciauz

quante ne sa gusher.. una più del diavolo.. incredibbile.. adesso sento quanto vuole x il progetto e faccio sto investimento...
dehehee

__________________
o sei parte della soluzione o sei parte del problema.

recensioni libri informatica

somma troncata a zero

qualcuno ha chiaro come si faccia la somma troncata a zero?

La relazione sulla complessità del programma come si struttura?

io uso un rbAlbero, ma ho un po' di problemi sulla menorizzazione delle chiavi, una volta inseriti tutti i filtri, mi ritrovo ad avere delle incongruenze strutturali del tipo che un nodo che deve stare a destra sta a sinistra o viceversa. Qualcuno mi sa aiutare?

grazie :-)

se le hai memorizzate con la logica degli alberi binari, dovresti aver scelto una delle 4 coordinate come chiave, quindi controlla quella parte di codice (posto che sia lo pseudocodice del cormen adattato) quando fai il confronto. In alternativa applica al tuo programma le procedure create da aguzzoli adattandole alle 4 coordinate...... magari se le hai ricreate su un foglio hai sbagliato una rotazione o qualcosa del genere, sono talmente casinose...

ps ehi non si copiano i nick!!! scherzo!!!!

__________________
I don't care if you're black, white, straight, bisexual, gay, lesbian, short, tall, fat, skinny, rich or poor. If you're nice to me, I'll be nice to you. Simple as that.

Purtroppo usando gli alberi è impossibile usare una sola coordinata come chiave. perchè può accadere di avere un rettangolo che comincia prima ma finisce dopo la radice.
Ad esempio potresti usare come chiave la coordinata (a) ed avere come radice (9,3,8,5). Come filgio sinistro della radice (5,3,23,6) e come figlio destro (11,3,29,5).
Cercando adesso il punto di coordinate (10,y) potrebbe strare sia nel nodo a sinistra che in quello a destra.

Fra l'altro usare un RB-albero significa avere un albero in cui ogni cammino è lungo circa O(lg n) ma se il punto è contenuto in tutti i rettangoli ( ad esempio i rettangoli sono uno dentro l'altro o hanno tutti un punto in comune ) allora è necesario attraversarli tutti.

la consegna è entro la mezzanotte di oggi o di domani??

Entro la mezzanotte di domani, cioè il 24 è INCLUSO.

Io non ce l'ho fatta, preferisco non consegnare il progetto pieno di bugs.

Complimenti a chi c'è riuscito!

Spero che il prossimo progetto sia più umano, io non trovo giusto che l'esame di algoritmi si basi su un ambiente di programmazione che rende tutto più difficile. Con gli strumenti che ci sono oggi a mio avviso non ha senso insegnare a programmare in ANSI C! E' giusto insegnare le BASI del C ma sviluppare un progetto del genere in C per me significa conoscere ben più delle basi!

Inoltre credo che il C non sia un linguaggio elegante e personalmente lo odio (ma questo è un altro dscorso...). Meglio Java, Visual Basic o .NET, che tra l'altro sono maggiormente apprezzati anche nel modo del lavoro!

Marco

W i bugs

Io invece sostengo viva i bugs....e consegno...ce provo....

Tra l'altro vorrei sapere da chi di voi consegna...m ache realzioen avete fatto? io ho qui 2 paginette sparute, voi?

anche io dei bugs....ma glieli segnate nella relazione?

__________________
http://www.voglioscendere.ilcannocchiale.it/

Governare gli italiani non è impossibile, è inutile. (G.Giolitti)

Io sostengo che con le nozioni apprese nel corso di laboratorio e basta questo progetto non fosse fattibile...ma è solo il mio povero punto di vista.

io si l'ho scritto nel commento della funzione nel file col sorgente

Originally posted by Skanky
io si l'ho scritto nel commento della funzione nel file col sorgente

Off-Topic:

skanky rulez
filu

__________________
quod fere libenter homines id quod volunt credunt
de bello gallico III,18

che figo il tuo avatar filu!!!!.

Io penso che non sia del tutto erronea la tua esternazione....

Originally posted by Hades1982
Io sostengo che con le nozioni apprese nel corso di laboratorio e basta questo progetto non fosse fattibile...ma è solo il mio povero punto di vista.

__________________
Spaghetti!!!

ciao a tutti!io ho conseganto il progetto ieri.siccome la discussione del progetto x me avverra' il 9 marzo....il voto lo sapro' solo tra 2 settimane?!

ma te l' ha detto il prof del nove marzo...anche io ho consegnato ieri ma non ho ancora saputo nulla

no l'ho letto dal sito di trubian
http://homes.dsi.unimi.it/~trubian/studenti.htm xo' bho!nn mi va di aspettare 2 settimane!!!

ahh ok ...io sono dell'altro turno...il progetto me lo deve vedere fiorentini....
ok grazie e in bocca al lupo

di niente!crepi anke a te!

Sto svolgendo il prgetto per l'esame di Algo del 6 aprile.
Volevo sapere da chi ha passato questo appello (quello del TD in cui sto scrivendo) che tipo di domande fa all'orale e se nel progetto conta di più il funzionamento o la struttura dati utilizzata?
Grazie

__________________
Federazione
Imbroglioni
Giuoco
Calcio

il funzionamento!!!

__________________
Spaghetti!!!