 | |
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 |
[LAB. ALGORITMI] Progetto FILTRI
Clicca QUI per vedere il messaggio nel forum |
| PuNk-MaD |
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!!! |
| Dante |
sì, l'ho visto... devo ancora pensarci... ma perchè un rb?
ciao |
| Dante |
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! |
| NOODLES |
significa che siamo solo nella parte positiva di piano, penso.
Infatti subito dopo dice che p(x,y)=max(0,o-(T1+...+Tk)). |
| marchinkus |
| gli alberi rb garantiscono una complessita O(lgn) anche nel caso peggiore |
| Drake83 |
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 |
| 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...! :) |
| drakend |
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...! :)
Non sono numeri in complemento a due... se no sarebbero tutti negativi, dato che b1 deve iniziare obbligatoriamente con 1. |
| drakend |
Originally posted by vinnie
E quindi???
E quindi ti devi fare un algoritmo che ti faccia la differenza fra due quantità positive: che ti faccia cioè la differenza come la faresti tu a mano. |
| drakend |
| 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... |
| 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... |
| drakend |
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...
Sì, intendo la sottrazione bit a bit... tenendo conto di eventuali riporti s'intende. Non si possono avere resti negativi, dato che la sottrazione è "tagliata" a zero, come dice il progetto. |
| 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. |
| Drake83 |
Ciao!
scusate ma voi ke strutture dati usate? |
| Gusher |
"... 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. |
| drakend |
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.
Non puoi fare così: il progetto dice esplicitamente di non usare i tipi aritmetici del C dal momento che la lunghezza delle configurazioni binarie è una qualunque. |
| Gusher |
| Estedi il tipo di dato tramite una struttura dati e il gioco è fatto :-) |
| drakend |
Originally posted by Gusher
Estedi il tipo di dato tramite una struttura dati e il gioco è fatto :-)
Cioè allocando i primi 4 byte nella prima struttura, e gli altri nelle successive ad es? |
| ranyus |
| io vi consiglierei una lista di adiacenza...ciao a tutti |
| PuNk-MaD |
| io direi di usare una lista concatenata doppia |
| drakend |
| E che ci mettereste dentro la lista? Un char e il prossimo puntatore? |
| Drake83 |
| 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 :( |
| Hades1982 |
| secondo voi qual'è la struttura dati più corretta per risolvere il progetto?vi prego aiuto |
| Skanky |
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. |
| 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? |
| Drake83 |
| 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? |
| vinnie |
| Ho detto una cazzata! Ho letto male. Tutto uguale. Forse pero' i sorgenti delle liste dinamiche possono (in parte) riciclarsi... :( |
| drakend |
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?
A pagina 3 il pezzo che probabilmente intendi tu dice, testualmente:
[...]dove a,b,c,d sono numeri naturali, e sigma è una stringa binaria[...]
a,b,c,d sono le quattro coordinate dei punti che caratterizzano il rettangolo e sono numeri naturali. Questo però non rigurda minimamente la stringa binaria e quindi non vedo come la limitazione ai soli numeri naturali delle coordinate dei punti dei rettangoli possa semplificare le operazioni binarie, le quali devono essere fatte su stringhe di cui non si conosce a priori la lunghezza.
Per conterle bisogna ovviamente utilizzare una struttura dati dinamica come una lista, però far contenere ogni bit in un char, ad esempio, è un grande spreco dato che si consumano 5 byte (1 per il char + 4 per il puntatore), che poi diventano 8 per problemi di allineamento della memoria. 1 byte di dato per 8 byte memorizzati? non credo che i prof di laboratorio sarebbero troppo contenti di una soluzione simile. |
| 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? |
| drakend |
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?
Non è inevitabile... :) |
| drakend |
| Piuttosto ma due filtri che si sovrappongono solo in parte influenzano in qualche modo il loro grado di annidamento? |
| Hades1982 |
| no,basta sommare i loro disturbi |
| Drake83 |
Originally posted by drakend
Piuttosto ma due filtri che si sovrappongono solo in parte influenzano in qualche modo il loro grado di annidamento?
no,devono essere inclusi propriamente x fare parte del grado di annidamento.cmq mi sembra un po strano il discorso di prima....mi sembra come il "cane ke si morde la coda"...cioè x fare strutture dinamike devo x forza usare puntatori quindi.......... |
| PuNk-MaD |
| 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!) |
| yeffa |
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! |
| SIMBIOS |
| Il maggiore problema resta proprio il criterio di ordinamento per il resto penso anche io che la struttura adatta sia un rb albero! |
| drakend |
| I punti che stanno esattamente sui bordi dei filtri appartengon ai filtri? Penso di sì, però... meglio chiedere! :D |
| PuNk-MaD |
| Drakend ovvio che valgono anche i punti del perimetro altrimenti con due filtri affiancati nei punti di incrocio dovrebbe risultare nessun filtro? |
| drakend |
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?
Sarà ovvio, ma meglio chiedere prima di fare cazzate. Se tu non ne hai sentito il bisogno complimenti per la tua bravura :D |
| pincopallino |
bah.......allora sono brava anch'io! =P
Sembrava ovvio anche a me! |
| drakend |
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. :lol:
|
| Skanky |
| Che casino mi sta fondendo il cervello a pensare alle procedure per gestire l'inserimento dei filtri nel modo appropriato |
| Skanky |
| gran casino ste procedure per gestire gli annidamenti |
| fulminato1 |
| una spiegazione rapida di questo thread? |
| Drake83 |
| Concordo pienamente! |
| fulminato1 |
| scusate, prima i thread erano separati adesso gli hanno uniti penso, scusate ankora! |
| tom80 |
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 |
| Bloody |
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 |
| tom80 |
| 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? |
| tom80 |
| 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? |
| 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'.......:sad:
ciauz |
| drakend |
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'.......:sad:
ciauz
Che chiave univoca usi per ordinare l'albero di ricerca? |
| Skanky |
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 |
| 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 |
| Drake83 |
Originally posted by drakend
Che chiave univoca usi per ordinare l'albero di ricerca?
scusa intendi in ke modo ordino i filtri?se intendi cio' io confronto a_corrente con a nuovo,se minore a sinistra se maggiore a destra se uguale quardo b e cosi' via...... |
| Drake83 |
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
si infatti quel problema si presenta.....infatti sto pensando ad un modo x gestire tale situazione....ci saranno un bel po' di controlli ma forse si puo' fare!Sperem!:sad:
ciau |
| Drake83 |
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? |
| SIMBIOS |
| scusate ma quando elimino un filtro R(a.b.c.d) e questo ne ha un altro annidato dentro tolgo pure lui? |
| SIMBIOS |
| bella grazie gusher:-D |
| PuNk-MaD |
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 |
| Hades1982 |
| 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) |
| 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? |
| sonica |
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?
perchè un albero ha garanzie di essere bilanciato se è un rbalbero o un b-albero.
inoltre non capisco come puoi inserire i primi 3 nodi, (a, b, c) nel disegno di esempio del progetto.
l'ordinamente in base al criterio "incluso propriamente" non genera un albero binario quindi non esistono più i concetti di ramo destro e ramo sinistro
ciao
sonica |
| Eruyomë |
| 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 |
| Dante |
| 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!!! |
| Dante |
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! |
| marco.pozzi |
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 |
| yeffa |
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 |
| Bloody |
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?
tieni presente che non ci sono limiti a valore della x e della y (meno che logicamente devono essere positivi)
io penso di usare alberi di intervalli.
Domandina mia: nella gestione dei bit dei segnali come l'avete gestito il bit di segno per il complemento che si fa quando bisogna implementare la sottrazione??
thanks |
| Polo |
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. |
| Drake83 |
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 |
| Gusher |
| 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) |
| 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 |
| Gusher |
| No devi gestirli tu con una struttura dati appropriata. |
| fabio |
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
beh lo shif di bit e lo xor esistono... il problema però è che dove li vai a memorizzare i bit su cui poi operi? :) aguzzoli dice chiaramente nel progetto che non vuole i tipi matematici del C... suggerisco un bell'array di caratteri..... |
| Bloody |
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 |
| fabio |
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..... :) |
| marco.pozzi |
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. |
| fabio |
| si: in pratica facendolo con le liste si avrà A linkato sia a C che B, una ripetizione in pratica. |
| giz17 |
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 |
| tom80 |
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 |
| marco.pozzi |
| 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? |
| Drake83 |
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 |
| iesse |
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 |
| marco.pozzi |
| 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. |
| fabio |
| ma sono l'unico ad aver usato le liste?? |
| marco.pozzi |
| 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. |
| 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...
:( |
| SIMBIOS |
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...
:(
fabio anche io sto' incontrando lo stesso problema!!io ho trasformato prima da bit a int..le operazioni le faccio in int e poi converto in binario! |
| fabio |
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... |
| Dante |
fabio
ma come fai a farlo con le liste? |
| fabio |
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!) |
| 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... |
| 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 |
| Drake83 |
| 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)... |
| Dante |
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
ma come fai a memorizzare un array di caratteri per la distorsione se non sai a priori quanto può essere lunga al massimo? |
| fabio |
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.... |
| Bloody |
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? |
|
|
|
|
