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

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